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;

}

{

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;

}

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.

Hi Harry,

ReplyDeleteThanks 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!

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

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

DeleteCorrect 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.

Deleteyou 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)

Deleteso the complexity is somewhere between O(n) and O(lg n)

Hi Harry!

ReplyDeleteDid you figure out about the time complexity?

Hi Harry,

DeleteIn 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

List of books to be referred for placement training preparation?

ReplyDeleteplacement training center in chennai

Why not start at the middle of the array?

ReplyDeleteHello 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.

ReplyDeleteInterview Tips

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

ReplyDeleteValid reasons for leaving a job?

ReplyDeletepart-time jobs

Awesome information, brain exercising post..

ReplyDeleteMoney Maker Research

ReplyDeleteGreat article Lot's of information to Read... Great Man Keep Posting and update to People..Thanks

free online tests

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

ReplyDeleteWord ending with letter..

csharp code examples help you about c#

ReplyDeleteGreat 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.

ReplyDeleteStatic code testing

Nice post http://www.selfcarinsurance.com

ReplyDeleteThe 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).

ReplyDeleteHi There,

ReplyDeleteI 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.

Szia,

ReplyDeleteIn 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

Hi Buddie,

ReplyDeleteWhat 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