This post is third in the series of programming job interview challenge, if you are not yet familiar with these series please take your time and read:

  1. A Programming Job Interview Challenge
  2. A Programming Job Interview Challenge #2

Well, last weeks challenge was very successful, all of the comments which contain answers to the question are now approved and can be viewed in challenge #2 post.

The correct answer to challenge #2:

As our first commentator (who answered correctly), Mike Agar said:

This is a Big “O” problem that screams for a LUT (Look Up Table). Don’t spin on each pixel, create your 256 entry look up table of all possible reversals, and do a quick pass over the 1000×1000 array by simply indexing into the table with the original value as the lookup.

Those guys provided the correct answer in their blogs:

Trung Dinh solution : http://www.taak.org/challenge2.htm.

Adam B answer : http://programmersthoughts.blogspot.com/

Igor Ostrovsky answer: http://igoro.com/archive/programming-job-interview-challenge/

Those guys provided the correct answer by leaving a comment:

Anton Irinev who provided an implementation, Heiko Hatzfeld, Bill Krueger, Niki, Kevin I, Chris Miller, Will (didn’t mention LUT but its very close), Compuboy, Eugene Efimochkin, Adrian Aisemberg, Tim, leppie and bartek szabat.

Roberto Orsini wrote a really great implementation of how to parallelise the problem here – http://blog.fogbank.org/ , using threads from the threadPool, but he didn’t use LUT to reverse the bits. Although this problem is perfectly parallelizable, you can’t rely on the fact that there is more than one CPU (unless stated it in the question). All of the others who provided bitwise operations: even if your solution is correct (XOR with 0xFF is wrong for instance) it is not the most efficient one, you should assume that your code should work on every machine and every processor and you can’t rely on specific hardware where a specific operation may be very efficient.

Edward Shen gave a very detailed answer by mail ,which is currently for the Dev102 eyes only (unlike comments and blog post which are public). We (Dev102 team) realized that we made a mistake because we introduced mail as one of the options to send answers. So, I would like to emphasize that:

  • Mail is no longer an option to send answers (unless you want to keep your answer private).
  • Comment with answers will not be approved until next weeks challenge (if readers will see the correct answer in one of the comments, it will become pointless).

This weeks question:

matrixYour input is mXn numeric matrix which is made up from sorted rows and sorted columns. Take a look at the following example, notice that all rows are sorted and all columns are sorted. What is the most efficient way to find an item in this matrix and what is the complexity of the solution.

Take your time…, do you know the answer?

Accept the challenge and provide your solution.



Tags :

