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

Design a data structure for efficient insert(),delete(),search(), return_any_value().

• Consider using a hash table or a balanced binary search tree

• For return_any_value(), use a random number generator to select a value

• Optimize for the most frequently used operations

Find the number of elements shifted in a sorted array after shifting n elements from right to first.

• Find the index of the minimum element in the shifted array

• The number of elements shifted is equal to the index of the minimum element

• Use binary search to find the minimum element in O(log n) time

Efficient way to search a given element in an array of integers with adjacent elements 1+ or 1- from each other.

• Use binary search algorithm to search the element in O(log n) time complexity.

• Check the middle element and compare it with the given element.

• If the middle element is greater than the given element, search in the left half of the array.

• If the middle element is smaller than the given element, search in the righ...read more

Reverse a singly linked list

• Iterate through the list and change the direction of the pointers

• Keep track of the previous, current, and next nodes

• Set the head of the list to the last node after reversing

Find the nth largest element from last in a singly linked list

• Traverse the list to find its length

• Traverse again to the (length-n)th node

• Return its value

Given a matrix and value k, find k*k submatrix with maximum sum.

• Iterate over all submatrices of size k*k and calculate their sum.

• Keep track of the maximum sum and the corresponding submatrix.

• Use dynamic programming to optimize the solution.

• Time complexity can be reduced to O(m*n*k^2) using prefix sum technique.