Google Interview Question Software Engineers
Country: United States
Interview Type: In-Person
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];
}
}
}
/*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;
}
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];
}
}
}
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++];
}
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])
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)
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);
}
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);
}
}
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);
}
}
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.
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]
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.
Assuming the matrix dimensions as M x N, valid input for the problem would be no more than M repititions of any number.
- valar February 29, 2016If 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.