## Amazon Google Interview Question for Software Engineer / Developers

• 3

Country: India
Interview Type: In-Person

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

this question is known as the "Josephus problem" ... search on wikipedia

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

So it is... I didn't think it could be done by pure mathematics, but indeed it can!

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

So? This question is about a data-structure, not the math behind the problem.

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

``````//ref: wikipedia

int josephus(int n, int k) {
return josephus(n, k, 1);
}
int josephus(int n, int k, int startingPoint) {
int newSp, survivor;
if(n == 1)
return 1;
newSp = (startingPoint + k - 2) % n + 1;

survivor = josephus(n - 1, k, newSp);
if (survivor < newSp) {
return survivor;
} else
return survivor + 1;
}``````

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

``````int josephus(int n, int k)
{
printf("LL Size: %d, OffSet: %d\n", n, k);
if (n == 1)
return 1;
else /* The position returned by josephus(n - 1, k) is adjusted because the
recursive call josephus(n - 1, k) considers the original position k%n + 1 as position 1 */
return (josephus(n - 1, k) + k-1) % n + 1;
}``````

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

As per given direction : I think it is the best one!
"There is an O(n) solution based on mathematics, the iterative equation is the following:

f=0;

f[i]=(f[i-1]+k)%i; (i>1)

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

typedef struct node
{
int value;
struct node* next;
}node;

node* getNode (int val) {
node *element ;
element = (node *) malloc (sizeof(node)) ;
element->value = val ;
element->next = NULL ;
return element ;
}

if ( head == NULL ) {
}
temp = temp->next ;
temp->next = element ;
}

while ( temp->next != head ) {
printf ( "%d ", temp->value ) ;
temp = temp->next ;
}
printf ( "%d", temp->value ) ;
}
}

node* getKthNode (node *list, int k, int size) {
int oldVal = 0, i, newVal ;

node *temp = NULL, *element ;
for ( i = 2 ; i <= size ; i ++ ) {
newVal = (oldVal + k) % i ;
oldVal = newVal ;
}
newVal ++ ;

temp = list ;
if ( size == 1 )
return list ;

for ( i = 1 ; i < newVal; i++ ) {
list = list->next ;
free (temp) ;
temp = list ;
}
element = list ;
element->next = NULL ;
list = list->next ;

for ( i = newVal+1 ; i < size ; i++ ) {
list = list->next ;
free (temp) ;
list = list->next ;
}
free (list) ;
return element ;
}

int main() {
node *head = NULL, *temp ;
int size, i, val, k;
printf ( "\nEnter the sie :\t" ) ;
scanf ( "%d", &size ) ;

for ( i = 0 ; i < size ; i ++ ) {
printf ( "\nEnter the value :\t" ) ;
scanf ( "%d", &val ) ;
}
printf ( "\n" );
printf ( "\nEnter the k :\t" ) ;
scanf ( "%d", &k ) ;

temp = getKthNode (head, k, size) ;
if ( temp != NULL )
printf ( "\nLast node :\t%d\n", temp->value ) ;
return 0;
}``````

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

How do you come up with such a equation....!!!!

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

``````/*
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package competition_problems;

//~--- JDK imports ------------------------------------------------------------

import java.util.ArrayList;

/**
*
* @author Ashish
*/
public class NewClass {
public static void main(String[] args) {
ArrayList list = new ArrayList();

int k     = 3,
i     = 0,
count = 0;

while (list.size() > 0) {
count++;
System.out.println(list);
i %= list.size();
i += k - 1;
list.remove(i % list.size());
}

System.out.println(count);
}
}``````

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

This is a tricky problem, i'm trying to figure out how to make it O(n). For instance, say we have n = 10 nodes and k = 100,000. Before we delete our first element, we would have traveled 100,000 times in a linked list. We would do this n-1 times = (n-1)*k = O(n*k). Assuming k is big, and not a "constant", this is not O(n).

Another solution is finding the index of the node to destroy via modular arithmetic and then go to that node to destroy it. Let n = 10 and k = 14. Assuming nodes numbered 0 to 9, and we start at 0, we have 10 % 14 = 4. So 0 + 4 = 4. Go to node 4 and delete it. We're not "starting" where node 4 was. Next, we now have n = 9 nodes, 9 % 14 = 5. 4 + 5 = node 9. Repeat this n-1 times until we have n nodes left. You can test this on paper with 10 labeled nodes from 0 to 9. We first delete node 4 then if we go around 14 more times we'll arive at node 9, which was 4 + 5. Unfortunately, this is (n-1)*n = O(n^2). This is better than O(n*k) if k is > n, but still not O(n).

