Round 1: Online Coding Round

Question 1: Array Reduction
There is an array of n integers called nums. The array can be reduced by one element by performing a move.
Each move has 3 steps:

1. Pick two different elements nums[i] and nums[j] (i and j are not equal)
2. Remove both elements
3. Add the sum of two selected elements to the end of the array
   Each move has a cost associated with it – the sum of 2 elements removed from the array during the move. Hence, calculate the minimum total cost of reducing the array to one element.

Question 2 : Valid BST Permutations
Given an integer n, determine number of valid BSTs that can be created by nodes numbered from 1 to that integer.

Question 3: Strongly Connected Groups
A group of people are considered to be strongly connected if each person knows every other person within the group. If the network has n people and there are m pairs of relationships connecting them, then find the minimum size of the largest strongly connected group. Think of people as graph nodes and their relations as edges.

Round 2: Coding Round

Question 1 : API Rate Limiter
Question 2: Extend the rate limiter to account different limits for different users
Question 3: Extend the rate limiter to apply something like carrying forward the balance.

Round 3: System Design Round

I was asked to implement a Unique Id Generator for a set of services. This was an open problem and I had discussions with the interviewer on APIs, API design, API responses, databases, SQL vs NoSQL, querying the database, generating the unique id using some encoding, server design.

Round 4: Manager Round

Had a detailed discussion on my resume and projects along with 8-10 managerial and values questions.