Problem 57 Suppose that there are 101 players entered in a ”single elimination” tennis tournament. In such a tournament any player who loses a match must drop out, and every match ends in a victory for some player - there are no ties. In each round of the tournament, the players remaining are matched into as many pairs as possible, but if there is an odd number of players left, someone receives a bye (which means an automatic vitory for this player in this round). Enough rounds are played until a single player remains who wins the tournament. How many matches are played in total?
Problem 58 The ”parity” of a number refers to whether it contains an odd or even number of 1-bits. The number has ”odd parity”, if it contains odd number of 1-bits and is ”even parity”, if it contains even number of 1-bits. Write a C function to find the parity of an unsigned integer.
Problem 59 Calculate: ab mod m for large values of a, b and m using an efficient algorithm. Value ranges: a ∈ [0,2147483647], b ∈ [2147483647], m ∈ [1,46340].
Problem 60 Lets assume we have a rat maze as represented by the following n×m matrix where S is the start location and F is the end location.
| S | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 1 | F |
The idea (as with any rat maze) is to traverse from S to F. The matrix can have only 0 and 1 as values. 1 represents a path that can be taken and 0 represents a blocked path. We can make the following assumption: S will always be (0,0) and F will always be (n,m).
How to find the shortest (or longest) path from S to F without actually traversing all the possible paths?
Problem 61 If two of the below statements are false, what chance is there that the egg came first?
1. The chicken came first.
2. The egg came first.
3. Statement I is false and Statement II is true.
Problem 62 The following program, when run,
#include < stdio.h > main()
{
int a,b,c; int count = 1 ;
for (b=c=10;a="- FIGURE?, UMKC,XYZHello Folks,\
TFy!QJu ROo TNn(ROo)SLq SLq ULo+\
UHs UJq TNn*RPn/QPbEWS_JSWQAIJO^\
NBELPeHBFHT}TnALVlBLOFAkHFOuFETp\
HCStHAUFAgcEAelclcn^r^r\\tZvYxXy\
T|S~Pn SPm SOn TNn ULo0ULo#ULo-W\ Hq!WFs XDt!" [b+++21]; )
| for(; a-- > 64 ; ) putchar ( ++c==’Z’ ? c = c/ 9:33 ^b&1); | ||
| return 0 ; } gives the following output: !!!!!! !!!!!!!!!! !!!!!!!!!!!!!!! !!!!!!!!!!!!!! !!!!!!!!!!!!!!! !!!!!!!!!!!! !!!!!!!!!!!! !!!!!!!!!!!! !!!!!!!! !!!!!!!!!! !!!!!!!!!!!!!! !!!!!!!!!!!!!!!! | | |
| !!!!!!!!!!!!!!!! | | !!!!! |
| !!!!!!!!!!!!!!!!!!! | | !!!!!!!!!! |
| !!!!!!!!!!!!!!!!!!!!!!! | ! | !!!!!!!!!! |
| !!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | !! | !!!!!!!!!!!! |
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !! !!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!!!!!!! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!!!!!!!
| !!!!!! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | !!!!!! |
| !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | !!!!! |
| !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | !!! |
| !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | ! |
!!!!!! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!! !!!!!!!!!!!!!!
!!!!!!!!!!!!
!!!!!!!!!!!!
!!!!!!!!!!!!
!!!!!!!!
!!!!!!
!!!!
Can you figure out the logic used in the program?
Problem 63 What are the next few numbers in the sequence 1, 20, 33, 400, 505, 660, 777 , 8000, 9009, 10100, 11121 ?
Problem 64 You are travelling in the jungles of Africa, when you are caught by a tribe of barbarians. They allow you to choose between death or solving their great challenge:
You are blindfolded and taken to a room, where you are asked to kneel. You feel hundreds of circular discs lying in front of you. You are told that one side of each disc is painted red, and the other, green. There are exactly 129 discs that currently are red side up. You have to divide the discs into two groups, such that each group has the same number of discs showing the red colour. Obviously, no peeking allowed.
Problem 65 Given an array of strings, you need to sort it using ”qsort” function provided by C. You may use the strcmp function provided by the C library.
#define SIZEOF(arr) ( sizeof(arr)/sizeof(arr [0])) int main()
{ char *arr[]={"abc","def","abcd"}; int i;
/*
* code to sort..
*...
*... */
for(i=0;i < SIZEOF(arr);i++)
printf("%s\n",arr[i]);
}
Problem 66 Here is a game one can buy in most toy stores, it’s called Hi-Q (or Brainvita). 32 pieces are arranged on a board as shown below:
| | | X | X | X | | |
| | | X | X | X | | |
| X | X | X | X | X | X | X |
| X | X | X | O | X | X | X |
| X | X | X | X | X | X | X |
| | | X | X | X | | |
| | | X | X | X | | |
The rules are as follows:
• In the beginning, only the centre position is unoccupied.
• A piece is allowed to move by jumping over one of it’s neighbours into an empty space.
• Diagonal jumps are not permitted.
• When a piece is jumped over, it is removed from the board.
Write an algorithm which determines a series of jumps so that all of the pieces except one are eventually removed, and the final piece ends up at the center position.
Problem 67 Suppose we wish to multiply four matrices of real numbers M1×M2×M3×M4 where M1 is 10 by 20, M2 is 20 by 50, M3 is 50 by 1, and M4 is 1 by 100. Assume that the multiplication of a p × q matrix by a q × r matrix requires pqr scalar operations, as it does in the usual matrix multiplication algorithm.
Find the optimal order in which to multiply the matrices so as to minimize the total number of scalar operations. How would you find this optimal ordering if there are an arbitrary number of matrices?
Problem 68 Describe a O(nlgn) time algorithm that, given a set S of n real numbers and another real number x, determines whether or not there exist two elements in S whose sum is exactly x.
Problem 69 Given an array of n numbers a1...an, find the second minimum number in n+lgn comparisons. You can only compare elements and you can’t assume anything about the range of values of the numbers.
Problem 70 An element in a sorted array can be found in O(lgn) time via binary search. But suppose I rotate the sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Now devise a way to find an element in the rotated array in O(lgn) time.
Problem 71 Write a program that will display a ”spiral” of n×n numbers, using constant space (no arrays allowed). For example, here’s what the spiral looks like for n = 10:
99 98 97 96 95 94 93 92 91 90
64 63 62 61 60 59 58 57 56 89
65 36 35 34 33 32 31 30 55 88
66 37 16 15 14 13 12 29 54 87
67 38 17 4 3 2 11 28 53 86
68 39 18 5 0 1 10 27 52 85
69 40 19 6 7 8 9 26 51 84
70 41 20 21 22 23 24 25 50 83
71 42 43 44 45 46 47 48 49 82
72 73 74 75 76 77 78 79 80 81
Problem 72 How do you efficiently find the largest repeating string and the number of times it repeats in a given string? For example, given string "abc fghi bc kl abcd lkm abcdefg", the function should return string "abcd" and the count of 2.
Problem 73 There are 4 buckets of 9 coins each. Real coins weigh one gram each, and fake coins weigh 2 grams each. Each bucket is either fake (contains only fake coins) or real (contains only real coins). Given a weighing machine, how can you determine all the buckets that are fake with just one weighing?
Problem 74 Given a binary tree, how do you verify whether it is a binary search tree?
Problem 75 Write a C function, which takes a number n and positions p1 and p2 and returns whether the the bits at positions p1 and p2 are the same or not.
Problem 76 Write a C function, which takes two numbers m and n (representing sets of elements; i’th bit is 1 if i is an element of the set), and checks whether m is a subset of n or not.
Problem 77 A majority element in an array A, of size n is an element that appears more than n/2 times (and hence there is at most one such element) Write a function which takes an array and emits the majority element (if it exists), otherwise prints NONE. Bonus: solve the problem in O(n) time.
For example, the majority element in 3 3 4 2 4 4 2 4 4 is 4, while the sequence 3 3 4 2 4 4 2 4 has no majority element.
No comments:
Post a Comment