Should I be assuming k is a constant and not another variable to the function? I mean, if the function is getLastNode(Nodes n, int k) then the input is not just n, k may change as well. If k was always 5 for example, then we could say O(n*5) = O(n).

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

When I said "we're not 'starting' where node 4 was", I meant NOW not NOT

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

Ugh, sorry, there really should be an edit here... if there is I couldnt find it. When I said we "repeat this n-1 times until we have n nodes left" I obviously meant until we have 1 node left. I apologize for this typo and the one in the above comment :(. Also, the reason its O(n^2) is because worst case every time we calculate the index we have to go n nodes away. Best case is 1 node away, which would be O(n).

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

Huh? You can alway compute k % n and work with that, no matter how large n is. The Circular Linked List solution is correct and it works.

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

Or how large k is...

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

Okay, so we have this circular linked list right? And we do k%n in constant time. So we've found which node to delete! Yay! So now we have to go to that node. Linked list search is O(n), right? It's not like we're already at the node, we CALCULATED its location now we have to GO to it with worst case O(n) NEXT assignments. Okay, cool. Now how many times do we have to delete nodes? n-1 times, then we just have one node left. Nice. So (n-1)*n? O(n^2). The mathematical solution by the Josephus problem is the correct O(n) solution. There are in fact no data structures. If a data structure is requested in O(n), im still waiting

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

@John: With the way you analyze time complexity (i.e. the wrong way), you will be waiting forever. Circular Linked Lists indeed work in O(n) time.

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

@Anonymous: When you can tell me how a linked list has O(1) delete time (when given an index via n % k, NOT the node pointer which WOULD be O(1)) then you can talk. You have to search for the node. What do you think this is, an array? You cant say LinkedList[n%k]. Its "Okay, I know the index, we must go to that node now". If you're using a circular linked list, you need O(n) for a search each time you delete, and you do this n-1 times. If you still can't see this, let's agree to disagree. You don't just tell someone they're wrong and don't explain yourself.

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

You delete the kth element and you continue to do it n times.
So complexity is O(kn);
k is constant => complexity is O(n).

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

That's fair, and is the primary argument here. I wasn't considering k constant, since one might ask "Which node will remain if we skip every 5, 10, 100, 1000, 100,000? You get the idea. But if the interviewer says we can call it a constant, that is all that matters :)

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

@John:

AJ has analyzed it incorrectly, though the final answer is actually correct.

Assume there is a starting node, which never gets deleted (this is there just for reference, to understand correctly).

In order to make "one" pass (i.e. to get back/just cross the starting point once), you only take O(n) time, _irrespective_ of k. This is because you move k, then k, then k etc till you delete n/k nodes, but take O(n) time as you move through the whole list (k * n/k). To delete the second node, you make use of the fact that you already have move k nodes. So deletion is not O(n) as you are claiming.

Now the size of the list has become n - n/k = n(1 - 1/k).

Now another round in this take O(n(1-1/k)) time!

So the total time is n + n(1-1/k) + n(1-1/k)^2 + ... + = O(nk) = O(n) for constant k.

Not that the above is incorrect too, as we are ignoring the k%n part, but for constant k, it is good enough.

Anyways...

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

When the interviewer specially asked "until one node is left".. which means we are always deleting the second node. So, K is fixed to be 2.
So, we do not have to assume that we are skipping 5,10,100,1000 etc nodes ever. Its fixed to 2 and that is constant. Also, i don't understand why is everyone writing generic "k" solutions when is question asks for a specific case.

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

@psy, "until one node is left" doesn't mean that "we are always deleting the second one". It is possible that at the very end, there are two nodes left and k=5 for example .. in which case, you traverse the full cycle twice (cover 4 elements) and delete the "first" element in the third cycle traversal.

While it is true that "k" may be a constant, it doesn't have to be a constant "2" in this question.

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

Hi,

There is an O(n) solution based on mathematics, the iterative equation is the following:

f=0;

f[i]=(f[i-1]+k)%i; (i>1)

Then you just need to follow the linked list from the head till you reach the f[n]+1 (starting from 1, not 0) element.

For the above example:
f = 0
f = (0+3)%2 = 1
f = (1+3)%3 = 1
f = (1+3)%4 = 0
f = (0+3)%5 = 3.

So the final answer is the 4th element in the list.

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

f=k;
f[i]=（f[i-1]+k)%(N-i+1)+1

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

