Facebook Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

Simple solution: Use MinHeap.

Add all the elements of first column to the heap and min heapify, print the root, remove and put the next from the same row. Repeat.

- patrj March 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 5 vote

IF there is no space contraint, we can use construct a BST and just print it out. It will take O(mn log(mn)) time.

Now that we have the space constaint, we read the first column print the lowest and delete the element. Read the next element from the row which had the lowest in the previous step and so on.

matrix = [ 
[20, 40, 80], 
[5, 60, 90], 
[45, 50, 55] 
] 

So you read 20 , 5 , 45

Print 5, read the next elemnt from row 2 (as 5 is from row 2)
20, 60, 45 ->  print 20 -> read 40
40 60 45 -> print 40 read 80
80 60 45 -> print 45 read 50
80 60 50 -> print 50 -> read 55
80 60 55 -> print 55 nothing to read
80 60 -> print 60 read 90
80 90 -> print 80 nothing to read
90 print 90 

finish

So 5, 20, 40, 45, 50 , 55, 60, 80, 90 is the  output

- Vijay March 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 votes

m*n matrix, only n elements can be read at a time not m elements as per your example.

- niraj.nijju March 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

This is m-way merging of m sorted arrays. It can be solved using min-heap (priority queue) with size m, in O(mn log m) time.

- ninhnnsoc March 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you please explain why the heap size is m ? m == array.size ?

- Scott March 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@Scott: m is the size of a column.
Imagine you have m arrays (each of size n), sorted already. You want to merge them into 1 single list.

The heap/priority queue is to store the m front elements of m arrays, initially.

Each time, the minimum element x in the heap is extracted, and put into the final list. Suppose x was come from the array k. Then, the next element of k-th array is inserted into the heap. This process continues until all elements are inserted/extracted to/from the heap.

Each insert/extract_min operation takes O(log m) for the heap of size m. Thus, overall time is: mn O(logm) = O(mn logm).

This algorithm takes O(m) space. In implementation, it takes 3m space for the heap: 1 int for the value, 1 int for the number k (for k-th array), 1 int for the index of next element in k-th array.

In C++ we can use pair of pairs, like pair<int val, pair<int k, int id> > to represent element of heap. This way will work without user-defined comparison function.

- ninhnnsoc March 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this logic is correct !! but, there's memory can store only one row at a time...

space complexity wise it's correct O(m) == O(3m)

but, this is FB question it won't be straight question, so may be there's something hidden logic

- Anonymous March 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

It is asked to use extra memory the size of "row", I believe this is not the expected solution..

- Anonymous March 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Remember that in ninhnnsoc's solution you are also using extra memory to remember which array the element in the heap came from so you can drop in the next element from that array.

- Anonymous March 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Well, if we have 1000*2 matrix and we have to STRICTLY adhere to constraint that no more than 2 slots of memory in RAM, my question is can we solve this problem (and ALSO we require better time complexity) ?

- Anonymous March 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a priority queue storing the active positions on the matrix, but having acustom comparison operator to compare the values in the respecive positions.

//compile as g++ -std=c++11 matrix_sort.cpp
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

void sorted_print( vector< vector<int> >& matrix )
{
    typedef pair<int,int> pos_t;
    
    if (matrix.empty()) 
        return;
    
    auto comp = [&matrix] ( const pos_t& a, const post_t& b ) { return matrix[a.first][a.second] > matrix[b.first][b.second]; } ;
    priority_queue< pair<int,int>, vector<pos_t> , decltype(comp) > mem(comp);

    for ( int i=0; i < matrix.size(); i++)
        mem.emplace( i, 0 );

    while (! mem.empty() )
    {
        auto next = mem.top();
        mem.pop();
        cout << matrix[ next.first][next.second] << " ";
        if ( next.second < matrix[next.first].size()-1 )
            mem.emplace( next.first, next.second+1 );
    }
}

int main()
{
    vector< vector<int> > matrix = { {20, 40, 80}, {5, 60, 90}, {45, 50, 55} };
    sorted_print( matrix );
}

- xsed_old_old March 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what is the complexity of your memory usage?

- Scott March 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Two integers per raw so 2*m where m= numer of raws.
Note that the above implemntation instantiates the priority_queue with a vector as the underlying container so no extra cost per node as it would be in a linked list implementation.

- xsed_old_old March 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

//compile as g++ -std=c++11 matrix_sort.cpp
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

void sorted_print( vector< vector<int> >& matrix )
{
    typedef pair<int,int> pos_t;
    
    if (matrix.empty()) 
        return;
    
    auto comp = [&matrix] ( const pos_t& a, const post_t& b ) { return matrix[a.first][a.second] > matrix[b.first][b.second]; } ;
    priority_queue< pair<int,int>, vector<pos_t> , decltype(comp) > mem(comp);

    for ( int i=0; i < matrix.size(); i++)
        mem.emplace( i, 0 );

    while (! mem.empty() )
    {
        auto next = mem.top();
        mem.pop();
        cout << matrix[ next.first][next.second] << " ";
        if ( next.second < matrix[next.first].size()-1 )
            mem.emplace( next.first, next.second+1 );
    }
}

