CareerCup

Here is my solution that uses multi-structured linked list to solve the problem:

"I know its a bit complicated, but when you will run the code, you will know that it works". :)

The solution might seem a bit complicated because I have modified the problem to also hold relations to other node data such as distance between two nodes, to make the problem more challenging.

Each node contains its ID and a link to another structure called Link. This "structure", Link is a linked list where each node of this link list tells what other nodes this node is connected to.

Link contains two fields. One field points to the actual structure (Relation) where all the data is kept such as what is the distance to the other node and what node it is connected to.
The other field just points to the next structure.

The header file goes as follows:

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

#ifndef __GRAPHNODES
#define __GRAPHNODES

struct nodeRelation;
struct linkStructure;
struct nodeStructure;

typedef struct nodeRelation
{
	int distance;
	struct nodeStructure *peer;
} Relation;

typedef struct linkStructure
{
	struct nodeRelation *edge;
	struct linkStructure *next;
} Link;

typedef struct nodeStructure
{
	int id;
	struct linkStructure *relations;
} Node;


Node* createNode(int givenID)
{
	Node *temp = (Node*) malloc (sizeof(Node*));
	
	temp->id = givenID;
	temp->relations = NULL;
}

void addEdge(Node *src, Node *dest, int givenDistance)
{
	Link *newLink = (Link*) malloc (sizeof(Link*));
	
	Relation *newRel = (Relation*) malloc (sizeof(Relation*));
	newRel->distance = givenDistance;
	newRel->peer = dest;
	
	newLink->edge = newRel;
	newLink->next = NULL;
	
	if (src->relations == NULL)
	{
		src->relations = newLink;
	}
	else
	{
		Link *temp = src->relations;
		
		while(temp->next != NULL)
		{
			temp = temp->next;
		}
		
		temp->next = newLink;
	}
}

void printRelations(Node *myNode)
{
	printf("Node ID: %d.\n\n", myNode->id);
	
	printf("Node Relations are: \n\n");
	
	Link *temp = myNode->relations;
	
	if (temp != NULL)
	{
		do
		{
			printf("Related To: %d\n", temp->edge->peer->id);
			printf("Distance: %d\n\n", temp->edge->distance);
		
			temp = temp->next;
		} while (temp != NULL);
	}
	else
	{
		printf("No Relations Found.\n\n");
	}
	
	printf("-------------------------------------\n\n");
}

#endif

And the main file goes as follows:

#include "graphNodes.h"

int main()
{
	Node *one = createNode(1);
	Node *two = createNode(2);
	Node *three = createNode(3);
	Node *four = createNode(4);
	Node *five = createNode(5);
	
	addEdge(one, two, 10);
	addEdge(one, four, 20);
	addEdge(one, five, 30);
	
	addEdge(two, one, 15);
	addEdge(two, five, 30);
	
	addEdge(three, five, 50);
	
	printRelations(one);
	printRelations(two);
	printRelations(three);
	printRelations(four);
	printRelations(five);
	
	return 0;
}

C Code:

First the header file to create double circular linked list:

#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[1]);
	int jumpBy = atoi(argv[2]) % 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;
}

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

Please care to tell me why the solution is wrong.

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)