 |
| Logical Questions For Interview preparations |
1)Given a rectangular (cuboidal for the puritans) cake with a rectangular
piece removed (any size or orientation), how would you cut the remainder of the
cake into two equal halves with one straight cut of a knife ?
Answer:
The cut (plane) should pass through the center of the two rectangles: the
outer cake and the inner hollow area. Since any plane passing through the
center of the cuboid will divide the volume in two halves, both the cake and
hollow area are divided into two equal halves.
2)How many points are there on the globe where by walking one mile south,
one mile east and one mile north you reach the place where you started.
Answer:
The answer is "many points". The set of such points is given as
{North pole, special circle}.
From north pole, walking one mile south followed by one mile east still
keeps you one mile south of North pole.
The special circle consists of a set of points defined as follows. Let's
say you were to locate a spot near the South Pole where the circular distance
"around" the Earth's North-South axis is 1 mile. The path of such a
journey would create a circle with a radius of approximately 840.8 feet
(because C=2.r.pi). Call this point X. Now consider another point Y one mile
north of X. The special circle is the circular path around North-South axis
going through Y. If you begin you journey from any point (say Y1) on this
special circle, and travel one mile south, you get to a point (say X1) on the
circle of point X. Now one mile east will bring you back to X1, because
circumference of circle of X is 1 mile. Then one mile North brings you back to
Y1. (Answer supplied by Kristie Boman)
3)In a X's and 0's game (i.e. TIC TAC TOE) if you write a program for this
give a fast way to generate the moves by the computer. I mean this should be
the fastest way possible.
Answer:
The answer is that you need to store all possible configurations of the
board and the move that is associated with that. Then it boils down to just
accessing the right element and getting the corresponding move for it. Do some
analysis and do some more optimization in storage since otherwise it becomes
infeasible to get the required storage in a DOS machine.
4)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.
Answer:
All three should move in the same direction - clockwise
or anticlockwise. Probability is 1/4.
5)There are 4 men 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 man walks at a different speed. A pair must walk together
at the rate of the slower mans pace.
Answer:
Man 1:1 minute to cross
Man 2: 2 minutes to cross
Man 3: 5 minutes to cross
Man 4: 10 minutes to cross
1 and 2 cross together. 1 comes back. then 3 and 4 cross. 2 comes back.
then 1 and 2 cross. Total time is 2+1+10+2+2 = 17.
6)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?
Answer:
Take one pill from first, two from second, three from third and so on.
Total pills are n(n+1)/2 and should weigh 10n(n+1)/2. If it weighs x gm less
than that then the x'th jar is contaminated, since we took x pills from that
jar which weighed 1 gm less.
7)One train leaves Los Angeles at 15 MPH 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?
Answer:
If distance is X miles between NY and LA, then it takes X/(15+20) hours for
the trains to collide, and bird will have travelled 25X/(15+20) = 5X/7 miles in
that time.
8)Imagine that you have 26 constants, labelled A through Z. Each constant
is assigned a value in the following way: A = 1; the rest of the values equal
their position in the alphabet (B corresponds to the second position so it
equals 2, C = 3, etc.) raised to the power of the preceeding constant value.
So, B = 2 ^ (A's value), or B = 2^1 = 2. C = 3^2 = 9. D = 4^9, etc., etc. Find
the exact numerical value to the following equation:
Answer:
(X - A) * (X - B) * (X - C) * ... * (X - Y) * (X - Z)
Answer is 0, because (X-X) is present in the product.
9)You have 12 balls. All of them are identical except one, which is either
heavier or lighter than the rest - it is either hollow while the rest are
solid, or solid while the rest are hollow. You have a simple two-armed scale,
and are permitted three weighings. Can you identify the odd ball, and determine
whether it is hollow or solid.
Answer:
Let the balls be numbered 1 to 12. Firstly, put 1-4 on
one side and 5-8 on other side. If both are equal then one of 9-12 is odd. Then
second try, weigh 9-10 vs 1-2, if equal, one of 11-12 is bad, else 9-10 is bad.
Testing which one is bad can be done by (third try) weighing 11 or 9,
respectively, with good ball 1. It also gives whether the odd ball is heavy or
light.
10)Write a routine to draw a circle (x ** 2 + y ** 2 = r
** 2) without making use of any floating point computations at all.
Answer:
The basic idea is to draw one quadrant and replicate it to other four
quadrants. Assuming the center is given as (x,y) and radius as r units, then
start X from (x+r) down to (x) and start Y from y up to (y+r). In the
iteration, keep comparing is the equation is satisfied or not within an error
of one unit for x and y. If not then re-adjust X and Y.
11)Given only putchar (no sprintf, itoa, etc.) write a routine putlong that
prints out an unsigned long in decimal.
Answer:
void putlong(unsigned long x)
{
// we know that 32 bits can have 10 digits. 2^32 = 4294967296
for (unsigned long y = 1000000000; y > 0; y /= 10) {
putchar( (x / y) + '0');
x = x % y;
}
}
12)Give a one-line C expression to test whether a number is a power of 2.
[No loops allowed - it's a simple test.]
Answer:
if (x && !(x & (x-1)) == 0)
13)What are the different ways to say, the value of x can be either a 0 or
a 1.
Answer:
Apparently the if then else solution has a jump when written out in
assembly.
if (x == 0)
y=0
else
y =x
There is a logical, arithmetic and a datastructure soln to the above
problem.
12)Give a fast way to multiply a number by 7.
Answer:
Multiply by 8 (left shift by 3 bits) and then subtract the number.
(x << 3) - x
13)Write a function that returns the factorial of a number.
Answer:
This is a typical, can-you-program warm-up question. Example 1 shows the
iterative and recursive solutions. Notice that in both solutions, I check the
input values and boundary conditions. Factorials of negative numbers are
undefined, and the factorial of both 0 and 1 are 1. The functions in Example 1
handle these cases correctly, and they initialize all variables.
14)Write a function that computes the nth number in the Fibonacci sequence.
Answer:
Example 2 contains both the iterative and recursive solutions. The
iterative version maintains variables to hold the last two values in the
Fibonacci sequence, and uses them to compute the next value. Again, boundary
conditions and inputs are checked. The 0th number in the Fibonacci sequence is
defined as 0. The first number in the sequence is 1. Return -1 if a negative
number is passed.
The recursive version of the Fibonacci function works correctly, but is
considerably more expensive than the iterative version. There are, however,
other ways to write this function recursively in C that are not as expensive.
For instance, you could maintain static variables or create a struct to hold
previously computed results.14
15)Write an implementation of strlen().
Answer:
Given a char pointer, strlen() determines the number of chars in a string.
The first thing that your strlen() implementation ought to do is to check your
boundary conditions. Don't forget the case where the pointer you are given is
pointing to an empty string. What about the case where the pointer is equal to
NULL? This is a case where you should state your assumptions. In many
implementations, the real strlen() doesn't check to see if the pointer is NULL,
so passing a NULL pointer to strlen() would result in a segmentation fault.
Making it clear to your interviewer that you are aware of both of these
boundary conditions shows that you understand the problem and that you have
thought about its solution carefully. Example 3 shows the correct solution.
16)Switch the integer values stored in two registers without using any
additional memory.
Answer:
To swap the values, you can carry out the following instructions:
Reg_1 = Reg_1 + Reg_2;
Reg_2 = Reg_1 - Reg_2;
Reg_1 = Reg_1 - Reg_2;
17)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).
Answer:
Contribute by John Foley:
#include <stdio.h>
int main() {
//--- constant data
const int arr[] = {1, 1, 2, 4, 4,
7, 8, 9, 14, 14, 20};
const size_t arrlen =
sizeof(arr)/sizeof(arr[0]);
int i;
for(i=0; i<arrlen; i++) {
//--- if this is the first
one, print no matter what
// if not, skip if we just printed the same
number
if(i && arr[i] ==
arr[i-1])
continue;
//--- print this number, update last
item
printf("%d\n",
arr[i]);
}
return 0;
}
18)(a-1) xor a == 0 - What does this do?
Answer:
It creates a mask over both the trailing zeros of an integer and the first
set bit from right. For example if a is 10101100 then result is 00000111.
On the other hand, (a-1) AND a == 0 is different. It tests whether 'a' is a
power of 2. Actually, it tests if a has only one instance of 1 bit, which is
same as 'a' being power of 2. For example, if a is 00010000 then result is 0,
and if a is 01001000 then result is 01000000 which is not 0.
19)What is a balanced tree
Answer:
given a linked list with the following property node2 is left child of
node1, if node2 < node1 else, it is the right child.
O P
|
|
O A
|
|
O B
|
|
O C
How do you convert the above linked list to the form without disturbing the
property. Write C code for that.
O P | | O B / / / O ? O ?
determine where do A and C go
20)What does the term cast refer to? Why is it used?
Answer:
A Casting is a mechanism built into C that allows the programmer to force
the conversion of data types. This may be needed because most C functions are
very particular about the data types they process. A programmer may wish to
override the default way the C compiler promotes data types.
21)Increment the variable next three different ways.
Answer:
next = next + 1;
next++;
and
next += 1;
22)Specify a C loop with the test at the bottom.
Answer:
next = 0; /* setup */
do { printf("Hello"); /* body */ next++; /* update */ } while (
next < max); /* test */
23)In a loop, what is the difference between a break and continue
statement?
Answer:
The break terminates the loop. The continue branches immediately to the
test portion of the loop.
24)What does a break statement do? Which control structures use it?
Answer:
The break statement unconditionally ends the execution of the smallest
enclosing while, do, for or switch statement.
25)In a loop, what is the difference between a break and continue
statement?
Answer:
The break terminates the loop. The continue branches immediately to the
test portion of the loop.
26)What is the switch statement?
Answer:
It is C's form of multiway-conditional (a.k.a case statement in Pascal).
27)What is the difference between a variable definition and a variable
declaration?
Answer:
A definition tells the compiler to set aside storage for the variable. A
declaration makes the variable known to parts of the program that may wish to
use it. A variable might be defined and declared in the same statement.
28)What is the purpose of a function prototype?
Answer:
A function prototype tells the compiler to expect a given function to be
used in a given way. That is, it tells the compiler the nature of the
parameters passed to the function (the quantity, type and order) and the nature
of the value returned by the function.
29)What is type checking?
Answer:
The process by which the C compiler ensures that functions and operators
use data of the appropriate type(s). This form of check helps ensure the
semantic correctness of the program.
30)List C's storage classes and what they signify.
Answer:
static - Variables are defined in a nonvolatile region of memory such that
they retain their contents though out the program's execution.
register - Asks the compiler to devote a processor register to this
variable in order to speed the program's execution. The compiler may not comply
and the variable looses it contents and identity when the function it which it
is defined terminates.
extern - Tells the compiler that the variable is defined in another module.
volatile - Tells the compiler that other programs will be modifying this
variable in addition to the program being compiled. For example, an I/O device
might need write directly into a program or data space. Meanwhile, the program
itself may never directly access the memory area in question. In such a case,
we would not want the compiler to optimize-out this data area that never seems
to be used by the program, yet must exist for the program to function correctly
in a larger context.