Puzzling puzzling...

some queries...

2006-02-21T06:00:00.000-08:00

-- What is the output?

Class X
{
};

printf("%d",sizeof(X));

Ans: 1

-- How to find factorial of a number greater than 13?

-- Can you display "Hello" message in C/C++ with empty main() function.
For example
void main(void)
{

}

Solutions:

C

#define main() main(){printf("Hello");} void abc()

void main()
{
}

C

int i = printf("Hello"); //Global variable i
main()
{
}

C++

class Sample
{
public:
Sample() { printf("Hello"); }
};

Sample s; //Global object

void main(void)
{
}

U got 2 code these!!! - 3

2006-02-04T05:45:00.000-08:00

3

Given a dictionary of words and a character set, design and implement
the most efficient search model to retrieve all dictionary words for a given
character set; for example, given a character set, {'o', 'd', 'g'}, "dog" and
"god", "go" and "do" (but not "good" } are the words that would be
output (considering that these words exist in the dictionary).

The dictionary is static and is input from a file present in the same
directory as the program. The file is an ASCII text file with each word
on a separate line. The words in the file are sorted in lexicographical order.
Dictionary as well as the character set contains only English alphabets
(upper and lower case not distinguished). There is no limit on the number
of words in the dictionary, and you should make your program scale to
large dictionaries. For example, the file could look like the following.

Aberration
Abrasion
An
And
...

The character set is given as a sequence of characters (with no separator
between them). For example, it could be "odg" for a set that represents
three characters 'o', 'd' and 'g'.

The output of the program should be written to an ASCII text file in the
same directory sorted in lexicographical order, which contains all the
dictionary words for a given character set - one word per line.

You can use the standard file I/O functions for your program.

The commandline of the program will be as follows

problem2

For eg., problem2 dict.txt odg output.txt

U got 2 code these!!! - 2

2006-02-04T05:41:00.000-08:00

2

Design and implement an efficient algorithm to remove consecutive 1char,
2char, 3 char... so on recurrences in dictionary words.
For example, "abbabccbc" first will become "ababcbc", then become "abc".
Similarly, "abcaab" will become "abcab" and but stays as it is after that.
You need to output only the last string ("abc" and "abcab" for the above
two examples).

The input to the file will be an ASCII string (of arbitrary size) from standard
input and output string should be sent to standard output.

The commandline of the program will be as follows

problem3
For eg., problem3 abbcabcc

U got 2 code these!!! - 1

2006-02-04T05:27:00.000-08:00

1

Consider a system where users query for and buy Songs. The system
stores the purchase transactions that have happened so far in the form
of a tuple (Ux,Sy) form meaning User x bought Song y.

Question: Whenever a user reviews content of a song S1, we want to
present the user the top 5 songs that other users have bought who also
have bought song S1. The program should not terminate and after
printing out the list of users, wait for the next input. The input could
also be a purchase transaction which would necessitate updating the
transaction history. Further details are given below

Input:

This is the name of a file that contains all
transactions that have happened so far in that system; this will be in
the form of a text file which contains one transaction per line. Each
transaction is a tuple containing the user ID and the song ID (both
are 32 bit numbers) separated by a space. For e.g., line "123 452"
(file contains no quotes) represents that user with ID 123 has bought
song ID 452.

This is the name of the file that contains the
purchase transactions that have to be updated to the system. The format
of this file is the same as that of transaction-history file.

The current query - the song ID that is being queried

Output:
Top 5 songs (sorted in decreasing number of purchases of that song and
separated by spaces) that other users bought who have also bought the
song that was input

Design characteristics:
a. The transaction history can contain up to 1,000,000 transactions.
b. Every day on an average 100,000 users use the system to review
content of some songs (not necessarily buy). Every user has got a
unique ID and every song has got a unique ID.
c. The solution should work for 1,000,000 songs and 100,000 users.
d. Every day 100,000 users review song details
e. Every day 10,000 users buy songs. (means every day there will be
10000 purchase transactions)

Example: In this example there are 4 users and 4 songs and whenever
a user selects a song one top other song that users bought when they
bought the selected song is displayed (note: u and s are given below for
illustration, the real file contains only numbers corresponding to unique
user and song IDs)
Transaction history: (U1, S1), (U1, S3), (U2, S2), (U3, S3), (U3, S4),
(U4, S1), (U4, S2) and (U4, S3)
song: S3 (only U1, U3, U4 bought this song)
output: S1 (was bought by U1 and U4, two people)

Commandline of the program

