2

I have to give my one of the biggest interviews next week and I am working hard for that. I have also enrolled myself for some mock interviews for that. So, coming to the problem last day I had this mock interview and I was asked this question:

Search an element in a sorted and rotated array

at first I was clueless but the interviewer asked me to break the problem at hand and then solve the smaller problem first so I decided to write binary search to find the element in the sorted array, surprisingly I was able to write the algorithm within a go since I had clear mental model of the problem at hand now I was asked to proceed and solve the given question. I thought for a second and told him that if I somehow know the peak point I can decide which direction to go to find the given element, he told me that I am on the right track and then boom I wasn't able to think properly on how to convert my logic into code, he gave me a couple of hints and it was too embarrassing for me to just sit and think.

The problem is after knowing the solution and knowing that my intuition was correct I am not sure why I failed, I need to know is there a different way of thinking of such problems to better understand the logic? Why I feel discomfort when I found a new problem on binary search although I knew and solved the original one? is there a gap in my mental modal?

Improve this question
5
  • I haven't looked at the Geeksforgeeks solution at all, but my first instinct would be to write a class or method that returns the elements from the original array unrotated or adjusts the index accordingly. It would then yield to an ordinary binary search.
    – Robert Harvey
    Dec 30, 2016 at 16:24
  • @RobertHarvey so how would you do that?
    – CodeYogi
    Dec 31, 2016 at 2:41
  • 1. Find out pivot point and divide the array in two sub-arrays. (pivot = 2) /*Index of 5*/ 2. Now call binary search for one of the two sub-arrays. (a) If element is greater than 0th element then search in left array (b) Else Search in right array (1 will go in else as 1 < 0th element(3)) 3. If element is found in selected sub-array then return index Else return -1.
    – Robert Harvey
    Dec 31, 2016 at 13:44
  • @RobertHarvey for finding pivot the criteria should be the left and right element should be small, right?
    – CodeYogi
    Dec 31, 2016 at 15:04
  • If you scan the array from left to right, you will find the pivot point when the right element is suddenly smaller than the left element. Read the GeeksForGeeks article carefully.
    – Robert Harvey
    Dec 31, 2016 at 15:06

1 Answer 1

Reset to default
4

it was too embarrassing for me to just sit and think.

Well here's your problem.

Programming isn't something that only happens when your fingers are on the keys. I've solved thorny problems while staring at the tile in my shower. Don't be afraid to take a moment, breath, and think. Hell ask for a bathroom break if you have to.

Also, while Robert Harvey's solution of returning an unrotated version of the array isn't O(log n) it would be acceptable to me in an interview if you recognized that it isn't O(log n) when you present it. In the agile world you make it work before you make it fast. I'd be more impressed if you asked if that was acceptable before you coded it.

Breaking a problem down isn't just dividing it into smaller parts. It's also challenging your assumptions about the requirements.

I might still push you for the fully O(log n) solution but now I'd be willing to give you more time to find it because you've shown me that you're not going to just disappear into the problem. As long as you're checking how much time you have and showing what you have figured out, I feel better waiting.

Talking while you think it through helps. They might not give you hints, but you can always use the interviewer as a duck.

Improve this answer
1
  • I'm retired now, but back when I had my own software company it was a running joke that I got more real work done in the shower than I did in the office. There was even talk of installing a shower in my office for those times when I needed a little steam to unclog the neurons.
    – Peter Rowell
    Jan 1, 2017 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.