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:

• Time Complexity: O(mn log m)

#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<<" ";
    }

}