Leisurehours's Blog

Ubuntu & Linux Recipes

Category: Puzzles

A Very Cool Unix Puzzle

by manojgumber

You have a magical program `tux.c’. When you type `cc tux.c’, your compiler appears to hang (i.e, you don’t get back the prompt). Now,during this time, you will be able to type any program `linux.c’ in the standard input and type Ctrl-D. Once you do this, you get back the prompt. Now, you type `a.out’ and magic, what you get will be the output of program `linux.c’! Question is, what is this program `tux.c’?

Source– Yahoo Interview Puzzle

array of 0's and 1's. keep 0 at even and 1 at odd places

by manojgumber

Q .
You are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no if 0s exceed no. of 1s or vice versa then keep them untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY.

input array:
{0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 }
output array:
{0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 }
Read the rest of this entry »

Find majority element in an array

by manojgumber

Problem – You have to find a majority element in an array . An element is majority element if it occurs more than half times the size of array.

Solution –

  1. Take two variables ,major which will contain majority element at the end and another count variable.
  2. Initialize major to first element of the array and set count to one.
  3. Now traverse the rest of array from the 2nd element.
  4. For each array element a[i] ,
    if ( major==a[i] )
    count++;
    else if ( count == 0 )
    {
    major=a[i];
    count=1;
    }
    else
    count--;
    
  5. At the end of traversing the array, major will consist of majority element.

Example:

A A A C C B B C C C B C C
  1. initially, major=A , count =1; Now traverse the rest of the array
  2. major=A , count=2
  3. major=A , count=3
  4. major=A , count=2
  5. major=A , count=1
  6. major=A , count=0
  7. major=B , count=1
  8. major=B , count=0
  9. major=C , count=1
  10. major=C , count=2
  11. major=C , count=1
  12. major=C , count=2
  13. major=C , count=3finally majority element = C

One duplicate , one missing element in an array

by manojgumber

You have an array of size 100 which stores integers from 0 to 99.
In this array one number is a duplicate, that means one is missing.

How can we find duplicate and missing ?
Read the rest of this entry »

Add two numbers without using +,-,*,/

by manojgumber

Method 1
int add(int a, int b)
{
while(a–)
b++;
return b;
}

Method 2
int add(int a, int b)
{
char *p=a;
return &p[b];
}

Method 3
By using the concept of binary adders, If p and q are two bits , then p^q is their sum and p&q is the carry generated by them
int
add (int a, int b)
{
int sum, carry;
do
{
sum = a ^ b;
carry = a & b;
a = sum;
b = carry << 1;
}
while (carry);

return sum;
}

Find the diameter of a tree

by manojgumber

Diameter of a tree is the maximum distance between two nodes in a tree. Hence we can see that maximum distance between two nodes will be always between leaf nodes. To find the distance between two leaf nodes, do the following–
Assuming that we are given pointer to any node of the tree.

  1. Do the BFS (breadth first Search) on the given node and find a node having maximum distance from the given node. The node having maximum distance from the given node will be a leaf node. Lets call it node1
  2. Now again apply the BFS on the node1 and find the maximum distance of any node from node1 . This distance is the diameter of the tree. Because node1 is a leaf of tree and BFS finds the shortest distance from node1 ( a leaf ) to all other nodes in tree. Clearly the node farthest from node1 will be a leaf and hence we will get the diameter of tree.