Groupon Interview Question for Software Engineer / Developers


Country: United States




Comment hidden because of low score. Click to expand.
3
of 3 vote

This can be done by bit modification in binary search with O(logN) time.
Please find the working code below....
INPUT : baseAddressOfArray, sizeOfArray, numToSearch.
OUTPUT : Index of element (-1 if element is not present)

int binarySearchOnRotatedArray(int arr[], int arrSize, int key)
{
    int mid, start=0, end1=arrSize-1;
    int index=-1;
    if(arr[start] == key)
        index = start;
    else if(arr[end1] == key)
        index = end1;

    while(index == -1 && start != end1 -1)
    {
        mid = (start+end1)/2;
        if(arr[mid] == key)     //If found the element
            index = mid;
        else if (arr[mid] < arr[start]) //Right part of mid is sorted array...
        {
            if(key > arr[mid] && key < arr[end1])
                start = mid;
            else
                end1 = mid;
        }
        else    //Left part of mid is sorted array....
        {
            if(key > arr[start] && key < arr[mid])
                end1 = mid;
            else
                start = mid;
        }
    }

    return index;
}

- Rahul November 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

HINT: Modify regular binary search.

- S O U N D W A V E November 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 votes

Hint: Does not work if elements can repeat.

- Anonymous November 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Input arr[] = {3, 4, 5, 1, 2}

Element to Search = 1

1) Find out pivot point and divide the array in two
sub-arrays. (pivot = 2) /*Index of 5*/


2) Now call binary search for one of the two sub-arrays.
(a) If element is greater than 0th element then
search in left array

(b) Else Search in right array
(1 will go in else as 1 < 0th element(3))


3) If element is found in selected sub-array then return index
Else return -1.

- rvndr November 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

input arr[]={3,4,5,6,7,8,1,2}

Suppose we want to search for 8 in above array , by your algorithm it will be searched only in {3--6} part and than will return -1

- Lalit November 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The key insight here is that doing a binary search of a rotated array is that portions of the array are still sorted, or represent another rotated array to search in. Thus, if you have the array
[7, 8, 1, 2, 3, 4, 5, 6], and you are searching for '5', this can be found in the second half of the array. So you need to tell binary search when to look in the sorted half, vs when to look in the unsorted half.

Example: If your index in binary search is 3, your value is 2, so you know the right portion will be sorted. If 5 is between 2 and the last element (6), just do binary search. Otherwise, the target would have to be in the first half (or nowhere at all). See the code below.

private static int binarySearchRotated(Integer[]list, int target, int low, int high) {
		if (low > high || high < low) {
			return -1;	//find closest index and return it
		}
		int index = (low + high) / 2;
		int first = list[0];
		int last = list[list.length-1];
		if (list[index] == target) {
			System.out.println("Found " + target + "at index: " + index);
			return index;
		} else if (list[index] < first) { //this means we're in the (second) sorted part of the array
			if (list[index] < target && target <= last) {	//if the target belongs in this half, just do binary search
				return BinarySearch(list, target, index+1, high);
			} else {	//otherwise, we have to look in the unsorted rotated portion
				return binarySearchRotated(list, target, low, index-1);
			}
		} else { //this means we're in the first half of the array, which is still sorted
			if (list[index] > target && target >= first) {	//if the target belongs in the first half, just do binary search
				return BinarySearch(list, target, low, index-1);
			} else {	//otherwise, we have to look in the unsorted rotated portion
				return binarySearchRotated(list, target, index+1, high);
			}
		}
	}

- rocketegg November 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Have a look at the solution here: knavite.blogspot.com/2013/11/searching-element-in-rotated-sorted.html . Please give feedback.

- Naved Alam November 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int find(int target, int left, int right , int [] rotate){
    	if (left>right){
    		return -1;
    	}
    	
    	int mid = (left + right) /2 ;
    	if (rotate[mid] == target){
    		return mid;
    	}else if (target > rotate [mid]){
    		
    			if (target>rotate[right]){
    				return find(target,left,mid-1,rotate);   
    	    	}else if (target<rotate[right]){
    	    		return find(target,mid+1,right,rotate);
    	    	}else {
    	    		return right;
    	    	}	   
    	}else {
    		   if (target>rotate[left]){
				  return find(target,left,mid-1,rotate);   
	    	   }else if (target<rotate[left]){
	    		  return find(target,mid+1,right,rotate);
	    	   }else {
	    		  return left;
	    	}	      		
    	}    	
    }

- Scott November 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int find(int target, int left, int right , int [] rotate){
    	if (left>right){
    		return -1;
    	}
    	
    	int mid = (left + right) /2 ;
    	if (rotate[mid] == target){
    		return mid;
    	}else if (target > rotate [mid]){
    		
    			if (target>rotate[right]){
    				return find(target,left,mid-1,rotate);   
    	    	}else if (target<rotate[right]){
    	    		return find(target,mid+1,right,rotate);
    	    	}else {
    	    		return right;
    	    	}	   
    	}else {
    		   if (target>rotate[left]){
				  return find(target,left,mid-1,rotate);   
	    	   }else if (target<rotate[left]){
	    		  return find(target,mid+1,right,rotate);
	    	   }else {
	    		  return left;
	    	}	      		
    	}    	
    }

