• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Rob Spoor
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Henry Wong
  • Liutauras Vilda
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Tim Holloway
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Mikalai Zaikin
  • Piet Souris

Interview question: write a binary search method and assume the array is unsorted

 
Ranch Hand
Posts: 239
12
Scala IntelliJ IDE Eclipse IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Can anyone explain this question to me? I received it as part of a technical interview as "homework." The question is, given an unsorted integer array, write a binary search method that returns an integer representing the index in the array where the element is located.

Am I wrong in thinking this is nonsensical? The idea of a binary search is that it is performed against a sorted array.

So I implemented a binary search method where I separately sort the array first, then wrote the following reply with my implementation: "On the binary search method, I want to note that if we assume that the given array is sorted, we can easily return the index of the element we find in the sorted array. On the other hand, if we assume the array is not sorted when it is received by the method, then I sort it beforehand using the Arrays.sort method, and the index that is returned is the index of the element in the now-sorted array. You can review my code to see this. There would be no meaningful way to return the original index value without using a supporting data structure. Let me know if you had something in mind such as using a supporting data structure (such as a tree) to hold the index values and the values of the array, search the tree for the value, and then return the index value found at that node with the value."

I received no reply to this for a week and finally heard back that they do not want to move forward in the interview process. Any thoughts?
 
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Scott Shipp wrote:Can anyone explain this question to me? I received it as part of a technical interview as "homework." The question is, given an unsorted integer array, write a binary search method that returns an integer representing the index in the array where the element is located.

Am I wrong in thinking this is nonsensical? The idea of a binary search is that it is performed against a sorted array.



Yeah, sounds pretty nonsensical to me. Unless the implication is that you're supposed to sort and then binary search. But if you're just doing a one-off retrieval, that's pointless. Just do a linear search.

Of course, if you expect to need to do additional searches, then at some point the cost of 1 sort + N binary searches becomes less than the cost of N linear searches, so in that case it might make sense. Still an oddly phrased question though. I wonder if it was deliberate, to see if you'd catch the nonsensicality of it, or if the interviewer is just confused.

So I implemented a binary search method where I separately sort the array first, then wrote the following reply with my implementation: "On the binary search method, I want to note that if we assume that the given array is sorted, we can easily return the index of the element we find in the sorted array. On the other hand, if we assume the array is not sorted when it is received by the method, then I sort it beforehand using the Arrays.sort method, and the index that is returned is the index of the element in the now-sorted array. You can review my code to see this. There would be no meaningful way to return the original index value without using a supporting data structure. Let me know if you had something in mind such as using a supporting data structure (such as a tree) to hold the index values and the values of the array, search the tree for the value, and then return the index value found at that node with the value."

I received no reply to this for a week and finally heard back that they do not want to move forward in the interview process. Any thoughts?



Your comments here sound spot-on to me. Whether your answer to that problem and the accompanying comments played a role in their decision is anybody's guess.
 
Scott Shipp
Ranch Hand
Posts: 239
12
Scala IntelliJ IDE Eclipse IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I am completely baffled. I can't think of anything but this that seemed odd about this interview. The last part of our in-person conversation was them letting me know that they would send me a "homework" problem to work through, complete, and send back. I would think that they wouldn't send the code problem unless the rest of the interview had gone well. I completed it the same day and sent it to them. All I can think is, oh well, se la ve. I will never know the reason.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Scott Shipp wrote:oh well, se la ve.



*C'est la vie, actually

But yeah, sometimes you just have to shrug, say, "Oh, well," and move on. You could still contact them and see what they'll tell you about why they passed. Maybe they found somebody with more experience, or who was willing to work for less, or maybe the interviewer was just an idiot and somebody else happened to tell him the answer he wanted to hear, even if it didn't make sense.
 
You showed up just in time for the waffles! And this tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic