Panda Guru LogoPanda
Guru

Oracle Interview Experince

Round 1

Questions:

  1. Simplify Path
  2. Sort a 2D matrix that is already row-wise and column-wise sorted into a 1D array.

Test Case:

#include<bits/stdc++.h> #define pp pair<int,pair<int,int>> using namespace std; int main(){ int m,n; cin>>m>>n; vector<vector<int>> grid(m,vector<int>(n,-1)); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ cin>>grid[i][j]; } } priority_queue<pp,vector<pp>,greater<pp>> pq; // {ele,ind} for(int i=0;i<m;i++){ pq.push({grid[i][0],{i,0}}); } /* TC- (m*n)LOG(m) SC- O(rows) at max PQ Size */ vector<int> ans; while(!pq.empty()){ int ele=pq.top().first; int row=pq.top().second.first; int col=pq.top().second.second; pq.pop(); ans.push_back(ele); if(col<n-1) pq.push({grid[row][col+1],{row,col+1}}); } for(auto x:ans){ cout<<x<<" "; } }
Candidate's Approach

The candidate used a min-heap approach to sort the 2D matrix into a 1D array. They initialized a priority queue to keep track of the smallest elements and iterated through the matrix, pushing the first element of each row into the heap. The candidate noted that the time complexity of their approach is O(mn log m) and the space complexity is O(rows) at maximum heap size.

Interviewer's Feedback

No feedback provided.