- Scott November 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class RotatedSortedArray { 
	// Array is assumed to be sorted in increasing order that has then been rotated. 
	// May not work if array is sorted in decreasing order and has then been rotated.
	public static int search(int key, int[] arr) {
		int mid;
		int start = 0;
		int end = arr.length - 1;
		while (start <= end) {
			if (arr[start] == key)
				return start;
			else if (arr[end] == key)
				return end;
			else {
				mid = (start + end) / 2;
				if (arr[mid] == key) {
					return mid;
				}
				if (arr[start] < arr[mid]) { // sorted to left of mid
					if ((key > arr[start]) && (key < arr[mid])) {
						end = mid;
					}
					else if (key > arr[mid])
						start = mid;
					else return -1; // key is less than start
				}
				else // sorted to right of mid
					if ((key > arr[mid]) && (key < arr[end]))
						start = mid;
					else // (key > array[end]) or (key < array[mid]
						end = mid;
			}
				
		} //while
		return -1;
	} //search
	
public static void main (String args[]) {
	int test = 0;
	int[] array = {0,1,2,3,4,5};
	int index = search(2, array);
	System.out.println("Output of test " + test + " is " + index);
	
	test = 1;
	array[0] = 1; // array is {1,1,2,3,4,5}
	index = search(1, array);
	System.out.println("Output of test " + test + " is " + index);
	
	test = 2;
	array[0] = 5;
	array[1] = 1;
	array[2] = 1;
	array[3] = 2;
	array[4] = 3;
	array[5] = 4; //array is {5,1,1,2,3,4}
	index = search(5, array); 
	System.out.println("Output of test " + test + " is " + index);
	
	test = 3;
	index = search(1, array);
	System.out.println("Output of test " + test + " is " + index);
/*	
	// Test cases for when array is in decreasing order and has then been rotated
	test = 4;
	for(int i=5; i>=0; i--) // array = {5,4,3,2,1,0}
		array[5-i] = i;
	index = search(4, array);
	System.out.println("Output of test " + test + " is " + index);
	
	test = 5;
	array[0] = 0;
	array[1] = 5;
	array[2] = 4;
	array[3] = 3;
	array[4] = 2;
	array[5] = 1; //array = {0,5,4,3,2,1}
	index = search(3, array);
	System.out.println("Output of test " + test + " is " + index); */
	
	} // main
}; //RotatedSortedArray

- perf_guru November 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var arr = [5, 6, 1, 2, 3, 4] ;

First get then length of the array.

var len = arr.length;

Then concat the array with itself

arr = arr.concat(arr);

now you get [1, 2, 3, 4, 5, 6, 1, 2, 3, 4]

truncate the array

arr = arr.slice(0, len);

then you do a binary search.

- chihungyu1116 January 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package ms.searching;

public class BinarySearchOnRotatedSortedArray {

	private int search(int[] input, int low, int high, int key) {
		// TODO Auto-generated method stub
		if (low > high) {
			return -1;
		} else {
			int mid = (low + high) / 2;
			if (input[mid] == key)
				return mid;
			// left is ordered
			else if (input[mid] > input[low]) {
				if (key < input[mid] && key >= input[low])
					return search(input, low, mid - 1, key);
				else
					return search(input, mid + 1, high, key);
			} else if (input[mid] < input[high]) {
				if (key > input[mid] && key <= input[high])
					return search(input, mid + 1, high, key);
				else
					return search(input, low, mid - 1, key);
			} else if (input[mid] == input[low]) {
				if (input[mid] != input[high])
					return search(input, mid + 1, high, key);
				else {
					int result = search(input, mid - 1, low, key);
					if (result == -1) {
						result = search(input, mid + 1, high, key);
					}
					return result;
				}
			}
		}
		return -1;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] input = { 15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14 };
		BinarySearchOnRotatedSortedArray bSRA = new BinarySearchOnRotatedSortedArray();
		int resultIndex = bSRA.search(input, 0, input.length - 1, 14);
		if (resultIndex != -1)
			System.out.println("The key found at " + resultIndex);
		else
			System.out.println("The key not found");
	}

}

- sLion August 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * Created by Samuel PC on 29/07/2015.
 */
public class SortedArrayRotated {



        public static void main (String[] args) throws java.lang.Exception
        {

            int[] array = {4,5,6,7,9,0,1,2,3};

            // get medium point
            int  key = 10;
            int start , end;
            start = 0;
            end = array.length-1;
            int result = findElem(array, key, start, end);
            System.out.println(result);

            key = 5;
            result = findElem(array, key, start, end);
            System.out.println(result);

            key = 1;
            result = findElem(array, key, start, end);
            System.out.println(result);
        }

    public static int findElem(int arrayElements[], int key, int start , int end) {
        int aux = (start+end) / 2 ;

        System.out.println(key+" - "+ start+" - "+ end);

        if(key == arrayElements[start]) {
            System.out.println("find key");
            return arrayElements[start];

        }
        if(key == arrayElements[end]) {
            System.out.println("find key");
            return arrayElements[end];
        }


        if(start == end || (end - start) == 1 ) {
            System.out.println("key not finded");
            return -1;
        }

        // find in the left part of the array
        if(key > arrayElements[start] && key < arrayElements[aux]){
            end = aux;
            return findElem(arrayElements,key,start,end);
        }else{
            // find in the right part of the array
            start = aux;
            return findElem(arrayElements,key,start,end);
        }

    }
}

- samuelteixeiras July 29, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More