Write an efficient C program to count the number of bits set in an
unsigned integer.
i/p o/p
==== ===
0(00) 0
1(01) 1
2(10) 1
3(11) 2
..... ...
2.
Write a small C program, which while compiling takes another program
from input terminal, and on running gives the result for the second
program. (NOTE: The key is, think UNIX).
Suppose, the program is 1.c
Then, while compiling
$ cc -o 1 1.c
int main()
{
printf("Hello World\n");
}
^D
$ ./1
Hello World
$
3.
Given a string s1 and a string s2, write a snippet to say whether s2 is a
rotation of s1 using only one call to strstr routine?
(eg given s1 = ABCD and s2 = CDAB, return true,
given s1 = ABCD, and s2 = ACBD , return false)
4.
What's the "condition" so that the following code
snippet prints both HelloWorld !
if "condition"
printf ("Hello");
else
printf("World");
5.
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
shows the first 11 ugly numbers.
By convention, 1 is included.
Write a program to find and print the 1500'th ugly number.
6.
Write a C program which when compiled and run, prints out a message
indicating whether the compiler that it is compiled with, allows /* */
comments to nest.
7.
Write a C function that will print 1 to N one per each line on the stdout
where N is a int parameter to the function. The function should not use
while, for, do-while loops, goto statement, recursion, and switch
statement.
8.
int main()
{
int i, n = 20;
for (i = 0; i < n; i--)
printf("*");
return 0;
}
Change/add only one character and print '*' exactly 20 times.
(there are atleast 3 solutions to this problem :-)
9.
You are given have a datatype, say X in C.
The requirement is to get the size of the datatype, without declaring a
variable or a pointer variable of that type,
And, of course without using sizeof operator !
10.
Given a singly-linked, find out the mid point of a single linked list in a
single parse of the list. Assume the program would be loaded in read-only
memory so no manipulation of the list is allowed.
11.
You are given a circular single linked list of sufficiently many number of
nodes(say more than 1 crore). You need to delete a node say P and you are
given a pointer to P in the circular single list.
Suggest the most efficient methodology of deleting the node P from the
circular single linked list without rounding about the circular single
linked list.
12.
Write a C Program to reverse a stack "in place" using recursion ?
You can only use the following ADT functions on Stack:
IsEmpty
IsFull
Push
Pop
Top
13.
You are provided with two stacks, and pop() and push() functions for them.
You have to implement queue i.e. enqueue() and dequeue() using the
available operations.
14.
How do you reverse the words in a string?
"My name is Amit Agarwal"
to
"Agarwal Amit is name My"
A O(n) and 'in space' solution is appreciable.
15.
You are given a sequence of numbers from 1 to n-1 with one of the
numbers repeating only once. (example: 1 2 3 3 4 5).
* How can you find the repeating number?
* What if i give you the constraint that you can't use a dynamic amount
of memory (i.e. the amount of memory you use can't be related to n)?
* What if there are two repeating numbers,instead of one (and the same
memory constraint?)
16.
Given an array of numbers, except for one number all the others, occur
twice. Give an algorithm to find that number which occurs only once in the
array.
17.
There is a series of numbers in ascending order. All these numbers
have the same number of binary 1s in them. Given the number of 1 bits set in
the numbers, write an algorithm/C program to find the nth number in
the series.
18.
Given a stack S, write a C program to sort the stack (in the ascending
order).
We are not allowed to make any assumptions about how the stack is implemented.
The only functions to be used are:
Push
Pop
Top
IsEmpty
IsFull
19.
Given a linked list, your are asked to find out the nth last element in
the linked-list. (n would be given as the argument to the function)
20.
The numbers are represented in linked-list with each node representing a
digit of the number as follows:
123 == 1 2 3 NULL
999 == 9 9 9 NULL
Write a C program to add two numbers.
I/P : 9 9 9 NULL
1 NULL
O/P : 1 0 0 0 NULL
You can assume that the number of elements in the linked-list is available
to you.
struct List
{
Node* head;
int noe; /* number of elements */
};
21.
There is a 100-story building and you are given two eggs.
The eggs (and the building) have an interesting property that
if you throw the egg from a floor number less than X, it will not
break. And it will always brake if the floor number is equal or greater than X.
Assuming that you can reuse the eggs which didn't broke, you got to find
X in a minimal number of throws.
Give an algorithm to find X in minimal number of throws.
22.
You are given a singly link-list such that each node of this list is also a
head of another link list of the same type. So, how does one flatten the
linked-list
struct node {
void *data; /* could be anything */
struct node *next;
struct node *down;
};
23.
Given: 2 Unsorted single linked list
Todo: Fastest and optimised way to merge and make a single sorted list with
these 2 unsorted single linked list.
24.
Given a numbers x and n, where n is a power of 2, write C code, which
gives the multiple of n which is greater than or equal to x.
ex :
I/P: 13 8
O/P: 16
I/P: 17 16
O/P: 32
The challenge: Do not use division or modulo operator.
25.
In C, copying of array as follows is not possible:
int a[10],b[10];
a = b;
a = GetAnArrayOfTenElements();
Can you think of a simple hack, which would enable us to get this effect?
26.
Assume that two robots land from two different
flights with the help of parachuttes (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(meeting).
You have the following instructions at your disposal
to write the program:
1) Step L - makes the robot take one step towards left
2) Step R - makes the robot take one step towards right
3) goto label - jump to the label
4) if P one instruction, where
P is a predicate which will be true when a robot senses a
parachutte. 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)
Could anybody write a program to help the robots to
meet :)? Make your own assumptions and justify them.
Remember the same program needs to be executed by both robots :-)
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)
20
/ \
8 22
/ \
4 12
/ \
10 14
I/P : 4 and 14
O/P : 8
(Here the common ancestors of 4 and 14, are {8,20}.
Of {8,20}, the lowest one is 8).
28.
Given an array of 2n elements of which n elements are same and the
remaining n elements are all different. Write a C program to find out the
value which is present n times in the array.
There is no restriction on the elements in the array. They are random
(In particular they not sequential.)
29.
Given two arrays A and B. Array 'A' contains all the elements of 'B' but
one more element extra.....
Find out the extra element......
Restrictions: Dont use any relational ops ( > or > or == etc....), array
elements are not in order ...,
30.
There are 2 cities A and B, dist. between them is 1000 Km
we have 3000 bananas in city A and a elephant can carry max 1000 bananas at
any given time and it needs to eat a banana every 1 Km.
How Many Max. No. of bananas one can transfer to city B?
Note : the elephant cannot go without bananas to eat.
31.
Assume memory is divided into blocks that are a power of 2 in size,
starting at address 0. The blocks may be words, doublewords, pages, and so
on.
Then, given a starting address "A" and a length "L", we wish to determine
whether or not the address range from "A" to "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 small piece of C code, to know if A+L crosses a boundary.
Challenge again is not to use division or modulo operator :-)
32.
Write an efficient function in C that deletes characters from a string.
Use 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 vs.
Brzny".
Justify any design decisions you make and discuss the efficiency
of your solution.
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)*(2*n+1) is divisible by 6, for any n>0
35.
Given an 8x8 chessboard,
* How many "total" number of squares are present in the board?
* How many "total" number of rectangles are preent in the board?
(for this problem assume that rectangles must have length and breadth
different)
36.
I would like to know the method one employs to subtract
the following fractions
+8 5/12 - 2 2/3
Note: 8 5/12 is a mixed fraction. Cannot represent it any
better on the monitor
What I expect is a step wise description of the procedure.
No this is not a test of one's analytical skill, just to see how
many people do it the easier way.
37.
Consider an array of integers, both positive and negative. You have to
find out the maximum sum possible by adding 'n' consecutive integers in
the array, n <= [ARRAY_SIZE]. Also give where in the array this sequence
of n integers starts.
38.
Given two sorted linked lists, L1 and L2, write a C program to compute
L1 /\ L2 (L1 intersection L2).
39.
Propose a data structure that supports the stack push and pop operations
and a third operation find_min, which returns the smallest element in
the data structure, all in O(1) worst case time.
40.
Given an array of integers (possibly some of the elements negative),
write a C program to find out the *maximum product* possible by adding
'n' consecutive integers in the array, n <= ARRAY_SIZE.
Also give where in the array this sequence of n integers starts.
41.
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?
42.
Given 6 match sticks of equal length. You are asked to form 4
equilateral triangles with these sticks. Obviously, you are not allowed
to break, split or bend the sticks.
43.
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
(Red,Green,Blue). Now we need to sort the array in such a way that all
the Red coloured balls come first, followed by blue and then green.
The restriction is that call to function ColorOfBall is a very costly
operation. You have to use it as less as possible. (In other words we
would be looking for the solution with least number of calls to the
function ColorOfBall.)
44.
Propose a data structure for the following:
- The data structure would hold elements from 0 to N-1.
There is no order on the elements (no ascending/descending order
requirement)
The complexity of the operations should be as follows:
* Initialization - O(1)
* Insertion of an element - O(1)
* Deletion of an element - O(1)
* Finding a element - O(1)
* Deleting all elements - O(1)
45.
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. a ball
cannot be placed on top of another ball.
If you find that too easy, and have loads of time to kill, then
how about arranging 22 balls in 21 lines of 4 :)
46.
Write a "C" function,
int AddOvf(int* result, int a, int b)
If there is no overflow, the function places the reusltant
sum a+b in "result" and returns 0. Otherwise it returns -1.
The solution of casting to long and adding to find detecting the
overflow is not allowed :-)
47.
Write a C function that rotates to the right by 'n' bit
positions the bits of an unsigned int x
No assumptions to be made on the the values 'n' can take and the
size of 'x'.
48.
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, cost to buy the skis is B units where B>>1.
49.
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.1f;
if(f==1.0f)
printf("f is 1.0f\n");
else
printf("f is NOT 1.0f\n");
return 0;
}
50.
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
No, this simple definition doesn't work:
#define CHAR(x) 'x'
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.