posted 4 years ago

I was reading the programming questions chapter of a book (something like How to Get Hired at Google). Every so often people complain my coding questions are too hard (they aren't) so I wanted to see what was in the book.

One question was to find the lowest number in a "sorted rotated array". The example is the numbers might appear as 3 4 5 6 7 1 2. You need to find "1". Now obviously a linear search would find it. Really a modified linear search as you can stop as soon as you get to the number 1 since it is lower than it's predecessor. You'd only have to go through the whole array if the lowest number was element 0. I thought about using something binary search related but couldn't think of anything that wasn't overly complex.

The author says you can use binary search. She says "If you compare the first and middle elements (3 and 6), you know that the range is still increasing." I don't see how you know that. In the provided example, that is true. But what if the numbers were 3 1 2 6 7 8? The first and middle elements are the same, but the answer isn't "go right."

Am I missing something?

One question was to find the lowest number in a "sorted rotated array". The example is the numbers might appear as 3 4 5 6 7 1 2. You need to find "1". Now obviously a linear search would find it. Really a modified linear search as you can stop as soon as you get to the number 1 since it is lower than it's predecessor. You'd only have to go through the whole array if the lowest number was element 0. I thought about using something binary search related but couldn't think of anything that wasn't overly complex.

The author says you can use binary search. She says "If you compare the first and middle elements (3 and 6), you know that the range is still increasing." I don't see how you know that. In the provided example, that is true. But what if the numbers were 3 1 2 6 7 8? The first and middle elements are the same, but the answer isn't "go right."

Am I missing something?

[OCA 8 book] [OCP 8 book] [Practice tests book] [Blog] [JavaRanch FAQ] [How To Ask Questions] [Book Promos]

Other Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, TOGAF part 1 and part 2

posted 4 years ago

Oh, right. Tricky! I can longer come up with a counter example that does meet the conditions so the answer makes sense now.

Bear Bibeault wrote:Jeanne Boyarsky wrote:But what if the numbers were 3 1 2 6 7 8?

That doesn't meet the criteria for the array.

Oh, right. Tricky! I can longer come up with a counter example that does meet the conditions so the answer makes sense now.

Other Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, TOGAF part 1 and part 2

Piet Souris

Rancher

Posts: 1979

67

posted 4 years ago

A quicky, because the champions legue final between Bayern and Dortmund is about to begin:

you can find the smallest number of a 'sorted rotated array' even faster still: take element 0.

Now, for a 'rotated sorted array' things would be a little different... ;)) (can't get my smilies to work)

Greetings,

Piet

you can find the smallest number of a 'sorted rotated array' even faster still: take element 0.

Now, for a 'rotated sorted array' things would be a little different... ;)) (can't get my smilies to work)

Greetings,

Piet

posted 4 years ago

The "rotation" splits the array into two halves, with the second half starting at the position of the least number in the array. Assuming there are no duplicates in the array, all numbers in the second half must be lower than all numbers in the first half (instead of rotation, think about it as swapping of the two halves). Therefore, if you take any two indexes and find that the first number is bigger than the second one, the boundary must be between them. This permits the binary search, of course. Lowest number is just to the right of the boundary.

In my opinion, this is a math quiz, not a programming question. Just writing a plain old binary search would be sort of a programming question, I'd say. I'm sure I wouldn't get it right if I had just a pencil and paper, though. I'm pretty grateful for

In my opinion, this is a math quiz, not a programming question. Just writing a plain old binary search would be sort of a programming question, I'd say. I'm sure I wouldn't get it right if I had just a pencil and paper, though. I'm pretty grateful for

`Arrays.binarySearch`