Amazon Development Centre India Software Development Engineer Interview Questions and Answers

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.

Find shortest path between 'S' and 'E' in a matrix filled with '0's and 'x's

• Use Breadth First Search (BFS) algorithm to find shortest path

• Create a visited matrix to keep track of visited cells

• Create a queue to store cells to be visited

• Start BFS from 'S' and keep track of distance to each cell

• When 'E' is found, return the distance to it