## IBM Interview Question for Software Engineer / Developers

• 2

Country: United States
Interview Type: Phone Interview

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

``````public static boolean isNumberInSorted2DArray(int[][] array, int element, int numberofRows, int numberOfcols)
{

int low = 0, high = numberOfcols -1;

while(low < numberOfcols && high >= 0)
{
if(array[low][high] == element)
return true;
if(element > array[low][high])
low++;
else
high--;
}

return false;
}``````

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

why is it better than the regular search through all the elements? The complexity seems to be the same..Since the 2d array has all the rows and columns sorted, there should be algorithm that is using the binary search to solve the problem more efficiently...

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

@S.Abakumoff: This is actually an optimal solution for a square 2d array, as far as I know. It is O(n) for an n*n matrix. An n*n matrix has n^2 elements, so naive search would be O(n^2). A binary search solution is possible, but it probably wouldn't be as good as you think it would be. You can only get O(nlogn) with typical binary search here, or perhaps O(n) with some clever variant.

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

okay, got it. I checked the web and found O(log(n!)) solution that involves binary search, but it's not a way better than O(n);

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

O (log(n!)) = O(n log n)

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

I believe there's better algorithm which makes use of the ascending order of diagonal.

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

@zyfo2: As far as I know, no faster algorithm than O(n) is known. Please provide specific details if you want to claim a better algorithm.

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

it also runs in O(n) but slightly better. because the algorithm above doesn't make full use of binary search.
leetcode.com/2010/10/searching-2d-sorted-matrix-part-ii.html
leetcode.com/2010/10/searching-2d-sorted-matrix-part-iii.html

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

I've seen this page before. The algorithm doesn't come with a proof that its worst-case bound is O(n),although it probably is. It's slightly better in the particular tests that were run, on the particular machine it was tested on.

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

I believe on average it's slightly better since it cuts down the matrix to half every time while this one eliminates just one column or one row at a time. it's just my thought.

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

@zyfo2: though it cuts the matrix in half, it creates two sub-cases whereas the algorithm presented in this answer only creates one. You can't compare the two algorithms just by arguing that one of them results in subcases that cut the input in half. The number of subcases is very important too.

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

There is a provable Omega(n) lower bound for this problem.

The idea being that you can create a matrix such that one of the main diagonals is an arbitrary given set. Querying for some member of that set in that matrix must take Omega(n) time in the worst case, for any algorithm.

For one such construction, given x_1, x_2, ... x_n place them in positions M[n], M[n-1], M[n-2],.., M[n] (M is matrix and M[i][j] is element of row i, column j).

Now chose Theta(n^2) numbers, all < min x_i, an arrange them so that the top left half of the matrix satisfies the condition, by filling row by and row, and starting with the smallest.

Similarly the bottom right right half can be filled to satify the properties.

Any element finding algorithm, must take Omega(n) in the worst case.

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

Python version of the O(N) algorithm:

``````def search(m, v):
# Search for v in a matrix where
# it is guaranteed that
#  m[r+1][c] >= m[r][c] and
#  m[r][c+1] >= m[r][c]
# Start in the upper right corner
# and go left or down.
r = 0
c = len(m) - 1
while True:
if m[r][c] == v:
return (r, c)
if v < m[r][c]:
# go left (column eliminated)
c -= 1
if c < 0: return None
else:
# go down (row eliminated)
r += 1
if r >= len(m): return None

test_matrix = [
[1, 2, 3, 14, 20],
[4, 6, 10, 15, 30],
[5, 7, 12, 16, 42],
[8, 9, 13, 27, 43],
]

for r in range(len(test_matrix)):
for c in range(len(test_matrix)):
v = test_matrix[r][c]
assert search(test_matrix, v) == (r, c)
assert search(test_matrix, 99) is None``````

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

Very nice. I think it is better than O(n). In any case we are checking at most (m+n-1) number of elements we are checking, where m is number of rows and n is number of columns. Please correct me, if I am wrong

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

@dadakhalandhar: it can't be better than O(n) if it involves checking m + n -1 elements. Just checking n elements is already O(n).

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

Sorry I messed in up the notations. I mean to say if the 2d array has r rows and c columns then it is O(r+c-1). Please correct me if I am wrong

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

We haven't really defined what N is in this problem.

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

