## VMWare Inc Interview Question for Interns

• -1
of 1 vote

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.

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.

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

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.

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

Size of the array is known

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

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,,4 -> 1,2, -> ,2 -> 2 is the last element.

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

Josephus Problem

``en.wikipedia.org/wiki/Josephus_problem``

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

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

n - [n/3]

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

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

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

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 = 

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

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

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

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

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.

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

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

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

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

undeleted in fact..

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

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

``````import java.io.BufferedReader;
import java.io.IOException;

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{
System.out.println("Enter the size of array: ");
a=new int[n];
System.out.println("Enter array Elements: ");
for(i=0;i<n;i++)
sum=((n-1)*n)/2;
}
catch(IOException ioe)
{
ioe.printStackTrace();
}

//if(n==2)
//a=-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)

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.

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.

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.

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

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);
return arr;
}
else{
System.out.println("Index is: "+indexArr);
return arr;
}
}
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);
}
}``````

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...

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

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

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.

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.

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

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

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.