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
Hi