10+ Amazon SDE (Software Development Engineer) Interview Questions and Answers

Program to calculate sum of level order tree

• Traverse the tree level by level using BFS

• Add the values of each level and return the sum

• Use a queue to store the nodes at each level

• Handle edge cases like empty tree or null root

Sorting a list of words with a random order using an alien dictionary

• Create a graph with nodes as characters and edges as the order of characters in words

• Topologically sort the graph to get the correct order of characters

• Use the order to sort the list of words

Find the maximum continuous sum in an array of integers.

• Use Kadane's algorithm to find the maximum subarray sum in linear time complexity.

• Initialize two variables, one for current maximum sum and another for overall maximum sum.

• Iterate through the array and update the variables accordingly.

• Example: For array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the maximum continuous sum is 6 (from index 3 to 6).

Yes, high and low level design principles are important in software development.

• High level design principles focus on overall architecture and system organization.

• Low level design principles focus on implementation details and code structure.

• Examples of high level design principles include SOLID, DRY, and KISS.

• Examples of low level design principles include naming conventions, code commenting, and code formatting.

• Both high and low level design principles are important for cre...read more

Program to find all sibling nodes of a BST

• Traverse the BST and keep track of parent node

• If a node has the same parent as another node, they are siblings

• Recursively check left and right subtrees

• Use a queue or stack to implement level order traversal

Find the length of longest increasing subsequence in an array.

• Use dynamic programming to solve the problem efficiently.

• Maintain an array to store the length of longest increasing subsequence ending at each index.

• Traverse the array and update the array for each index.

• Return the maximum value in the array as the length of longest increasing subsequence.

Find maximum of every window of size K in an array

• Iterate through the array and maintain a deque of indices of elements in the current window

• Remove indices from the front of the deque if they are outside the current window

• Remove indices from the back of the deque if their corresponding elements are smaller than the current element

• The front of the deque will always contain the index of the maximum element in the current window

Implement binary search in a semi-infinite array.

• Start with the first element and keep doubling the index until the target element is less than the current element.

• Perform binary search on the subarray from the last doubled index to the current index.

• If the target element is not found, repeat the process by doubling the last index and searching again.

• Handle edge cases where the target element is at the first index or not present in the array.

Convert an expression to post-fix notation.

• Start with an empty stack.

• Scan the expression from left to right.

• If the scanned character is an operand, output it.

• If the scanned character is an operator, pop two operands from stack, output them in post-fix notation and push the result back.

• Repeat until the end of expression.