The program is invoked with the filename of the transaction-history file.
After the transaction history is read into the program, program waits for
input - which is of one of the following types:
1. query command - will print to standard output the list of
songs that other users bought who also bought this song (top 5 - sorted
in decreasing number of purchases of that song); print a new-line after
the list
2. purchase command gives an input file that lists the
latest purchases that have happened. The file has the same format as the
transaction history. The program should update the history with the
purchases listed in the file
3. exit command exits the program

An example run of the program could be as follows (the numbers are
for illustration only)

problem1 history.txt
query 1907
12 23990 2311
query 67621
123 52322 5378
purchase pur0202.txt
query 9792
89023 3289 23424
query 2308
91 391 1 1232
exit

2006-01-30T02:02:00.000-08:00

An array of size N has distinct values 1…N in random order. You have
only operator called rev(X) (where X is any value from 0 to N-1) which
reverses all values from 0 to X (example values 2,3,1,4 and rev(2) gets
you 1,3,2,4). Our objective is to sort the array using minimum number of
Rev(X) functions. How many permutations of N size array require exactly
N number of rev(X) operators to get sorted
a. for size 3 only 1,3,2 requires 3 moves.

Algorithms...

2006-01-29T03:09:00.000-08:00

1
Give a one-line C expression to test whether a number is a power of 2.
Now implement it without using loops.
Answers here
2
Implement an algorithm to sort a linked list.
Answers here

3
Reverse a string.
Answers here

4
Given a linked list which is sorted, how will you insert in sorted way.
Answers here

5
Implement an algorithm to insert in a sorted list.
Answers here

6
Delete an element from a doubly linked list.
Answers here

7
Implement an algorithm to sort an array.
Answers here

8
Given a sequence of characters, how will you convert the lower case characters to upper case characters?
Answers here

9
Write a routine that prints out a 2-D array in spiral order.
Answers here

10
Give a fast way to multiply a number by 7.
Answers here

11
Write a function that takes in a string parameter and checks to see whether or not it is an integer, and if it is then return the integer value.
Answers here

12
How would you print out the data in a binary tree, level by level, starting at the top?
Answers here

13
Write a routine to draw a circle given a center coordiante (x,y) and a radius (r) without making use of any floating point computations.
Answers here

14
Implement a TIC-TAC-TOE game assuming Computer as one of the player. Optimize it for fast computer play time and space. Do some analysis on memory and processing requirements .
Answers here

15
You are given two strings: S1 and S2. Delete from S2 all those characters which occur in S1 also and create a clean S2 with the relevant characters deleted.
Answers here

16
Write a small lexical analyzer for expressions like "a*b" etc.
Answers here

17
Given an array t[100] which contains numbers between 1 and 99. Return the duplicated value. Try both O(n) and O(n-square).
Answers here

18
Write efficient code for extracting unique elements from a sorted list of array.
Answers here

19
Print an integer using only putchar. Try doing it without using extra storage.
Answers here

20
Write a function that allocates memory for a two-dimensional array of given size(parameter x & y)
Answers here

21
How would you do conditional compilation ?
Answers here

22
Write an algorithm to draw a 3D pie chart ?
Answers here

23
Write a funtion that finds repeating characters in a string.
Answers here

24
Write a routine to reverse a series of numbers without using an array.
Answers here

25
Write a function to find the nth item from the end of a linked list in a single pass.
Answers here

26
Write a function to compute the factorial of a given integer.
Answers here

27
Give me an algorithm for telling me the number I didn't give you in a given range of numbers. (Numbers are given at random)
Answers here

28
Write a function that finds the last instance of a character in a string.
Answers here

Level 4

2006-01-29T03:00:00.000-08:00

1

What is the length of the shortest string that contains all strings of size 9
with characters ABCDEFGHI (repetitions are allowed)?
Example: "AABBA" contains all strings of size 2 (AA,AB,BA,BB)
with characters AB.
Ans: 387420497

2

7**7= 823543 (7 power 7). What is the next power of 7 that ends
with 823543?
Ans: 5007

3

An array of size 32767 (2 power 15 - 1) is given. All cells are initialized
to ZERO. The objective is to set 32766th cell to ONE following the rules
(array index starts with ZERO) below:

1. You can have maximum of 15 ONE's set at any time in the array.
2. You can flip the Xth cell to ONE or ZERO only when (X-1)th cell is
set to ONE.
3. ZERO'th cell can be flipped without any conditions.
How many minimum flips are needed to set the 32766th cell to ONE?
Ans: Not known

4