54 Responses to “A Programming Job Interview Challenge #3”


  1. Daniel

    Said on May 12, 2008 :

    Solution in O(n logn):

    This looks like a strong candidate for binary search. However, we can limit the number of searches needed by checking the max and min of the rows.

    //go the shortest way
    if (numrows > numcols){
    for(i=0; i target || mat[numrows-1][i] < target) continue;
    do binary search on current column;
    } else{
    for(i=0; i target || mat[i][numcols-1] < target) continue;
    do binary search on current column;
    }
    }

  2. Abdullah

    Said on May 12, 2008 :

    My solution would be preparing a hash table whose keys are unique items of this matrix and values are lists of points that keeps the items’ positions in the matrix. Hash entries would look like below :
    KEY VALUES
    [5] (1,3), (2,2)
    [8] (1,5), (2,4), (3,2), (4,1)

    Each time you seek an item in the hash table you find the matrix bins in which the item stays.

    If you do not allow us to define another data holder class, most speedy way would be binary searching the item in the rows from up to down.
    Each time you search a row, you keep the nearest bigger item’s row index at hand, and your upper limit for the next row to binary search becomes this index. This way the number of items you have to look at each row decreases by you go down.

  3. N. Terviewee

    Said on May 12, 2008 :

    If you presented this problem in an interview and made me an offer, I’d turn you down.

    If the object of creating the matrix in the first place is efficient storage, you’ve already failed by storing copies of the same item (5, 9, 11, etc.) in multiple cells. That creates ambiguity in that you now have no idea whether the 9 you’ve found is the “right” one. In fact, the sample you provide has four paths to find the number 9. Two reach the same cell along different paths which have the same length; the other two reach two different cells on same-length paths.

    That aside, I do know the solution to the problem.

    – N.T.

  4. Amit

    Said on May 12, 2008 :

    Hi

    First of all let me say that This kind of attitude won’t you get many job offers…
    Second, if you don’t like it you don’t have to answer it. And Third, according to what you wrote i doubt you have the correct answer.

    Amit

  5. N. Terviewee

    Said on May 12, 2008 :

    Ah, ye of little faith…

    That kind of attitude toward criticism won’t get you too many hires, at least not if you’re looking for top-quality people. I’ve had interviewers tell me post-offer that my criticism of their problems contributed to their desire to hire me. Having close to 30 years of writing software under my belt does have its advantages.

    Anyway, since you’ve asked me to put my money where my mouth is, I will:

    I’ll go on the assumption that finding any instance of a value is considered a correct outcome.

    1. Begin in the upper-left corner.

    2. If the value in the cell equals the search value, return success.

    3. If there are neither cells to the right or below, return failure (not found).

    4. Examine the cells to the right and below.

    Treating a missing cell’s value as the smallest possible value for your numeric type (or, better yet, NaN if that’s supported):

    5. If neither cell’s value is less than or equal to the search value, return failure (not found).

    5. Move to the cell which has a greater value but is not greater than the search value.

    6. Go back to step 2.

    You get bonus points if you can tell me why step 2 occurs where it does instead of after step 5.

    –N.T.

  6. John S.

    Said on May 12, 2008 :

    How are we to handle the situation of multiple entries? Which is the correct one?

  7. N. Terviewee

    Said on May 12, 2008 :

    Corrections:

    The last two steps should be numbered 6 and 7.

    My final comment should read “You get bonus points if you can tell me why step 2 occurs where it
    does instead of after step 6.”

    –N.T.

  8. Zeus

    Said on May 12, 2008 :

    I’m taking the question to imply that I’m asked to find value x’s position(s) within the matrix, hope I’ve not failed at the first hurdle of question comprehension!

    Given they’re sorted, I think I’d probably go with something that uses the 0th & Mth column, and the 0th and Nth row to see if the value you’re looking for is bound within those limits…

    Then only iterating through the whole row/column if the value is between the two.

    Must be noted though, I’m a fairly new programmer and am not really familiar with the efficiencies of matrices! :) (In fact this is probably a rather crude method. I look forward to seeing the answers.)

  9. Amit

    Said on May 12, 2008 :

    In case of multiple entries, finding any one of them will be OK.
    to make it simpler, you can assume that if a number appears, it appears only once.

    Amit

  10. beefarino

    Said on May 12, 2008 :

    What constitutes “finding an item” in the matrix? Determining if the matrix contains the number at all, listing {m,n} for each occurrence, etc?

    Please elaborate.

  11. Shahar Y

    Said on May 12, 2008 :

    Hi beefarino,

    Finding an item means giving its position in the matrix. In case of multiple entries, provide the position of the first occurrence you found. As Amit wrote in his comment, You can assume that if a number appears, it appears only once (to make it simpler).

  12. Ian Suttle

    Said on May 12, 2008 :

    Can you provide a sample question for locating an item?

  13. Kimmen

    Said on May 12, 2008 :

    Maybe the matrix holds ununique items?

  14. Shahar Y

    Said on May 12, 2008 :

    Ian Suttle –
    Sampe question: is 19 exist in the matrix? if it does provide its location.
    Is this what you ment?

    Kimmen-
    As alredy written in previous comments: if ununique items exist, finding one of them is fine. The given matrix is just an example, you can draw your own matrix (sorted rows, sorted columns) which contain only unique items.

  15. Zeus

    Said on May 12, 2008 :

    Apologies if you get this comment twice, I made one earlier but it seems to have disappeared!

    I would do something along the lines of using the 0th and Mth row and 0th and Nth column values to determine whether the required value was within that row/column, then only iterate through the row if the required value was within that bound…

    Given the comments, the iteration would stop at the first instance of the value being found.

    I’ve not been programming long, so this is likely a crude solution :) I look forward to seeing other more technical answers!

  16. commenter

    Said on May 12, 2008 :

    Outline of solution (I think?!) using recursive search. I have no idea if this is the fastest search. I would _guess_ that the efficiency is O(logN) or something like that?:

    Given a search value n and grid g, you could do this:

    Work out the coordinates of the cell in the ‘centre’ of g (rounding down, when the width or height is an even number, say). Call this coordinate c

    If grid[c] == n:
    return c.

    If grid[c] n:
    {
    Search the grid with bottomright corner being the cell above C, and topleft being the topleft of g. If it’s found, return the coord.

    Search the grid with topright corner being the cell to the left of C, and bottomleft being the bottomleft of g. If it’s found, return the coord.
    }

    When a sub-grid is zero dimension, obviously don’t search it.

    When the grid is 1×1, don’t search the non-existent sub-grids.

  17. Rob L

    Said on May 12, 2008 :

    Seems pretty simple for a small matrix (maybe I’m missing something), but here’s my first glance psuedo code anyway;

    For each row in matrix (first to last):
    If last column value numberToFind And NOT first column Then skip to next row
    Else If value > numberToFind And IS first column Then give up (number isn’t in the matrix)

  18. David

    Said on May 12, 2008 :

    An immediate solution is the following:

    WLOG, assume that the rows are longer than the columns. Then, iterate through the rows, and do a binary search on each of them for the number. This should take O(numrows * log(numcols)).

    As for a better solution, I’m playing around with crawling down the diagonal entries (by diagonal, I mean that, if the matrix were rectangular, we just start at (0,0) and increment both indices by 1) [binarily] to find the first entry that’s greater than or equal to our number. If the indices for this entry are (a,b), then we know that the rectangular regions with diagonal vertices at (0,0)-(a-1,b-2) and (a,b)-(numcols, numrows) do not contain our number. We can then recurse on the two remaining rectangular regions. The problem with this is, I’m not sure that this solution is necessarily better than the first one.

    A third solution- and this one’s actually efficient!
    Call the number that we’re looking for “a”.
    (if we find “a” at any point in this, terminate)
    Start from the bottom left corner. Walk up the column until we get to the smallest number greater than “a”. Let’s say that this entry is of index (0, s). Then, move to the next column, at entry (1, s), and repeat the procedure.

    Because the entry at (1,s) is greater than the entry at (0, s), we have the invariant that every time we switch columns, the entry that we are at is greater than a. We end when we reach a border or the rectangle, and perform a binary search on the remaining list of numbers.

    This way of traversing the matrix is just a path in which we can only go up or to the right. So, the path length is O(numrows+numcols), which is also the running time of this procedure.

  19. Kimmen

    Said on May 12, 2008 :

    Shahar Y:
    hehe.. I know. I didn’t refresh the page before posting. I posted after I had a talk with my colleague about other stuff, which was a bit foolish of me.

  20. David

    Said on May 12, 2008 :

    Sorry- I forgot to mention that if in the first column, the last entry is less than “a”, we just walk right to the next column. So we just walk right and up until we find a.

  21. Catweazle

    Said on May 12, 2008 :

    Start at the top-left, working down diagonally to the right. If the target number is less than the number in the current cell but greater than the number in the previous cell, then search up the current column until reaching a number less than the target; similarly search back along the current row. When reaching the “bottom” of the diagonal line (bottom row or rightmost column), just search the remaining columns or rows respectively.
    O(sqrt(mXn))

  22. JT

    Said on May 12, 2008 :

    I could be way off the mark here with regards to runtime complexity, as I don’t have a lot of experience computing it, but here is my solution (in PHP) which runs in (i think) O(max(m,n)).

    <?php

    $data = array(
    array(1,4,7,8,9,11),
    array(2,5,8,10,11,12),
    array(5,6,9,12,14,15),
    array(7,8,12,15,17,20),
    array(8,9,17,18,19,22) );

    function check($x1,$y1, $x2, $y2, $v) {
    global $data, $i;
    $i++;
    $xx1 = $x1 + (bool)($data[$x1][$y2] $v);
    $yy1 = $y1 + (bool)($data[$x2][$y1] $v);

    if ($xx2 < $xx1 || $yy2 < $yy1 )
    return “Number not found ($i iterations)”;
    if ($x2 == $xx2 && $y1 == $yy1 )
    return “Found $v at ($x2,$y1) ($i iterations)”;
    if ($x1 == $xx1 && $y2 == $yy2 )
    return “Found $v at ($x1,$y2) ($i iterations)”;
    return check($xx1,$yy1,$xx2,$yy2,$v);
    }
    function locate($v) {
    global $data, $i;
    $i = 0;
    echo check(0,0,count($data)-1,count($data[0])-1,$v).”;
    }

    for ($j=0;$j

  23. Daniel Gary

    Said on May 12, 2008 :

    Because the end of each column/row represents the maximum value for that column/row, and the first represents the minimum value for that column/row, you can create a bounding box to limit your search area.

    Solution:

    findPosition(int p)
    {
    minX = 0;
    minY = 0;
    maxX = 0;
    maxY = 0;
    for(i=0;i<m;i++)
    {
    if(matrix[i,0] <= p maxX)
    maxX = i;
    }
    else
    if(maxX)
    i=m;
    }
    for(i=0;i<n;i++)
    {
    if(matrix[0,i] <= p maxY)
    maxY = i;
    }
    else
    {
    if(maxY)
    i=n;
    }
    }

    for(x=minX;x<maxX;x++)
    {
    for(y=minY;y<maxY;y++)
    {
    if(matrix[x,y] == p)
    return {x,y};
    }
    }
    return false;
    }

  24. Niki

    Said on May 12, 2008 :

    Just a little nitpicking on the solution to the previous problem (reversing bytes): I think your answer is not optimal, at least not for every machine. I’ve just implemented a version using SIMD/shift operations, and it’s almost twice as fast as the LUT version (LUT: 0.8 ms, SIMD: 0.5 ms). However, I don’t think there’s any way of knowing this without actually implementing both versions. Results might even be different on different machines. All in all, not a good interview question, unless you give the interviewee a few hours time to find the answer.

    If anyone told me in an interview “X is the optimal solution”, I probably wouldn’t hire him to implement performance-critical code: He can’t know if X really is optimal, and if he thinks it is, he probably wouldn’t bother to properly profile his code later on, because he “knows” it’s optimal.

  25. alvins

    Said on May 13, 2008 :

    If you are trying to find y, Loop across coords (x,x) where x = y. If val(x,x) = y, you have found it. Otherwise check coords (z,x) and (x,z) where z < x for match. Continue loop above.

  26. Tristan

    Said on May 13, 2008 :

    Hi,

    assuming we stop at correct comparison.
    1)start in top right corner
    2)compare target with current,
    3)compare target with down 1, compare with left 1.
    4)if target greater than down move down,else move left.
    5)goto 3)

    this solution has a running time of O(m+n)

    by taking advantage of the fact that to the right and downwards are numerically greater than the current value we can quickly partition the matrix into three segments. Greater(right and down), Lesser (left and up), and the relevant portion(left and down). Since we start in top right corner the fourth partition (right and up) is empty to start and is not useful in our discussion as it is filled with discarded entries.

    If the target is greater numerically then we can eliminate the target row, so we move down the column. if the target is numerically less than we can eliminate the current column so we focus on the row.

  27. Anton Irinev

    Said on May 13, 2008 :

    on each step we may exclude either bottom row or right column (similarly, we exclude top row or left column), so the complexity is O(n + m)

    int i1 = 0, i2 = matrix.GetUpperBound(0); // bottom and top rows
    int j1 = 0, j2 = matrix.GetUpperBound(1); // left and right columns
    string answer = null;

    while (i1 <= i2 && j1 <= j2) {
    if (matrix[i1, j1] == requaredValue) answer = i1 + “, ” + j1; else
    if (matrix[i1, j2] == requaredValue) answer = i1 + “, ” + j2; else
    if (matrix[i2, j1] == requaredValue) answer = i2 + “, ” + j1; else
    if (matrix[i2, j2] == requaredValue) answer = i2 + “, ” + j2;

    if (answer != null) {
    System.Console.WriteLine(answer);
    break;
    }

    if (matrix[i2, j1] requaredValue) j2–; else i1++;
    }

  28. Adam

    Said on May 13, 2008 :

    My solution would be something like this:

    X – the number we search for

    1. Check witch matrix dimension is smaller. The smaller dimension will be called number of rows from now on.

    2. Perform a binary search in the first column, to find an index of the largest number = X. If it is equal to X then the solution is found, otherwise – there is also no X in the matrix. The index found is b.

    4. Perform a binary search for X in every row between a and b (inclusive-inclusive).

  29. Kevin

    Said on May 13, 2008 :

    I think something like this would be optimal (pseudocode):

    find_value(array a, int value)
    {
    if a[0][0] > value || a[a.length-1][a.width-1] a.width
    a1 = find_value(a[0..(a.length/2)][0..(a.width], value)
    a2 = find_value(a[(a.length/2+1)..(a.length)][0..(a.width)], value)
    if a1 != NULL
    return {a1[0], a1[1]};
    else if a2 != NULL
    return {a2[0]+(a.length/2), a2[1]};
    else
    return NULL;
    else
    a1 = find_value(a[0..(a.length)][0..(a.width/2)], value)
    a2 = find_value(a[0..(a.length)][(a.width/2+1)..(a.width)], value)
    if a1 != NULL
    return {a1[0], a1[1]};
    else if a2 != NULL
    return {a2[0]+(a.length/2), a2[1]};
    else
    return NULL;
    }

    should be O(lg n) because in every 2 cuts, 1 will be pruned by tree

  30. Kimmen

    Said on May 13, 2008 :

    The solution:
    I won’t provide any code, because my solution isn’t very pretty coded ;P. First off, I created a method, FindValue(value, region) which returns duple. The region argument is a region in the matrix. The FindValue is called recursively.

    FindValue works by using BinarySearch on each edge (row/column) of the given region. Here I used .net’s BinarySearch which return a negative value if not found. The negative value can be used to get the index of the closest largest value of the value we wanted to find. If the value was not found on any of the edges, you can create a new region to search in using the results from the BinarySearches.

    The complexity of a binary search is O(log n), so each call to FindValue would be 2*O(log N) + 2*O(log M) => O(log (N*M)). As the each call to FindValue divides the search area (the region gets smaller), which means O(log n), I would say the complexity is something like O(log log(n*m)).

  31. Asim

    Said on May 13, 2008 :

    @Niki:

    Oddly enough I’ve started reading a textbook on algorithms
    . This page will be of interest to you:

    http://tinyurl.com/6hchrp

    By benchmarking your answer on a particular architecture/system, in one sense you are clearly correct. However, interview questions such as these are posed from a computer science perspective. Referring to the link above, after making an assumption that the ‘RAM Model of Computation’ is valid, then the LUT is a clear winner over any arithmetic approach.

    Remember Dijkstra’s words: ‘computers are to computer science as telescopes are to astronomy’.

  32. Edward Shen

    Said on May 13, 2008 :

    Assumptions: All entries unique, standard desktop computer used, and probably some more I am forgetting to mention atm.

    Two solutions depending on how often the values change.

    First solution is when the matrix doesn’t change much. A lookup table could be created, making the solution O(log(mn)). This of course takes time, so its not practical if the table constantly changes in a way that breaks the lookup table.

    If I am restricted to search operations only (if complexity includes time to build look up table), I can come up with a very rudimentary algorithm which finds iterates through the m or n (whichever is shorter), and binary searches each row/column until an answer is found. This gives a complexity of m log n (where m is the shorter of the two; also log is base 2).

    While trying to optimize, I came up with the following algorithm:

    Do a binary search for the number on all diagonal matrix indices’ values ([0,0] to [m,m]).
    If you hit the number you’re done, if not, u effectively eliminate all numbers above and to the left of the number smaller than it along the diagonal, and all numbers below and to the right of the bottom. Say the number we are looking for is 6, then the above operation eliminates roughly half of the entries as follows:

    O = (open to inspection)
    X = (eliminated)

    X X X X O O O O
    X X X X O O O O
    X X X X O O O O
    X X X 5 O O O O
    O O O O 7 X X X
    O O O O X X X X
    O O O O X X X X
    O O O O X X X X

    This operation’s complexity is log m since it is binary search.

    Now you’re left with half as many candidate entries. The worst case scenario has a m/2 diagonal for both matrices.

    We then perform the same operation on those two halves.
    Each of these two operations have a complexity of log(m/2) worst case. Continue splitting until the number is found or compare the bottom left and upper right values if we end up in a 2×2 matrix. When n is longer than m (assume m is always the sorter side), we would need to add log(n) as well to binary search extra entries.

    Because the worst case scenario big O notation is hard to write out with this site’s char set, I’m just going to roughly calculate the general complexity of this algorithm to be (log m)^2 + log(n). This estimate will slowly move away from the real complexity as m grows large… I’ll update later if it is required…

  33. OJ

    Said on May 13, 2008 :

    Niki, why did you post that comment here instead of where it belongs?

    This is an interesting little problem. I shall have a dabble at a solution when I get home from work.

  34. Marcos Silva Pereira

    Said on May 14, 2008 :

    A quite simple to solve.

    1. Go to the last column at the first row;
    2. If the value is greater than the searched number, go left, if it is smaller, go down;
    3. Do it until you could walk in the matrix or find the searched element.

    Kind Regards

  35. Eugene Efimochkin

    Said on May 14, 2008 :

    Okay, time to go to lunch, so here’s quick:

    Let’s name the item we search with Z.

    We have both rows and columns sorted. Hence we use a binary search to find the row where the first element is less or equal to Z, and the last one is greater or equal to Z. Then we use a binary search on that row to find the position of Z exactly.

    Isn’t that fast enough? Can’t tell anything about complexity right now, so I definitely failed this interview.

  36. Sol_HSA

    Said on May 14, 2008 :

    I agree, this is not a very good interview question.

    However.

    If the grid is small enough, I’d probably just brute-force it. For sufficiently large grids the answer gets more complicated..

    If the grid is accessed only rarely, we get to some kind of nifty 2-dimensional binary search which might be interesting to work out; if there’s several accesses to the same data, I’d probably pre-process it to a linear list which is faster to seek.

  37. benishor

    Said on May 14, 2008 :

    That’s how I’d do it : http://hq.scene.ro/matrix_search.txt

  38. trzn

    Said on May 14, 2008 :

    Asim, why should we assume running code on a scientific non-existing imaginary computer?

    Niki is right. On a typical modern environment (including desktop and mobile devices) LUT is not the fastest solution.

  39. Shahar Y

    Said on May 14, 2008 :

    Niki

    I profiled those two options and got different results – LUT is better. Can you please ellaborate more about your tested code and how did you get those numbers? How did you implement the LUT? Did you measure only the first access to the LUT (the first access is really slow, but all the others are done from the cache)? How did you implement the SIMD/shift operations?

  40. Jonathan Gilbert

    Said on May 14, 2008 :

    // This solution is O(m lg n), where n is the longer dimension.

    #define DEBUG

    using System;

    class Challenge3
    {
    static void Main()
    {
    int[][] matrix = new int[][]
    {
    new int[] { 1, 4, 7, 8, 9, 11 },
    new int[] { 2, 5, 8, 10, 11, 12 },
    new int[] { 5, 6, 9, 12, 14, 15 },
    new int[] { 7, 8, 12, 15, 17, 20 },
    new int[] { 8, 9, 17, 18, 19, 22 },
    };

    for (int y=0; y < matrix.Length; y++)
    {
    for (int x=0; x rows);

    int linear_dimension = transpose ? rows : cols;
    int logarithmic_dimension = transpose ? cols : rows;

    for (int linear = 0; linear < linear_dimension; linear++)
    {
    int index = 0;
    int count = logarithmic_dimension;

    if (get(matrix, count – 1, linear, transpose) value)
    {
    #if DEBUG
    Console.WriteLine(“Bailing at {0} {1}”, transpose ? “row” : “column”, linear);
    #endif
    return false;
    }

    #if DEBUG
    Console.WriteLine(“Doing binary search of {0} {1}”, transpose ? “row” : “column”, linear);
    #endif

    while (count > 0)
    {
    int middle = index + count / 2;

    #if DEBUG
    Console.WriteLine(” First: {0} Middle: {1} Last: {2} Value: {3} {4}”, index, middle, index + count – 1, get(matrix, middle, linear, transpose), value);
    #endif

    int comparison = value – get(matrix, middle, linear, transpose);

    if (comparison == 0)
    {
    #if DEBUG
    Console.WriteLine(“Found it!”);
    #endif
    x = transpose ? middle : linear;
    y = transpose ? linear : middle;
    return true;
    }

    if (comparison > 0)
    {
    count = (count + 1) / 2 – 1;
    index = middle + 1;
    }
    else
    count /= 2;
    }
    }

    return false;
    }

    static int get(int[][] matrix, int row, int col, bool transpose)
    {
    if (transpose)
    return matrix[col][row];
    else
    return matrix[row][col];
    }
    }

  41. Jonathan Gilbert

    Said on May 14, 2008 :

    Instead of posting a fix for the blog mangling of my previous post, I’ve simply put the code up at the URL in the “Website” field of this post.

  42. bizonul

    Said on May 14, 2008 :

    The solution is an extension of binary search:
    private Point GetPosition(int value, int[,] matrix, int topLeftRow, int topLeftCol, int bottomRightRow, int bottomRightCol)
    {
    Point retPos;
    if (topLeftCol > bottomRightCol || topLeftRow > bottomRightRow)return new Point(-1, -1);
    if (topLeftCol == bottomRightCol && topLeftRow == bottomRightRow)
    {
    if (matrix[topLeftRow, topLeftCol] == value) return new Point(topLeftRow, topLeftCol);
    else
    {
    return new Point(-1, -1);
    }
    }
    else
    {
    retPos =
    GetPosition(value, matrix, topLeftRow, topLeftCol, (topLeftRow + bottomRightRow)/2,
    (topLeftCol + bottomRightCol)/2);
    if (retPos.X > -1 && retPos.Y > -1) return retPos;

    retPos =
    GetPosition(value, matrix, (topLeftRow + bottomRightRow)/2 + 1, topLeftCol, bottomRightRow,
    (topLeftCol + bottomRightCol)/2);
    if (retPos.X > -1 && retPos.Y > -1) return retPos;

    retPos =
    GetPosition(value, matrix, topLeftRow, (topLeftCol + bottomRightCol)/2 + 1,
    (topLeftRow + bottomRightRow)/2,
    bottomRightCol);
    if (retPos.X > -1 && retPos.Y > -1) return retPos;

    retPos =
    GetPosition(value, matrix, (topLeftRow + bottomRightRow)/2 + 1, (topLeftCol + bottomRightCol)/2 + 1,
    bottomRightRow, bottomRightCol);
    return retPos;
    }
    }

  43. leppie

    Said on May 14, 2008 :

    Off the top of my head:

    Choose the smaller of n and m for linear search, then the other can be done doing a binary search.

    So given m is smaller, complexity will be O(m log n).

  44. Trung Dinh

    Said on May 14, 2008 :

    A few approaches come to mind:

    A. Do binary search of the rows. O(m log n)
    B. Do binary search of the columns. O(n log m)
    C. If (m < n) do A else do B. In cases where n <> m, this would be faster than either A or B.
    D. If you do a lot of lookup of the same matrix, it may
    be worthwhile to transform the matrix into a linear
    arrays of m x n values and indices.

    values[m x n], x[m x n], y[m x n]

    This could be done using merge sort O(N log N) where
    N = m x n. Subsequent searchs would be O(log N)
    using binary search.

  45. drax

    Said on May 14, 2008 :

    No code from me – but I would guess some sort of recursive traversal algorithm – first you need to determine if its col or row precendence (either should be just as optimal over a large search set)
    find the col entry and then the corrsponding row entry (ir vice versa) – as i said no code tho – I’m too old for that kind of thinking now :-)

  46. Matt Howells

    Said on May 14, 2008 :

    Use a two-dimensional binary search.

    Look at the central element of the matrix. If its equal to the object you are searching for, output the indices (i,j). If it is greater than the element you are searching for, split the matrix into two matrices; one containing all elements of the matrix less than the element in the i-dimension, and the other containing all elements less than the element in the j-direction and greater than or equal to the element in the y-direction. If the element is less than the object you are searching for, split the matrix into the two equivalent higher matrices.
    Recurse (or use an equivalent loop).

  47. Asim

    Said on May 14, 2008 :

    @trzn

    Without starting a flame thread or becoming a troll, let me just say that any solution is based upon assumptions. My point was that, when it comes to interview questions, one should realise that the interviewer is usually coming from a CS angle and hence doesn’t really care about computers; algorithms are their pride and joy.

    Is this “realistic”? Is this the “best” approach? Is this “optimal”? It depends on your circumstances. Assumptions allow one to compromise between ease of understanding/implementation and efficiency.

    You answered your own question by prefixing your argument with “On a typical modern environment”, and hence you made an assumption, which is inevitable.

    Hope I didn’t come across as facetious. Cheers.

  48. Adam B.

    Said on May 15, 2008 :

    Best-case scenario, two binary searches will find the element. Worst-case scenario will take four. My answer’s at http://programmersthoughts.blogspot.com/2008/05/dev102com-programming-challenge-3.html

  49. Jonas Christensen

    Said on May 20, 2008 :

    There are a qicker way to reverse the bits than using a look up table.

    This solution only need 3 operations. I cant take full credits :) Rich Schroeppel came up with this in 1972.

    unsigned char pixel;

    pixel = (pixel * 0x0202020202ULL & 0x010884422010ULL) % 0x03FFUL;

    Regards
    Jonas Christensen

  50. Shahar Y

    Said on May 20, 2008 :

    Hi Jonas Christensen,

    Your solution is good but works best on 64bit machine (won’t be as efficient in 32bit machines)- http://graphics.stanford.edu/~seander/bithacks.html#ReverseByteWith64BitsDiv

    Besides, how is it faster than reading from the cache?

  51. Jonas Christensen

    Said on May 20, 2008 :

    You are right it wont be faster, guess I was abit to fast posting.

    But its a nice trick by Rich.

  52. Vivek Kanala

    Said on May 20, 2008 :

    Did any one tried searching diagonally across the matrix?

  53. benishor

    Said on May 20, 2008 :

    I did here : http://hq.scene.ro/matrix_search.txt
    However, it’s not the optimal solution although it may sometimes provide faster answers depending on the dataset.

  54. Ates Goral

    Said on July 21, 2008 :

    If speed is a concern, don’t restrict the look-up table to a mere 256 bytes. Using a 16-bit look-up table will only take up 2^17 = 128K bytes. That’s nothing when you consider the amount of RAM a typical computer has in the early 21st century :)

Post a Comment