int main()
{
    vector< vector<int> > matrix = { {20, 40, 80}, {5, 60, 90}, {45, 50, 55} };
    sorted_print( matrix );
}

- Anonymous March 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Find the smallest of all the elements in the 1st column. Then, move one row further in the column having the smallest element and compare the n elements. This way, you need not store the elements in a buffer.

- alregith March 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# Compile as Python 2.7
def MatrixSortedStr (matrix):
    result = ""
    m = len (matrix)
    
    if (m == 0):
        return result
    n = len(matrix[0])   # length of columns
    nIndex = list()
    for i in range (m):
        nIndex.append(0)
    
    limit  = m*n
    counter = 0
    while (counter < limit):
        i = 0
        minSet = False
        minIndex = -1
        while (i < m):
            if (nIndex[i] < n):
                if (minSet == False ):
                    minIndexMatrix = i
                    minSet = True
                else:
                    if (matrix[minIndexMatrix][nIndex[minIndexMatrix]] > matrix[i][nIndex[i]]):
                        minIndexMatrix = i
            i += 1
        if (result == ""):
            result = str(matrix[minIndexMatrix][nIndex[minIndexMatrix]])
        else:
            result += " " + str( matrix[minIndexMatrix][nIndex[minIndexMatrix]])
        nIndex[minIndexMatrix] += 1
        counter += 1


    return result
            

matrix = [[20, 40, 80],[5, 60, 90],[45, 50, 55]]
print (MatrixSortedStr(matrix))

- Mahmoud Assi March 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def MatrixSortedStr (matrix):
    result = ""
    m = len (matrix)
    
    if (m == 0):
        return result
    n = len(matrix[0])   # length of columns
    nIndex = list()
    for i in range (m):
        nIndex.append(0)
    
    limit  = m*n
    counter = 0
    while (counter < limit):
        i = 0
        minSet = False
        minIndex = -1
        while (i < m):
            if (nIndex[i] < n):
                if (minSet == False ):
                    minIndexMatrix = i
                    minSet = True
                else:
                    if (matrix[minIndexMatrix][nIndex[minIndexMatrix]] > matrix[i][nIndex[i]]):
                        minIndexMatrix = i
            i += 1
        if (result == ""):
            result = str(matrix[minIndexMatrix][nIndex[minIndexMatrix]])
        else:
            result += " " + str( matrix[minIndexMatrix][nIndex[minIndexMatrix]])
        nIndex[minIndexMatrix] += 1
        counter += 1


    return result
            

matrix = [[20, 40, 80],[5, 60, 90],[45, 50, 55]]
print (MatrixSortedStr(matrix))

- Mahmoud Assi March 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#compile as Python 2.7

def MatrixSortedStr (matrix):
result = ""
m = len (matrix)

if (m == 0):
return result
n = len(matrix[0]) # length of columns
nIndex = list()
for i in range (m):
nIndex.append(0)

limit = m*n
counter = 0
while (counter < limit):
i = 0
minSet = False
minIndex = -1
while (i < m):
if (nIndex[i] < n):
if (minSet == False ):
minIndexMatrix = i
minSet = True
else:
if (matrix[minIndexMatrix][nIndex[minIndexMatrix]] > matrix[i][nIndex[i]]):
minIndexMatrix = i
i += 1
if (result == ""):
result = str(matrix[minIndexMatrix][nIndex[minIndexMatrix]])
else:
result += " " + str( matrix[minIndexMatrix][nIndex[minIndexMatrix]])
nIndex[minIndexMatrix] += 1
counter += 1


return result


matrix = [[20, 40, 80],[5, 60, 90],[45, 50, 55]]
print (MatrixSortedStr(matrix))

- Mahmoud Assi March 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a multi array merge similar to the mergesort but with multiple list or arrays. So a min heap is solution for this. In .NET can be done using a SortedDictionary which behave similarly to a min Heap.

I seems very complex but it is necessary to handle repeated numbers when using a SortedDictionary.

This algorithm is O(n*mlogm)
n -> total rows
m -> total columns