An array of size 32762 is given. 0th cell value is 1, 1st cell value is 2, ..... ,
36761th cell value is 36762. In each iteration the array is split into two
equal halves and they are merged by taking one element from each half.
Example: Consider the array of size 4. If the array is 12345678, in the
first iteration it is split as 1234 and 5678 and merged as 15263748; second
iteration its split again as 1526, 3748 and merged as 13572468; third
iteration its split as 1357 and 2468 and after merging it becomes again
12345678. How many minimum iterations are needed for the array
(of size 32762) to come back to original array?
Ans: 16380

Level 3

2006-01-29T02:50:00.000-08:00

1

9 people hold 5119 shares in a company. In every decision voting, any
subset or all of the 9 people can participate.If a person participates in
voting, he/she can either vote FOR or AGAINST the decision.
The number of votes is equal to the number of shares a person holds.
For every decision there shouldn't be a TIE between the two choices.
In a decision, a group with smaller number of people should never
win over higher number of people. What is the least number of
shares a person can hold?
Ans: 1 (not sure)

2

An array of size 4 is given which can contain only ZERO or ONE values.
Objective is to make all values to ZERO's or ONE's. Initial values can be
any thing. At each iteration you can toggle only one or two cells of the
array. After you toggle, the array is circular shifted by the system.
The circular shift can happen by random length (it can be circular shifted
by one cell, two cells, three cells or four cells). You can't maintain the
state of your previous operation, so you don't know which cells you
touched in the previous iteration. How many maximum iterations are
needed to make the array into all ZERO's or ONE's given any initial values?
Ans: 1 (not sure)

3

A 5*5 array is initialized to all 1s. Each cell can be either 0 or 1. When you
flip a cell (m,n) (say from 1 to 0) all its four neighbors(left, right, up and
down) flip. You need to change the array into all ZEROs by flipping the
cells. How many minimum flips are required?
Ans: not known

4

Consider a string "abc" and a stack with push and pop operations. Given
any permutation of "abc", we can process the characters in that order and
try to output "abc" using the stack. For example, if the string "cab" is given,
"abc" can be generated using the following sequence of operations -
1) push 'c' 2) output 'a' 3) output 'b' 4) pop 'c'. However, given a string
"bca", it is not possible to generate "abc". Now, consider the string
"macbeth". How many permutations of this string can generate "macbeth"
using one stack and a sequence of push and pop instructions?
Ans: 429

Level-2

2006-01-29T00:44:00.000-08:00

1	What is the probability of two people arriving at a restaurant withing 8 minutes of each other between 1 PM and 5 PM?The answer needs to be rounded to 4 decimal places with no trailing zeroes. (e.g .15 needs to be represented as 0.15, 0.154567 needs to be represented as 0.1546) Ans: 0.0734
2	6 people got on a train at its starting point. There are 12 stations on which they can get off (excluding the starting point. What is the total number of different ways they can do this considering that no more than 3 people get off at the same station? Ans: 11440
3	A machine has 64 KB of virtual memory and 1 KB of physical memory. This machine uses a set-associative page table with a page size of 64 bytes and 4 sets. The low order bits of the virtual page number are used to decide the set in which a virtual page is placed. The page replacement algorithm in each set is round-robin: on the first page fault, the first page in the set is replaced. On the second page fault, the second page in the set is replaced and so on. The contents of the page table are given in increasing order of physical page number below, where the virtual page number is in hex: 0x348, 0x28c, 0x280, 0x164, 0x79, 0x3fd, 0x331, 0x55, 0xaa, 0x6e, 0x2e2, 0x246, 0x3db, 0x3df, 0x193, 0x337. A program issues the following virtual addresses in hex: 0xb888, 0xda80, 0xe9d0, 0x1dc8, 0xf6c4, 0x2a80, 0x64ec, 0xd590. What are the final contents of the Page Table? Ans: 0x348,0x28c,0x280,0x164,0x79,0x3fd,0x331,0x55,0x36a,0xaa,0x356,0x246,0x3a7,0x77,0x3db,0x193
4	I have a 4 bit number "n" in mind (that is, 0 <= n <= 15). To help you guess this number, I have answered seven questions below (the least significant bit is bit 1 and the most significant bit is bit 4 ): Q1. Is bit 1 equal to 1? Yes Q2. Is bit 2 equal to 1? Yes Q3. Is bit 3 equal to 1? No Q4. Is bit 4 equal to 1? No Q5. Is the sum of bits 1, 2 and 4 even? No Q6. Is the sum of bits 1, 3 and 4 even? Yes Q7. Is the sum of bits 2, 3 and 4 even? No The catch here is that the answer to exactly one of the seven questions above is wrong, the other six are correct. Which answer is wrong? (For example, if the answer to Q6 above is wrong, your response should be 6.) Ans: 1
5	9 0s are placed from 0th cell to 8th cell of an array; 8 1s are placed from 10th cell to end of the array. On the whole, there are 18 cells, so that just one cell remains unoccupied. 0s only move rightward; 1s move leftward. Every move is either a move to the next empty cell or a jump over one cell which has different value. In any case, no two values are allowed in the same square. The goal is to move 1s into 8 leftmost positions and the 0s into 9 rightmost positions. How many minimum moves are needed to achieve this? Ans: 88
6	All 7 digit permutations of number 1234567 are sorted and kept in an array of 5040 elements. (0th element is 1234567, 1st element is 1234576 and 5039th element is 7654321.) What is the 1646th element in this array? Ans: 3265174
7	A character in an alphabet is represented in 12 bits. How many characters are there in the alphabet which have at least one sequence of 3 adjacent 0s? Ans: 2391
8	Given a 9 X 9 sided square(rows 0 to 8, columns 0 to 8) where the cell(8,3) contains a RED dot (rest of the cells dont contain the RED dot). How many squares are present of any size without having the RED dot in them? Ans: 260

Level 1

2006-01-29T00:24:00.000-08:00

1) There are 14 steps. A person is starting from the bottom climbing to the top.
A person can climb, at a time, one, two or three steps.
In how many ways can he climb the steps and reach the top?
Ans: 3136

