## Posts

Showing posts from November, 2010

### Divide the bill among three

Three men walk into a restaurant and each order the lunch special that costs \$10. When they are ready to pay the \$30, the owner of the restaurant pulls the waiter aside and says: "These three men are my friends. Give them \$5 off the check". When walking towards the table, the waiter thinks: "\$5 split between 3 men? Not easy. I'll give them each \$1 and keep the last \$2". He does so, everybody is happy. Tips and taxes aside, how much did each man pay?

### Grab gold from mine

There are three people who discover a gold mine full of gold; but it also has some fluids which can be harmful to human body if it comes in direct contact. To take out the gold you need to put in a special fluid on your hand and then wear a glove and then you can put your hand inside the mine and take out the gold. Now the problem is that they have only two gloves with them; but all three want gold but if they cannot mix their fluid's either and don't want to be in direct contact with the gold mine's fluid also. Now what stategry can they come up with so that all three get the gold without being harmed(i.e. no direct contact with the Mine's fluid and no mixing of fluid's of each other)

### Three missionaries and three cannibals

Three missionaries and three cannibals had to cross a river in a boat which held two people. If some missionaries were outnumbered, on either shore, by the cannibals, their missions were over. How would all six cross the river, given that all of them could row?

### Can the camel cross the desert

There is a desert of 1000kms long. A camel is there and 3000 bananas. At one go a camel can take 1000 bananas. For each one km to walk camel eats 1 banana. How many bananas can we cross to the other side of desert.

How can I reverse a linked list recursively with minimum number of temporary pointers

### Circular game survival

I want to play a game on a circular table; the rules of which are something like this.
(i) I will declare how many people are there initially which is say n.
(ii) I will declare the starting position
(iiI) I will declare k, which is the person i will keep killing till there is one survival.

Eg:: if n =6 and k=3 i will first kill 3rd person then 6th person and so on finally 1st will survive.
Now since you are the intelligent among the lot so i want you to come up with a formula which given k and n can help you figuring out a seat for yourself so that you will survive.
1.
#include
int main()
{
int a=10;
switch(a)
{
case '1':
printf("ONE\n");
break;
case '2':
printf("TWO\n");
break;
defa1ut:
printf("NONE\n");
}
return 0;
}

2.
The following C program segfaults of IA-64, but works fine on IA-32.

int main()
{
int* p;
p = (int*)malloc(sizeof(int));
*p = 10;
return 0;
}

Why does it happen so?

3.
int main()
{
float f=0.0f;
int i;

for(i=0;i<10;i++)

f = f + 0.1f;

if(f == 1.0f)

printf("f is 1.0 \n");

else
printf("f is NOT 1.0\n");

return 0;

}

4.

#include

int main()
{
int a = 1,2;
printf("a : %d\n",a);
return 0;
}

5.

#include
int main()
{
int i=43;
printf("%d\n",printf("%d",printf("%d",i)));
return 0;
}

6.
Are the following two function prototypes same?

int foobar(void);
int foobar();

