C question

[electroRF]

Hi,

I'm facing this problem which I don't manage to solve.

You got a sorted array of size N, that was shifted by unknown shifting.

i.e. instead of {1,2,3,4,5,6,7,8} it became: {6,7,8,1,2,3,4,5}.

You're given a number and need to tell if it's in the array, and in which index.

You need to do this in log(N).

How do you do that?

I thought of making a binary search, first for finding the original start of the array.

Then split it to 2 arrays, and make another binary search.

This will result in log(N).

However,

How can you find the original start of the array in this case: {2,1,2,2,2} or {2,2,2,1,2}, in log(N)?

Thank you!

 

[KeepItSimpleStupid]

In general, you can only binary search on a sorted list with non-duplicates.

What can make the search easier though is to split the list at a power of 2 index. So, if you have 5 items, use an initial list of 4 and a list of 2. When you split either list you get one element which is a LOT easier to work with than fractional indexes.

You will have to check both sides of the split for equality and handle that case separately.

 

[NorthGuy]

Since you have the array, it should've been filled earlier. This could only be done in (N). It would not be a performance decrease if you marked the minimum point while filling the array. You can then pass this information to the searching routine.

 

[misterT]

How can you find the original start of the array in this case: {2,1,2,2,2} or {2,2,2,1,2}, in log(N)?

I don't think there is a O(log(n)) solution for that kind of case. You need to traverse the array to find the smallest number (which is next to the largest number). so, O(n) is best you can do.

I do not understand why the array is being shifted? Is this a real application, or is this just some kind of school problem? Shifting array entries is time consuming and often unnecessary.

 

[electroRF]

Thanks a lot guys.

KISS and Mister T, please find my comments to yours below:

In general, you can only binary search on a sorted list with non-duplicates.

What can make the search easier though is to split the list at a power of 2 index. So, if you have 5 items, use an initial list of 4 and a list of 2. When you split either list you get one element which is a LOT easier to work with than fractional indexes.

You will have to check both sides of the split for equality and handle that case separately.

KISS

I'm not sure i followed you regarding splitting the array at a power of 2 index, and how does it help.

Say that you got this array: {2,2,2,2,2,1,2,2,2,2,2,2,2,2,2} (15 Items).

How would it help splitting it?

at which point do you stop splitting the array?

I don't think there is a O(log(n)) solution for that kind of case. You need to traverse the array to find the smallest number (which is next to the largest number). so, O(n) is best you can do.

I do not understand why the array is being shifted? Is this a real application, or is this just some kind of school problem? Shifting array entries is time consuming and often unnecessary.

T,
thats a question from intreview i found on the web.
I'm aiming to leave my Q&A job and find a position in SW development (hopefully low-level embedded programming).
So i'm practicing all sort of questions.

The question states that you CAN find a number in a sorted array that was shifted, in Log(N)

 

[misterT]

The question states that you CAN find a number in a sorted array that was shifted, in Log(N)

Was that special case {2,2,2,2,2,1,2,2,2,2,2,2,2,2,2} given in the question, or did you make it up? I think it is impossible to find the '1' in that array without traversing the array linearily. That is O(n)

 

[misterT]

I regret one interview I had.. pissed me off. You really need to be honest and say what you think.. do not try to guess what the other person wants to hear.
https://www.electro-tech-online.com/threads/strangest-job-interview-ive-had.134239/#post-1123501

 

[electroRF]

Hi T

Thanks a lot for sharing the horrible interview.
I wonder why the interviewer didn't give you a 2nd chance with another question, how can you judge a candidate by just one question, which was very unusual.

I'm looking for exactly these kind of questions, would you mind share some nice docs / pdfs with C interview questions?

Was that special case {2,2,2,2,2,1,2,2,2,2,2,2,2,2,2} given in the question, or did you make it up? I think it is impossible to find the '1' in that array without traversing the array linearily. That is O(n)

This special case was something I thought of.

If the array contains no equal items, for example looks like that (after being shifted): {4,5,6,7,8,1,2,3}

you can easily find the smallest number's index by binary search - every time you split the array to two, and continues with the one part where its first organ is bigger than its last organ (if none of the two parts fulfills it, then it means the array is already sorted and wasn't shifted).


But then I thought of this special case of having equal items in the array.

 

[misterT]

I wonder why the interviewer didn't give you a 2nd chance with another question, how can you judge a candidate by just one question, which was very unusual.

I was kind of visiting that company and this one guy thought they might have a job for me. So he got this other guy and told him to ask me some questions.. it was a total mess. I'm actually glad that I did not end up working for that company.

Anyway, I think you have that one covered. You are just over thinking and double guessing yourself. I had this one book which was full of job-interview questions and answers.. I'll try to find it.

 

[electroRF]

I was kind of visiting that company and this one guy thought they might have a job for me. So he got this other guy and told him to ask me some questions.. it was a total mess. I'm actually glad that I did not end up working for that company.

So you got into the interview without preparation?
wow, I wouldn't have the balls.

You keep applying for positions in startups?

Anyway, I think you have that one covered. You are just over thinking and double guessing yourself. I had this one book which was full of job-interview questions and answers.. I'll try to find it.

I'd love that! thanks

 

[misterT]

You keep applying for positions in startups?

No.. they keep contacting me I mostly hate what they do. Bunch of hobbyists financed by government. They have passion, but no business. Or.. only business, no passion. Aiming for stars with knee-deep in mud.

I did not find the book yet.. I do not remember if it was a book about job interviews etc, or was it just a chapter in some programming book. I'll try to find it.

 

[electroRF]

well you can refer them to me I'd love relocate to Finland (;

Don't you wanna try a start-up and see how it is?



Thanks for trying to find the book mate

 

[misterT]

Don't you wanna try a start-up and see how it is?

The one company that interviewed me was a startup company called PowerKiss http://powerkiss.de/
The technology is very simple, there is nothing to it. The reason why the company is succesfull is because of very skilled marketing people. There are no jobs for electrical engineers. And I have not ever seen their product in use anywhere. Most start-ups are just marketing ********. The ones with real technological inventions are too expensive to be called "start-ups".