This is not my interview question. It was conducted for my friend. He cleared his interview. Now I am sharing/solving all the questions asked to him.
Question 1: Given a sorted array of numbers, some of which may be repeating. Find the first occurrence of a given number.
Answer: In this case we use a binary search which is modified a bit to find min or max.
If Binary search matches, get the minimum element in left subtree.
Fetch Mid
Check whether high is lower than low, return
Element matches again, so check if next left subtree matches.
Element does not matches, find if right subtree has the same element.
Remaining is the binary search.
Following is the program for the solution
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* Problem: Given a sorted array of numbers, some of which may be repeating.
* Find the first occurrence of a given number.
*
* E.G. 1, 2, 2, 4, 8, 9, 10, 10, 10, 12
*
* @author Praveen
*
*/
public class FindFirstElement {
/**
* This method reads the input and prepares the array and call the relevant method.
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
/**
* N is the number of test cases.
*/
int N = Integer.parseInt(line);
for (int i = 0; i < N; i++) {
String[] values = br.readLine().split(" ");
int[] array = new int[values.length];
for (int index = 0; index < values.length; index++) {
array[index] = Integer.parseInt(values[index]);
}
String find = br.readLine();
int element = Integer.parseInt(find);
System.out.println(findIndexForElement(array, element, 0, array.length - 1));
}
}
/**
* Solution is to use a modified binary search.
* 1. If Binary search matches, get the minimum element in left subtree.
* 2. Remaining is the binary search.
* @param array
* @param element
* @param low
* @param high
* @return
*/
private static int findIndexForElement(int[] array, int element, int low, int high) {
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (array[mid] == element) {
return getMin(array, element, low, mid - 1);
} else if (array[mid] > element) {
return findIndexForElement(array, element, low, mid - 1);
} else {
return findIndexForElement(array, element, mid + 1, high);
}
}
/**
* Finds the element that it first in the array.
* Solution:
* 1. Fetch Mid
* 2. Check whether high is lower than low, return
* 3. Element matches again, so check if next left subtree matches.
* 4. Element does not matches, find if right subtree has the same element.
* @param array
* @param element
* @param low
* @param high
* @return
*/
private static int getMin(int[] array, int element, int low, int high) {
int mid = (low + high) / 2;
if (low > high) {
return high + 1;
} else if (array[mid] == element) {
return getMin(array, element, low, mid - 1);
} else {
return getMin(array, element, mid + 1, high);
}
}
}
This program has been tested with the following test cases:
15
1 2 2 4 8 9 10 10 10 12
12
1 2 2 4 8 9 10 10 10 12
16
1 2 2 4 8 9 10 10 10 12
10
1 2 2 4 8 9 10 10 10 12
2
1 2 2 4 8 9 10 10 10 12
1
1 2 2 4 8 9 10 10 10 12
0
1 2 2 4 8 9 10 10 10 12
9
1 2 2 4 8 9 10 10 12
12
1 2 2 4 8 9 10 10 12
16
1 2 2 4 8 9 10 10 12
10
1 2 2 4 8 9 10 10 12
2
1 2 2 4 8 9 10 10 12
1
1 2 2 4 8 9 10 10 12
0
1 2 2 4 8 9 10 10 12
9
1 2 2 4 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13
10
If you think that I have still missed something during testing. Suggest me.