The following programs should be of some help in finding the answer: (Compile and run both the p…

### c puzzles

1.
enum {false,true};

int main()
{
int i=1;
do
{
printf("%d\n",i);
i++;
if(i < 15) continue; }while(false); return 0; } Output : 1

Within a do or a while statement, the next iteration starts by reevaluating the expression of the do or while statement.

2.

#include
#define f(a,b) a##b
#define g(a) #a
#define h(a) g(a)

int main()
{
printf("%s\n",h(f(1,2)));
printf("%s\n",g(f(1,2)));
return 0;
}
Just by looking at the program one "might" expect the output to be, the same for both the printf statements. But on running the program you get it as:
bash\$ ./a.out
12
f(1,2)
bash\$

Why is it so?

### guess the output

#include

#define TOTAL_ELEMENTS (sizeof(array) / sizeof(array[0]))
int array[] = {23,34,12,17,204,99,16};

int main()
{
int d;

for(d=-1;d <= (TOTAL_ELEMENTS-2);d++)
printf("%d\n",array[d+1]);

return 0;
}

### Red Marbles, Blue Marbles

Problem: you have two jars, 50 red marbles, 50 blue marbles. you need to place all the marbles into the jars such that when you blindly pick one marble out of one jar, you maximize the chances that it will be red. (when picking, you’ll first randomly pick a jar, and then randomly pick a marble out of that jar) you can arrange the marbles however you like, but each marble must be in a jar.

### 100 Doors in a Row

Problem: you have 100 doors in a row that are all initially closed. you make 100 passes by the doors starting with the first door every time. the first time through you visit every door and toggle the door (if the door is closed, you open it, if its open, you close it). the second time you only visit every 2nd door (door #2, #4, #6). the third time, every 3rd door (door #3, #6, #9), etc, until you only visit the 100th door.

question: what state are the doors in after the last pass? which are open which are closed?

### Brush up your c skill (check how many you have done)

C Interview Questions.
use these questions to brushup your skills.
Instructions:
1.Please ignore any case-sensitive errors and un-included libraries.

Q1.
main()
{
int i;
clrscr();
printf("%d", &i)+1;
scanf("%d", i)-1;
}
a. Runtime error.
b. Runtime error. Access violation.
c. Compile error. Illegal syntax
d. None of the above
Ans: d, printf( ) prints address/garbage of i,
scanf() dont hav & sign, so scans address for i
+1, -1 dont hav any effect on code

Q2.
main()
{
int i;
float *pf;
pf = (float *)&i;
*pf = 100.00;
printf("n %d", i);
}
a. Runtime error.
b. 100
c. Some Integer not 100
d. None of the above
Ans: b) illegal syntax for using return

Q3.
main()
{
int i;
float *pf;
pf = (float *)&i;
*pf = 100.00;
printf("n %d", i);
}a. Runtime error.

b. 100
c. Some Integer not 100
d. None of the above
Ans: d) 0

Q4.
main()
{
int i = 0xff ;
printf("n%d", i<<2); } a. 4 b. 512 c. 1020 d. 1024 Ans: c) 1020

Q5.
#d…

write a user defined generic malloc function.Inside this function you may call standard malloc function.The prototype of this function should be void malloc1(anything that you wish).

### guess no of apples

The servant reached the first gate and said, "May I go through to show the king my wonderful apples?" The guard replied, "You may if you give me half of your apples." The servant then said, "Fine but you have to give me back one apple." The guard agreed. The servant did this to the rest of the guards and finally met the king. The servant still had the same amount of apples that he had started with. How is this possible?

### where the man was fishing?

A man decided to go fishing and went to the sea. He used the best bait and best rod, but caught nothing for hours. Another man walked by and said, " That is a pretty useless spot to fish, nothing lives in there. "Where was the man fishing?

### birthday puzzle

One day Jenny celebrated her birthday. Two days later her older twin brother, Jerry, celebrated his birthday. How is this possible?

### finds a substring in a string and replaces

Write a function which finds a substring in a string and replaces all occurrences with another string.
Prototype of the function :
char* FindReplace(char* src, char* find, char* replace);

### Horse race

There are 25 horses and you need to figure out the three fastest horses by placing them into races. Assume there is no tie in the speed. There are five tracks so for each race, you can place five horses and figure out the relative rank among those five horses but you don't have the exact finishing time, i.e. there is no direct comparison between results from two different races. What's the minimum number of races you need to arrange in order to figure out the three fastest horses?

### Party Teaser

I was at a party with MS one evening where he got bored and started keeping track of the number of handshakes made by people. A person was called "odd person" if he made an odd number of handshakes, otherwise he was called "even person". After some time MS said to me, "Hey AD, do you know that there are an even number of odd persons?" I replied, "Big deal, MS. There will be always an even number of odd persons!" But still he seemed confused. Justify ...

### Jar's and pills problem.

You have 5 jars of pills. Each pill weighs 10 gram, except for contaminated pills contained in one jar, where each pill weighs 9 gm. Given a scale, how could you tell which jar had the contaminated pills in just one measurement?

