LApstrEz BLoG

A WeBLoG of an Ordinary Geek

BillyG upto it again…

Posted by lapstre on January 25, 2006

Posted Originally on LApstrEz BLoG –
Hi there,

Long time since i sat down to write. College,Projects and Training, One hectic combination enough to drive u mad and tired by the end of the day. I tried to catch up but couldn’t write any good blogposts. Felt guilty and put in a few scrap blogposts, and tried to get rid of that strange feelin…
Amidst all this hullaboo came Code4Bill , A Microsoft talent hunt contest in India. I took the first attempt and made mockery of myself, for the second i was too tired to even try. So i just shut up and went to bed. Got the questions for the 1st and 2nd at the end of the post, Have a look and see where u figure…
Bill Gates (aka BillyG) was spotted showing off his pet toys at the Consumer Electronics Show in Las Vegas. Apart from showing off Vista, the big kid also bragged about his latest new soft toy, The new Windows Media Center Edition. For more on his inaugural keynote address at CES click HERE.
Another person who was in the lime light recently was me(Bleargh!), who caused up quite a stir by requestin my HOD to cancel my previously approved project. The class was flabbergasted at the idea, especially since lots of projects got rejected. I claimed the reason to be lack of time, but the HOD convinced me to tone down the project to suit the time constraints(Why din’t i think of that before??? Darn!).And hey, Guess what i found when i was browsin the web, A “Hangman” script i can add to my site, Hangman is one of my favourite games, have a go at it, u’ll like it…

Hah and now, Back to preparing for my reviews in college.

Before i go “Congratulations ot all those who made it thro the first round of Code4BIll…”

Gotta run, Bye

CODE 4 BILL CONTESTQuestions for attempt1
(Psst : Don’t curse me please, I din’t set the Questions)

1. There are 18 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?

2. You are given an infinite number of cookie boxes containing either 6, 9 or 260 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?

3. A Binary Tree can be fixed given its nodes in Pre-Order and In-Order sequence. The Pre-Order of a tree is j,f,h,e,c,d,a,i,b,g and In-order traversal of this tree is h,f,e,c,j,a,d,b,i,g. 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.

4. Examine the code below. Each second, the function Writer is called 6 times, following which the function Reader is called 3 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 <stdio.h>

#define BUFFER_SIZE 20
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 “, value);
buffer[writeIndex] = value;
writeIndex = IncrementCircular(writeIndex);

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-8 disks and peg one contains 9-10 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?

6.Multiply 11102 represented in base -7 with 14340 represented in base -8 and represent the output in base -9.

7.An array contains 4 occurences of 0s, 10 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?

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 1274th number in this series?


Questions for attempt2

1. What is the probability of two people arriving at a restaurant withing 11 minutes of each other between 1 PM and 2 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)

2. 4 people got on a train at its starting point. There are 10 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 2 people get off at the same station?

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: 0x208, 0x24c, 0x340, 0x324, 0x339, 0x3bd, 0x3f1, 0x215, 0x36a, 0x2e, 0x3a2, 0x6, 0x29b, 0x39f, 0x253, 0xf7. A program issues the following virtual addresses in hex: 0xe8b8, 0x94dc, 0xe00, 0x7730, 0xa6f4, 0xdab0, 0x2638, 0x2c80. What are the final contents of the Page Table?

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? No
Q2. Is bit 2 equal to 1? No
Q3. Is bit 3 equal to 1? Yes
Q4. Is bit 4 equal to 1? Yes
Q5. Is the sum of bits 1, 2 and 4 even? No
Q6. Is the sum of bits 1, 3 and 4 even? No
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.)

5. 8 0s are placed from 0th cell to 7th cell of an array; 8 1s are placed from 9th cell to end of the array. On the whole, there are 17 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 8 rightmost positions. How many minimum moves are needed to achieve this?

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 1170th element in this array?

7. A character in an alphabet is represented in 11 bits. How many characters are there in the alphabet which have at least one sequence of 3 adjacent 0s?

8. Given a 9 X 9 sided square(rows 0 to 8, columns 0 to 8) where the cell(7,0) 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?

You even botheres to read thro this much of stuff??? Hats Off!


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: