Background

Education: B.Tech in CSE from Tier2/3
Previous Experience: Around 3.5 YOE at Top MnC (MAANG)

HR reached out to me via linkedin for Bangalore location

Phone Screening Round: (Indian Interviewer)

Don't rememmber the exact question but Similar to this was asked.

We have given an array of size n and integer k. We have to find the maximum value in every consecutive k elements.
Follow up: Can you do it in O(n*log(k)) TC and O(1) SC.

Onsite-1: (USA Interviewer)

You are given a sequence of versions numbered from a to b. There is a check that succeeds at version a and fails at version b. At some unknown point between these two versions, the check transitions from passing to failing and then continues to fail for all subsequent versions.

Your task is to identify the first version where the check starts to fail.

Follow-up: How we can optimise this when we are allowed to use multiple threads.

Onsite-2: (South American Interviewer)

Interviewer left question vague, I had to ask multiple questions for understanding the question.
You're given a list of direct partnerships between individuals. If two individuals are directly partnered, they are considered "Connected". If two individuals are not directly connected but are part of the same extended network through a chain of connections, they are "Related".

You need to implement two functions:

1. areConnected(x, y) – returns true if x and y are directly connected.
2. areRelated(x, y) – returns true if x and y are connected through a mutual network, but not directly.

Follow-up: Can we do this in constant time? Preproccessing was allowed
I had to code complete DSU and map solution in given time.

Onsite-3: (USA Interviewer)

Interview started with basic introdution and jump to questions related to cpp as my preffered coding language was cpp. After 5-6 mins, we jumped to the question.

You're given a collection of entries grouped by category. Each entry belongs to a specific category (e.g. source), and each category has multiple entries associated with it.

You are also given a limit max_entries, which is the total number of entries you're allowed to retain across all categories combined.

You need to determine the maximum value of X such that the following rule holds:

1. For any category with X or fewer entries, retain all of them.
2. For any category with more than X entries, retain only the latest X entries.

Your goal is to maximize X such that the total number of retained entries across all categories does not exceed max_entries.

Googyness round was expected to schedule after technical rounds but I didn't hear back from HR yet. Though interiew went fine.