VMWare Inc Interview Question
InternsCountry: India
Interview Type: Phone Interview
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.
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.
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();
}
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 "*"
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
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.
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];
}
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);
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)
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;
}
}
}
}
}
}
//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);
}
}
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...
its not possible to get only one remaining element every time. it can be two or one or zero remaining element.explain your question
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.
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