Wednesday, September 23, 2015

No. 58 - Search in Adjacent Numbers


Question: Given an array where two neighboring elements are adjacent (in absolute difference 1), can you write an algorithm to search an element in the array and return its position? If the element appears multiple times, please return the first occurrence.

For example, if given the array {4, 5, 6, 5, 6, 7, 8, 9, 10, 9} and an element 9, the element appears twice in the array, and the first occurrence is at position 7.

Analysis: The most simple and straightforward solution is to traverse the array and compare elements one by one. This strategy works for every array, and it does not utilize the property of the array where two neighboring elements are in absolute difference 1.

Let's try to search the first 9 from the array {4, 5, 6, 5, 6, 7, 8, 9, 10, 9}. Firstly we are at position 0 where the element 4 is. The difference between 9 and 4 is 5, so we move to the position 5. Why? Because the absolute difference between two neighboring elements is 1. If the numbers in the array is increasingly sorted, the element at position 5 is 9. If some elements decrease, 9 should sit on the right of position 5. Therefore, 5 is the leftmost possible position of the element 9.

It's 7 at position 5. The difference between 7 and 9 is 2, so we move to right by distance 2 to the position 7, where the first occurrence of 9 has been found.

We can summarize the solution: We begin from the first element of the element, and compare it with the given number. If the absolute difference is n, move to the right by distance n. Then we compare the current visited element. Repeat until the given element is found, or the position is beyond the length of the array when the given element is not available.

The solution can be implemented in C/C++ as below:

int findFirst(int* nums, int length, int target)
{
  
if (nums == nullptr || length <= 0)
      return -1;

  
int index = 0;
  
while (index < length && nums[index] != target)
   {
     
int delta = target - nums[index];
      index += abs(delta);
   }

  
if (index < length)
      return index;

  
return -1;
}

The source code with unit test cases is shared at http://ideone.com/zuwjui.

More coding interview questions are discussed in my book< Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this article in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact the author via zhedahht@gmail.com . Thanks.

16 comments:

  1. Hi Harry,

    Thanks for sharing this interesting questions with super clean code. Actually I have two comments about this question:

    1. It seems that the example is incorrect since element 8 only appears once.
    2. I'm interested in the time complexity of the solution.

    Thanks again for this awesome post!

    ReplyDelete
    Replies
    1. Thanks for your comment. It's a typo. It should be element 9 which appears twice.

      Delete
    2. I'm also curious about the time complexity, but have not figured out. Can anyone help?

      Delete
    3. Correct me if I'm wrong, if we have N numbers and the target number is T and the first number is F, then in the worst case, we may need N / |T - F| steps to reach it.

      Delete
    4. you can consider o(n) as an upper bound since worst case you need to check all the elements. best case will be if the array is sorted in reverse natural order eg 10, 9, 8, 7, 6, 5, 4, 3, 2, 1. in that case if you're looking for 12, you will make 2, 4, 8... jumps so basically it's O(lg n)
      so the complexity is somewhere between O(n) and O(lg n)

      Delete
  2. Hi Harry!

    Did you figure out about the time complexity?

    ReplyDelete
  3. List of books to be referred for placement training preparation?
    placement training center in chennai

    ReplyDelete
  4. Why not start at the middle of the array?

    ReplyDelete
  5. Hello my friend! I would like to tell you that this write-up is awesome, great written and include almost all important info. I recently came to know about http:www.yesiamhired.com, their Interview Tips are very effective.
    Interview Tips

    ReplyDelete
  6. Integrated you software data at the best way of informatica system please call us on :- many new informatica interview questions references available online but this data warehouse interview questions one which is mentioned here is best in all possible ways. Always emphasize in getting this informatica questions

    ReplyDelete

  7. Great article Lot's of information to Read... Great Man Keep Posting and update to People..Thanks
    free online tests

    ReplyDelete
  8. Great information, containing all information and also has a great impact on the new technology. Its very helpful for me.

    Word ending with letter..

    ReplyDelete
  9. Great information, containing all information and also has a great impact on the new technology. Its very helpful for me. Integrated you software data at the best way of informatica system.would like to tell you that this write-up is awesome, great written and include almost all important info.

    Static code testing

    ReplyDelete