This approach does a good job of removing the K factor from the complexity, but O(n) is still expensive. Granted, you're forced into it here anyway since the data is in a linked list, so this might be a very reasonable solution for this situation. If we had an array we could do much better.

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

What does f[i] means in your iteration equation?

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

Can somebody explain the recursion?? Why it's working?

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

Code :

``````int delete_kth_node( node *head, int n, int k)
{

while(n > 1)
{
int dist = (k % n)-1;
node *temp = NULL;

if(dist == -1)
dist = n-1;

while(dist > 0)
{
current_node = current_node->next;
dist--;
}

temp = current_node->next;
current_node->next = temp->next;

free(temp);
temp = NULL;
n--;

printf("\n");

current_node = current_node->next;
}

}``````

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

``````int delete_kth_node( node *head, int n, int k)
{
// while no of nodes or length is 1
while(n > 1)
{
int dist = (k % n)-1; //avoid the redundant moves in the circular list, this is the optimization, n-1 to reach just 1 node prev to the node being deleted.
node *temp = NULL;

//when k=0 or when k=n,
// we need to reach to the last but prev node in the list e.g. 1->2->3->1 then reach to 3.
if(dist == -1)
dist = n-1; // special case

while(dist > 0)
{
current_node = current_node->next;
dist--;
}

temp = current_node->next;
current_node->next = temp->next;

free(temp);
temp = NULL;
n--;

printf("\n");
current_node = current_node->next;
}
}``````

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

I think it got misformatted. Sorry for that.

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

OK, so this is still a rather naive solution. You're not making any optimizations that help you on large values of n, only on large values of k. This solution is still O(n) for fixed k.

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

Hi eugene,
the thing to note is that we are gaining the optimization after more and more iterations. Since n is decremented each operation and frequently n will become smaller than k and will remain smaller than k going further, hence optimizations gain will be significant no matter what. No doubt the mathematical formula given above seems best if correct in all scenario. Since we directly know what to delete straightaway.

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

can someone please comment or provide details if i missed something here?
thanks guys.

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

I didn't check your code for correctness, but the general approach makes sense. It is at worst O(NK). Still a relatvely far cry from being optimal. A more mathematical algorithm will produce something more like O(KlogN) (+ O(N) if you need to do it on a linked list instead of an array).

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

Can you explain how can one avoiding traversing till kth node for every deletion?

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

For the explanation, using int dist = (k % n)-1 I come to the node just before the one which we need to delete.

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

Even i don't get how we can avoid traversing till kth node, eugene can throw light on it. Thanks buddy.

Just one more observation for base:

1 base case optimization i see is when k=0 is passed as parameter to the function, in that case don't enter the while loop preseve the first node and keep deleting the list 1 by 1 in linear time.

1-2-3-4-1
k=0, n=4

here k%n=0
therefore dist = -1 => dist = n-1 = 3

But if we observe closely then 1 should be the last node remaining.
1-1 2-3-4-2
1-1 3-4-3
1-1 4-4
1-1

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

int delet_kh_node( node*& head, int k)
{
{
{
{
for(int i=1; i<k-1; i++ )

delete t;
}
}
}

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

you are ignoring the optimization mentioned in post above where you don't have to traverse the link list when k > length. Note that length keeps on decrementing after each operation.

consider the case when k=102 and len = 5 in that case you will do unncessary traversal over the list. whereas by doing a (k%n) -1 you could avoid all them and just point yourself one node previous to the node you want to delete.
e.g.
1-2-3-4-5-1
k=102 and len = 5
k%len - 1= 2 -1 = 1
hence just move 1 node and delete 2 directly in 1 step. Saving you 20 repetead traversal of the circular list.

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

``````import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class QCircularList {
private static final int K_ELEMENT = 3 - 1;

public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(1, 2, 3, 4, 5));
int idx = K_ELEMENT;
while (list.size() != 1) {
System.out.println("removed element at index: " + idx);
list.remove(idx);
printList(list);
idx = nextRemovalIndex(idx, list);
}

}

private static int nextRemovalIndex(int idx, ArrayList<Integer> list) {
int loop = 0;
do {
idx++;
idx = idx % list.size();
loop++;
} while (loop < K_ELEMENT);
return idx;
}

