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
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).
52.
How could i 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.
53.
A multiple choice test has 15 questions and 4 choices for each answer.
Each question has only one answer correct.
How many ways can the 15 questions be answered so that
- Exactly 3 answers are correct
- Atleast 3 answers are correct
54.
cwd
xor ax, dx
sub ax, dx
cwd- convert word ot double word. sign extend DX:AX, with DX having the
signed bit
xor ax, dx => ax = ax xor dx
sub ax, dx => ax = ax - dx
55.
In a calendar year (assume non-leap), determine how many Friday the
thirteenths there can be. What is the smallest number possible?
56.
Write a Recursive function which generates the PowerSet of a given Set.
The Set is passed to the Function as a String. And the Function should
print the Subsets as Strings.
[Note:]
PowerSet( {1,2,3} ) = 0, 1, 2, 3, 12, 13, 23, 123 //0 is Null Set.
And the Order of the SubSets is not Mandatory.
Sample TestCase:
I/P :"abc"
O/P:
0
a
b
ab
c
ac
bc
abc
57.
Bangla numbers
====== =======
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.
Input
-----
The input file may contain several test cases. Each case will contain a
non-negative number <= 999999999999999.
Output
------
For each case of input, 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
http://acm.uva.es/p/v101/10101.html
58.
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.
The problem is : How many matches are played in total?
59.
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 program to find the parity of an unsigned integer.
60.
Calculate: B^P mod M for large values of B, P and M using a very
efficient algorithm.
Value ranges:
B 0-2147483647
P 0-2147483647
M 1-46340
61.
Lets assume we have a rat maze as represented by the following NxM 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).
As seen from above, there can be many paths from S to F.
How do we find the shortest (or longest) path from S to F without actually
traversing all the possible paths.
Please post (with proof/explantion) your algorithms. Also can you then think
of ways to optimize the algo?
62.
I. The chicken came first.
II. The egg came first.
III. Statement I is false and Statement II is true.
If two of the above statements are false, what chance is there that the egg
came first?
63.
#include
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;
}
The above program, when run gives the following output:
!!!!!!
!!!!!!!!!!
!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!
!!!!!!!!!!!!
!!!!!!!!!!!!
!!!!!!!!!!!!
!!!!!!!!
!!!!!!!!!!
!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!! !!!!!
!!!!!!!!!!!!!!!!!!! !!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!! ! !!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !! !!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !! !!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!!!!!!!
!!!!!! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !
!!!!!! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!
!!!!!!!!!!!!
!!!!!!!!!!!!
!!!!!!!!!!!!
!!!!!!!!
!!!!!!
!!!!
Can you figure out the logic used in the program?
64.
Here is an interesting sequence..
1 20 33 400 505 660 777 8000 9009 10100 11121
What are the next few numbers in the above sequence?
65.
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 know what you will choose ;)
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.
66.
Given an array of strings, you need to sort it using "qsort"
function provided by C. You can use the "strcmp" function provided
by the C language as well.
#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]);
}
67.
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
* 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.
68.
Suppose we wish to multiply four matrices of real numbers
M1 x M2 x M3 x 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 x q matrix by a q x 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?
69.
Describe a (n log2 n) 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.
70.
Given an array of n numbers a[1], a[2],..., a[n], find the
second minimum number in n + log n comparisons. You can only
compare elements. You can't assume anything about the range of values
of the numbers.
71.
An element in a sorted array can be found in O(log n) 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(log n) time.
72.
Write a program that will display a "spiral" of NxN 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
For N = 2
3 2
0 1
For N=3
8 7 6
1 0 5
2 3 4
For N=4
15 14 13 12
4 3 2 11
5 0 1 10
6 7 8 9
73.
How do u find the largest repeating string and the number of times it
repeats in a given string efficiently offcourse !?
ex :
String : "abc fghi bc kl abcd lkm abcdefg"
Ans : "abcd" count = 2
74.
There are 4 buckets of coins. Real coins weigh one gram each. fake grams
weigh 2 grams each. Each bucket is fake (contains only fake coins) or real
(contains only real coins). You have weighing machine, which can be used
only one weighing. If there are 9 coins per bucket, how can you determine
all the buckets that are fake with just one weighing.
75.
Given a binary tree, you need to verify it is a binary search tree or not.
How do you do that?
76.
Write a C function, which takes a number n and positions p1 and p2 and
returns if the the bits at positions p1 and p2 are same or not.
77.
Write a C function, which takes two numbers m and n, (which are representing
and bit set) and checks whether m is a subset of n or not.
78.
A majority element in an array A, of size N is an element that appears more than N/2 times (and hence there is atmost
one such element)
Write a function which takes an array and emits the majority element (if it exists), otherwise prints NONE as follows:
I/P : 3 3 4 2 4 4 2 4 4
O/P : 4
I/P : 3 3 4 2 4 4 2 4
O/P : NONE
If the answers is incorrect or not given, you can answer the above question in the comment box. If the answers is incorrect or not given, you can answer the above question in the comment box.