Meta Onsite first round experience - Pass / Fail

Round 1

Questions:

1. Copy Linked List with Random Pointer
   Specific question not provided.
   Clarifying questions asked:

   • Can we have duplicates?
   • How will input be given to me?
   • Can we have negative numbers?

   Candidate's Approach:

   • Iterated through the linked list to create a copy of each node.
   • Stored copy nodes in a hashmap where the key is the node's value and the value is the node's copy.
   • In a second pass, iterated over the original linked list to construct the next and random pointers.
   • Adjusted the approach to handle duplicate values by using the original node as the key in the hashmap.

   Test Case Verification:

   • Verified the code with the input provided by the interviewer.
   • Noted an issue where a dummy node was created unnecessarily instead of returning the copy linked list head directly.

2. Vertical Order Traversal
   Specific question not provided.
   Clarifying questions asked:

   • What happens if there are multiple nodes on the same column?
   • What if there are multiple nodes on the same column and row?
   • Will the tree be perfectly balanced?
   • Can we have duplicates?
   • How will input be given to me (object or array of nodes)?
   • What if the root itself is null?

   Candidate's Approach:

   • Explained the choice of BFS for solving the problem.
   • Described how to leverage the column index and group values by column index using a hashmap.
   • Discussed tracking the minimum column index to ensure proper order when adding node values.