private static void printList(List<Integer> asList) {
int i = 0;
for (int a : asList) {
System.out.println("a[" + i + "]: " + a);
i++;
}
System.out.println("---------------------------");
}

}``````

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

again O(nk) solution!

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

sorry I rush the answer, no need the method that loops to calculate the next index

``````public class QCircularList {
private static final int K_ELEMENT = 3 - 1;

public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(1, 2, 3, 4, 5));
int idx = K_ELEMENT;
while (list.size() != 1) {
System.out.println("removed element at index: " + idx);
list.remove(idx);
printList(list);
idx = (idx+K_ELEMENT) % list.size();
}
}

private static void printList(List<Integer> asList) {
int i = 0;
for (int a : asList) {
System.out.println("a[" + i + "]: " + a);
i++;
}
System.out.println("---------------------------");
}
}``````

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

void delete_node(struct circular **node, int pos)
{
struct circular *q, *p, *temp;
int i=0,j;
q = *node;
if((*node) == NULL)
else if((*node)->next == NULL)
printf("final node is %d\n",(*node)->data);
else
{
q=(*node);
while(q->next != q)
{
for(i=1;i<pos;i++)
{
q = q->next;
}
if(q && q->next && (q->next != q))
{
temp = q->next;
q->next = q->next->next;
if(temp)
delete temp;
}
p = q;
while(p->next != q)
{
p = p->next ;
printf("%d-->",p->data);
}
p=p->next;
printf("%d\n\n",p->data);
}
}
}

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

#include <stdio.h>

struct node{
int info;
struct node * next;
};

struct node * temp = (struct node *)malloc(sizeof(struct node));
temp->info = x;
}

void display(){
struct node * temp = head;
while(temp!=NULL){
printf("%d\n",temp->info);
temp = temp->next;
}
}

void makeCircular(){
struct node * temp = head;
while(temp!=NULL && temp->next!=NULL){
temp=temp->next;
}
}

void deleteK(int pos){
struct node * temp1;
int i;
for(i=1;i<pos-1;i++){
}
free(temp1);
deleteK(pos);
else
}

int main(){
makeCircular();
deleteK(5);
return 0;
}

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

Internal stack memory size O(k)
again Time = O(nk)

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

``````private static void delete(node first, int i) {
// TODO Auto-generated method stub
node save = first;
node startfrom = first;
node prev = null;
int count =1;
while(count<i){
if(first.next==first){
System.out.println( "" +first.data + first.next.data + first.next.next.data + first.next.next.next.data + first.next.next.next.next.data);
return;
}
else{
prev = first;
first = first.next;
count++;
}

}
prev.next = first.next;
startfrom = first.next;
first = null;
first = save;
System.out.println( "" +first.data + first.next.data + first.next.next.data + first.next.next.next.data + first.next.next.next.next.data);
delete(startfrom,i);

}``````

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

``````#include<stdio.h>
typedef struct node
{
int value;
struct node* next;
}Node;
typedef Node* NodePtr;
void PrintList(NodePtr list);
int Length(NodePtr list);
int ValueAt(NodePtr list,int pos);
int main()
{
NodePtr List=NULL;
//int a[]={1,2,3,4,5,6};
int i=0,count,data,k;
scanf("%d",&k);
scanf("%d",&count);
for(i=0;i<count;i++)
{
scanf("%d",&data);
//PrintList(List);
}
PrintList(List);
int n=Length(List);
int *f=(int *)malloc(sizeof(int)*n);
//printf("\nLength= %d",Length(List));
f=0;
for(i=1;i<n;i++)
{
f[i]=(f[i-1]+k)%(i+1);
}
printf("\n Node to be deleted is %dth node and its value is %d",f[n-1]+1,ValueAt(List,f[n-1]+1));
}

{
NodePtr travel=NULL;
NodePtr newNode;
newNode=(NodePtr)malloc(sizeof(Node));
newNode->value=data;
newNode->next=list;
if(list==NULL)
{
newNode->next=newNode;
list=newNode;
return list;
}
travel=list;
while(travel->next!=list)
{
travel=travel->next;
}
travel->next=newNode;
return list;
}

void PrintList(NodePtr list)
{
NodePtr travel=list;
printf("\n");
while(travel->next!=list)
{
printf("%d ->",travel->value);
travel=travel->next;
}
printf("%d -->",travel->value);
printf("%d",travel->next->value);
}

int Length(NodePtr list)
{
int count=0;
NodePtr travel=list;
while(travel->next!=list)
{
count++;
travel=travel->next;
}
count++;
return count;
}

int ValueAt(NodePtr list,int pos)
{
int i=1;
NodePtr travel=list;
while(travel->next!=list)
{
if(i==pos)
return travel->value;
i++;
travel=travel->next;
}
if(i==pos)
return travel->value;
}``````

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

``````import java.util.LinkedList;

public static <E> E kRemove(LinkedList<E> list, int k) {
/*
size    k-condition         result
0                           IllegalArgumentException
1                           return list
n       k in [0..n-1]       return list
*/

if (list.size() == 0)
throw new IllegalArgumentException();

if (list.size() == 1)
return list.element();

if (k < 0 || k >= list.size())
throw new IndexOutOfBoundsException();

int start = 0;
while (list.size() > 1) {
int elToDelete = (start + k - 1) % list.size();
list.remove(elToDelete);
start = elToDelete % list.size();
}
return list.element();
}
}``````

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

{*p=node;
node=node->next;count++;}
{t=node->next;
node->next=t->next;
t->next=NULL;
else if(count==k)
{
}

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

O(nk) solution with internal stack space o(n-1)

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

}
current=current.next;
}
int killtimes=1;
while(current.next!=current){
if(killtimes==times){
pervious.next=current.next;
current.next=null;
current=pervious.next;
killtimes=1;
continue;
}
else{
pervious=current;
current=current.next;
killtimes++;
}
}
return current.data;
}

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

all codes looks very clustered. i have simple solution.
node *cur=start;
while(cur->next!=cur)
{
node *temp=cur->next->next;
cur=temp->next // for next deltion;
delete(temp);

}

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

``````namespace
{
template <typename T>
struct Node
{
T value;
int next;
Node() : next(-1) {}
};

template <typename T>
class Ring
{
int _capacity; // Capacity of Ring (initially)
int _size; // Valid Node Count
int _current; // Current node
Node<T>* _nodes; // Collection of Nodes

public:
Ring(int cap) : _capacity(cap), _size(0), _nodes(NULL), _current(-1)
{
_nodes = new Node<T>[cap];

for(int aa = 0; aa < cap; ++aa)
_nodes[aa].next = (aa+1)%cap;

_size = cap;
_current = 0;
}

~Ring()
{
if(_nodes) { delete [] _nodes; _nodes = NULL; }
}

int Size() const { return _size; }

int DeleteAndMove(int step)
{
if(_size < 1) throw "The ring is empty";

//
// Move prior to deleting node
//
for(int aa = 0; aa < step - 1; ++aa)
_current = _nodes[_current].next;

int toDelete = _nodes[_current].next;
printf("deleting %d ..\n", toDelete);
_nodes[_current].next = _nodes[toDelete].next;
_nodes[toDelete].next = -1;
_current = _nodes[_current].next;
--_size;

return _size;
}
};

void DeleteTest(int size, int space)
{
Ring<int>* ring = new Ring<int>(size);

try
{
while(ring->Size() != 1)
{
ring->DeleteAndMove(space);
}
}
catch(const char* msg)
{
fprintf(stderr, "%s\n", msg);
}
}
}

void SK::SampleQuestions::KthNodeRemoval()
{
DeleteTest(101, 7);
}``````

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

Above will leak memory (forgot to delete 'ring'). Spoiled from smart-pointers...

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

I guess double link list will work. The total traversal will be O(N). We'll start following the next pointer with count, once find 'k' delete the node. In case nxt is null we'll follow previous to get (k-count) and keep on doing unless get prev==NULL and ther revert to next and so on.

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

A nxn array of pointers to the given circular linked list.
If I understand the question correctly, the problem is to design a data structure that is efficient enough to delete all elements in linked list for any given value of k in O(n) time. In other words for any value of K, this data structure that you design should take O(n) time to delete all the elements.
Note: The deletion should follow the pattern specified in the question.

In order to achieve this, we have to cache the deletion sequence for each value of K.
A simple nxn dimension array would suffice. Each row would contain the deletion sequence for a given value of K.
Example:
a[n][n]
The deletion sequence for K=1 could be cached in the 0th row of the array, a to a[n] - n pointers the the 1st successor of every element starting from the head.
For k=2 the sequence would be stored in the 1st row of the array, a to a[n].

In general, for any value of K, we just need to delete the all nodes in the row k-1 sequentially, a[k-1] to a[k-1][n]. - this will achieve O(n) time.

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

