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.

34 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
    Replies
    1. Hi Harry,

      In debt to you for making my learning on the No. 58 - Search in Adjacent Numbers area so hassle-free! I lay my faith on your writings.

      I have a small mailing list program running on an EC2 instance, Windows 2016 Server. Emails are send to my SES account which a daily limit well beyond what I'm sending.

      The AWS Serverless Application Model (AWS SAM) extends AWS CloudFormation to provide a simplified way of defining the Amazon API Gateway APIs, AWS Lambda functions, and Amazon DynamoDB tables needed by your serverless application AWS Training .

      But nice Article Mate! Great Information! Keep up the good work!

      Regards,
      Kevin

      Delete
  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
  10. The time complexity is O(N). Assume the array is [4,3,4,3,4,3,4,3,...,4,3] and you are looking for 5. It is going to take you n/2 jumps whihc is O(n).

    ReplyDelete
  11. Hi There,

    I am shocked, shocked, that there is such article exist!! But I really think you did a great job highlighting some of the key No. 58 - Search in Adjacent Numbers in the entire space.

    I am a freelancer and I previously created an account using a gmail address and obtained my certification with this account. During the registration process of the APN program it needs a non gmail address so i used my professional address, how can i merge or link the certifications of my first account with the APN program?

    Super likes !!! for this amazing post. I thinks everyone should bookmark this.

    Thanks a heaps,
    Preethi.

    ReplyDelete
  12. Szia,

    In total awe…. So much respect and gratitude to you folks for pulling off such amazing blogs without missing any points on the No. 58 - Search in Adjacent Numbers. Kudos!


    Should they be allowed to create ec2 and rds instances, iam user/groups, etc? Or should system admins create the infrastructure and just provide developers access to resources after?
    AWS Training


    Very useful article, if I run into challenges along the way, I will share them here.

    Thanks a heaps,
    Radhey

    ReplyDelete
  13. Hi Buddie,


    What you’re saying is absolutely correct No. 58 - Search in Adjacent Numbers , but this isn’t the exact situation everywhere. Where most smart folk work on a project - why can’t you do this the Boss asks :).


    I have posted a few times a issue about a couple of resources in my account which can not be deleted through AWS Management Console. No answer up to now. AWS Training USA




    Thank you very much and will look for more postings from you.


    Obrigado,
    Irene Hynes

    ReplyDelete
  14. Thank you for sharing them! I hope you will continue to have similar posts to share with everyone!
    - USPS Tracking

    ReplyDelete
  15. PRBULLS - is a multi-platform media and content marketing company.
    Content marketing is the publication of material designed to promote a brand, usually through a more oblique and subtle approach than that of traditional push advertising. Content marketing is most effective when it provides the consumer with accurate and unbiased information, the publisher with additional content and the advertiser with a larger audience and ultimately, a stronger brand…
    Content Marketing Company

    ReplyDelete
  16. Coding

    Holiday Camps - Have fun with bricks while learning at the same time! Bricks 4 Kidz offers the best STEM and Coding Enrichment platform for your child. Join us now!



    Coding

    Holiday Camps - Have fun with bricks while learning at the same time! Bricks 4 Kidz offers the best STEM and Coding Enrichment platform for your child. Join us now!

    ReplyDelete
  17. content marketing for brands This was website contain many things to study, Thank you for sdharing this.

    ReplyDelete
  18. This article is a great article that I have seen in my blog career so far, it helps me a lot in Search in Adjacent Numbers, and will continue to do so in the future.

    website development company in Surat Gujarat

    ReplyDelete
  19. So is there any true magical matka of numbers that can help you to turn your fortunes around? Are there some unique combinations of numbers that you can learn? Are there some numerology rules that you should know about that can help you win big each time with guaranteed success?

    It may sound a bit odd to you but there is no such magical Satta matka of numbers or specific numbers that you can bet on for guaranteed success. Even those websites that promise you to make the winner in each round of the Indian matka are completely vague and absurd, to say the least.

    Instead, here we will try to elaborate on some more logical tips that can help you win the matka. Some of these tips may sound very simple and absurd as you know them. But the ground rules in the matka of Indian matka are the same and using some basic principles you can have more chances of success than failure.

    ReplyDelete
  20. ترفندهایی که هر خانمی باید برای ارایش صورت بداند.

    ReplyDelete