public static List<int> GetSortedList(int[][] matrix)
{
	List<int> result = new List<int>();
	SortedDitionary<int, List<Tuple<int,int>>> minHeap = 
		new SortedDictionar<int, List<Tuple<int, int>>>();

	// Initialize the minHeap with the numbers as sorted key 
	// and a list of tuples with the index and the row index
	// I use a list as multiple rows could have the same value.
	for(int i = 0; i < matrix.Length; i++)
	{
		int[] array = matrix[i];

		if(!minHeap.ContainsKey(array[0]))
		{
			minHeap.Add(
				array[0], 
				new List<Tuple<int,int>> {
					new Tuple<int, int[]>(0, array)
			});
		}
		else
		{
			minHeap[array[0].Add(new Tuple<int, int[]>(0, array));
		}
	}

	while(minHeap.Count > 0)
	{
		var kvp = minHeap.First(); // O(1)
		minHeap.Remove(kvp.Key);

		// Going through the list of repeated number arrays
		for(int i = 0; i < kvp.Value.Count; i++)
		{
			int number = kvp.Key;

			// Adding to the result
			result.Add(number);

			int nextIndex = kvp.Value[i].Item1 + 1;
			int[] array = kvp.Value[i].Item2;

			// It just picked the last number so not adding back
			if(nextIndex == array.Length)
			{
				continue;
			}
			
			int next = array[index];

			if(!minHeap.ContainsKey(next))
			{
				// O(logm)
				minHeap.Add(
					next, 
					new List<Tuple<int,int[]>> {
						new Tuple<int, int[]>(nextIndex , array)
					});
			}
			else
			{
				// O(logm)
				minHeap[next].Add(
					new Tuple<int, int[]>(nextIndex , array));
			}
		}
	}

	return result;
}

- Nelson Perez March 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

JUST 2 slots for 1000*2 and O(minimum) w.r.t time...Is it solvable if NO more than 2 SLOTS? Optimization also is the task next!

- Name March 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Note: n is the number of rows, m number of columns.

Here's a priority queue n-way merge based code where I'm indeed pulling at most one row at a time into memory. The total space complexity is O(m) + O(3*n) though. Time complexity is: O(n*m*log(n)) + O(n*m^2*log(n)) so O(n*m^2*log(n)). I'm assuming pulling the row I need into memory is O(m).

class IntegerWithOrigin {
  // value, row, column
}
		
public void printInOrder(Matrix matrix) {
  if (matrix == null) {
    return;
  }

  PriorityQueue<IntegerWithOrigin> minQueue = new HeapPriorityQueue<IntegerWithOrigin>();
  int rowInBuffer = -1;
  int[] buffer = new int[matrix.getM()];
  for (int i = 0; i < matrix.getN(); i++) {
    matrix.readRowInto(i, buffer);
	rowInBuffer = i;

	minQueue.add(new IntegerWithOrigin(buffer[0], i, 0));
  }

  while (!minQueue.isEmpty()) {
    IntegerWithOrigin min = minQueue.getTop();
	System.out.println(min.getValue());
	if (min.getColumn() < matrix.getM() - 1) {
	  if (min.getRow() != rowInBuffer) {
	    matrix.readRowInto(buffer, min.getRow());
	  }
	  min.setColumn(min.getColumn() + 1);
	  min.setValue(buffer[min.getColumn()]);
	  minQueue.add(min);
	}
  }

}

Here is a brute force solution with O(m) space complexity. Time complexity is O(n^2*m^3):

public void printInOrder(Matrix matrix) {
  if (matrix == null) {
    return;
  }

  int[] buffer = new int[matrix.getM()];
  int lastPrintedValue = Integer.MIN_VALUE;
  int printedElements = 0;
  while (printedElements != matrix.getN() * matrix.getM()) {
    int currentMin = Integer.MAX_VALUE;
    for (int i = 0; i < matrix.getN(); i++) {
	  matrix.readRowInto(i, buffer);
	  int at = 0;
	  while (at < buffer.length && buffer[at] <= lastPrintedValue) {
	    at++;
	  }
	  if (at < buffer.length && buffer[at] < currentMin) {
	    currentMin = buffer[at];
	  }
	}
	System.out.println(currentMin);
	lastPrintedValue = currentMin;
	printedElements++;
  }

}

- P March 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Merge multiple sorted arrays without min heap

#define INT_MAX 2147483647

void PrintMatrix(int *Matrix, int M, int N)
{
	int *ArrIndexes = new int[N];

	for(int i = 0; i < N; i++)
	{
		ArrIndexes[i] = 0;
	}

	for(int i = 0; i < M*N; ++i)
	{
		int Min = INT_MAX;
		int MinArray = 0;

		for(int j = 0; j < N; j++)
		{
			int *arr = &Matrix[j*M];

			if(ArrIndexes[j] < M)
			{
				if(arr[ ArrIndexes[j] ] < Min)
				{
					Min = arr[ ArrIndexes[j] ];
					MinArray = j;
				}
			}
		}

		TRACE("%d", Min);
		if(i != M*N-1)
		{
			TRACE(", ");
		}

		ArrIndexes[MinArray]++;

	}

}

void ArrayTest::run()
{
	int Matrix[3][3] = { {20, 40, 80}, {5, 60, 90}, {45, 50, 55} };

	PrintMatrix((int *)Matrix, 3, 3);
	
}

- Art March 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

suppose a mergesort function is available (we can write our own if it is not available.). Just put the rows into mergesort functions. one at a time.

- hiuhchan March 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def matrix_to_list(mtx, n, m):

	heap = []
	ret = []

	for i in range(len(mtx)):
		heapq.heappush(heap, Node(mtx[i][0], i, 0))

	while len(heap) > 0:
		item = heapq.heappop(heap)
		if item.col < (m - 1):
			heapq.heappush(heap, Node(mtx[item.row][item.col + 1], item.row, item.col + 1))

		ret.append(item.num)

	return ret

- arvin March 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algorithm: Treat the rows as sorted elements of a sequence and perform mergesort on the elements.
Work:

O(mn*log(m))

Span:

O(mn)

Proof of Work and Span: The merge operation is linear work, so the work of merge at the root node is

mn

. The work at the lowest level of the call tree is

2^log(m)*n = mn

. Thus, work of the algorithm is the same at all levels. By the brick method (i.e. Master's Theorem), overall work must be

O(mn*log(m))

. Algorithm has

O(mn)

at the root and

O(n)

span at the lowest level of the call tree, so it is root-dominated in terms of span. Thus, span is

O(mn)

.

- narainsk March 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This code is using O(n*m)complexity. row is n, col is m.
if i m wrong, than plz, correct me.

public class Matrix1{
    public static void main(String []args){
   
      int [][] m=new int[][]{
	       { 20, 40, 80 },
	       { 5, 60, 90 },
	       { 45, 50, 55 } };
	  
	  int i=0,j=1,k=2,a=0,b=0,c=0;
	  for(int p=0;p<9;p++){
	       if(c<3&&a<3&&b<3){
	        if(m[i][a]<m[j][b]&&m[i][a]<m[k][c]){
			    System.out.print(m[i][a]+" , ");
				a++;
				if(c==3)
				   mass(m,j,b,k,c,p);
			}
			else if(m[j][b]<m[i][a]&&m[j][b]<m[k][c]){
			    System.out.print(m[j][b]+" , ");
				b++;
				if(c==3)
				   mass(m,i,a,k,c,p);
			}
			else if(m[k][c]<m[j][b]&&m[k][c]<m[i][a]){
			    System.out.print(m[k][c]+" , ");
				c++;
				if(c==3)
				   mass(m,i,a,j,b,p);
			}
		  }	
	   }
	 }
	 public static void mass(int arr[][],int i,int a,int j,int b,int p){
	      int l=9-p;
		  for(int e=0;e<l;e++){
		      if(a==3&&b!=3){
			     System.out.print(arr[j][b]+" , "); b++;
			  }
			  if(b==3&&a!=3){
			     System.out.print(arr[i][a]+" , "); a++;
			  }
			 if(a!=3&&b!=3){ 
		      if(arr[i][a]<arr[j][b]){
			      System.out.print(arr[i][a]+" , ");
				  a++;
			  }
			  else{
			     System.out.print(arr[j][b]+" , ");
				 b++;
			  }
			 } 
		  }
	 }
   
}

- sadhanaj28 March 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Without a space constraint, we can solve this by inserting all the elements into a binary search tree, then pulling them out in order.
O(m * n * log(m * n))
(Note that std::set is typically implemented as a binary search tree)

void printSortedWithBST(int **data, int m, int n)
{
	std::set<int> tree;
	for (int i = 0; i < m; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			tree.insert(data[i][j]);
		}
	}
	for (set<int>::const_iterator it = tree.begin(); it != tree.end(); ++it)
	{
		printf("%d ", *it);
	}
	printf("\n");
}

If we are space constrained, we can keep an array of indices to indicate our current position in each row, then continuously pull out the lowest value at the current indices until we have printed all the numbers
O(m * n * n)

void printSortedSpaceConstrained(int **data, int m, int n)
{
	int toPrint = m * n;
	int index[m];
	for (int i = 0; i < m; ++i)
	{
		index[i] = 0;
	}

	while (toPrint > 0)
	{
		int minValue = INT_MAX;
		int minIndex = 0;
		for (int i = 0; i < m; ++i)
		{
			if (index[i] < n && data[i][index[i]] < minValue)
			{
				minValue = data[i][index[i]];
				minIndex = i;
			}
		}
		printf("%d ", minValue);
		++index[minIndex];
		--toPrint;
	}
	printf("\n");
}

- Anonymous March 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Without a space constraint, we can insert all the elements into a binary search tree, then pull them out in order
(Note: std::set is typically implemented as a BST)
O(m * n * log(m * n))

void printSortedWithHeap(int **data, int m, int n)
{
	std::set<int> tree;
	for (int i = 0; i < m; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			tree.insert(data[i][j]);
		}
	}
	for (std::set<int>::const_iterator it = tree.begin(); it != tree.end(); ++it)
	{
		printf("%d ", *it);
	}
	printf("\n");
}