Array where after array.length -1 position we come back to position 0.
Basically using modulo operation.
For elements which are removed in those cells in the array we can have some pre-defined indentifier number to indicate empty cell.
Removal for single element will be O(1) since we can find the exact index which has to be free.
So for n elements the removal will be O(n).
Please provide suggestions on this solution.

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

The same solution came to my mind first time. Can anybody point out what is the problem with this one?

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

After 10 rounds, you will have a difficult time keeping tracking of the deleted elements. By skipping over k, you have to skip over non-deleted elements. In an array it will be difficult. With a circular list, it will be easy.

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

I also don't see any way to do the whole thing in O(n). I hope the person who posted this question didn't mean O(n) for each iteration, hence O(n^2) total...

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

I may be missing something here but couldn't you use an array?

To remove every kth item we increment by the index by k and remove that item. We just need to check to see if our index is greater than array.length() -1, and if it is simply take that away from the index to maintain a circular structure.

Then if we encounter an item that has been removed (either by noticing it is null, or by having a special static 'removed' item to swap with if the array items may be null) we simply increment the index by 1. (Because the next item should be in this index, it's just that rebuilding an array is expensive). That should only happen if the array length is evenly divided by k.

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

Your algoritm is correct but is not O (n). To get O (n), you should be performing each delete in constant time. As you remove more and more elements leaving null values intheir place, you will encounter more null values ... you will be touching linear nulls per delete (not constant)

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

Correct.

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

This is josephus problem..

This can be done either using recursion

``````int josephus(int n, int k)
{
if (n == 1)
return 1;
else
/* The position returned by josephus(n - 1, k) is adjusted because the
recursive call josephus(n - 1, k) considers the original position
k%n + 1 as position 1 */
return (josephus(n - 1, k) + k-1) % n + 1;
}``````

or by iteration,

``````f = 0
f[i] = (f[i-1]+k)%i``````

final result would be

``f[n]+1``

``````void precomp() {
int i;
val = 0;
for (i = 2; i < MAX; i++)
val[i] = (val[i-1]+k)%i;
}``````

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

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

typedef struct node
{
int value;
struct node* next;
}node;

node* getNode (int val) {
node *element ;
element = (node *) malloc (sizeof(node)) ;
element->value = val ;
element->next = NULL ;
return element ;
}

if ( head == NULL ) {
}
temp = temp->next ;
temp->next = element ;
}

while ( temp->next != head ) {
printf ( "%d ", temp->value ) ;
temp = temp->next ;
}
printf ( "%d", temp->value ) ;
}
}

node* getKthNode (node *list, int k, int size) {
int oldVal = 0, i, newVal ;

node *temp = NULL, *element ;
for ( i = 2 ; i <= size ; i ++ ) {
newVal = (oldVal + k) % i ;
oldVal = newVal ;
}
newVal ++ ;

temp = list ;
if ( size == 1 )
return list ;

for ( i = 1 ; i < newVal; i++ ) {
list = list->next ;
free (temp) ;
temp = list ;
}
element = list ;
element->next = NULL ;
list = list->next ;

for ( i = newVal+1 ; i < size ; i++ ) {
list = list->next ;
free (temp) ;
list = list->next ;
}
free (list) ;
return element ;
}

int main() {
node *head = NULL, *temp ;
int size, i, val, k;
printf ( "\nEnter the sie :\t" ) ;
scanf ( "%d", &size ) ;

for ( i = 0 ; i < size ; i ++ ) {
printf ( "\nEnter the value :\t" ) ;
scanf ( "%d", &val ) ;
}
printf ( "\n" );
printf ( "\nEnter the k :\t" ) ;
scanf ( "%d", &k ) ;

temp = getKthNode (head, k, size) ;
if ( temp != NULL )
printf ( "\nLast node :\t%d\n", temp->value ) ;
return 0;
}``````

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

C Code:

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

#ifndef __DATASTRUCTURE
#define __DATASTRUCTURE

typedef struct node
{
int id;
struct node *next;
struct node *prev;
} Node;

Node* createNextNode(int id, Node *callingNode)
{
Node *temp = (Node*)malloc(sizeof(Node));

temp->id = id;

if (callingNode != NULL)
{
temp->next = callingNode->next;
temp->prev = callingNode;

callingNode->next = temp;

temp->next->prev = temp;
}
else
{
temp->next = temp;
temp->prev = temp;
}

return temp;
}

