Win a copy of Think Java: How to Think Like a Computer Scientist this week in the Java in General forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

The binary search algorithm - would my implementation be acceptable in a job interview ?

 
Andy Jack
Ranch Hand
Posts: 257
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I tested the code i made with many test inputs. It seems to be working perfectly. Its much longer, but would it be acceptable to you were an interviewer and I did it like this in a Job Interview ?

One - Made by me



Two -



 
Anayonkar Shivalkar
Bartender
Posts: 1557
5
Eclipse IDE Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Andy,

Logic wise, I don't see anything odd in your code.

However, if I were the interviewer, I would ask below questions:
1) How are you getting value of isSorted? That is - how are you deciding that the array is sorted? And more importantly, why are you deciding it? By default, binary search works only on sorted arrays; and deciding if an array is sorted or not might take more time in case of very large arrays.
2) Just like you are having condition 'toFind > myArray[lastIndex]', why there is not other condition (toFind < myArray[0])?

Point 2 is not a big deal, but for point 1: I wouldn't check the 'orderness' of an array unless explicitly asked. Yes, you may get wrong output if you provide an unsorted array(that is - wrong input), but that is known limitation of binary search. YMMV.

HIH.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12122
30
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There's really no reason to ever do



just do



or

 
Andy Jack
Ranch Hand
Posts: 257
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Anayonkar Shivalkar wrote:Hi Andy,

Logic wise, I don't see anything odd in your code.

However, if I were the interviewer, I would ask below questions:
1) How are you getting value of isSorted? That is - how are you deciding that the array is sorted? And more importantly, why are you deciding it? By default, binary search works only on sorted arrays; and deciding if an array is sorted or not might take more time in case of very large arrays.



Hey Fred ! Thanks for taking the time to review my clunky code . I appreciate it very much.

I did not show the sort method which sets the boolean class member isSorted = true once it does the sorting. Since search(int) is public, i don't want to get an error if the user of the class calls search before sort accidentally.
 
Andy Jack
Ranch Hand
Posts: 257
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
fred rosenberger wrote:There's really no reason to ever do



I am not able to understand why we should not do that ?
 
Pat Farrell
Rancher
Posts: 4678
7
Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Andy Jack wrote:


I am not able to understand why we should not do that ?

Its very clearly bad style. If you want to test a boolean, test it. if (!boolean)

omit unnecessary words.

Performance-wise, the compiler or the JIT optimizer will implement it as if it were if (!boolean) anyway.
 
Pat Farrell
Rancher
Posts: 4678
7
Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If I were asking the question, I'd expect you to not write a binary search algorithm, but rather to use one of the Java Collections framework structures. The Collections framework are robust, fast, and well tested.

The goal should not be to re-write the wheel, but to pick the right wheel and use it.
 
Andy Jack
Ranch Hand
Posts: 257
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Pat Farrell wrote:If I were asking the question, I'd expect you to not write a binary search algorithm, but rather to use one of the Java Collections framework structures. The Collections framework are robust, fast, and well tested.

The goal should not be to re-write the wheel, but to pick the right wheel and use it.


I strongly disagree. I feel that one must first know the basics and then use these tools or frameworks. Make your own code
and compare it with the efficient ones - reveal the flaws in your own thinking. Patch those flaws.
To me, it seems that a solid foundation in DS and Algo is a must for being a developer and also for job interviews.


 
Pat Farrell
Rancher
Posts: 4678
7
Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The fundamental point of Object Oriented Programming is to encourage, and if possible, force, code reuse. The Collections exist. Use them. Re-implementing them takes time better spent on the domain problems.

Now, if the job interview was for the Google Guava team, I'd have a different answer. But for a typical IT professional job, do-it-yourself is really replicate-existing-work.
 
Mike Simmons
Ranch Hand
Posts: 3076
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think being well-grounded in algorithms is a good thing, and it can indeed help in interviews (often more than it helps in the actual job). That said, in any job interview I would first give an answer based on efficient use of existing libraries. If the interviewer is really interested in seeing how well you can code something from scratch, and wants to use an algorithm question to do it, fine - they can guide the interview that way easily enough, and you can show your stuff then. But I would definitely recommend against taking a do-it-yourself approach from the beginning. Many interviewers will take that as a sign that you'll waste time reinventing the wheel, rather than getting on with more productive work.
 
Anayonkar Shivalkar
Bartender
Posts: 1557
5
Eclipse IDE Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Andy Jack wrote:
fred rosenberger wrote:There's really no reason to ever do



I am not able to understand why we should not do that ?

I missed this

The main reason you are not supposed to do this is - if by mistake you write something like:the code will compile, and will assign false value to isSorted (needless to say, it will never enter inside 'if' condition).

Also, as Pat and Mike has mentioned, you need to understand requirements first. If the interviewer is testing your knowledge of existing APIs, then you are supposed to make use of existing methods (instead of writing your own code).
 
Andy Jack
Ranch Hand
Posts: 257
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Anayonkar Shivalkar wrote:
Andy Jack wrote:
fred rosenberger wrote:There's really no reason to ever do



I am not able to understand why we should not do that ?

I missed this

The main reason you are not supposed to do this is - if by mistake you write something like:the code will compile, and will assign false value to isSorted (needless to say, it will never enter inside 'if' condition).


Now I remember. That is exactly what I had done in the above code. No wonder my code was not working properly.
 
Andy Jack
Ranch Hand
Posts: 257
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is what the class looks like -



 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic