Friday 27 January 2012

Puzzles

Puzzle 1: Classic: If a bear walks one mile south, turns left and walks one mile to the east and then turns left again and walks one mile north and arrives at its original position, what is the color of the bear.
 
 


Puzzle 2: Given a rectangular (cuboidal for the puritans) cake with a rectangular piece removed (a size or orientation), how would you cut the remainder of the cake into two equal halves with one straight cut of a knife?

 

Puzzle 3: 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.

 

Puzzle 4: You have 8 balls. One of them is defective and weighs less than others. You have a balance to measure balls against each other. In 2 weighings how do you find the defective one?

 

Puzzle 5: Why is a manhole cover round?

 

Puzzle 6: How many cars are there in the USA?

 


Puzzle 7: You've got someone working for you for seven days and a gold bar to pay them. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker?

 


Puzzle 8: One train leaves Los Angeles at 15mph heading for New York. Another train leaves from New York at 20mph heading for Los Angeles on the same track. If a bird, flying at 25mph, leaves from Los Angeles at the same time as the train and flies back and forth between the two trains until they collide, how far will the bird have traveled?

 


Puzzle 9: You have two jars, 50 red marbles and 50 blue marbles. A jar will be picked at random, and then a marble will be picked from the jar. Placing all of the marbles in the jars, how can you maximize the chances of a red marble being picked? What are the exact odds of getting a red marble using your scheme?

 


Puzzle 10: Imagine you are standing in front of a mirror, facing it. Raise your left hand. Raise your right hand. Look at your reflection. When you raise your left hand your reflection raises what appears to be his right hand. But when you tilt your head up, your reflection does too, and does not appear to tilt his/her head down. Why is it that the mirror appears to reverse left and right, but not up and down?

 


Puzzle 11: 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?

 


Puzzle 12: If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?

 


Puzzle 13: You have a bucket of jelly beans. Some are red, some are blue, and some green. With your eyes closed, pick out 2 of a like color. How many do you have to grab to be sure you have 2 of the same?

 


Puzzle 14: There are four dogs/ants/people at four corners of a square of unit distance. At the same instant all of them start running with unit speed towards the person on their clockwise direction and will always run towards that target. How long does it take for them to meet and where?

 


Puzzle 15: You're given an array containing both positive and negative integers and required to find the sub-array with the largest sum (O(N) a la KBL). Write a routine in C for the above.

 


Puzzle 16: 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. [ I ended up giving about 4 or 5 different solutions for this, each supposedly better than the others ].

 


Puzzle 17: Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without making use of any floating point computations at all. [ This one had me stuck for quite some time and I first gave a solution that did have floating point computations ].

 


Puzzle 18: Among 12 identical looking golf balls there is one that is defective in weight. It is either heavier or lighter than the standard one. You have a balance. You can only weigh 3 times to find out which one is defective and whether it is heavier or lighter.

 


Puzzle 19: There are 3 glasses. The biggest one can hold 24 ounces. The medium one can hold 11 ounces and the smallest one can hold 5 ounces. Now you have 24 ounces of soft drink in the largest glass. Can you use just these 3 glasses to make the largest glass contain 12 ounces of soft drink by pouring soft drink from one glass to another?
 



Puzzle 20: There are 4 women who want to cross a bridge. They all begin on the same side. You have 17 minutes to get all of them across to the other side. It is night. There is one flashlight. A maximum of two people can cross at one time. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each woman walks at a different speed. A pair must walk together at the rate of the slower woman's pace.
Woman 1: 1 minute to cross
Woman 2: 2 minutes to cross

Woman 3: 5 minutes to cross

Woman 4: 10 minutes to cross

For example if Woman 1 and Woman 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Woman 4 then returns with the flashlight, a total of 20 minutes have passed and you have failed the mission. What is the order required to get all women across in 17 minutes? Now, what's the other way?

 


Puzzle 21: If you have two buckets, one with red paint and the other with blue paint, and you take one cup from the blue bucket and poor it into the red bucket. Then you take one cup from the red bucket and poor it into the blue bucket. Which bucket has the highest ratio between red and blue? Prove it mathematically.

 


Puzzle 22 : You have 4 jars of pills. Each pill is a certain weight, except for contaminated pills contained in one jar, where each pill is weight + 1. How could you tell which jar had the contaminated pills in just one measurement?

 


Puzzle 23: The SF Chronicle has a word game where all the letters are scrambled up and you have to figure out what the word is. Imagine that a scrambled word is 5 characters long:
> How many possible solutions are there?
> What if we know which 5 letters are being used?
> Develop an algorithm to solve the word.

 




