VMWare Inc Interview Question for Software Engineer Interns

Team: NSBU
Country: United States
Interview Type: Phone Interview

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

Overall time complexity is O(Log n)

``````public class NumberOfOccuranceOfn {

public static int first(int[] arr,int start,int last,int num){
int mid;
int foundAt=-1;
while(start<=last){
mid=(last+start)/2;
if(arr[mid]>num){
last=mid-1;;
}else if(arr[mid]<num){
start=mid+1;
}
//when found number, now we need to find the first occurrence of that repeated number
else{
foundAt=mid;
last=mid-1;
}
}
return foundAt;
}
public static int last(int[] arr,int start,int last,int num){
int mid;
int foundAt=-1;
while(start<=last){
mid=(last+start)/2;
if(arr[mid]>num){
last=mid-1;;
}else if(arr[mid]<num){
start=mid+1;
}
//when found number, now we need to find the first occurrence of that repeated number
else{
foundAt=mid;
start=mid+1;
}
}
return foundAt;
}
public static int NoOfOccurances(int[] arr,int num){
int start=first(arr, 0, arr.length-1, num);
int end=last(arr, 0, arr.length-1, num);
return end-start+1;

}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr={9,9,9,9,9,9};
System.out.println(NoOfOccurances(arr, 9));
}``````

}

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

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.

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

``````"""
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)``````

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

How the complexity would be O(n) when you are finding the 'K' key in the sorted input filled with 'K'. it should be O(1) i think. Did i miss something

And also, to find the insertion point, we need to use Binary search itself

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

1. find first occurence of n - O(logn) - i
2. find last occurence of n - O(logn) - j
3. return j-i+1;

Overall : O(logn+logn) - O(logn)

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

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

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.

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.