With the space constraint, we can keep an array of indices to indicate the position in each row of the lowest value that hasn't been printed, then continuously pull out the lowest value of the current indices until you have printed all the numbers
(Note: I am keeping n indices, which technically is a column, not a row, but it will always be ints, even if the data represents objects of a different kind)
O(m * n * n)

void printSortedSpaceConstrained(int **data, int m, int n)
{
	int toPrint = m * n;
	int index[m];
	for (int i = 0; i < m; ++i)
	{
		index[i] = 0;
	}

	while (toPrint > 0)
	{
		int minValue = INT_MAX;
		int minIndex = 0;
		for (int i = 0; i < m; ++i)
		{
			if (index[i] < n && data[i][index[i]] < minValue)
			{
				minValue = data[i][index[i]];
				minIndex = i;
			}
		}
		printf("%d ", minValue);
		++index[minIndex];
		--toPrint;
	}
	printf("\n");
}

- Nick March 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my Java implementation using PriorityQueues it uses O(m) space

import java.util.PriorityQueue;

public class SortMatrix {

    public static void main(String[] args) {
        int[][] matrix = {
                {45, 50, 55},
                {20, 40, 80},
                {5, 60, 90},
                {1, 2, 3},
        };
        sort(matrix);
    }

    public static void sort(int[][] matrix) {
        for (int i = 1; i < matrix.length; i++) {
            if (matrix[i-1][0] > matrix[i][0]) {
                int[] tmp = matrix[i-1];
                matrix[i-1] = matrix[i];
                matrix[i] = tmp;
                i = 0;
            }
        }

        int rows = matrix.length, cols = matrix[0].length;
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                Integer peek = heap.peek();
                if (peek != null && peek > matrix[i][j]) {
                    System.out.println(matrix[i][j] + " ");
                    continue;
                }

                if (heap.size() > cols) {
                    System.out.println(heap.poll() + " ");
                }
                heap.add(matrix[i][j]);
            }
        }

        while (heap.peek() != null) {
            System.out.println(heap.poll() + " ");
        }
    }
}

- Alex Rashkov March 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {

int array[][] = { { 20, 40, 80 }, { 5, 60, 90 }, { 45, 50, 55 } };

int sortIndex[] = new int[array.length];
for (int i = 0; i < array.length; i++) {
sortIndex[i] = 0;
}

for (int i = 0; i < array.length * array[0].length; i++) {
int min = 0;
for (int j = 0; j < sortIndex.length; j++) {
if (sortIndex[j] != -1) {
min = array[j][sortIndex[j]];
break;
}
}

int indexMin = 0;
for (int j = 1; j < sortIndex.length; j++) {
if (sortIndex[j] != -1 && array[j][sortIndex[j]] < min) {
min = array[j][sortIndex[j]];
indexMin = j;
}
}
System.out.print(min + " ");

sortIndex[indexMin] = sortIndex[indexMin] + 1;
if (sortIndex[indexMin] >= array[0].length) {
sortIndex[indexMin] = -1;
}
}
}

- Magemello March 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {

        int array[][] = { { 20, 40, 80 }, { 5, 60, 90 }, { 45, 50, 55 } };

        int sortIndex[] = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            sortIndex[i] = 0;
        }

        for (int i = 0; i < array.length * array[0].length; i++) {
            int min = 0;
            for (int j = 0; j < sortIndex.length; j++) {
                if (sortIndex[j] != -1) {
                    min = array[j][sortIndex[j]];
                    break;
                }
            }

            int indexMin = 0;
            for (int j = 1; j < sortIndex.length; j++) {
                if (sortIndex[j] != -1 && array[j][sortIndex[j]] < min) {
                    min = array[j][sortIndex[j]];
                    indexMin = j;
                }
            }
            System.out.print(min + " ");

            sortIndex[indexMin] = sortIndex[indexMin] + 1;
            if (sortIndex[indexMin] >= array[0].length) {
                sortIndex[indexMin] = -1;
            }
        }
    }

- Magemello March 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

using Groovy way and recursion

class ListOrderNumbersFromMatrix {
def static evaluate(matriz) {
def minQueue = null
def min = null

matriz.each() { Queue row ->

if (min == null)
min = row.peek()

if (row.peek() && row.peek() <= min)
minQueue = row;
}

println minQueue.poll();

if (!matriz.flatten().empty)
evaluate(matriz)

}

static void main(String[] args) {
def matriz = [
[20,40,80] as LinkedList,
[5,60,90] as LinkedList,
[45,50,55] as LinkedList
]

ListOrderNumbersFromMatrix.evaluate(matriz);
}

}

- Felipe Pina March 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can refer to this code. It uses heap data structure.

This code works fine except the first element printed will always be mat[0][0].

package practice;

import java.util.Scanner;

public class matrix_sorting_problem {
	static int m=3,n=4;
	static int[] a;
	static int[][] mat;
	public static void main(String args[]){
		
		mat=new int[m][n];
		Scanner s=new Scanner(System.in);
		for(int i=0;i<m;i++){
			System.out.println("enter values for col "+i );
			for(int j=0;j<n;j++){
				mat[i][j]=s.nextInt();
			}
		}
		
		a=new int[m];
		int c=0;
		int cou=0;
		for(int i=0;i<m;){
			if(c<n){
			a[i]=(mat[c][cou]*100)+(c*10)+cou;
			//System.out.println("values of a"+ i+ "   "+ a[i]);
			c++;
			i++;
			}
			else{
				c=0;
				cou++;
				a[i]=(mat[c][cou]*100)+(c*10)+cou;
				//System.out.println("values of a"+ i+ "   "+ a[i]);
				i++;
			}
					
		}
		matrix_sorting_problem m=new matrix_sorting_problem();
		for(int x=0;x<11;x++)
		System.out.println(m.getmin());
		
	}
	
	void heapify(){
		int temp=a[0];
		int col=temp%10;
		int row=(temp/10)%10;
		//System.out.println(a[0]+"   "+col+"   "+row);
		if((col+1)<n){
		a[0]=(mat[row][col+1])*100+row*10+col+1;
		//System.out.println(a[0]+"   "+col+"   "+row);
		}else{
			int flag=0;int i=0;
			col=(a[i]%10)+1;
			row=(a[i]/10)%10;
			while(flag!=1){
				
				//System.out.println(col+ "    " +row);
				//System.out.println("stuck here");
				if(col<n){
				a[0]=(mat[row][col])*100+row*10+col;
				//System.out.println(a[0]);
				flag=1;
				}else{
					i++;
				}
				if(i<m){
				col=(a[i]%10)+1;
				row=(a[i]/10)%10;}
				else{
					a[0]=999;
					flag=1;
				}
			}
		}
		//a[0]=a[a.length-1];
		int i=0;
		/*for( i=0;i<m;i++){
			System.out.print("   "+ a[i]);
		}*/
		i=0;
		while(((2*i)+1<a.length)&&(((a[i]/100)>(a[2*i+2]/100))||((a[i]/100)>(a[2*i+1]/100)))){
			//System.out.println("stuck here in while- value of i"+ i);
			if(a[2*i+1]/100>a[2*i+2]/100){
			//	System.out.println("executing if");
				int temp1=a[i];
				a[i]=a[2*i+2];
				a[2*i+2]=temp1;
				i=2*i+2;
			}else{
			//	System.out.println("executing else");
				int temp1=a[i];
				a[i]=a[2*i+1];
				a[2*i+1]=temp1;
				i=2*i+1;
			}
		}
	}
	
	int getmin(){
		int temp= a[0];
		//System.out.println(temp);
		heapify();
		
		return temp/100;
	}
	
}

- Vaishnavi March 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The below code is just for reference. It uses heap data structure.

This code works fine except the first element printed will always be mat[0][0].

package practice;

import java.util.Scanner;

public class matrix_sorting_problem {
	static int m=3,n=4;
	static int[] a;
	static int[][] mat;
	public static void main(String args[]){
		
		mat=new int[m][n];
		Scanner s=new Scanner(System.in);
		for(int i=0;i<m;i++){
			System.out.println("enter values for col "+i );
			for(int j=0;j<n;j++){
				mat[i][j]=s.nextInt();
			}
		}
		
		a=new int[m];
		int c=0;
		int cou=0;
		for(int i=0;i<m;){
			if(c<n){
			a[i]=(mat[c][cou]*100)+(c*10)+cou;
			//System.out.println("values of a"+ i+ "   "+ a[i]);
			c++;
			i++;
			}
			else{
				c=0;
				cou++;
				a[i]=(mat[c][cou]*100)+(c*10)+cou;
				//System.out.println("values of a"+ i+ "   "+ a[i]);
				i++;
			}
					
		}
		matrix_sorting_problem m=new matrix_sorting_problem();
		for(int x=0;x<11;x++)
		System.out.println(m.getmin());
		
	}
	
	void heapify(){
		int temp=a[0];
		int col=temp%10;
		int row=(temp/10)%10;
		//System.out.println(a[0]+"   "+col+"   "+row);
		if((col+1)<n){
		a[0]=(mat[row][col+1])*100+row*10+col+1;
		//System.out.println(a[0]+"   "+col+"   "+row);
		}else{
			int flag=0;int i=0;
			col=(a[i]%10)+1;
			row=(a[i]/10)%10;
			while(flag!=1){
				
				//System.out.println(col+ "    " +row);
				//System.out.println("stuck here");
				if(col<n){
				a[0]=(mat[row][col])*100+row*10+col;
				//System.out.println(a[0]);
				flag=1;
				}else{
					i++;
				}
				if(i<m){
				col=(a[i]%10)+1;
				row=(a[i]/10)%10;}
				else{
					a[0]=999;
					flag=1;
				}
			}
		}
		//a[0]=a[a.length-1];
		int i=0;
		/*for( i=0;i<m;i++){
			System.out.print("   "+ a[i]);
		}*/
		i=0;
		while(((2*i)+1<a.length)&&(((a[i]/100)>(a[2*i+2]/100))||((a[i]/100)>(a[2*i+1]/100)))){
			//System.out.println("stuck here in while- value of i"+ i);
			if(a[2*i+1]/100>a[2*i+2]/100){
			//	System.out.println("executing if");
				int temp1=a[i];
				a[i]=a[2*i+2];
				a[2*i+2]=temp1;
				i=2*i+2;
			}else{
			//	System.out.println("executing else");
				int temp1=a[i];
				a[i]=a[2*i+1];
				a[2*i+1]=temp1;
				i=2*i+1;
			}
		}
	}
	