It is total number of elements in the 2d array

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

Yes, if N is the total number of elements, the algorithm is O(sqrt(N)) for a square matrix. The analysis that concluded this algo was O(N) had N as the number of rows in a square matrix, and there are sqrt(number of elements) rows in a square matrix.

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

In the problem what mentioned is "monotonically sorted 2D array", but not mentioned array is square. Thus the order is O(max(r,c)), where r is # of rows, # of columns.

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

@Anonymous: Agreed that the algorithm will work for an arbitrary rectangular matrix. The complexity analysis was just for the square matrix case. Also agreed that the complexity for the rectangular case is O(max(r,c)), or equivalently O(r + c).

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

To clarify, I am defining N as the perimeter of the rectangle. The algorithm does not depend on it being a square. At worst it does m+m comparisons (N/2), which makes it O(N).

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

Yes, it's valid to frame it that way. If N is the perimeter of the rectangle, the algorithm is O(N).

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

Suppose I have [1 2 5 13 16 18 25; 4 6 7 14 17 19 31; 10 12 15 16 18 33 35] and I want to search 15, I will compare with the middle element i.e., 14 and 15 is greater than 14 so I know that it cannot be in the quadrient that is less than or equal to 14 ([1 2 5 13; 4 6 7 14]). So will left with remaing 3 Quadrients. We will do it recurssively.

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

Yes, this approach has a recurrence formula of T(n) = 3 T(n/2) + C where C is a constant. The complexity will therefore be O(n^log_2(3)), which is about O(n^1.58). This is better than the naive solution, and worse than the O(n) answer.

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

class BinarySearch_2D
{
public static void main(String args[])
{
int arr[][]=new int[][]{{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20},{21,22,23,24,25}};
int flag =0, search=249;

for(int i=0;i<arr.length;i++)
{
int n = arr[i].length;
int first = 0;
int last = n - 1;
int middle = (first + last)/2;
while( first <= last )
{
if ( arr[i][middle] < search )
first = middle + 1;
else if ( arr[i][middle] == search )
{
flag=1;
System.out.println(search + " is found at [" + (i+1)+"]["+(middle + 1) + "].");
break;
}
else
last = middle - 1;

middle = (first + last)/2;
}
}
if(flag==0)
}
}

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

``````public static boolean search(int target, int startL, int startR,
int[][] array, int len) {
for (int i = startL; i < array.length; i++) {
for (int k = startR; k < len; k++) {
if (target == array[i][k]) {
return true;
} else if ((k == (len - 1)) && (target < array[i][k])) {
len--;

break;
} else if ((k == (len - 1)) && (target > array[i][k])) {
startR = k;

break;
}
}
}

return false;
}``````

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

Here is divide & conquer algorithm. I believe it has logarithmic complexity, because on each step we discard at least quarter of elements. Code in C#:

``````static bool Find(int[,] arr, int value, int xmin, int ymin, int xmax, int ymax)
{
if (xmin > xmax || ymin > ymax) return false;
int pivotX = (xmin + xmax) / 2, pivotY = (ymin + ymax) / 2;

if (value < arr[pivotX, pivotY])
return
Find(arr, value, xmin, ymin, xmax, pivotY - 1) ||
Find(arr, value, xmin, pivotY, pivotX - 1, ymax);
if (value > arr[pivotX, pivotY])
return
Find(arr, value, xmin, pivotY + 1, xmax, ymax) ||
Find(arr, value, pivotX + 1, ymin, xmax, pivotY);
return true;
}

static bool Find(int[,] arr, int value)
{
return Find(arr, value, 0, 0, arr.GetLength(0) - 1, arr.GetLength(1) - 1);
}

static void Main(string[] args)
{
int[,] arr = new int[,]
{
{ 1, 2, 3, 14, 20 },
{ 4, 6, 10, 15, 30 },
{ 5, 7, 12, 16, 42 },
{ 8, 9, 13, 27, 43 }
};
Console.WriteLine(Find(arr, 19)); //  false
Console.WriteLine(Find(arr, 27)); //  true
}``````

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

The recurrence relation here, where X is the total size of the input, is T(X) = 2*T(X/2) + c, which yields T(X) = O(X). The asymptotic runtime is therefore equal to that of checking each element one by one.

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.