VMWare Inc Interview Question for Interns


Country: India
Interview Type: Phone Interview




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

This is the Josephus problem. There is a formula to calculate result directly only when k=2. For other cases, there are solutions with O(n) or O(klogn) time complexities. Therefore, O(1) is impossible when k=3.

- Will August 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(1) time complexity is possible if size is known. Please confirm.

- OTR August 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I dont understand your question.....!

Either it should be out when elements is <3 or How you can delete the 3rd element when there will be only 1 remaining in list. It will throw index out of bound when it try to access 3rd element with 2 remaining in list.

- Muhammad Tariq Akram August 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Size of the array is known

- Saurabh Singhal August 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

a[n%3] where n is length. When 2 elements are remaining just do eenie meenie miney mo.
I assume that when you delete a 3rd element, the next third element must be counted from begining. For exmaple, in 1,2,[3],4 -> 1,2,[4] -> [1],2 -> 2 is the last element.

- Anonymous August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Josephus Problem

en.wikipedia.org/wiki/Josephus_problem

- EOF August 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Ths wat i found ,
If (i am wrong)
{
Sorry;
} else
{ pay mee..
}
}

Kiddingggggggg..Here is the code..


#include <stdio.h>
#include <stdlib.h>

int main()
{
int a[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14};
int n = sizeof(a)/sizeof(int);
int i, j = 2, count = 0;
printf("The are %d elements in the array\n", n);
for (i = 2; i<n ; i++)
{
if ((i)%3 != 2)
{
a[j] = a[i];
j++;
}
else
{
count++;
}
}
printf("Number of elements removed are : %d\n", count);
printf("Resultant array is\n");
for (i = 0; i < n - count; i++)
{
printf("%d ", a[i]);
}
printf("\n");

getch();
}

- subbu September 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

n - [n/3]

- elber.kam August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a[n%3] where n is length. When 2 elements are remaining just do eenie meenie miney mo

- Noobie August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I assume that when you delete a 3rd element, the next third element must be counted from begining. For exmaple, in 1,2,[3],4 -> 1,2,[4] -> [1],2 -> 2 is the last element.

- Noobie August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assume f(n) returns the index. Here is the O(log(n)) algorithm. I would like to go ahead and blindly claim that O(1) does not exist. :)

int f(int n)
{
	int k_new = 1, k_old = 1;
	while(k_new <= n)
	{
		k_new = round(k_old * 1.5)
		k_old = k_new;
	}
	return k_old;
}

Example:
n = 11;
step1: k_old = 1, k_new = 1;
step 2: k_old = 1, k_new = 2;
step 3: k_old = 2, k_new = 3;
step 4: k_old = 3, k_new = 5;
step 5: k_old = 5, k_new = 8;
///step 6: k_old = 8, k_new = 12'
f(11) = k_old = 8.
A0 = [*1 2 3 *4 5 6 *7 8 9 *10 11]
A1 = [*2 3 5 *6 8 9 *11]
A2 = [*3 5 8 *9]
A3 = [*5 8]
A4 = [8]

I marked the numbers which are removed in next iteration with "*"

- Ehsan August 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You got the question wrong. In an array of 7 elements, the order of removal of elements would be : 3,6,2,7,5,1
So, remaining element is 4

- Saurabh Singhal August 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your question is too general to be interpreted "correctly".
Every third element of an <<array>> means indices "3k" for k > -1.
The example you gave me is a linked list with sentinel (ring).
However, the nature of the problem is the same. I don't think you can do it in O(1). But I don't have a proof.

- Ehsan October 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int f(int *a,int n,int k){
int i,j;
i=1;
j=2;
while(i<n) {
a[j]=-1;
i++;
j=(j+k)%n;
while(a[j]==-1)
j=(j+1)%n;
}
return a[j];
}

- Anonymous September 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will leave one element deleted..........check it

- Anonymous September 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

undeleted in fact..

- Anonymous September 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am going to assume "delete" means marking with a special value. Do this for every third element till only one remains.

int[] arr = { 2,3,4,5,7,8,9};
		int n = arr.length;
		// x holds the index to be marked deleted. An index gets deleted at every iteration 	 //of the loop, so its run n-1 times.
		int x =0;
		for(int i=0; i< n-1; i++)
		{
		
			arr[x] = -1;
			x = (x+3) %n; // next index to delete

		}
		
		// Finally, x has the index of remaining element.
		System.out.println(x);

