Google | L3 | Bangalore | Screening Round

Exp - 1.5+ YOE
Tier 2 college.
Recuriter reached out to me on 30 May. Scheduled interview after 3 weeks. There were 5 rounds in total including screening.

Screening round was virtual.
45min
Ques - Given a collection of 2D boxes with different sizes, find the maximum number of boxes you can nest inside each other.
Note that this is the level of nesting, not total boxes nested. For example
This has a max nesting level of 2, even though there are 3 boxes.

[100,100], [20,80], [39,39]
max nesting - 2

[100,100], [39,39], [20,80], [29, 29], [19, 79], [10, 10] - 4

gave sorting and longest decreasing subsequence based solution but was not able to solve edge cases.

Verdict - Rejected

Feedbacks and code correction suggestions much appreciated.

bool comp(vector<int> a, vector<int> b){  
  return a[0]>b[0];  
}  
  
int maxNestingLevel(vector<vector<int> > &allBoxes) {  
  sort(allBoxes.begin(),allBoxes.end(), comp)  
    // longest desc subseq  
    int n = allBoxes.size();  
    
  vector<int> widthds ;  
  for(auto it: allBoxes){  
    widhts.push_back(it[1]);  
  }  
    
  int dp[n];  
  dp[0] = 1;  
    
  for(int i=1;i<n;i++){  
    for(j=0;j<i;j++){  
      if(widhts[i] < widhts[j])  
        dp[i] = max(dp[i], dp[j]+1);  
    }  
  }  
    
  int ans = -1;  
    
    
  for(auto it: dp){  
    ans = max(ans,it);  
  }  
    
  return ans;  
}