## Google Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

Assuming the matrix dimensions as M x N, valid input for the problem would be no more than M repititions of any number.

If we need unique values in columns as well, One way we could allow repetitions is by filling the matrix in a zig-zag pattern, starting from top-left like below

(0,0)->(0,1)->(1,0)->(0,2)->(1,1)->(2,1)... and so on.

Comment hidden because of low score. Click to expand.
0
of 2 vote

It's impossible to do this in less than nlogn if there are no constraints besides the ones you've told. Otherwise we could just have 1xn matrix and use the algorithm to get a general sorting algorithm which is faster than nlogn, which is impossible.

Comment hidden because of low score. Click to expand.
0
of 0 vote

c++, implementation, O(n log n)

``````void sortMatrix(vector<vector<int>>& matrix) {
int column, row, i, j, k;
vector<int> arr;

column = matrix.size();
if (column == 0) return;

row = matrix[0].size();
arr.assign(column * row, 0);
for (i = 0; i < column; i++) {
k = i * row;
for (j = 0; j < row; j++) {
arr[k + j] = matrix[i][j];
}
}
sort(arr.begin(), arr.end());
for (j = 0; j < row; j++) {
k = j * column;
for (i = 0; i < column; i++) {
matrix[i][j] = arr[k + i];
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/*Works for main and follow-up
Time complexity(let n=rows m=columns)
Sorting rows-Time: O(nmlogm) Space: O(m)
Sorting columns-Time: O(mnlogn) Space: O(n)
Removing Row repeats-Time: O(nm) Space:O(1)
Removing Column repeats-Time: O(nm) Space: O(1) */
public class Point
{
int row;
int col;
public Point(int r,int c)
{
row=r;
col=c;
}
}
public int[][] sort(int[][] m)throws NullPointerException
{
if(m==null)
{
throw new NullPointerException();
}
if(m.length==1 && m[0].length==1)
{
return m;
}
sortRows(m);
sortColumns(m);
fixRepeatsRow(m);
fixRepeatsCol(m);
return m;
}

private void sortRows(int[][] m)
{
for(int i=0;i<m.length;i++)
{
Arrays.sort(m[i]);
}
}
private void sortColumns(int[][]m)
{
MinHeap<Integer> mh;
for(int i=0;i<m[0].length;i++)
{
mh==new MinHeap<Integer>(m.length);
for(int r=0;r<m.length;r++)
{
mh.insert(m[r][i]);
}
int rowIdx=0;
while(!mh.isEmpty())
{
m[rowIdx++][i]==mh.extractMin();
}
}
}

private void fixRepeatsRow(int[][] m)
{
for(int r=0;r<m.length;r++)
{
for(int c=1;c<m[0].length;c++)
{
if(m[r][c]==m[r][c-1])
{
Point p=findClosest(r+1,c-2,r-1,c+1,m);
if(m[p.row][p.col]<m[r][c])
{
swap(r,c-1,p.row,p.col,m);
}else
{
swap(r,c,p.row,p.col,m);
}
}
}
}
}

private void fixRepeatsCol(int[][] m)
{
for(int c=0;c<m[0].length;c++)
{
for(int r=1;r<m.length;r++)
{
if(m[r][c]==m[r-1][c])
{
Point p=findClosest(r-2,c+1,r+1,c-1,m);
if(m[p.row][p.col]<m[r][c])
{
swap(p.row,p.col,r-1,c,m);
}else{
swap(p.row,p.col,r,c,m);
}
}
}
}
}

private void swap(int r1,int c1, int r2,int c2,int[][] m)
{
int tmp=m[r1][c1];
m[r1][c1]=m[r2][c2];
m[r2][c2]=tmp;
}

private Point findClosest(int r1,int c1,int r2,int c2,int[][] m)
{
if((r1>=0 && r1<m.length) && (c1>=0 && c1<m[0].length))
{
return new Point(r1,c1);
}
if((r2>=0 && r2<m.length) && (c2>=0 && c2<m[0].length))
{
return new Point(r2,c2);
}
return null;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void sort(int[][] a) {
int rowCount = a.length;
int colCount = a[0].length;
int[] temp = new int[rowCount * colCount];
for (int r = 0; r < rowCount; r++) {
for (int c = 0; c < colCount; c++) {
temp[r * colCount + c] = a[r][c];
}
}

Arrays.sort(temp);
for (int c = 0; c < colCount; c++) {
for (int r = 0; r < rowCount; r++) {
a[r][c] = temp[r * rowCount + c];
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void MatrixSort(vector<vector<long>>& data)
{
vector<long> sorted;
for (size_t i = 0; i < data.size(); i++)
for (size_t j = 0; j < data[i].size(); j++)
sorted.push_back(data[i][j]);
QuickSort(sorted, 0, sorted.size() - 1);
size_t k = 0;
for (size_t i = 0; i < data.size(); i++)
for (size_t j = 0; j < data[i].size(); j++)
data[j][i] = sorted[k++];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def merge(lst1, lst2):
if len(lst1) == 0:
return lst2
if len(lst2) == 0:
return lst1
if (lst1[0] > lst2[0]):
return [lst2[0]] + merge(lst1, lst2[1:])
return [lst1[0]] + merge(lst1[1:], lst2)

def mergesort(lst):
if len(lst) <= 1:
return lst
middle = len(lst)/2
return merge(mergesort(lst[:middle]), mergesort(lst[middle:]))

def sort_2d_matrix(matrix):
lst = []
for row in matrix:
lst += row
sorted_lst = mergesort(lst)
col_len = len(matrix[0])
for i in range(len(matrix)):
for j in range(col_len):
matrix[i][j] = sorted_lst[i+j*col_len]

matrix = [[4, 4, 6, 2], [1, 2, 9, 5], [0, 8, 7, 3], [2, 3, 5, 4], [1, 2, 8, 6]]
sort_2d_matrix(matrix)
for i in range(len(matrix)):
print(matrix[i])``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Are negative numbers allowed here.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Solution {
public:
vector<vector<int>> sortMatrix(vector<vector<int>>& M)
{
if (M.size() == 0) return vector<vector<int>>();
if (M.size() < 2 || M[0].size() < 2) return M; // skip if one dimension array
int rows = M.size(), cols = M[0].size();
vector<int> arr = vector<int>(rows * cols, 0);
for (int i = 0; i < rows; i++) {
int k = i * cols;
for (int j = 0; j < cols; j++)
arr[k+j] = M[i][j];
}
std::sort(arr.begin(), arr.end());
M[0][0] = arr[0];
rearrange(M, rows, cols, arr, 1, 1);
return M;
}
void rearrange(vector<vector<int>>& M, int rows, int cols, vector<int>& arr, int r, int c)
{
std::queue<int> reserv;
int k = (r - 1) * cols + (c-1) + 1; // start point for searching in arr

M[r][c] = arr[(c + 1) * r + c];
// fill all (r-1) elems in j-th column
for (int i = 0; i < r; i++) {
while (c > 0 && k < (c + 1) * r + c && M[i][c-1] == arr[k]) { reserv.push(k); k++; }
//if ((c + r - k) < (r - i - 1))  std::cout << "NO SOLUTION " << std::endl; // MUST BE TRUE
M[i][c] = arr[k++];
}
// fill all (c-1) elems in i-th row
for (int j = 0; j < c; j++) {
if (!reserv.empty()) {
M[r][j] = reserv.front();
reserv.pop();
} else M[r][j] = arr[k++];
}
if (r == rows - 1 && c == cols - 1) return; // reach the end - we are done;
if (r < rows - 1) r += 1; // only advance if more row
if (c < cols - 1) c += 1; // only advance if more col
rearrange(M, rows, cols, arr, r, c);
}
}``````

the idea is following: fix the (i, j) location and fill the j-th column and then i-th row. using a sorted array, we fix the point for (i, j)-th cell being (i*cols + j)-th elem in sorted array.

the trick part, all elems in each row should be unique, which is taken care of by the code when we fill the j-th column. it basic scan from k to (i, j)-th in the sorted array and the one not equal to the last one in i-th row.

time complexity: m*n for initialize arr, (m*n)log(m*n) for sorting, and m*n for rearrange
so, in short, it is (m*n) log (m*n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Solution {
public:
vector<vector<int>> sortMatrix(vector<vector<int>>& M)
{
if (M.size() == 0) return vector<vector<int>>();
if (M.size() < 2 || M[0].size() < 2) return M; // skip if one dimension array
int rows = M.size(), cols = M[0].size();
vector<int> arr = vector<int>(rows * cols, 0);
for (int i = 0; i < rows; i++) {
int k = i * cols;
for (int j = 0; j < cols; j++)
arr[k+j] = M[i][j];
}
std::sort(arr.begin(), arr.end());
M[0][0] = arr[0];
rearrange(M, rows, cols, arr, 1, 1);
return M;
}
void rearrange(vector<vector<int>>& M, int rows, int cols, vector<int>& arr, int r, int c)
{
std::queue<int> reserv;
int k = (r - 1) * cols + (c-1) + 1; // start point for searching in arr

M[r][c] = arr[(c + 1) * r + c];
// fill all (r-1) elems in j-th column
for (int i = 0; i < r; i++) {
while (c > 0 && k < (c + 1) * r + c && M[i][c-1] == arr[k]) { reserv.push(k); k++; }
//if ((c + r - k) < (r - i - 1))  std::cout << "NO SOLUTION " << std::endl; // MUST BE TRUE
M[i][c] = arr[k++];
}
// fill all (c-1) elems in i-th row
for (int j = 0; j < c; j++) {
if (!reserv.empty()) {
M[r][j] = reserv.front();
reserv.pop();
} else M[r][j] = arr[k++];
}
if (r == rows - 1 && c == cols - 1) return; // reach the end - we are done;
if (r < rows - 1) r += 1; // only advance if more row
if (c < cols - 1) c += 1; // only advance if more col
rearrange(M, rows, cols, arr, r, c);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Solution {
public:
vector<vector<int>> sortMatrix(vector<vector<int>>& M)
{
{
if (M.size() == 0) return vector<vector<int>>();
// skip if one dimension array as it is trivial
if (M.size() < 2 || M[0].size() < 2) return M;
int rows = M.size(), cols = M[0].size();
vector<int> arr = vector<int>(rows * cols, 0);
for (int i = 0; i < rows; i++) {
int k = i * cols;
for (int j = 0; j < cols; j++)
arr[k+j] = M[i][j];
}
std::sort(arr.begin(), arr.end());
M[0][0] = arr[0];
rearrange(M, rows, cols, arr, 1, 1);
return M;
}
void rearrange(vector<vector<int>>& M, int rows, int cols,
vector<int>& arr, int r, int c)
{
int k = 0;
std::queue<int> reserv;
if (c == cols - 1 && r > c) k = r * cols;
else if (r == rows - 1 && c > r) k = rows * c;
else k = r * c;

M[r][c] = arr[(c + 1) * r + c];
// fill all (r-1) elems in j-th column
if (c >= r) {
for (int i = 0; i < r; i++) {
while (k < (c + 1) * r + c && M[i][c-1] == arr[k]) {
reserv.push(k); k++; }
//if ((c + r - k) < (r - i - 1))  // enough left
M[i][c] = arr[k++];
}
}
// fill all (c-1) elems in i-th row
if (c <= r) {
for (int j = 0; j < c; j++) {
if (!reserv.empty()) {
M[r][j] = reserv.front();
reserv.pop();
} else M[r][j] = arr[k++];
}
}
// reach the end - we are done;
if (r == rows - 1 && c == cols - 1) return;
if (r < rows - 1) r += 1; // only advance if more row
if (c < cols - 1) c += 1; // only advance if more col
rearrange(M, rows, cols, arr, r, c);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

sorry for repeating post, but there are some mistakes in the previous code ...

``````class Solution {
public:
vector<vector<int>> sortMatrix(vector<vector<int>>& M)
{
{
if (M.size() == 0) return vector<vector<int>>();
// skip if one dimension array as it is trivial
if (M.size() < 2 || M[0].size() < 2) return M;
int rows = M.size(), cols = M[0].size();
vector<int> arr = vector<int>(rows * cols, 0);
for (int i = 0; i < rows; i++) {
int k = i * cols;
for (int j = 0; j < cols; j++)
arr[k+j] = M[i][j];
}
std::sort(arr.begin(), arr.end());
M[0][0] = arr[0];
rearrange(M, rows, cols, arr, 1, 1);
return M;
}
void rearrange(vector<vector<int>>& M, int rows, int cols,
vector<int>& arr, int r, int c)
{
int k = 0;
std::queue<int> reserv;
if (c == cols - 1 && r > c) k = r * cols;
else if (r == rows - 1 && c > r) k = rows * c;
else k = r * c;

M[r][c] = arr[(c + 1) * r + c];
// fill all (r-1) elems in j-th column
if (c >= r) {
for (int i = 0; i < r; i++) {
while (k < (c + 1) * r + c && M[i][c-1] == arr[k]) {
reserv.push(k); k++; }
//if ((c + r - k) < (r - i - 1))  // enough left
M[i][c] = arr[k++];
}
}
// fill all (c-1) elems in i-th row
if (c <= r) {
for (int j = 0; j < c; j++) {
if (!reserv.empty()) {
M[r][j] = reserv.front();
reserv.pop();
} else M[r][j] = arr[k++];
}
}
// reach the end - we are done;
if (r == rows - 1 && c == cols - 1) return;
if (r < rows - 1) r += 1; // only advance if more row
if (c < cols - 1) c += 1; // only advance if more col
rearrange(M, rows, cols, arr, r, c);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Perhaps @xSH meant to say Counting Sort.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Not sure if this can be a feasible solution. My idea is that the maximum non conflicting configuration can be obtained by placing the elements diagonally.
e.g.
say a 6x6 matrix

1 2 3 4 5 6
2 3 4 5 6 7
3 4 5 6 7 8
4 5 6 7 8 9
5 6 7 8 9 10

So i can sort all elements is O(Nlog(N)) time and then place them in the following order to achieve least conflict. If a configuration is possible it should be this otherwise no configuration is possible.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

my python solution, but worst-case time complexity is O(nlogC + n)

``````from copy import deepcopy

class myMatrix:

def __init__(self, myArr):

self.myArr = deepcopy(myArr)
self.row = len(myArr)
self.col = len(myArr[0])

for r in range(self.row)  :

self.myArr[r] = sorted(self.myArr[r])
if r > 0:
self.checkPrevRow(r)

def checkPrevRow(self,r) :

p = r-1
for c in range(self.col):
if self.myArr[r][c] < self.myArr[p][c]:
(self.myArr[r][c], self.myArr[p][c]) = (self.myArr[p][c], self.myArr[r][c])
self.checkPrevRowC(p, c)

def checkPrevRowC(self, r, c):

for pr in range(r,0, -1):
if self.myArr[pr][c] > self.myArr[pr-1][c]:
return
else:
(self.myArr[pr][c], self.myArr[pr-1][c] ) = (self.myArr[pr-1][c], self.myArr[pr][c])

def printSorted(self) :

print('The Sorted Array is: ')

for r in range(self.row):
print(self.myArr[r])

def main():
a = [[3, 2 , 1],[1, 9, 4],[2, 2, 2],[3, 7, 1],[6, 5, 2]]

print('The unsorted array is: ')
for r in range(len(a)):
print(a[r])

m = myMatrix(a)
m.printSorted()

if __name__=="__main__":
main()``````

Sample Output:
The unsorted array is:
[3, 2, 1]
[1, 9, 4]
[2, 2, 2]
[3, 7, 1]
[6, 5, 2]
The Sorted Array is:
[1, 2, 2]
[1, 2, 3]
[1, 3, 6]
[2, 4, 7]
[2, 5, 9]

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Can do faster, indeed.

In the original algorithm, we walked the heap and placed the min value in the output table. Instead of a heap we could simply sort the input using integer sort which is linear in the size of the input. This preprocessing step would therefore be linear, and so is the walk, so the total time is linear.

Comment hidden because of low score. Click to expand.
0

sorting is typically O(n*log(n)), so you don't get lower complexity; or do you mean Radix sorting ? that is also not O(n) .... so I don't see what you mean

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.