### Guess my Birthday

My birthday is in January. What is the smallest number of yes/no questions you need to ask to guess the day of my birthday.

### How to reach from point A to point B

You have to get from point A to point B. You don’t know if you can get there. What would you do.

### [MS]excel labels

Excel labels its rows with letters. For example row 0 is labeled 'A', row 1 is labeled 'B', row 26 is labeled 'AA', and so on.

Design, and implement in C, an algorithm that will map any row number, such as 2842, into into its proper row designation. For instance row 2842, maps to the designation 'DEI'

### Coins on a table

There is a table on which a number of coins are placed. You also know that there are as many coins with Head up as many coins with Tail up. Now you have to divide the coins (number of coins is even) into two equal piles such that number of coins with Heads up and Tails up in either piles be the same. The catch is you are blind folded and you cannot determine the sides (for sure) if you are blinded

### Age of sons

There are two guys standing before a building with multiple floors.
First: "I have three children, the product of their ages is 36, can you guess their ages?"
Second: "No"
First: "The sum of their ages is equal to the number of floors in the opposite building, can you guess now?"
Second: "No"
First: "My youngest son is a very good dancer"
Second: "Yeah, I know now"
Assuming that both these guys are extremely intelligent and follow common-sense logic to find out the ages of first's children.

Source: IIT Roorkee

### second max elements of linked list

Given a single linked list of integers, write a function to find the 2nd largest element from the list in linear time without extra space. Test for all the test cases.

I know its easy. Just thought to share this question with others as it is asked in microsoft interview.

### check if one list is reverse of other

Given two linked list. We have to find that whether the data in one is reverse that of data in other. No extra space is to be used and traverse the lists only once

### find unique elements

Write, efficient code for extracting unique elements from a sorted list of array. e.g. (1, 1, 3, 3, 3, 5, 5, 5, 9, 9, 9, 9) -> (1, 3, 5, 9).
o(n)

And what if the elements are not in sorted order.

### Interview Q: given an array of numbers, return array of products of all other numbers (no division)

There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].
Solve it without division operator and in O(n) and constant space.

Input : [1, 2, 3, 4, 5]
Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]
= [120, 60, 40, 30, 24]

### distribute the gold coins

You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it?

### Truth and Lies

So we all know the famous question when a person has to find out which of the two paths lead to his destination and there are two guys sitting there, one of which always speaks the truth and the other always lies. What is the single question he can ask to reach his aim?
Ans: He asks to any one "What would the other guy say if I ask him the direction to my address?" and take the opposite of the answer he gets.

Similar question.
There are two ways (like previous question). One right and the other wrong. But there are 3 guys. One will always speak the truth or keep mum(if he does not know the answer). One will always lie or keep mum(if he does not know the answer). The third will never keep mum and may speak the truth or lie with equal probability. You can ask two questions. Find out your destination.
The "keep mum" clause has been added to provide more breadth to the kind of questions you may ask e.g. you can now ask him to tell you if Clinton actually had a hot affa…

### Truth or lie question

You are lost in a forest. The forest is between two villages. In villageA live only liars, they always lie. In village B people always tell the truth. You want to go to village B. Then you see a man from village A or B. You can ask him only one question.
Which question will you ask him to know for sure where village B is ?

### 100 passengers boarding airplane..figure out seating

100 passengers are boarding an airplane with 100 seats. Everyone has a ticket with his seat number. These 100 passengers boards the airplane in order. However, the first passenger lost his ticket so he just take a random seat. For any subsequent passenger, he either sits on his own seat or, if the seat is taken, he takes a random empty seat. What's the probability that the last passenger would sit on his own seat

Source: Stanford

### Sort an array of 0s, 1s and 2s

Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.

Example
Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}

### Point of intersection of 2 linked lists

Given pointers to the heads of two linked lists. They intersect at some element, and proceed as a single list there-onwards. Find the point of intersection in O(n).

