Amazon Software Development Engineer II interview questions

Find the least common ancestor of given two nodes in a tree

Questions (A1) Design a single machine, single user system for hotel table reservations. Constraints: assume 16 tables with capacity 4, 16 tables with capacity 8. Can book for just 1 hr. Max 2 months in advance. Which classes, which data-stuctures? (A2) What happens when a party of 16 requests for a table. You can join tables which are next to each other. Implement this. ------ (B1) Design a deck of cards. (B2) Now assume 10 million users are using this card deck. ------- (C1) Given a binary tree, print all the leaf nodes. (C2) Now, print all the left most nodes, and all right most nodes ( assume there is a triangle around the binary tree, so all nodes which falls on that triangle , print them in clockwise ordering). ------ (D1) Given an array which contains series of 0s and series of 1s, find the index where 1s start. How would you test this method? (D2) Assume input array has infinite length, how will you find the index in O(logn) time? ---------- Answers: A1. Array of size 32. Each element in the array contains linkedList sorted by startTime where each link represents timeslot that is already booked/reserved. A2. Get a list of tables which are available in the requested time period, check if there is a contiguous set of tables which total up to 16 and then reserve those tables. B1. Deck class. Card class. Suit enum. Value Enum. Card contains Value and Suit enums. Deck contains an array of 52 cards. Constructor of Deck initializes 52 card class. Card should expose comparable interface. Deck should expose Shuffle and iterator interface. Some considerations: Should Deck be singleton? Should Deck be made generic to accept different types of cards? Should Desk be made threadsafe? B2. If there are 10 million users on the same machine using 10 million Decks, then we don't really need 520 million cards. Each Card instance is immutable. So we just need 52 card instances which are shared between 10 million Decks. C1: Leaf nodes: Preorder traversal limited to leaves. C2: Left side: Preorder traversal limited to nodes which matches certain criteria. Right side: Only visit those nodes that meet certain criteria - Post Order traversal. D1: binary search O(logN) Testcases: null array, empty array, array with just one element - 0, array with just one element - 1. array with only 0s. array with only 1s. 5 element array with 2 0s and 3 1s, array with numbers other then 0 and 1. D2: 2 step process: (i) Find the block in which transition from 0 to 1 happens. (ii)Then find the exact index within that block. For #i, consider first block with size K, if no transition in this block, then check next block with size 2K, then 4K, then 8K. Once we find the block with transition then step#ii is simple binary search.