void deleteNode(Node *unwantedNode)
{
unwantedNode->prev->next = unwantedNode->next;
unwantedNode->next->prev = unwantedNode->prev;

free(unwantedNode);
}

void printNodesForward(Node *startNode)
{
Node *temp = startNode;

do
{
printf("%d\t", temp->id);
temp = temp->next;
}while(temp != startNode);

printf("\n");
}

void printNodesBackward(Node *startNode)
{
Node *temp = startNode;

do
{
printf("%d\t", temp->id);
temp = temp->prev;
}while(temp != startNode);

printf("\n");
}

#endif``````

Then the actual code to remove every kth node in o(n) time. Note that the traversal to reach the nth node takes o(n) time.

``````#include "dataStructure.h"

int main(int argc, char **argv)
{
if (argc != 3)
{
printf("Usage: ./a.out <totalNodes> <jumpBy>\n");
return 1;
}

int totalNodes = atoi(argv);
int jumpBy = atoi(argv) % totalNodes;

Node *callingNode = createNextNode(1, NULL);
Node *startNode = callingNode;

int i = 2;

do
{
callingNode = createNextNode(i, callingNode);

i++;
}while(i != totalNodes+1);

while(totalNodes != 1)
{
for (i = 1; i != jumpBy; i++)
{
startNode = startNode->next;
}

Node *unwantedNode = startNode;
startNode = startNode->next;
deleteNode(unwantedNode);

printNodesForward(startNode);

totalNodes--;
}

return 0;
}``````

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

General approach for this problem is to use circular linkedlist.

Just using a plain circular linked list will give O(kn) complexity. if k=n, that would lead to O(n^2) complexity. Something like this -

``````struct node *r = root;
struct node *todelete = NULL;
for (int i=n; i>0; --i)
{
for (int j=0; j < k; j++)
r = r->next;

todelete = r->next;
r->next = r->next->next;
free(todelete);
}``````

This is due to the traversal we do every loop to reach the kth node. So finding a way to remove this traversal each time.

Use a array which has random access. Create array of length n and store all n elements in them. At each position of the array store the data. start the deletion process. in each loop jump to that kth location & delete that data. Incase we goto a location with no data (it might have already been deleted), then shift one place to right & see if there is data there. And so on... This approach is somewhat like "openaddressing hashtable collision resolution approach".

Time O(n), space O(2n)

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

Data Structure

Node is a class with 2 instance variable int X and int Y as coordinates.
Circle is a class with a instance variable NodesLinkedList. Connect the last node to the first Node in the linked list to make it circular Linked List.
To removing the K th Node from NodesLinkedList add a Method removeNode(Int k)

For Ease of understanding
Assume NodesLinkedList has 100 Nodes. 100 th Node is connected to 1 st Node.
Node to be deleted K th Node is 5.
First time 5 th node is deleted and 95 nodes remain. This goes on till we have last 4 nodes.
Since this is circular. It goes on until we have 1 node.

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

The question asks you to design a O(n) time complexity. Is it possible that we use basic array implementation and after every deletion we make a fresh copy of array of (current_size-1)? After first iteration new array is of size n-1 and we perform k % (n-1) to find next index to be deleted.

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

So, as many said before, this problem can be easily implemented using a Circular Double Linked List, and guaranteeing a O(n) complexity. Specifically, the complexity of this implementation will be O(k*n), and because k is a constant, O(k*n)=O(n). Here's my C++ implementation. I think it's quite simple to understand:

``````struct Node
{
Node* next;
int v;
Node* prev;
};

Node* GetLastNode(Node* node, int k)
{
Node * tmp = node;

while(tmp!= NULL)
{
for(int i = 0; i<k; i++)
tmp = tmp->next;

//Remove tmp node
Node* to_remove = tmp;
tmp->prev->next = tmp->next;
tmp->next->prev = tmp->prev;

//Update the Node pointer
tmp = tmp->prev;

//Check if we reached the last element
if(tmp==tmp->prev)
break;

delete to_remove;
}

return tmp;
}``````

Note: This implementation can run a little faster if we knew in advance the size of the circular list. Thus, instead of running the "for" loop for k iteration, we can run it in k%n iterations. Of course, in each of the While iteration, we must update the value of "n".

There is also an elegant solution using a Single Linked List. In this case, whenever we want to remove a Node A from the list, we simply copy to the node A the full content of its A->next (pointers and value) and then delete the A->next.

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

