## 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;
}``````

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

HINT: Modify regular binary search.

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

Hint: Does not work if elements can repeat.

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.

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

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;
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);
}
}
}``````

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.

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;
}
}
}``````

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;
}
}
}``````

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 = 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 = 5;
array = 1;
array = 1;
array = 2;
array = 3;
array = 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;
array = 5;
array = 4;
array = 3;
array = 2;
array = 1; //array = {0,5,4,3,2,1}
index = search(3, array);
System.out.println("Output of test " + test + " is " + index); */

} // main
}; //RotatedSortedArray``````

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.

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");
}

}``````

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);
}

}
}``````

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