Find minimum element in rotated and sorted array.

Problem : We have to find an element which is having lowest value in the given array which is sorted and rotated. FYI: This question was asked me in oracle interview.(All elements of the array are unique)
what is sorted and rotated array ?
Sorted array (ONLY) :

Sorted and rotated array (BOTH): 

                                   
By brute force approach we can find that element in O(n) , off course this is not expected answer
any interviewer would like to hear at least not in F2F interview  :P
So what next ?  Since we have a sorted array  and we have to find a solution better than O(n) so Binary search may be handy to solve this problem. If we see diagram closely we can find that  main rationale behind this problem is :

 If (array is rotated )   
    lowest element is that element whose previous element is always higher   
 else  
    first element is lowest element.  

Algorithm : 

  Do simple binary search  
       find middleIndex from startIndex and endIndex of array  
        if (element@middleIndex > element@(middleIndex+1))   
           lowest element is element@(middle+1)  
           return "we are done!!"  
        else if (element@middleIndex < element@(middleIndex-1))  
            lowest element is element@(middle)  
             return "we are done!!"  
        else   
           if(element@middleIndex < element@endIndex)  
             Do not move in right direction , since elements are in increasing order.  
             go to left direction and  repeat binary search methd   
           else   
             Do not move in left direction , since elements are in increasing order.  
             go to right direction and  repeat binary search methd 
       

Now we will write the sample java code for this .

 public class FindMinimumInRotatedArray {  
   public FindMinimumInRotatedArray() {  
     super();  
   }  
 private int findMinInSortedAndRotated(int arr[], int low, int high)  
 {  
   // Added to handle the case when array is not  
   // rotated at all  
   if (high < low) return arr[0];  
   // If there is only one element left  
   if (high == low) return arr[low];  
   // Find mid  
   int mid = low + (high - low)/2; /*To avoid overflow do not use (low + high)/2;*/  
   if (mid < high && arr[mid+1] < arr[mid])  
     return arr[mid+1];  
   // Check if mid itself is minimum element  
   if (mid > low && arr[mid] < arr[mid - 1])  
     return arr[mid];  
   // Decide whether we need to go to left half or right half  
   if (arr[high] > arr[mid])  
     return findMin(arr, low, mid-1);  
   return findMin(arr, mid+1, high);  
 }  
   public static void main(String[] args) {  
     FindMinimumInRotatedArray findMinimumInRotatedArray = new FindMinimumInRotatedArray();  
     int[] arr = { 6, 7, 8, 9, 1, 2, 3, 4, 5 };  
     System.out.println(findMinimumInRotatedArray.findMinInSortedAndRotated(arr, 0, 9));  
     }  
 }  

Sample output : 1

when we execute program we will get 1 output , since it is minimum element.

Now if we twist the question little bit what will happen if all elements of the array are not unique.
-------------------------------------------------------------------------------------------------------
Happy learning!!
Nikhil

Find an element in 2D sorted array or search target element in 2D sorted array

Problem : We have to find key element in the sorted 2D array - which is sorted row and column wise.

Brute force approach :  Iterate 2D array and find whether that element is present or not. It's obvious but not a satisfactory solution. Complexity will be  O(n^2) .So we can think of  something in order of O(logn) or O(n).
we can have several method using binary search or via zig-zag movement of matrix.
One of best possible solution :  (using Zig-zag movement)
logic behind this is that we will start from top right corner of matrix and will reach to bottom left , so we have three possible option to move on either left , bottom or diagonally. But given matrix is sorted in row and column wise ,so we will drop the idea of moving diagonally here.
Now we can move either in left or bottom which will be decided by comparing key and matrix elements.
Pseudo explanation :

 if ( key == matrix(row,column) )  
     key is found here @ (row,column)  
 else if(key > matrix(row, column))  
      Move in column wise , since element which i am looking for must be below the  
      current elements (since elements are sorted.)  
 else  
     Move in left direction  

Picture speaks better that text

Now we can write sample code in java as follows :

 public class FindAnElementin2DSortedArray {  
   public FindAnElementin2DSortedArray() {  
     super();  
   }  
   //zig zag matehod with O(n) complexity  
   public static boolean findByZigzagMethod(int[][] mat, int m, int n, int key) {  
     int row = 0, col = n - 1;  
     while (row < m && col >= 0) {  
       if (mat[row][col] == key) {  
         return true; // key==matrix(row, column) so return true.
       }  
       if (mat[row][col] < key)  
         row++;  
       else  
         col--;  
     }  
     return false; //control reach here means key not found.
   }  
   public static void main(String[] args) {  
     FindAnElementin2DSortedArray findAnElementin2DSortedArray = new FindAnElementin2DSortedArray();  
     int[][] mat = {{2,3,4},{8,12,13},{10,15,18}};  
     System.out.println(FindAnElementin2DSortedArray.findByZigzagMethod(mat, 3, 3,10));   
   }  
 }  

Sample output : true

When we run this program we find that key is found there and it returns true.


Reference: http://leetcode.com/2010/10/searching-2d-sorted-matrix.html

Interview experience at Oracle India Pvt Ltd- Application engineer 2

Interview process took two weeks. This interview was for application developer(Oracle ADF) and interview was mainly all about jaba related stuff and data structure/puzzles/Aptitude.

First round : This round was mainly focused on checking java concepts and related technologies.
1. How java program runs ? (Assume you do not IDE to press F12)
    Low level explanation comprises of Concepts of class Loader(Bootstrap, extension and etc.) and
    memory were expected. I handled it correctly with minor stopping.
2. JVM garbage collection ?
    Explanation of Young Gen,Old Gen were expected. Some concepts related to sweep and clean
    algorithm to explain garbage collection process.
3. Where you have used Interface and abstract class ?
    I explained it with example I faced and justified its use.
4. Comparable and Comparator related questions , along with code to sort the objects.
    When we will go for Comparator not Comparable ?
5. What is reflection API ?
     I explained with an use-case ?
6. Did you use it in your work some time ?
     I answered, NO. Just I know it.
7. A puzzle a famous one : Eight ball (7 equal + 1 unequal) . In how many weighing you will find
    odd ball which is unequal ?
8. Linked List vs Array List difference ?
    When did you use Linked list and it pros/cons compare to ArrayList.
9. HashMap related Question  and how do we iterate it ?
10. Simple SQL query using : Sql Functions and database Join.

Second Round : Data structure and algorithm/Project related stuff mention in resume/Apti
1.Explain any of your project where you learnt most?
   I explained it with ease. But after that I was feeling heat of questions, Why you did this ?
   What are other way we can do it ?
   What will happen if we use this Data Structure ?
    I answered almost. However, One question i could not related to Timezone in java.(Calendar
    related concepts)
2. Explain internal working of HashMap?
    How hashcode() and equals() are important for it ?
3.  Apti/puzzle question :
     Two train coming from opposite direction and one bee is running in a tunnel, how much distance
     it covers before train collide ?
     Angle between minute and hand at 3:15 ?  -- no formula applying directly
4. LinkedList related question :
     Reverse a linked list ?
     How to find middle of linked list in O(n) without counting not of elements ?
 5. Basic questions from Design pattern ?
     What is MVC pattern ?
     What are the patterns you have used and where ?

Third round :
1. Some Questions related to technologies mentioned in my resume. Where I have used and what I
    learned from it ?
2. Basic fundamental questions related to computer science.
It was very short round and show gets over.

It was a great experience for being interviewed after working for more than 2 years at Vanenburg Software. Finally,got offer from Oracle after 3 month (It was worst part of the recruitment process).

Related post :
1. Interview experience at Informatica, Hyderabad- Senior software engineer