Binary Search

This blog is part of series that i wanted to start Preparation of Coding Interview

Binary search is one of the first search algorithm that we learn, it is simple to implement and very powerful, gives 0(log n) guarantee.

Quick recap of binary search

  


















It is simple to implement but nearly all binary search were broken due to one bug for long time, you can read about it @ Nearly All Binary Searches are Broken  

Enough of history lets get back to topic and discus some of the interview question on this 

 - Implement Binary Search

This question is still asked so you should practice it because all the logic around index manipulation is little tricky.


Look the line that is finding MID, it is the line that had the bug

 -Find rotation point

This is small variation of binary search, you have to find rotation point in ordered array, for e.g 

Elements are in increasing order then it drops to min value and then again elements are in increasing order.

How do you define rotation point ?
for any element if both left & right element are greater then current element is at rotation point.

In above case 5th element is at rotation point because both left(4th) and right(6th) are greater than 5th

Another example 
char[] values = {'i', 'j', 'k', 'v', 'a', 'b', 'c', 'd'}

5th element(i.e 'a') is at rotation point

Simple Binary Search will not work on this because 2 sorted array are joined in this.
If you try to solve this by brute force then have to go through each element till you find element that is less than previous.

Brute force solution will look something like below



Since this array is sorted , so it is possible to write hybrid binary search that can take advantage of sorted data.

Now real question is how to decided when to go left or right ?

If we just apply normal binary search logic then mid point is 'v'(i.e 4), now which element should be compared to decided left/right ?

Ah it is the first one ('i') , if mid is greater than first then go to right or if it is less than first then go to left.

Lets put some picture to understand it.

 Step 1 - v > i , so we go to right
 Step 2 - b < i, so we go to left
 Step 3 - mid value (a) is at rotation point and program ends.

Code will look something like below



Hopefully visualization was ok enough to explain how to approach this problem.
My visualization skills are very bad & i have to work on it.

Preparation of Coding Interview

I want to share my coding interview experience, so i have decided to write blog series about questions that are asked and this is first one in that series.

Coding interview are very common these days and if you find company that does not have it as part of selection process then i think you should stay away from them.

Lets start with why coding interview is required and reason is very simple especially in times when every company is adopting agile and they don't want to wait for months after hiring to know about coding skills of developer.

So that is the reason why it is the first gate that you have to pass as developer. 

Jeff Atwood share interesting experience about why-cant-programmers-program and type of question that is asked to filter out candidate. FizzBuzz is very good question to start with. 

I would advise to try FizzBuzz to make sure you are not surprised and think about testing also because we are in world of TDD. 


What types of question are asked

Different types of question are asked in coding interview and it depends on type of company you apply

 - Algorithms & Data structures

This is very common for Silicon valley company or product development company and some serious preparations is required for these types of interview if your daily work involves only playing with frameworks(i.e hibernate/spring etc). 

Things become more difficult for such interview because may developers(like me) are focused so much on learning emerging framework to build bleeding edge Resume that we tend to forget basic algorithm and start tagging ourself as some XYZ framework developer and company also help to the cause by putting such job requirement.

- Simple problems using TDD

This type of questions is also very common and it is make sure that you don't leave testing to QA team and write a code that is defect free , easy to understand and maintainable.

- Refactoring problems

You don't work on green field project every day and most of the time is spent in reading others code and adding features to it, so employer want to know "how do you quickly understand code written by somebody else and add new feature to it".

TDD becomes more important in such questions because it can be used to build all the safety net around existing code before you start changing it.

Above question can be asked as pair programming question or take a home type of question, so you have to build solution based on time given to you. 

Some of the things employer wants to check are

 - Simplicity/Readability of code.
 - Maintainability of code. 
 - Design principal usage.

Bottom line is you have to prepare for coding interview to survive in fast changing market.

Stay tuned up for questions.