Puzzle 24: Imagine a disk spinning like a record player turn table. Half of the disk is black and the other is white. Assume you have an unlimited number of color sensors. How many sensors would you have to place around the disk to determine the direction the disk is spinning? Where would they be placed?

 


Puzzle 25: Imagine an analog clock set to 12 o'clock. Note that the hour and minute hands overlap. How many times each day do both the hour and minute hands overlap? How would you determine the exact times of the day that this occurs?

 


Puzzle 26:Pairs of primes separated by a single number are called prime pairs. Examples are 17 and 19. Prove that the number between a prime pair is always divisible by 6 (assuming both numbers in the pair are greater than 6). Now prove that there are no 'prime triples.'

 


Puzzle 27:There is a room with a door (closed) and three light bulbs. Outside the room there are three switches, connected to the bulbs. You may manipulate the switches as you wish, but once you open the door you can't change them. Identify each switch with its bulb.

 


Puzzle 28:Imagine you are standing in front of a mirror, facing it. Raise your left hand. Raise your right hand. Look at your reflection. When you raise your left hand your reflection raises what appears to be his right hand. But when you tilt your head up, your reflection does too, and does not appear to tilt his/her head down. Why is it that the mirror appears to reverse left and right, but not up and down?

 


Puzzle 29:Three people check into a hotel. They pay $30 to the manager and go to their room. The manager finds out that the room rate is $25 and gives $5 to the bellboy to return. On the way to the room the bellboy reasons that $5 would be difficult to share among three people so he pockets $2 and gives $1 to each person.Now each person paid $10 and got back $1. So they paid $9 each, totalling $27. The bellboy has $2, totalling $29.Where is the remaining dollar?

 