There are 3 baskets. one of them have apples, one has oranges only and the other has mixture of apples and oranges. The labels on their baskets always lie. (i.e. if the label says oranges, you are sure that it doesn't have oranges only,it could be a mixture) The task is to pick one basket and pick only one fruit from it and then correctly label all the three baskets

### Find first non repeating character in a String

if input = "total" answer = "o"
if input = "tweetweer" answer = "r"
if input = " gnu " answer = ...

Approach - to do in O(n)

1. Parse the string character by character and populate a map with count of each character
2. parse the string again and lookup character in map and get the count, store the key returning 1 first as a potential answer
3. As a part of step2 also check if any character has a count > 1 in which case return the answer stored in step2 else return null

### cross the bridge

Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it’s only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes?

### classic hat problem

There are four man standing in front of a firing-squad. Two of them (nr.1 & 3) wear a black hat and two of them (nr.2 & 4) wear a white hat. They are all facing the same direction and between nr.3 and nr.4 stands a brick wall (see picture). So nr.1 can see nr.2 & 3, nr.2 sees nr.3, nr.3 sees only the wall and nr.4 doesn't see a thing. The men know that there are two white and two black hats.
The commander of the firing-squad is willing to let the men go if one of them can say what color hat he is wearing. The men are not allowed to talk. The only thing they may say is "I'm wearing a white/black hat". If one of the men knows which hat he is wearing he must tell it and all men will be free.
Which man knows 100% sure what color hat he's wearing?

### find odd one out??

You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you fine the ball that is heavier by using a balance and only two weighings?

### Reverse word's of a string in O(1) space.

Reverse the words of a string
Eg:: if string is GNU programs are the best
Output = best the are programs GNU

note :: You are not allowed to use extra space and do it in the best time complexity

### Village of Men cheating on wifes

Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and annoces that at least one husband has benn unfaithful. What happens?

### MS Question : Should i shoot you

Lets play a game of Russian roulette. You are tied to a chair and can,t get up.Here is the gun , six chambers all empty. Now I put two bullets in the gun and I put these bullets in the adjecent chambers. I close the barrel and spin it. I put the gun to your head and pull the trigger. Clik and the slot was empty. Now before we start the interview I want to pull the trigger one more time , which one do you prefer , that I spon the barrel first or that I just pull the trigger ?

### golden chain

A man has a gold chain with 7 links. he needs the service of a laborer for 7 days at a fee of one gold link per day. however, each day of work needs to be paid for separately. in other words, the worker must be paid each day after working and if the laborer is ever overpaid he will quit with the extra money. also he will never allow himself to be owed a link.

what is the fewest no of cuts to the chain to facilitate this arrangement and how does that guarantee payment?

### Cut a cake into two pieces

How do you cut a rectangular cake into two equal pieces when someone has already taken a rectangular piece from it?

The removed piece an be any size or at any place in the cake. You are only allowed one straight cut.

### Ant's on a triangle

There are 3 ants at 3 corners of a triangle, they randomly start moving towards another corner. What is the probability that they don’t collide?

### Min in a circular list

You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don’t know where the circular list begins

### Room with three bulbs

Imagine you are in a room with 3 switches. In an adjacent room there are 3 bulbs (all are off at the moment), each switch belongs to one bulb. It is impossible to see from one room to another. How can you find out which switch belongs to which bulb, if you may enter the room with the bulbs only once?

### FIFO queue using Stacks

You have two stacks available to you; now you have to implement a FIFO queue using the two stack's and support Enqueue and Dequeue operations in the best possible time complexity. You can assume that the Stack supports push(), pop(), peep() and size() opertions and they are available to you

### N Monks problem

There's a monastry of fifty monks that have taken a vow of silence. They go through the same routine every day. They wake up, pray. They go to lunch, their only meal of the day, were they all sit round a big circular table, and eat a simple meal. Then they go back to their rooms and pray. Then they fall asleep.

One day, the head monk of the area comes to visit. He's a bit different - he's allowed to talk and has a life outside the monastry. He tells them that there is currently a plague ravaging the land. People everywhere are dying. The disease manifests itself as red blotches on the forehead. The blotches are the only manifestation of the disease for three months, whereupon the next stage starts, a horribly painful death.

The head monk tells them that at least one of their midst will have the disease, probably more. Anybody with the disease should kill themselves, to save all of the pain and suffering. By killing themselves, they will restrict the movement of the disease…

### predict o/p

int main()
{

int i =2;
int c = (i!=0)?(i!=1)?(i!=2)?(-2):(-3):(-4):(-5);
printf("%d",c);
return 0;
}

suggest one data structure for storing a sparse polynomial of the form a+ bx +cx^2 +...nx^n when n is large ?given two such polynomials write an algorithm to add them and store them in a third polynomial.

### check for overflow

find the sum of two numbers and check for overflow.
both the numbers are within integer limit but their sum may exceed.

### number of bits altered to swap

find the number of bits needed to be altered in order to swap two numbers(integers).
ex:- a=15,b=7
swap it such that b=15

### count number of 1's

given a number you have to find number of 1's in its binary form.
ex:-5 = 101
output:-2

### count number of coins

Given a list of 3 coins, their values (1,3,5), and the total sum 11. Find the minimum number of coins the sum of which is 11 (we can use as many coins of one type as we want).

Hint: use dynamic programming

### find duplicates.

Given an array of size N in which every number
is between 1 and N, determine if there are any
duplicates in it. You are allowed to destroy the
array if you like.

### Card's with vowel and even numbers

There are 4 cards on a table. Each has a number on one side and a letter on the other. The cards show A,B,1 and 2. Which 2 cards would you turn over to test the rule that "All cards with a vowel on one side have an even number on the other"

### Measure 45 minutes with one match

You have two ropes of rough non-countinuous composition (in other words these ropes are not ideally uniform.) You know that each will take exactly half an hour to burn no matter which end is lit. How can you with only one match (which only sustains a flame for a few seconds) measure a time interval of 45 minutes...

### Rectangle intersect

Two rectangle is given with following data structure
rectangle {
int left_X;
int Left_X;
int right_X;
int Right_Y;
}
Two are in X-axis wise. How to find that they are intersected or not?

### dynamically allocates 2 dimensional array

Implement a function foo that dynamically allocates a 2 dimensional array of integers and returns it. The signature of the function is as under -
int **foo(int rows, int columns)

### getbits function in c

Implement a function getbits, that returns the(right adjusted) n bits that begin at position p of an integer. Assume bit position 0 is at the right end and that n and p are sensible positive values.

### Placing cigar's on circular table

Let's play a simple game. I have a circular table and an unlimited supply of identically shaped Cuban cigars. We each take turns placing a cigar on the table without disturbing any other cigars already there in the process and without overlapping any pair of cigars. The winner will be last person to successfully place a cigar on the table subject to the given restrictions. If I give you the option of going first, how would you play in order to win.

Hint -

- What are the features of a circle and how does this dictate your first move?

give it a try..

### Choose the correct door?

On the game show "Let's make a deal", Monty Hall (the host) walks up to a contestant and gives them \$100 unless they want to play "the three doors". They usually turn down the money and play "the three doors". Now behind one of the doors is an enormous cash prize, behind the other too are silly prizes such as a years supply of toilet paper or a goat. So Monty asks this same contestant to pick a door, which they do. Then, before opening the chosen door and revealing what's behind it, he opens one of the other doors which reveals one of the lesser prizes. Monty then gives this contestant the option of staying with their chosen door or switching to the other door which still remains closed. The contestant then decides what to do and is rewarded with whatever prize is behind the door they finally chose. So the question is, what is the probability to win if he switches?

### Welcome everybody

Dear friends, I'm almost back in the blogosphere as a consumer rather than as a producer.
I do have an interest in programming languages and strongly believe that the ability to work in multiple, different languages makes you a better programmer.
This blog is not for collection of problems and their solutions rather we can discuss solution or better say optimized solution to different problem which can be found only through discussion among bunch of techies..:)
so do contribute to this blog and you can contact me priyaranjan.nit@gmail.com