2) You are given an infinite number of cookie boxes containing either 6, 9
or 140 cookies. You are allowed to use these boxes in any combination so
desired. What is the maximum number of cookies that you cannot give
out using the above boxes?
Ans: 283

3) A Binary Tree can be fixed given its nodes in Pre-Order and
In-Order sequence. The Pre-Order of a tree is c,g,d,j,i,f,e,a,b,h and In-order
traversal of this tree is i,f,j,d,e,g,c,b,a,h. What will be the Post-Order traversal
of the same binary tree? Each alphabet in the sequence represents one node
of the binary tree. Give the output as a comma separated list
of alphabets(nodes),for eg. a,b,c,d,e,f,g,h,i,j.
ANS: f,i,j,e,d,g,b,h,a,c

4) Examine the code below. Each second, the function Writer is called 4 times,
following which the function Reader is called 1 times (in the same thread there
is no multithreading involved here). The same cycle repeats every second.
What is the first number to be printed by this program?

#include 

#define BUFFER_SIZE 16
int buffer[BUFFER_SIZE];

int writeIndex = 0;
int readIndex = 0;

int IncrementCircular(int start)
{
int sum = start + 1;
return sum >= BUFFER_SIZE ? sum - BUFFER_SIZE : sum;
}

void Reader()
{
if (readIndex != writeIndex)
{
// Consume buffer[readIndex] here.
readIndex = IncrementCircular(readIndex);
}
// else, buffer is empty.
}

void Writer()
{
static int value = 1;
if (IncrementCircular(writeIndex) == readIndex)
{
// The buffer is full - print the value.
fprintf(fpq"%d\n", value);
}
else
{
buffer[writeIndex] = value;
writeIndex = IncrementCircular(writeIndex);
}
++value;
}
ANS: 20

5)Tower of Honoi: we are given a tower of N disks, initially stacked in
increasing size on one of three pegs. The objective is to transfer the entire
tower to one of the other pegs, moving only one disk at a time and never a
larger one onto a smaller. In this variation of tower of honoi, peg two
contains 1-4 disks and peg one contains 5-9 disks. How many minimum
moves are needed to move all the disks to the third peg moving only one
disk at a time and never a larger one onto a smaller?
ANS: 542

6)Multiply 13332 represented in base -7 with 15117 represented in
base -8 and represent the output in base -9.
ANS:50554230

7)An array contains 8 occurences of 0s, 4 occurences of 1s and 7 occurences
of 2s in any order. The array is to be sorted using only swap operations.
What is the minimum number of swaps needed in the worst case to sort
the array?
ANS: 20

8)An LCD(Liquid Crystal Display) can represent 0 to 9 digits.
If you turn the LCD upside-down, some of the numbers still remain valid
numbers for example 16 becomes 91. If you index all positive numbers(>0)
that can produce valid numbers when you upside down the display
(like 1st one is 1, 2nd one is 2, 3rd one 5... 7th one is 10), what is the
1254th number in this series?
ANS: 5661