Amazon Software Development Engineer Interview Questions, Process, and Tips

Find all permutations of a given string, handling duplicates.

• Use recursion to generate all possible permutations

• Use a hash set to keep track of already generated permutations

• Handle duplicates by skipping already generated permutations

• Time complexity is O(n!)

• Return an array of strings containing all permutations

Prove that in-order traversal of a BST is always sorted and vice versa

• In-order traversal of a BST visits nodes in ascending order

• If a binary tree's in-order traversal is sorted, it is a BST

• A BST's left subtree contains only nodes with values less than its root

• A BST's right subtree contains only nodes with values greater than its root

Sort an array of 0s, 1s, and 2s without using counting sort.

• Use three pointers to keep track of the positions of 0s, 1s, and 2s.

• Traverse the array and swap elements to their respective positions.

• Time complexity: O(n), Space complexity: O(1).

Find an element k in a sorted array such that Max(k) < n.

• Use binary search to find the largest element smaller than n

• Start with mid element and adjust search range based on comparison with n

• Return -1 if no such element exists

Find the first occurrence of 1 in a sorted array of 0s and 1s.

• Use binary search to find the first occurrence of 1.

• If mid element is 1, check left subarray for first occurrence.

• If mid element is 0, check right subarray for first occurrence.

Find minimum vertices to place policemen in an acyclic graph of a city to cover all roads.

• Use Depth First Search (DFS) to traverse the graph

• Maintain a set of visited vertices to avoid revisiting

• For each unvisited vertex, place a policeman and mark all connected edges as covered

• Repeat until all edges are covered

• Return the minimum number of policemen placed

Pre-process a dictionary to output anagrams of a given string. Data structure, time and space complexity?

• Create a hash table with sorted string as key and list of anagrams as value

• Iterate through dictionary and sort each string, add to hash table

• To find anagrams of given string, sort it and look up in hash table

• Time complexity: O(n * klogk), space complexity: O(n)

• n = number of strings in dictionary, k = length of longe

Check if a binary tree is a BST or not and give time and space complexity.

• Traverse the tree in-order and check if the elements are in ascending order

• Keep track of the maximum value seen so far while traversing

• If any element violates the ascending order, return false

• Time complexity: O(n), Space complexity: O(h) where h is the height of the tree

Design a lift system using OOPs concepts.

• Create a Lift class with methods like moveUp(), moveDown(), openDoor(), closeDoor()

• Create a Floor class with methods like requestLift()

• Use inheritance to create different types of lifts like passenger lift, cargo lift, etc.

• Use encapsulation to hide the internal workings of the lift system from the outside world.

• Use polymorphism to allow different types of lifts to respond differ

Find minimum length substring of string a containing all characters of string b.

• Use sliding window approach

• Maintain a frequency map of characters in b

• Move the window until all characters of b are present

• Update the minimum length substring as you move the window