Hello, folks. Hope you are doing good :)

I recently gave Google interviews and failed them :(
Nonetheless, it was a good learning experience but I am unsure about the solutions to few problems. Especially round 4. I felt I did great but feedback says otherwise. Please, share your solutions it would be helpful to gauge the performance :)

• Screening Round
  Find the longest path passing through the root in a binary tree such that all nodes form an arithmetic progression with the given difference. So for the following tree with given difference -2, we have longest length as 7 (6 -> 4 -> 2 -> 0 -> -2 -> -4 -> -6)
  

• Onsite 1
  Given an undirected graph with weighted(non-negative) edges. There is a source node and a destination node. Find the total number of paths from source to destination with the constraint: you can go from node A to node B iff shortest_path(A, destination) > shortest_path(B, destination). For the following graph where source node is C and destination node is H, answer should be 3 (valid paths: CDEH, CDH, CBH)

• Onsite 2
  Build a data structure to perform three operations (Restaurant is full initially):
  1) waitList (string customer_name, int table_size):
  Add customer with given name and table size they want to book into the waitlist
  2) leave (string customer_name):
  Customer wants to leave the waitlist so remove them.
  3) serve (int table_size):
  This means restaurant now has a free table of size equal to table_size. Find the best customer to serve from waitlist
  Best Customer: Customer whose required size is less than or equal to the table_size. If multiple customers are matching use first come first serve.
  For e.g. if waitlist has customers with these table requirements => [2, 3, 4, 5, 5, 7] and restaurant is serving table_size = 6 then best customer is index 3 (0-based indexing).

• Onsite 3
  Standard behavioral round with some hypothetical scenarios

• Onsite 4
  Given an array generate its double-shuffle i.e. double every array element and append it's double to the same array. Now shuffle this array randomly.
  For e.g. if the array is [1, 3, 2] then it's double is [1, 3, 2, 2, 6, 4]. Finally, shuffle this array randomly which can be [3, 4, 2, 1, 2, 6]
  Now given a double-shuffle array find it's original array. Using above example, if double-shuffle is [3, 4, 2, 1, 2, 6] then return [1, 2, 3] (in no particular order)

• Onsite 5
  Given a binary tree, find the path directions to go from node A to node B. For e.g. for the following binary tree path between 5 to 7 is ["up", "up", "right", "right", "left"] (Note: we can only use "up", "right", "left" directions)

As I said, I was sure about the response of the all the rounds except 4th onsite. I felt I did well but feedback was negative. But, that's OK. I will prepare well and re-apply in a year.
Also, please, share your approaches to the problems :)