[Offer] Meta | Business Engineer L4 | London | Feb 2025

# Round 1 - Screening
* Sum Root to Leaf Numbers
* Coded perfectly, discussed TC and SC
* Palindromic Substrings
- Tried pretending that “solving the problem” approach with a little but of acting and took up a lot of time to discuss on how to build palindrome matrix
- Proposed building a palindrome 2D boolean matrix, started with len = 1, 2, and so on…
- Once `palin[beg][end]` computation is complete, if the value is `True` I add it to the `vector<string> result`.
- Asked for more optimisation - I proposed we don’t need to maintain the nxm array, we can only keep last 3 length boolean array.
- The most optimal solution was start from each index and start branching out to on both sides - I couldn’t provide that.

Learnings: The time is really less for Meta interviews, don’t try to pretend you are solving the problem. After clarifications, immediately jump into the solution.

# Round 2 - DSA Round 1

After Basic introduction, jumped to the first problem.

• Buildings With an Ocean View
  - Asked if I’m allowed to traverse from the end, interviewer was ok. Implemented the solution, did dry run and discussed TC & SC.
  - Follow Up 1:
  - What is buildings had ocean on both sides. Share the list of buildings which had ocean view in at least one of the sites.
  - Proposed to 2 pass(forward and backward) algorithm and store them in sets(hashmap) to remove the duplicates. At the end return them as a vector.
  - He asked me if I’m aware of any of the hash algorithms, I said no - no worries.
  - Follow Up 2:
  - If you can remove at least one building, how to decide which building to remove so that no of total buildings with ocean view is increased.
  - Proposed, for ith building I’ll maintain monotonically decreasing building length till (i-1)th index. That won’t work, if the (i+1)th building had the same height.
  - Then I proposed from right I’ll store them in multiset and then try to remove current building and see if there any other larger building exists on the right side.
  - I only had discussed the solutions for both the Follow Ups, no need to write any codes.
• Given M sorted arrays with N total elements. Find the Kth element in the sorted array.
  - I initially proposed to merge all the sorted arrays using divide and conquer method. Wrote the code for that as well.
  - I screwed up during the complexity analysis, usually it should be `O(NlogM)`. But somehow I came up with `O(N^2logM)`, which isn’t correct.
  - He asked me if we had to solve this brute force way, how would you do it? I mentioned maintaining M pointers for all the individual arrays and take smallest element out of these m indexes. Wrote the code for that. This was a solution for `O(MK)` complexity.
  - Then he hinted me, the outer loop for K is definitely problem constant, we can’t do much about it - how can we optimise the inner O(M) loop. I instantly gave the response of using a heap/priority queue data structure and always pick up the small the element from the top.
  - He was satisfied and said no need to write the code, since it’s anyway just two method calls(push and pop/top). He further asked regarding the complexities about why pq/set and why it’s logarithmic - explained the underlying heap structure and heapify process. Reducing the overall complexity to `O(K*logM)`

# Round 2 - DSA Round 2
- No introduction, straight to the problem
- Sliding window Average
- Find average of each Sliding window. Given an input array of n elements and a sliding window for size k, find the average of each sliding window.

input = [1,2,3,4,5]
k = 3
output = [2.0, 3.0, 4.0]
(1+2+3)/ 3 = 2.0
(2+3+4)/3 = 3.0
(3+4+5)/3 = 4.0
Expectation was to solve it in O(n) time and O(1) space.

- Interviewer tried to throw me by saying “Can we do better than linear time?” I logically countered, why it’s not possible to have better than linear time.
- I coded it up, discussed around SC/TC. During dry run, I discussed various test cases and handle that in the code as well(e.g. k ≤ 0).
- He was very much focused around how do I handle with the validation and various use cases(which I believe should’ve asked during clarification phase).
- Find Peak Element (Needed to find the local minimum element, smaller or equal is considered for local minima).
- He asked me to do better than linear time, proposed the binary search solution using O(logN) solution.
- Later he mentioned consider only smaller element to evaluate the local minima element, what changes will be required in that case (proposed to change ≤ symbol <).
- Later he encountered the use case where we had duplicates, which I had to handle by shrinking the window (lo++, hi--).
- e.g. 1 2 2 2 2 2 2

# Round 3 - Hiring Manager
Bunch of Tell me about a time kind of questions and deep discussions around my answers.

# Round 4 - System Design
Design a crowd sourced 3D Street View and video source is Smartphone attached to a Car. Depending on the season or time of the day the customer will see different rendered 3D view of the street.

Learning: Whatever you're saying, just to try to document that - since that whiteboard/coderpad will be the source of truth for the interviewer.

# Round 5 - XFN Collaboration
Bunch of Tell me about a time kind of questions and deep discussions around my answers.