Elixir of Life: August 2007

Tuesday, August 28, 2007

Detect a loop in a linked list

How would you detect a loop in a linked list? Write a C program to detect a loop in a linked list.

/*
Start two pointers at the head of the list
Loop infinitely
If the fast pointer reaches a NULL pointer
Return that the list is NULL terminated
If the fast pointer moves onto or over the slow pointer
Return that there is a cycle
Advances the slow pointer one node
Advances the fast pointer two node
*/

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

struct linkedList{
int element;
struct linkedList* next;
};

typedef struct linkedList* List;

/* Takes a pointer to the head of a linked list and determines
if the list ends in a cycle or is NULL terminated
*/

int DetermineTermination(List *head)
{
List *fast, *slow;
fast = slow = head;
while(1)
{
if(!fast || !fast->next)
return 0;
else if(fast == slow || fast ->next == slow)
return 1; // Loop detected
else{
slow = slow->next;
fast = fast->next->next;
}
}
}

Powered by ScribeFire.

Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?

struct linkedList{
int element;
struct linkedList* next;
};

typedef struct linkedList* List;

void deleteNode(List Node)
{
List tmp;
if(Node)
{ // If current node is not NULL

tmp = List->next; // take backup of next Node
Node->element = Node->next->element; // replace current node element with next Node element
Node->next = Node->next->next; // change next pointer to next to next
free(tmp); // free the next Node which was taken backup

}
return;
}

Powered by ScribeFire.

Reverse a linked list

Here is the iterative and recursive solution:

struct linkedList{
int element;
struct linkedList *next;
};

typedef struct linkedList* List;

List reverseList(List L)
{
List tmp, previous=NULL;

while(L){
tmp = L->next;
L->next = previous;
previous = L;
L = tmp;
}
L = previous;
return L;

}

List recursiveReverse(List L)
{
List first, rest;
if(!L)
return NULL;
first = L;
rest = L->next;
if(!rest)
return NULL;
rest = recursiveReverse(rest);
first->next->next = first;
first->next = NULL;
L=rest;

return L;
}

Powered by ScribeFire.

Monday, August 20, 2007

memcpy function implementation

//Most simplified copy function.
void *memcpy(void* dest, const void* src, size_t count)
{
char *s = (char *)src;
char *d = (char *)dest;
for(; count; count--)
{
*s++ = *d++; //usage of operator precendence
}
}

Card Shuffling Algorithm

The Algorithm

Step 1: Initialize the cards. For each i in the [0...n-1] range, set card[i] = i.

Step 2 (optional): Seed the random number generator.

Step 3: Let i = 0.

Step 4: Let j = random_number MOD n.

Step 5: Exchange the values of card[i] and card[j].

Step 6: Let i = i + 1. If i is less than n, go to step 4.

Sample Source Code

Here is a sample C function implementing the algorithm:

void shuffle(int *card, int n) {
	int i, j, k;

	for (i = 0; i &lt; n; i++)
		card[i] = i;

	for (i = 0; i &lt; n; i++) {
		j = rand() % n;
		k = card[i];
		card[i] = card[j];
		card[j] = k;
	}
}

Question :

Write a C Program to reverse a stack "in place" using recursion ?
You can only use the following ADT functions on Stack:
IsEmpty
IsFull
Push
Pop
Top

Solution:

void reverse()
{
....int a = s.pop();
....if(s.count!=1)
........reverse();

....Push(a);
}

void Push(int a)
{
....int m = s.pop();
....if(s.count!=0)
........Push(a);
....Else
........s.push(a);

....s.push(m);
}

Sunday, August 19, 2007

No of BTS's

Question :

Given a number N, find the number of binary search trees(BST) possible with numbers 1,2....N

for E.g. if N = 2 , no. of BSTs with node-values 1 and 2 = 2
if N = 3 , no. of BSTs with node-values 1,2 and 3 = 5

Solution:

recursive sol for the same

int countTrees(int numKeys) {

if (numKeys <=1) {
return(1);
}
else
{
// there will be one value at the root, with whatever remains
// on the left and right each forming their own subtrees.
// Iterate through all the values that could be the root...

int sum = 0;
int left, right, root;

for (root=1; root<=numKeys; root++) {
left = countTrees(root - 1);
right = countTrees(numKeys - root);

// number of possible trees with this root == left*right
sum += left*right;
}

return(sum);
}
}

MS Question

Question:
------------

Given an array having 16000 unique integers, each lying within the range 1<x<20000, how do u sort it. U can load only 1000 numbers at a time in memory.

Solution:

Have an array of 2500 bytes (memory equaivalent of 625 ints) - Each bit in the array will show the presence/absence of a num betw 1-20,000. Lets call this the "presence-bit-map".

Since you can store the presence of 8 nos in a byte, you need (20,000/8) = 2500 bytes.

Initialize all bytes in the presence-bit-map to 0, meaning 'absent'.

Iterate the large integer list(be it in file / mem) once. For every number encountered, set the corresponding bit to 1(indicating present) in the presence-bit-map.

Now, by scanning the presence-bit-map once, you can write the present numbers in sorted order.

complexity
===========
The soln has a complexity of 'order of n', where n is 20,000 in this particular case. O(n) is the best u can get for a sorting problem !

O(n) is possible here coz we have 2 facts that could be taken advantage of
1. Numbers are known to be unique
2. Nos. are known to be in a specific range.

In a generic sorting problem, O(n) is usually not achievable since we can't assume anything like this.

I planned to maintain all the data structure and Algorithm questions which will surely benefit me and my friends .. So keep watching this page for more entries ..