VMWare Inc Interview Question
Software Engineer InternsTeam: NSBU
Country: United States
Interview Type: Phone Interview
This problem is trap. If you perform binary search for n and once found, going in left and right direction till we see n results in worst case O(n) time (when entire array is filled with n). We don't want that, however arriving it this way is normal and interviewer will ask if there is better way.
Lets denote array indexes as L and R. Once found at mid, we should continue binary searches for start index of n. Once found, say s then we look for index of last n using binary search once more.
"""
Given a sorted array arr[] and a number x, write a function that counts the occurrences of x in arr[].
Expected time complexity is O(Logn)
"""
def occurrences(arr, num):
first = 0
last = 0
for idx, val in enumerate(arr):
if val == num:
first = idx
break
for idx, val in reversed(list(enumerate(arr))):
if val == num:
last = idx
break
occurrence = last-first+1
print "Number {} appeared {} times in {}.".format(num, occurrence, arr)
return occurrence
ip = [1, 1, 2, 2, 2, 2, 2, 3, 4]
occurrences(ip, 2)
This is how you will solve in C#:
// Count Occurrence of n in integer array arr.
public static int countOccurrence(int[] arr, int n) {
int first = binarySearch(arr, n, true);
if (first >= 0) {
int last = binarySearch(arr, n, false);
return last - first + 1;
}
return 0;
}
// Finding First or last occurrence of integer n in sorted integer array: arr, searchFirst= true means search first occurrence else search last occurrence.
// Return index location in array for given n either first or last index. If not found return -1.
public static int binarySearch(int[] arr, int n, bool searchFirst) {
int result = -1;
if (arr != null && arr.Length > 0) {
int low = 0, high = arr.Length - 1;
while (low<=high) {
int mid = low + (high-low)/2;
if (arr[mid] == n) {
result = mid;
if (searchFirst) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
else if (arr[mid] > n) {
high = mid-1;
}
else {
low = mid+1;
}
}
}
return result;
}
public class CountOfOccurence {
public static void main(String[] args) {
int[] a = {1, 1, 2, 2, 2, 2, 3};
int n = 2;
int count = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] == n) {
count++;
}
}
if (count > 0) {
System.out.println(count);
} else {
System.out.println("number does not exist in array");
}
}
}
public class CountOfOccurence {
public static void main(String[] args) {
int[] a = {1, 1, 2, 2, 2, 2, 3};
int n = 2;
int count = 0;
for (int value : a) {
if (value == n) {
count++;
}
}
if (count > 0) {
System.out.println(count);
} else {
System.out.println("number does not exist in array");
}
}
}
Overall time complexity is O(Log n)
}
- sivapraneethalli November 13, 2016