aspose file tools*
The moose likes Beginning Java and the fly likes The binary search algorithm - would my implementation be acceptable in a job interview ? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Java 8 in Action this week in the Java 8 forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "The binary search algorithm - would my implementation be acceptable in a job interview ?" Watch "The binary search algorithm - would my implementation be acceptable in a job interview ?" New topic
Author

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

Andy Jack
Ranch Hand

Joined: Nov 22, 2012
Posts: 257
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 -




Java Newbie with 72% in OCJP/SCJP - Super Confused Jobless Programmer.
I am a "newbie" too. Please verify my answers before you accept them.
Anayonkar Shivalkar
Bartender

Joined: Dec 08, 2010
Posts: 1464
    
    5

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.


Regards,
Anayonkar Shivalkar (SCJP, SCWCD, OCMJD, OCEEJBD)
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10925
    
  12

There's really no reason to ever do



just do



or



There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Andy Jack
Ranch Hand

Joined: Nov 22, 2012
Posts: 257
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

Joined: Nov 22, 2012
Posts: 257
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

Joined: Aug 11, 2007
Posts: 4639
    
    5

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

Joined: Aug 11, 2007
Posts: 4639
    
    5

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

Joined: Nov 22, 2012
Posts: 257
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

Joined: Aug 11, 2007
Posts: 4639
    
    5

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

Joined: Mar 05, 2008
Posts: 2970
    
    9
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

Joined: Dec 08, 2010
Posts: 1464
    
    5

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

Joined: Nov 22, 2012
Posts: 257
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

Joined: Nov 22, 2012
Posts: 257
This is what the class looks like -



 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: The binary search algorithm - would my implementation be acceptable in a job interview ?
 
Similar Threads
Test driven development - how do you suggest i test this code for correctness ?
Binary Search problem
Problem with merge sort
recursive binary search : used code may have alternative?
Broken code