## IBM Interview Question for System Administrators

• 1
of 1 vote

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

For M X N matrix, If we use heap, I think this is possible in O(nlogM) where n is total number of elements.
1, For every node in heap, store i,j which shows current cell's row, column.
2, Initialize heap with first elements of each row.
3, Whenever the elements are removed replace the next element in the same row using i,j value of the removed node.
4, If entire row is exhausted, decrease heap size by 1.
Continue till heap size is zero.

Since each elemetn is visited once & heap is of size M, order is O(nlogM).

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

If this kind of matrix is there then elements in the first row would be the only elements and plus the element at a[i][i].....So elements in first row can be printed in n^2 times and element at a[i][i] can be printed in constant time..........hence running time shud be O(n^2)

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

i dont find the above algo feasble... need a bit of more clarification..

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

just construct a BST of M*N elements scanning row by row.This can be done in O(MN) time in the worst-case(skewed BST).Then perform inorder traversal which takes atmost O(MN) time in the worst case.So,total time is O(2MN)=O(MN).

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

O(n^2 logn) is trivial, but O(n^2) seems difficult.

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

struct element
{
value // value of the element in the Matrix
(i,j) //location of the element
}

// Q is priority Q based on Value

Start from (i,j) = (0,0) - as it is the minimum in the Matrix

Add element[0][0] to Priority Q //element.value = a[0][0], element.i=element.j=0

while(Q not empty)
{
x = Q.pop() // gets the minimum from the Q based on value
print x.value
Add neighbour values of (x.i,x.j) to a Priority Q // which are a[i+1][j] &
a[i][j+1]
}

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

This Algorithm is also of time complexity O(n2logn).
Analysis:
Maximum heap size can be n.
There can be n2 insertions
Hence n2 * logn = n2logn

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

My bad..I think the solution is no better than O(n2logn).

However, cant we just simply sort treating the matrix as single row of all numbers and print them. Regular sorting takes O(n2).

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

There are a total of n2 elements. So even if you treat whole matrix as a single array, complexity is n2*log(n2). Which is same as n2*log(n).

Hence, it doesn't help.

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

Create a min heap of the first row in the matrix
Remove the min element and replace this with the element in the first column till the last element in the first column.

we have scanned the topmost row and leftmost column...
Now consider the new matrix where the toprow and left column does not exist.
Do the same as above with the new matrix

Time complexity => O((M+N)logN)

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

take the matrix as
1 2 4
3 4 5
5 6 7

o/p will be : 1,2,3,4,5,4,5,6,7 which is wrong

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

can any one please give the code so that the complexity is calculated.

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

Why is this question tagged under Operating System?

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

Can be done in linear time. Use 2 pointer- 1 would move from top to bottom and other from left to right. Compare the elements pointed by 2 ptrs, push the smaller elt in the output array and increment this prt. I tried to implement it in Java. Below is the code:

``````public class SortMatrix {
public static void main(String[] args)
{
int[][] input = new int[][] {{5,10,11,12},{6,16,26,27},{7,22,27,36},{8,23,38,43}};
int[] op = sortMatrix(input);
{
for(int i:op)
{
System.out.print(i +", ");
}
}

}

public static int[] sortMatrix(int [][] collection)
{
int numOfColls = collection.length;
int numOfRows = collection[0].length;
int[] output = new int[numOfColls*numOfRows];
int a = 1;
int b = 0;
int c = 0;
int d = 1;
int opctr = 0;
output[0] = collection[0][0];
while(++opctr<output.length)
{
if(a==c && b==d) //both the ptr ponting to the same elt
{
output[opctr] = collection[a][b];
a++;
d++;
}
else if(collection[a][b]<collection[c][d])
{
output[opctr] = collection[a][b];
a++;
}
else
{
output[opctr] = collection[c][d];
d++;
}

if(a==numOfColls)
{
a = c;
b++;
}
if(d==numOfRows)
{
d = b;
c++;
}
}
return output;
}
}``````

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

Here you go. Don't you think here interpretation of column and row is wrong.

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

why not user a merge sort on each row...
main() {
int a[NXM];
int b[N][M] = {{1,2,4},{3,4,6},{5,6,7});
for (i = 0 i < NXM; i++) {a[i] = 0;}
merge(a, b);
}

merge(int a[], int b[][]) {

for(int i = 0; i< N; i++) {
mergeMatrix(a, b[i]);
}

mergeMatrix(int a[], int b[]) {
mergeSort(a, b);
}

Complexity O(NM)

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

We can do sorting in O(n root(n)) , Matrix is a youngs tableau . So we can sort those elements as explained in the below link

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.