How to delete a node in the singly link list ?

Given a pointer to a node in a singly linked list, how do you delete the node ?
A simple solution is to traverse the linked list until you find the node you want to delete. But this solution requires pointer to the head node which contradicts the problem statement.
Fast solution is to copy the data from the next node to the node to be deleted and delete the next node. Something like following.

    struct node *temp  = node_ptr->next;
   node_ptr->data  = temp->data;
   node_ptr->next  = temp->next;
   free(temp);

In java, the code would look something like this :

1	public void deleteNode(Node node){

2	Node temp = node.next;

3	node.data = temp.data;

4	node.next = temp.next;

5	//do nothing with temp and let the garbage collector remove it

6

}

Continue

Vertical sum of binary tree

Find vertical sum of given binary tree.

Example:

Code:

     1
   / \
 2     3
/ \   / \
4   5 6   7

The tree has 5 vertical lines
Vertical-1: nodes-4 => vertical sum is 4
Vertical-2: nodes-2 => vertical sum is 2
Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12
Vertical-4: nodes-3 => vertical sum is 3
Vertical-5: nodes-7 => vertical sum is 7
We need to output: 4 2 12 3 7

We can do an inorder traversal and hash the column. We call Traverse(root, 0) which means the root is at column 0. As we are doing our traversal, we can hash the column and increase its value by T.data. A rough sketch of my function looks like this -

Traverse(Tree T, int column)
{
if(T==NULL) return;
Traverse(T.left, column-1);
Hash(column) += T.data;
Traverse(T.right, column+1);
}

Traverse(root, 0);
Print Hash

Continue

Card shuffle

Write a program to shuffle an pack of cards in the most efficient way. This question can be asked in several flavors.
Knuth Shuffle / Fisher-Yates Shuffle(Modified version by Durstenfeld) algorithm is the answer to all the trick questions. So how does this algorithm work ?
Fisher and Yates’ original method was designed to be implemented using pencil and paper, with a precomputed table of random numbers as the source of randomness. Modern approach suggested by – Richard Durstenfeld is as follows:
To shuffle an array a of n elements:

for i from n - 1 downto 1 do
        j ← random integer with 0 ≤ j ≤ i
        exchange a[j] and a[i]

Reduced time complexity to O(n), compared to O(n²) for the naive implementation. A sample java implementation :

01	import java.util.Random;

02

03	static Random rng = new Random();

04	public static void shuffle(int[] array) {

05	// i is the number of items remaining to be shuffled.

06	for (int i = array.length; i > 1; i--) {

07	// Pick a random element to swap with the i-th element.

08	int j = rng.nextInt(i); // 0 <= j <= i-1 (0-based array)

09	// Swap array elements.

10	int tmp = array[j];

11	array[j] = array[i-1];

12	array[i-1] = tmp;

13

}

14

}

Continue