AceTheInterview
Jobs in Pune | Work better in teams | Socialize with friends | Submit Q&A | Tell a friend
Search site for 

Top 100 Interview Questions & Answers in a convenient and easy to read book!

“I bought this guide a few days ago to prepare for my interview with Oracle. Many of the questions they asked me were from this guide. I found this book absolutely great!”

– Ravi, California

Read more comments...

Interview Questions And Answers RSS Feed

Answer »

  1. Submitted By: Fritz Stugren — May 7, 2008
    +4 votes
      + -

    The optimal solution has a M+N cost. I’ll describe the algorithm, since the comment editor may swallow the code if I don’t edit it properly:

    - You have to start from the [M-1][0] or the [0][N-1] corners. Because of the distribution of values in the matrix, when you start form one of those corners, the value you look for can be in only one direction (for [M-1][0], all values to the right on the row are larger, and all values up on the column are smaller.) If you started from [0][0] all values to the right on the row and below on the column are larger so the value may be anywhere. Same for [M][N], all values on the row and column are smaller.

    - Indexes are i for row and j for column
    - Start from [M-1][0] (i=M-1, j=0).
    - If the search value is larger than array[i][j], move right on the row (j++)
    - If the search value is smaller than array[i][j] move up on the column (i–)
    - otherwise you found it, exit the loop
    - the loop goes on as long as the value is not found and both i and j are larger than or equal to zero and smaller than their max limits (M and N, respectively). If i or j becomes invalid, the value is not in the array.

    Small tweaks can be added to reduce the solution space even further - e.g. - if both the leftmost and the rightmost values on a row are larger than the value we search for, skip that row altogether and move to the one above it.

    Code (chances are that the snippet may be cut off… fingers crossed). Give it a try… it works

    int arr[6][5] = {
    	{1, 3, 7, 9, 11},
    	{2, 6, 8, 12,19},
    	{7, 9, 13,17,20},
    	{9, 14,15,18,30},
    	{12,16,18,22,33},
    	{31,32,36,38,39}};
    
    const int M = 6;
    const int N = 5;
    
    void search(int arr[][], int val)
    {
    	int i = M-1;
    	int j = 0;
    	bool found = false;
    
    	while(i>=0 && i<M && j>=0 && j<N && !found)
    	{
    		printf("%dn", arr[i][j]);
    		if(arr[i][j]==val)
    		{
    			printf ("found at [%d][%d]", i, j);
    			found = true;
    		}
    		else if(arr[i][j]<val)
    			j++;
    		else
    			i--;
    	}
    
    	if (!found)
    		printf ("not found");
    }
    
  2. Leave an Answer/Comment

    To prove you're a person (not a spam script), type the security text shown in the picture. Click here to regenerate some new text.
    Click to hear an audio file of the anti-spam word

Our Sponsors
Our Sponsors
Contact Us | FAQ | Sitemap | Terms of Use | Privacy Policy | Tell a Friend

Copyright © 1999-2006 Jeeve Technologies LLC. All rights reserved.