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

}

- sivapraneethalli November 13, 2016 | Flag Reply
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.

- vishalsahunitt November 11, 2016 | Flag Reply
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)

- Anonymous November 14, 2016 | Flag Reply
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

- dsalgos143 November 11, 2016 | Flag Reply
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)

- Raj November 11, 2016 | Flag Reply
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;
}

- nitinmu December 14, 2016 | 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