- Aparna September 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Mod3Array {
	static int i;
	static int n;
	static int a[];
	static int deleted;
	static int sum;
	public static void increment()
	{
		int count=0;
		while(count<3)
		{
			if(i<(n-1))
			{
				i++;
				if(a[i]!=-999)
					count++;
				//System.out.println("up " + count+i);
			}
			else
			{
				i=(n-1)%i;
				if(a[i]!=-999)
					count++;
				//System.out.println("down " + count+i);

			}
		}
	}
	public static void main(String args[])
	{
		
		//Mod3Array ob= new Mod3Array();
		
		try{
			BufferedReader b=new BufferedReader(new InputStreamReader(System.in));
			System.out.println("Enter the size of array: ");
			n=Integer.parseInt(b.readLine());
			a=new int[n];
			System.out.println("Enter array Elements: ");
			for(i=0;i<n;i++)
				a[i]=Integer.parseInt(b.readLine());
			sum=((n-1)*n)/2;
		}
		catch(IOException ioe)
		{
			ioe.printStackTrace();
		}
	
		
		//if(n==2)
			//a[0]=-999;
			for(i=-1;i<n&&n>1;)
			{
				increment();
				a[i]=-999;
				
				deleted+=1;
				sum-=i;
				if(!(deleted<(n-1)))
					break;
				
			}
			for(i=0;i<n;i++)
				System.out.print(" "+a[i]);
		System.out.println("\nIndex is = " + (sum));
	}

}

T(n)=o(3n)=o(n)

- Nilotpal September 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There will be 1 element left at the end count from where you left, assume it to be circular.

- Nilotpal September 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

element index=(N-2^floor(logN/log2))+1
where N is the size of array.

- Divya Sachan October 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

element index=(N-2^floor(logN/log2))+1
where N is the size of array.

- Divya Sachan October 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution will work if there is no 0 element in input array. Correct me if my solution is wrong
{
{
{
int[] numbers = {1,2,3,4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
int counter = 3;
int lastelement = 0;
int remFlag = numbers.Length;
if (numbers.Length >= 3)
{
for (int i = 2; ; )
{
if (i <= numbers.Length - 1 && counter >= 3)
{
numbers[i] = 0;
--remFlag;
counter = 0;
++i;
}
if (i > numbers.Length-1)
{ i = 0; }

if (numbers[i] != 0)
{
++counter;
if (remFlag == 2 && counter == 2)
{
lastelement = numbers[i];
}
if (counter < 3)
{
++i;
}

}
else
{
++i;
}

// check for the last element
if (remFlag == 1)
{
return lastelement;
}
}
}
}
}
}

- Venky October 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Compiled code. Execute it as it is.


public class JosephusProblem {
	public int PrintLastAfterDeletingThird(int[] arr){
		int j,k=arr.length+1,n=0,N=0,Tcount=0, temp=arr.length;
		int[] indexArr=new int[temp];
		for(int index=0; index<temp;index++){
			indexArr[index]=index;
		}
		while(true){
			j=0;
			int len=temp-Tcount;
			N=n;
			if(len==2){
				if(n==0){
					System.out.println("Index is: "+indexArr[1]);
					return arr[1];
				}
				else{
					System.out.println("Index is: "+indexArr[0]);
					return arr[0];
				}
			}
			for(int i=0;i<len;i++){
				if(((i+N)%3)!=2){
					arr[j]=arr[i];
					indexArr[j]=indexArr[i];
					j++;
				}
				else{
					k=i;
					n=len-k-1;
					Tcount++;
					if(Tcount==temp-1){
						break;
					}
				}
			}
		}
	}
	
	public static void main(String[] args){
		JosephusProblem jp=new JosephusProblem();
		int[] a=new int[]{1,7,6,5,4,3,2,1,0};
		int b=jp.PrintLastAfterDeletingThird(a);
		System.out.println(b);
	}
}

- ankit.hbtik October 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution I am proposing here would be little complex as elements in array in not unique.
But for simplicity lets assume the elements are unique and then we can see the non-unique case
a) build a linked list copying elements of array in same sequence
b) have a hashmap keyed by element of array (which is assumed to be unique)
when array lands at a[(i+3)%n], get the node from linked list and search one on right/left and copy that element into a[(i+3)/n]. Delete the node in the list.
This way we keep copying neighbor element so that looping through the array does not get stuck in a endless circle. We stop at a point when list has only one node. from the hashmap keyed by element one can get index in O(1)

The solution gets little tricky if array elements are not unique. We need to replace the deleted node pointer with neighbor and proceed...

- Anonymous September 28, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

its not possible to get only one remaining element every time. it can be two or one or zero remaining element.explain your question

- anshuman saurabh August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Of course we have to find the last element remaining, like in josephus problem.
Don't just ask anything, try to get a solution, in minimum information.

- Anonymous August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

What a dumb question. It's going to boil down to an array with just two elements which is trivially the first two elements of the original array. How do you decide which one to choose in the end? A coin toss? Maybe that will give you that O(1) time complexity.

- Anonymous August 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 votes

I think this was supposed to be a special case of the Josephus problem. The question could have been worded a bit more clearly.

- eugene.yarovoi August 22, 2013 | Flag


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