Stage III: Hard Questions
Trees (BT, BST)
Binary Tree Maximum Path Sum
Task: Find the maximum sum of any path between any two nodes in a binary tree. The path does not need to pass through the root.
Companies: Google, Amazon, Facebook
Serialize and Deserialize Binary Tree
Task: Design an algorithm to convert a binary tree to a string (serialize) and back to the tree (deserialize).
Companies: Google, Amazon, Facebook, Microsoft
Construct Binary Tree from Preorder and Inorder Traversal
Task: Given the preorder and inorder traversals of a tree, construct the original binary tree.
Companies: Amazon, Microsoft, Bloomberg
Binary Tree Right Side View
Task: Imagine yourself standing on the right side of a binary tree. Return the values of the nodes you can see ordered from top to bottom.
Companies: Facebook, Amazon
Kth Smallest Element in a BST
Task: Given the root of a BST and an integer k, return the kth smallest element in the tree.
Companies: Amazon, Facebook, Google
Graphs
Word Ladder
Task: Find the length of the shortest transformation sequence from a beginWord to an endWord, changing one letter at a time, where each transformed word must be in a given dictionary.
Companies: Amazon, Facebook, Google, LinkedIn
Number of Connected Components
Task: Given n nodes and a list of edges, count the number of connected components.
Companies: Amazon, Facebook, Google
Pacific Atlantic Water Flow
Task: Find all grid cells from which water can flow to both the Pacific (top/left) and Atlantic (bottom/right) oceans.
Companies: Google, Amazon
Course Schedule II
Task: You are given courses and prerequisites. Return a valid order in which you can take the courses. If it's impossible, return an empty array.
Companies: Facebook, Amazon, Google
Alien Dictionary
Task: You are given a list of words from an alien language, sorted lexicographically. Infer the correct order of letters in this language.
Companies: Google, Facebook, Amazon, Airbnb