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