Puzzle 30: A line of 100 airline passengers is waiting to board a plane. they each hold a ticket to one of the 100 seats on that flight. (for convenience, let's say that the nth passenger in line has a ticket for the seat number n.) Unfortunately, the first person in line is crazy, and will ignore the seat number on their ticket, picking a random seat to occupy. all of the other passengers are quite normal, and will go to their proper seat unless it is already occupied. if it is occupied, they will then find a free seat to sit in, at random. What is the probability that the last (100th) person to board the plane will sit in their proper seat (#100)?

 


Puzzle 31: 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. What state are the doors in after the last pass? which are open which are closed?

 


Puzzle 32: 100 fogcreek programmers are lined up in a row by an assassin. the assassin puts red and blue hats on them. they can't see their own hats, but they can see the hats of the people in front of them. the assassin starts in the back and says "what color is your hat?" the fogcreek programmer can only answer "red" or "blue." the programmer is killed if he gives the wrong answer; then the assassin moves on to the next programmer. the programmers in front get to hear the answers of the programmers behind them, but not whether they live or die. they can consult and agree on a strategy before being lined up, but after being lined up and having the hats put on, they can't communicate in any way other than those already specified. what strategy should they choose to maximize the number of programmers who are guaranteed to be saved?
 



Puzzle 33: Four men are lined up on some steps. They are all facing in the same direction. A wall seperates the fourth man from the other three.
So to summarise :-
Man 1 can see men 2 and 3.

Man 2 can see man 3.

Man 3 can see none of the others.

Man 4 can see none of the others.

The men are wearing hats. They are told that there are two white hats and two black hats. The men initally don't know what colour hat they are wearing. They are told to shout out the colour of the hat that they are wearing as soon as they know for certain what colour it is.

They are not allowed to turn round.

They are not allowed to talk to each other.

So the question is -

Who is the first person to shout out and why?

 


Puzzle 34: If you are throwing the suitcase out of a floating boat into the water:
If it sinks: The water level will rise ever so slightly if the volume of the suitcase is greater than it's weight. If the volume is less than the weight, the water level will go down when the suitcase sinks. This is because the suitcase's weight would cause it to make the boat a little lower since it has to displace as much water as the suitcase weighs.
If the suitcase floats: The water level will remain the same. since, the water will be displaced enough to account for the weight of the suitcase, either in the boat or by itself.
If the suitcase is being thrown away on a cruise ship: the water level will stay the same.

 


Puzzle 35: An analog clock reads 3:15. What is the angle between the minute hand and hour hand?

 


Puzzle 36: Imagine an analog clock set to 12 o'clock. Note that the hour and minute hands overlap. How many times each day do both the hour and minute hands overlap? How would you determine the exact times of the day that this occurs?

 


Puzzle 37: Imagine a disk spinning like a record player turn table. Half of the disk is black and the other is white. Assume you have an unlimited number of color sensors. How many sensors would you have to place around the disk to determine the direction the disk is spinning? Where would they be placed?

 


Puzzle 38:Two boys sell apples. Each sells thirty apples a day. The first boy sells his apples at two for five rupees (and therefore earns Rs 75 per day). The second boy sells his apples at three for five rupees (and therefore earns Rs 50 per day). The total received by both boys each day is therefore Rs 125. One day, the first boy is sick, and the second boy takes over his apple selling duties. To accommodate the differing rates, the boy sells the sixty apples at five for Rs 10. But selling sixty apples at five for Rs 10 yields only Rs 120 earnings at the end of the day. What happened to the other 5 rupees?

 


Puzzle 39: While a red mark was placed on the forehead of each of three blindfolded women seated facing each other in a circle, they were told that the mark might be either red or white. Upon removal of the blindfolds, each was to raise her hand if she saw at least one red mark, and then to take it down if she could logically deduce the color of her own mark. All three hands were quickly raised, but then one of them lowered her hand. How did she know?

 


Puzzle 40: Potatoes are made up of 99% water and 1% "potato matter." Chaitu bought 100 pounds of potatoes and left them outside in the sun for a while. When he returned, he discovered that the potatoes had dehydrated and were now only made up of 98% water. How much did the potatoes now weigh?

 


Puzzle 41: If a boy and a half can eat a hot dog and a half in a minute and a half, how many hot dogs can six boys eat in six minutes?

 


Puzzle 42: An explorer wishes to cross a barren desert that requires 6 days to cross, but one man can only carry enough food for 4 days. What is the fewest number of other men required to help carry enough food for him to cross, the constraint is that each man should survive?

 


Puzzle 43: Grass grows in a field at some rate r, where r is the units of grass grown per day. It is known that if 10 sheep are turned out in the field, the grass will be gone in 20 days. On the other hand, if 15 sheep are turned out in the field, the grass will be gone in 10 days. If 25 sheep are turned out in the field, when will the grass be gone?

Some FAQs on C & Data Structure

  • Ques 1: How do you reverse a singly linked list? How do you reverse a doubly linked list? Write a C program to do the same.
  • Ques 2: Given only a pointer to a node to be deleted in a singly linked list, how do you delete it.
  • Ques 3: How do you sort a linked list? Write a C program to sort a linked list.
  • Ques 4: How to declare a structure of a linked list?
  • Ques 5: Write a C program to implement a Generic Linked List.
  • Ques 6: How do you reverse a linked list without using any C pointers?
  • Ques 7:How would you detect a loop in a linked list? Write a C program to detect a loop in a linked list.
  • Ques 8:How do you find the middle of a linked list? Write a C program to return the middle of a linked list.
  • Ques 9:If you are using C language to implement the heterogeneous linked list, what pointer type will you use?
  • Ques 10: How to compare two linked lists? Write a C program to compare two linked lists
  • Ques 11: How to create a copy of a linked list? Write a C program to create a copy of a linked list.
  • Ques 12: Write a C program to free the nodes of a linked list.
  • Ques 13: Can we do a Binary search on a linked list?
  • Ques 14: Write a C program to return the nth node from the end of a linked list.
  • Ques 15: How would you find out if one of the pointers in a linked list is corrupted or not?
  • Ques 16: Write a C program to insert nodes into a linked list in a sorted fashion.
  • Ques 17:Write a C program to remove duplicates from a sorted linked list.
  • Ques 18: How to read a singly linked list backwards?
  • Ques 19: How can I search for data in a linked list?
  • Ques 20: What is the difference between a linked list and Array?
  • Ques 21: Implement a linked list. Why did you pick the method you did?
  • Ques 22: Implement an algorithm to sort a linked list. Why did you pick the method you did? Now do it in O(n) time.
  • Ques 23: Given two sorted linked lists, write a function to merge them into one.
  • Ques 24: Delete an element from a doubly linked list.
  • Ques 25: Find the nth node from the end of a singly link list in a single pass.
 
C Functions Implementation Questions
  • Ques 1: Write your own C program to implement the atoi() function.
  • Ques 2: Implement the memmove() function. What is the difference between the memmove() and memcpy() function?
  • Ques 3: Write C code to implement the strstr() (search for a substring) function.
  • Ques 4: Write your own printf() function in C.
  • Ques 5: Implement the strcpy() function.
  • Ques 6: Implement the strcmp(str1, str2) function.
  • Ques 7: Implement the substr() function in C.
  • Ques 8: Write your own File copy() function.
  • Ques 9: Write C programs to implement the toupper() and the isupper() functions.
  • Ques 10: Write a C program to implement your own strdup() function.
  • Ques 11: Write a C program to implement the strlen() function.
  • Ques 12: Write your own strcat() function
  • Ques 10: Write a C program to implement your own strdup() function.
  • Ques 11: Write a C program to implement the strlen() function.
  • Ques 12: Write your own strcat() function
  
C Programming Questions
 
  • Ques 1: Right a program to implement malloc.
  • Ques 2: Write a C program to swap two variables without using a temporary variable .
  • Ques 3: What is the 8 queens problem? Write a C program to solve it.
  • Ques 4: Write a C program to print a square matrix helically.
  • Ques 5: Write a C program to reverse a string.
  • Ques 6: Write a C program to reverse the words in a sentence in place.
  • Ques 7: Write a C program generate permutations.
  • Ques 8: Write a C program to calculate pow(x,n).
  • Ques 9: Write a C program which does wildcard pattern matching algorithm.
  • Ques 10: How do you calculate the maximum subarray of a list of numbers?
  • Ques 11: How to generate fibonacci numbers? How to find out if a given number is a fibonacci number or not? Write C programs to do both.
  • Ques 12: Solve the Rat In A Maze problem using backtracking.
  • Ques 13: What Little-Endian and Big-Endian? How can I determine whether a machine's byte order is big-endian or little endian? How can we convert from one to another?
  • Ques 14: Write C code to solve the Tower of Hanoi problem.
  • Ques 15: Write C code to return a string from a function.
  • Ques 16: Write a C program which produces its own source code as its output.
  • Ques 17: Write a C progam to convert from decimal to any base (binary, hex, oct etc...).
  • Ques 18: Write C code to check if an integer is a power of 2 or not in a single line?
  • Ques 19: Write a C program to find the GCD of two numbers.
  • Ques 20: Finding a duplicated integer problem.
  • Ques 21: Write code to remove duplicates in a sorted array.
  • Ques 22: How do you initialize a pointer inside a function?
  • Ques 23: Write C code to dynamically allocate one, two and three dimensional arrays (using malloc()).
  • Ques 24: How would you find the size of structure without using sizeof().
  • Ques 25: Write a C program to multiply two matrices.
  • Ques 26: Write a C program to check for palindromes.
  • Ques 27: Write C code to implement the Binary Search algorithm.
  • Ques 28: Write code to add two polynomials.
  • Ques 29: Write a program to add two long positive numbers (each represented by linked lists).
  • Ques 30: How do you compare floating point numbers?
  • Ques 31: Is there something we can do in C but not in C++?
  • Ques 32: How to swap the two nibbles in a byte ?
  • Ques 33: How to scan a string till we hit a new line using scanf()?
  • Ques 34: How do you get the line numbers in C?

Thursday 26 January 2012

Write a C program to print the Fibonacci Series upto to the first 'n' terms

#include<stdio.h>
#include<conio.h>
void main()
{
    int f=0, s=1, t, n, ct;
    clrscr();
    printf("Enter the value of 'n': ");
    scanf("%d",&n);
    printf("\nFibonacci series:\n");
    printf("%5d%5d", f, s);
    ct=3; //becoz we already displayed 2 values and we r going the third value
    while(ct<=n)
    {
        t=f+s;
        printf("%5d", t);
        f=s;
        s=t;
        ct++;
    }
    getch();
}

Write a C program to genarate all the prime numbers between 1 to 'n'

#include<stdio.h>
#include<conio.h>
void main()
{
    int st, n, x, flag;
    clrscr();
    printf("Enter the value of 'n': ");
    scanf("%d", &n);
    for(st=1; st<=n; st++)
    {
        x=2; flag=0;
        while(x<=st/2)
        {
            if(st%x==0)
            {
                flag=1; break;
            }
            x++;
        }
        if( flag==0)
        printf("%5d", st);
    }
    getch();
}

Write a C program to calculate the following Sum:- sum=1-x2/2! +x4/4!-x6/6!+x8/8!-x10/10!

#include<stdio.h>
#include<conio.h>
#include<math.h>
void main()
{
    int ct, ft;
    float sum=0, x, power, fact;
    clrscr();
    printf("--------PROGRAM FOR SUM OF EQ. SERIES------");
    printf("\n\nEnter the value of X : ");
    scanf( "%f", &x);
    ct=0;
    for(power=0; power<=10; power=power+2)
    {
        fact=1; for(ft=power; ft>=1; ft--)
        fact =fact* ft;
        sum=sum+(pow(-1,ct)*(pow(x,power)/fact)); //EQ. FOR SUM SERIES
        ct++;
    }
    printf("\n Sum : %f",sum);
    getch();
}