Uber | SDE 2 | Blr | Rejected

Current Experience: 2.2 years
Current company: Microsoft
current TC: 20L base + 10L stocks/year

How I applied: Applied via referral

Phone screen:
Interviewer joined the call and pasted the problem statement without any introduction:

Develop a feature to determine if an ad has had X impressions without a click over a Y day rolling window.

An add event can contain will look like as follow:

{  
id: int,  
timestamp: int,  
eventType: click | impression  
}

Sample test case:
x = 3, y = 3

timestamp: 100, id: 1, type: impression
timestamp: 101, id: 1, type: impression
timestamp: 102, id: 1, type: click
timestamp: 104, id: 1, type: impression
timestamp: 106, id: 1, type: impression
timestamp: 107, id: 1, type: impression
timestamp: 109, id: 1, type: click

The impression events need to be counted between two click events.
So, in the above sample for ad event id - 1
at timestamp 102, impression count in last y mins = 2
at timestamp 106, impression count in last y mins = 2
at timestamp 107, impression count in last y mins = 2
at timestamp 109, impression count in last y mins = 1
maxImpressionCount = 2, which is less than 3 so answer is false for this case.

My solution:

// {id, timestamp, type}  
// vector<int>& ad1 = {1, 1001, 1} // 1->for click, 0->for impression  
  
bool cmp(std::vector<int>& ad1, vector<int>& ad2) {  
    return ad1[1] < ad2[1];  
}  
  
bool getAdWithXImpressions(vector<vector<int>> ads, int x, int y) {  
  sort(ads.begin(), ads.end(), cmp);  
  queue<vector<int>> q;  
  map<int, int> impressions; // adEvent id -> number of impressions  
  for (vector<int>& adEvent: ads) {  
    if (adEvent[2]) {  
      int mxImpressionCnt = 0;  
      for (auto it = impressions.begin(); it!=impressions.end();it++) {  
        mxImpressionCnt = max(mxImpressionCnt, it->second);  
      }  
        
      if (mxImpressionCnt >= x) {  
        return true;  
      }  
        
      impressions[adEvent[0]] = 0;  
    } else {  
      if (q.empty()) {  
        q.push(adEvent);  
        impressions[adEvent[0]]++;  
      } else {  
        vector<int> firstEvent = q.front();  
          while (adEvent[1] - firstEvent[1] > y) {  
            q.pop();  
            impressions[firstEvent[0]]--;  
            if (impressions[firstEvent[0]] == 0) {  
              impressions.erase(firstEvent[0]);  
            }  
            if (q.empty()) {  
              break;  
            }  
            firstEvent = q.front();  
          }  
          int mxImpressionCnt = 0;  
          for (auto it = impressions.begin(); it!=impressions.end();it++) {  
            mxImpressionCnt = max(mxImpressionCnt, it->second);  
          }  
          if (mxImpressionCnt >= x) {  
            return true;  
          }  
          q.push(adEvent);  
          impressions[adEvent[0]]++;  
      }  
    }  
  }  
    
  int mxImpressionCnt = 0;  
  for (auto it = impressions.begin(); it!=impressions.end();it++) {  
    mxImpressionCnt = max(mxImpressionCnt, it->second);  
  }  
  if (mxImpressionCnt >= x) {  
    return true;  
  }   
  return false;  
}

The problem statement was kept vague and I got clarity on what is to be done after asking clarifying questions. I had used a priority queue solution, and it worked perfectly on test cases that the interviewer tried on.

Got positive feedback in this round, so next set of rounds (DSA and LLD) were scheduled.

Round 1: DSA
https://leetcode.com/problems/squares-of-a-sorted-array/
I coded the optimal solution.

Follow-up 1: Then there was another variant of this problem as a follow-up, I was able to explain my approach but did a small mistake in implementation which I only identified while dry running the code.

Follow-up 2: How do I get the kth smallest element given the same input as the original problem.
I gave an O(k) solution but the interviewer was looking for O(logk) solution. Could not think of the O(logk) solution as very little time was left.

Round 2: LLD
Design BookMyShow. It was a toned down version of this famous problem with user scenarios and expections very clearly from the interviewer.

I was able to code the solution in Java, faced some issue during compilation but was able to solve it and demoed the code on happy path and other paths too.

As the requirements were pretty clear, I had to ask less clarifying questions and could jump to coding directly, but this thing bite me back.

Verdict: Rejected
Feedback:

In DSA round, the feedback points to an edge case I missed (which I only identified while dry running the code before handing over to interviewer).
In LLD round, the interviwer feedback was on my code quality and clarifying questions.

In hindsight, my LLD was not up to the mark. Gotta keep practicing :)