	int getmin(){
		int temp= a[0];
		//System.out.println(temp);
		heapify();
		
		return temp/100;
	}
	
}

- Vaishnavi March 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* Using In place sorting , no additional rows in memory, making use of the sort order */

#include <stdio.h>
2
3 void main () {
4
5 #define ROW 3
6 #define COL 3
7
8 int mat[ROW][COL]= {
9 { 0,1,5,} ,
10 { 5, 90,100} ,
11 { -1,2,2 }
12
13 } ;
14
15 int swapped_column=-1,swapped_row=-1,i,j,k,m,tmp,l,swapped = 0;
16
17
18 for (l=0;l<ROW;l++) {
19 for (i=0;i<COL;i++) {
20 for (j=l+1;j<ROW;j++) {
21
22 swapped_column = 0;
23 swapped_row = j;
24
25 if ( *(*(mat +l) + i ) > *(*(mat + j) + 0 )) {
26 swapped = 1 ;
27 for (k=1;k<COL ; k++ ) {
28
29 if ( *(*(mat +l) + i ) > *(*(mat + j) + k )) {
30 swapped_column = k;
31 swapped_row = j;
32 swapped = 1 ;
33 }
34
35 }
36 if (swapped) {
37 tmp = *(*(mat +l) + i ) ;
38 *(*(mat +l) + i ) = *(*(mat + j) + 0 ) ;
39 for (m=0;(swapped_column> 0 ) && (m<swapped_column ); m++ ) {
40 *(*(mat +j)+m) = *(*(mat +j)+ (m+1)) ;
}
42 *(*(mat +swapped_row) + swapped_column) = tmp ;
43 swapped =0 ;
44 }
45 }
46 }
47 }
48 }
49
50
51 for (i=0;i<ROW;i++) {
52 for (j=0;j<COL;j++) {
53 printf("%d\t", *(*(mat+i)+j) ) ;
54 }
55 printf("\n") ;
56 }
57
58 }

- Priyesh March 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1 /* Using in place sort., maing use of the existing row sort order */
2 #include <stdio.h>
3
4 void main () {
5
6 #define ROW 3
7 #define COL 3
8
9 int mat[ROW][COL]= {
10 { 0,1,5,} ,
11 { 5, 90,100} ,
12 { -1,2,2 }
13
14 } ;
15
16 int swapped_column=-1,swapped_row=-1,i,j,k,m,tmp,l,swapped = 0;
17
18
19 for (l=0;l<ROW;l++) {
20 for (i=0;i<COL;i++) {
21 for (j=l+1;j<ROW;j++) {
22
23 swapped_column = 0;
24 swapped_row = j;
25
26 if ( *(*(mat +l) + i ) > *(*(mat + j) + 0 )) {
27 swapped = 1 ;
28 for (k=1;k<COL ; k++ ) {
29
30 if ( *(*(mat +l) + i ) > *(*(mat + j) + k )) {
31 swapped_column = k;
32 swapped_row = j;
33 swapped = 1 ;
34 }
35
36 }
37 if (swapped) {
38 tmp = *(*(mat +l) + i ) ;
39 *(*(mat +l) + i ) = *(*(mat + j) + 0 ) ;
40 for (m=0;(swapped_column> 0 ) && (m<swapped_column ); m++ ) {
41
42
43 *(*(mat +j)+m) = *(*(mat +j)+ (m+1)) ;
44
45 }
46 *(*(mat +swapped_row) + swapped_column) = tmp ;
47 swapped =0 ;
48 }
49 }
50 }
51 }
52 }
53
54
55 for (i=0;i<ROW;i++) {
56 for (j=0;j<COL;j++) {
57 printf("%d\t", *(*(mat+i)+j) ) ;
58 }
59 printf("\n") ;
60 }
61
62 }

- priyeshnn March 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private ArrayList<ArrayList<Integer>> mMatrix;

    private void initMatrix() {
        if (mMatrix == null) {
            mMatrix = new ArrayList<>();

            ArrayList<Integer> tmp = new ArrayList<>();
            tmp.add(20);
            tmp.add(40);
            tmp.add(80);
            mMatrix.add(tmp);

            ArrayList<Integer> tmp2 = new ArrayList<>();
            tmp2.add(5);
            tmp2.add(60);
            tmp2.add(90);
            mMatrix.add(tmp2);

            ArrayList<Integer> tmp3 = new ArrayList<>();
            tmp3.add(45);
            tmp3.add(50);
            tmp3.add(55);
            mMatrix.add(tmp3);
        }
    }

