Amazon SDE Intern Interview Questions and Answers

Find square root of a number using basic arithmetic operations without power operator and inbuilt libraries.

• Use binary search to find the integer part of the square root

• Use long division method to find the decimal part of the square root

• Repeat the above steps until desired accuracy is achieved

• Handle edge cases like negative numbers and numbers less than 1

Remove duplicates from a sorted linked list

• Use two pointers - one to iterate through the list and another to keep track of unique elements

• Compare current node with next node, if they are equal, skip the next node

• Repeat until end of list is reached

Addition of two linked lists and return the result as a linked list.

• Traverse both linked lists simultaneously

• Add corresponding nodes and carry over the sum

• Create a new linked list with the sum

Find leaf nodes in a binary tree and print path to each leaf node.

• Traverse the binary tree using depth-first search (DFS)

• When reaching a leaf node, store the path from root to that leaf node

• Repeat the process for all leaf nodes in the tree

Find the deepest left node in a binary tree.

• Traverse the tree recursively and keep track of the depth and whether the current node is a left node.

• If the current node is a leaf node and its depth is greater than the deepest left node found so far, update the deepest left node.

• Return the deepest left node found.

• Example: For the binary tree with root node 1, left child 2, and left child of 2 being 4, the deepest left node is 4.

• Example: For the binary tree with root node 1, left ...read more

Count occurrences of a given element in a sorted array.

• Use binary search to find the first and last occurrence of the element.

• Subtract the indices to get the count.

• Handle edge cases like element not present in the array.

Min-stack is implemented using O(N) space by keeping track of minimum value at each element.

• Use two stacks - one to store the actual elements and another to store the minimum value at each step.

• When pushing an element, check if it is smaller than the current minimum and update the minimum stack accordingly.

• When popping an element, also pop from the minimum stack if the popped element is the current minimum.

Implement a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• Use two stacks - one to store the actual elements and another to store the minimum values.

• When pushing an element, check if it is smaller than the current minimum and push it to the min stack if so.

• When popping an element, check if it is the current minimum and pop from the min stack if so.

• Top operation can be implemented by returning the top element of the main stack.

• GetMin op...read more