Algorithm is based on Josephus_problem#The_general_case on wikipedia. Time complexity is O(n). The code in C:

``````#include <stdio.h>
#include <assert.h>

struct Node {
int val;
Node* next;
Node(int val_, Node* next_ = NULL) :
val(val_), next(next_) {}
};

int josephus(int n, int k)
{
int f = 0;
for (int i = 2; i <= n; i++)
f = (f + k) % i;
return f;
}

{
if (head == NULL) return 0;
int n = 0;
do {
q = q->next;
n++;
return n;
}

{
if (n == 0) return NULL;
int idx = josephus(n, k);
printf("idx: %d\n", idx);
for (int i = 0; i < idx; i++)
}

Node* list_5_nodes()
{
Node* node5 = new Node(5);
Node* node4 = new Node(4, node5);
Node* node3 = new Node(3, node4);
Node* node2 = new Node(2, node3);
Node* node1 = new Node(1, node2);
node5->next = node1;
return node1;
}

void test_josephus()
{
assert(josephus(5, 3) == 3);
assert(josephus(1, 3) == 0);
}

void test_len()
{
assert(len(list_5_nodes()) == 5);
}

void test_kill_kth()
{
printf("%d\n", only->val);
}

int main(int argc, const char *argv[])
{
test_josephus();
test_len();
test_kill_kth();
return 0;
}``````

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

You can arrange the nodes as the distance from their center. What I have done here is defined a simple list, and each element of list is a node that describes the distance from the center. Then from that list I retrieve an element randomly and delete it. I do that until there is one element left.

I could have also done it sequentially i.e delete node 1, node 2.... node n-1

Or I could have made a function to delete the user-specified node until one last element is left.

``````import random

nodes = list()

for i in range(0, 5):
n = input("Enter distance from circle: ")
n = int(n)
nodes.append(n)

def pickRandom(start, end):
return random.randint(start, end)

i = len(nodes) - 1
while (i != 0):
print(nodes)
del(nodes[pickRandom(0, i)])
i = i-1

print(nodes)``````

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

the question is asking you to delete the kth item, not a random item

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

Please care to tell me why the solution is wrong.

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

Oh now I get the question. I understood it completely wrong. Thanks.

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

A circular linked list might be the solution.

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

you travel k distance every time, so you will take O(k*n)

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

The trick is to find a data structure that can do this whole removal in O(n). That basically means O(1) for each removal. If you use a circular linked list, it would take O(n) for each removal, and O(n^2) overall.

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

Downvoters are morons. They are forgetting that nodes are being deleted.

This is, in fact correct and gives an O(n) time algorithm.

In one "round", you will delete 1/k th of the nodes, so in effect, this will give an n + n/k + n/k^2 + ..... = O(n) time algorithm.

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

Make that

n + n/r + n/r^2 + ... = O(n).

where r = 1 - 1/k.

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

To remove each node until there's only 1 left, that requires n iterations right? For each iteration, it takes O(k) to traverse your linked list to identify the node to be removed. So the overall algorithm is O(n*k), and not O(n).

And please explain how in one round, you will delete 1/k-th of the nodes. Just want to make sure I am understanding your complexity analysis correctly.

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

@Sunny: Why are you resetting your traversal? To delete the first node, you have to travel O(k) nodes. Then O(k) for the next node and so on...

And once nodes are deleted, there are no longer n nodes.

Consider k = 2 for instance.

In the first "round" you remove all the even integers: number left is half of that before!

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

@Anonymous, what is wrong with Sunny's analysis? the algorithm is exactly the same ... its just a different way of doing the analysis. you iterate through "k" items before deleting the "k"th item. So, for every item that is deleted, you are touching "k" items. For a total of "n" items, you will be iterating/touching "n*k" items .. so, O(n*k) is the running time. This is O(n) only if "k" can be considered a constant.

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

For Josephus problem k is constant.

Also, @whateva, you do k mod n, not k each time. So if loop contains 2 elements and k is a million, you don't keep going around like crazy...

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

This can be done with the help of doubly circular linked list where we can have track of both the previous and next pointers and at last we can add and remove the element in O(n) time

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

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

given a pointer to a node you can remove that node in O(1) time by just changing the previous and next pointers in a doubly circular linked list.

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

See my "answer" down below please, I'm not sure that a linked list would be O(n) if k isn't a constant, or consistently small.

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

accessing every kth element will take k steps hence complexity will be O(kn). I don't think doubly link list solves this problem.

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.