private int getColMin() {
        int minIndex, minValue;
        ArrayList<Integer> row = mMatrix.get(0);
        minIndex = 0;
        minValue = row.get(0);
        for (int i = 1; i < mMatrix.size(); i++) {
            row = mMatrix.get(i);
            int nextValue = row.get(0);
            minValue = Math.min(minValue, nextValue);
            if (minValue == nextValue) {
                minIndex = i;
            }
        }
        return minIndex;
    }

private void printSorted() {
        while (!mMatrix.isEmpty()) {
            int colMin = getColMin();
            ArrayList<Integer> row = mMatrix.get(colMin);
            // Print: row.get(0));
            row.remove(0);
            if (row == null || row.isEmpty()) {
                mMatrix.remove(colMin);
            }
        }
    }

- Implementation with Java ArrayList March 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution using mean heap. Space complexity is O(m).

void print_matrix(int *matrix[], int h, int w)
{
  int x, y;
  heap minHeap(h, true);
  for (y = 0; y <h; y++)
    minHeap.add(node(0, y, matrix[y][0]));
  while(minHeap.size())
  {
    node min = minHeap.extract();
    cout << min.value << " ";
    if (min.x < w-1)
      minHeap.add(node(min.x+1, min.y, matrix[min.y][min.x+1]));
  }
}

- hankm2004 July 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. find the smallest number in the first column and print it out.
2. remove the smallest number from its row, and shift all number to the left.
3. repeat.
Assume the max value in the matrix is smaller than 10^32-1

public void printSortedMatrix(int[][] matrix)
	{
		for(int a=0;a<matrix.length*matrix[0].length;a++){
			int min = Integer.MAX_VALUE;
			int index = 0;
			for(int i=0;i<matrix.length;i++){
				if(matrix[i][0] < min){
					min = matrix[i][0];
					index = i;
				}
			}
			System.out.print(min+",");
			for(int j=1;j<matrix[0].length;j++){
				matrix[index][j-1] = matrix[index][j];
			}
			matrix[index][matrix[0].length-1] = Integer.MAX_VALUE;
		}
	}

- jiahuang August 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

All the above solutions provide a good way of solving this problem except that memory requirement isn't met. How about we solve it this way.

Consider the matrix to be 3X3.
1. Sort the [0,0] [0,1] and [0,2], this will result in sorted first row. Infact this step can be skipped since individual rows are already sorted.
2. Then sort [0,1] [0,2] and [1,0] (basically it is a sliding window of the number of elements in a row.
3. Then sort [0,2] [1,0] and [1,2] and so on
4. Need to do this till no more swaps are happening. Basically a bubble sort in K batches.

{{ { void CustomSort(int** matrix, int Rows, int Cols, int startIndex, int endIndex, bool& swapped)
{
swapped = false;
for (int i = startIndex; i < endIndex; i++)
{
int currentRow = i / Rows;
int currentCol = i / Cols;

int nextRow = (i + 1) / Rows;
int nextCol = (i + 1) / Cols;

if (matrix[currentRow][currentCol] > matrix[nextRow], [nextCol])
{
swap(matrix, currentRow, currentCol, nextRow, nextCol);
swapped = true;
}
}


}
void MatrixSortconstrainedByRowMemory(int** Matrix, int Rows, int Cols)
{
int totalElements = Rows * Cols;
Bool swapped = true;
while (swapped)
{
for (int i = 0; i < totalElements; i = i + Cols)
{
CustomSort(Matrix, Rows, Cols, i, (i + Cols) - 1, swapped);
}
}

}
} }}

- Alpha August 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{ {

void CustomSort(int** matrix, int Rows, int Cols, int startIndex, int endIndex, bool& swapped)
{
swapped = false;
for (int i = startIndex; i < endIndex; i++)
{
int currentRow = i / Rows;
int currentCol = i / Cols;

int nextRow = (i + 1) / Rows;
int nextCol = (i + 1) / Cols;

if (matrix[currentRow][currentCol] > matrix[nextRow], [nextCol])
{
swap(matrix, currentRow, currentCol, nextRow, nextCol);
swapped = true;
}
}


}
void MatrixSortconstrainedByRowMemory(int** Matrix, int Rows, int Cols)
{
int totalElements = Rows * Cols;
Bool swapped = true;
while (swapped)
{
for (int i = 0; i < totalElements; i = i + Cols)
{
CustomSort(Matrix, Rows, Cols, i, (i + Cols) - 1, swapped);
}
}

}
} }}

- Alpha August 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Loop through the matrix and insert each element into a Binary Search Tree
2. Print inorder traverse

- Yogourta June 01, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More