Problem 26 Assume
that two robots land from two different flights with the help of parachutes (at
different points) on an infinite plane. Each robot leaves its parachutte on
landing and goes in search of the other robot. The problem is to write a
program which will be executed by both the robots for rendevezvous.
You have the following
instructions at your disposal to write the program:
• Step
L - makes the robot take one step towards left.
• Step
R - makes the robot take one step towards right.
• Goto
label - jump to the label.
• When
P then [one instruction].
P is a predicate which will be true when a robot
senses a parachute. It will be true as long as the robot is near it. The moment
it takes a step towards left or right after sensing it, then P will become
false. As part of ’if’ statement one can execute one instruction which could be
(1) or (2) or (3)
Write a
program to help the robots to meet. Make your own assumptions and justify them.
Remember that the same program needs to be executed by both robots.
Problem 27 Given
the values of two nodes in a binary search tree, write a C program to find the
lowest common ancestor. You may assume that both values already exist in the
tree. The function prototype is as follows:
int FindLowestCommonAncestor(node* root,int
value1,int value)
For example, given the tree
20
/ \
8 22
/ \
4 12
/ \
10 14
and 4 and 14 as input, the function should return 8. Here
the common ancestors of 4 and 14, are {8,20};
8 is the lowest of them.
Problem 28 Given
an array of 2n elements in which n elements are same and the remaining n elements are all different, write a C
program to find out the value of the n repeated
elements. The elements appear in arbitrary order.
Problem 29 You are given two
arrays, A and B. Array A contains all elements of the array B, and one extra element. Find the value of the
extra element.
Bonus: Solve the problem without
using relational operators (<, >, etc).
Problem 30 The distance between cities A
and B is 1000 km. We have 3000 bananas in city A, and an elephant that can
carry at most 1000 bananas at once. The elephant must eat a banana every 1km;
it cannot go furhter if it runs out of the banana supply. What is the maximum
number of bananas that can be transferred to the city B?
Problem 31 Assume
memory is divided into blocks starting at addrass 0 and of size N which is a power of 2. The blocks may
be words, doublewords, pages, and so on. Given a starting address a and a length l, determine whether or not the address range from [a,a + l − 1] crosses a block boundary. The quantities a and l are unsigned and any values that fit in a register are possible.
Pictorially:
|---N------|----N-----|----N-------|
+----------+----------+---- ... ---+----------+
| | | | |
+----------+----------+---- ... ---+----------+
^
|-----L-----|
|
|
A
Write a C function which test
whether a + l+ crosses a block boundary. Bonus: do not use division or modulo
operators.
Problem 32 Write an efficient C function
that deletes characters from a string. The function shall have the prototype void RemoveChars(char str[], char remove[]);
where any character existing in remove must be deleted from str.
For example, given a str of "Battle of
the Vowels:Hawaii" and remove of "aeiou", the function should
transform str to "Bttl f th Vwls:Hw".
Justify any design decisions you make and discuss the efficiency of your
solution.
Problem 33 Write
an algorithm to check whether a given unsigned number is a multiple of 3, without using division and modulo operators.
34 Prove
that n(n + 1)(2n + 1) is
divisible by 6, for any n > 0.
Problem 35 Given
an 8x8 chessboard, calculate:
•
The number of subsquares in the board.
•
The number of subrectangles in the board.
Note that rectangles are
restricted to having different width and height.
Problem 36 Describe
the stepwise procedure for subtracting mixed fraction 8
. Note: This is not a test of one’s analytical skill, it’s just to
see how many people do it the easier way.
. Note: This is not a test of one’s analytical skill, it’s just to
see how many people do it the easier way.
Problem 37 Consider
an array containing positive and negative integers. You have to find out the
maximum a) sum, b) product possible by adding / multiplying n consecutive integers in the array,
with n <= array size. Also find
the starting index of the sequence.
Problem 38 Given two sorted linked lists, l1 and l2, write a C program to compute their intersection l1∩ l2.
Problem 39 Propose
a data structure that supports in O(1)
time all of the following operations: Push, Pop, and FindMin which
returns the smallest element present in the stack.
Problem 40 A
man has two cubes on his desk. Every day he arranges both cubes so that the
front faces show the current day of the month. What numbers are on the faces of
the cubes to allow this?
Problem 41 Given 6 match-sticks of
equal length, you are asked to form 4 equilateral triangles. You are not allowed
to break, split or bend the sticks.
Problem 42 Say
we have a data structure as follows:
enum { RED,BLUE,GREEN}; struct Ball
{ /*...*/ int color; } ;
int ColorOfBall(Ball b)
{ return b.color;
}
Ball arr[SIZE];
The array arr consists of balls of with one of the three colours. Sort
the array in such a way that all the red balls come first, followed by blue and
then green. The restriction is that call to function ColorOfBall very costly, and it has to be used as little as
possible. In other words, find a solution with the least number of calls to the
function ColorOfBall.
43 Propose
a data structure that holds elements from 0 to n − 1 and supports all of
the following operations in O(1)
time: initialization, insertion of an element, deletion of an element, finding
an element, deleting all elements.
[Note: I seem to remember seeing this as an exercise in one of the
Knuth’s books.]
Problem 44 Given
13 balls, how would you arrange them in 9 lines, such that there are 4 balls in
each line? You can assume that the lines are arranged in 2-D space and that a
ball cannot be placed on top of another ball.
Bonus: if you
find that too easy, and have loads of time to kill, then how about arranging 22
balls in 21 lines of 4 ? Problem 45 Write
a C function int AddOvf(int* result, int a, int b)
which returns 0 and places the
sum a+b into *result if the addition can be performed without overflow.
Otherwise (in the case of overflow), the function returns -1. You are not allowed to cast integers to long to
check for the overflow.
Problem 46 Write a C function that
rotates right an unsigned integer by n bits.
Problem 47 A
skier must decide every day she goes skiing whether to rent or buy skis, unless
or until she decides to buy them. The skier does not know how many days she
will go on skiing before she gets tired of this hobby. Suggest a strategy for
the skier minimizing her cost, given the cost of rent is 1 unit, and the cost
to buy the skis is B units where
Problem 48 Can you explain the
behaviour of the following C program?
int main()
{ float f=0.0f; int i;
for(i=0;i<10;i++)
f += 0.1 f; if(f==1.0f)
printf("f is 1.0 f\n");
else
printf("f is NOT 1.0 f\n");
return 0 ;
}
Problem 49 You need to write a
simple macro CHAR(x) which takes a character x
and converts it into ASCII value of x:
printf("%c",CHAR(a)) ==> a
printf("%c",CHAR(X)) ==> X 50 Here is a small one to drive
away the afternoon siesta: consider a point P(n,n) in the cartesian co-ordinate
system. A robot has to start from the origin and reach this point. The only
steps the robot can take are 1 unit right or 1 unit up. How many different
paths can the robot take to point P?
Is there an optimal path to point P ( both up and right steps incur the same
cost)?
Problem 51 How
could you prevent a class from being used as a base class in C++? For example:
consider some class ABC. I would like the user to create objects of class ABC
but prevent him from deriving classes from ABC and creating objects of the
derived class.
Problem 52 A
multiple choice test has 15 questions and 4 choices for each answer. Each
question has only one answer correct. In how many ways can the 15 questions be
answered so that:
• Exactly
3 answers are correct
• Atleast
3 answers are correct
Problem 53 What does the following
chunk of code do?
cwd
xor ax, dx ; ax := ax xor dx sub ax, dx ; ax :=
ax - dx
cwd converts
a 16-bit word into sign-extended 32-bit double word stored in dx:ax registers. Problem 54 What is the smallest / largest
possible number of friday 13ths in a year?
Problem 55 Write
a recursive function which generates the power set of a given set. The set is
passed to the function as a string, and the function should print the subsets
as strings.
Example: given
"abc", the function should print
(the
empty string, encode it somehow), a, b, ab, c, ac,
bc, abc.
Problem 56 Bangla
numbers normally use ’kuti’ (10000000), ’lakh’ (100000), ’hajar’ (1000) ,
’shata’ (100) while expanding and converting to text. You are going to write a
program to convert a given number to text with them.
The input file may contain
several test cases. Each case will contain a non-negative number ≤
999999999999999. For each input case, you have to output a line starting with
the case number with four digits adjustment, followed by the converted text.
Sample Input
------------
23764
45897458973958
Sample Output
-------------
1. 23 hajar 7 shata 64
2. 45 lakh 89 hajar 7 shata 45 kuti 89 lakh 73 hajar
9 shata 58
No comments:
Post a Comment
Hi