## BillyG upto it again…

Posted by lapstre on January 25, 2006

Posted Originally on LApstrEz BLoG – http://www.Journalhome.com/lapstre

Hi there,

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

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);

}

else

{

buffer[writeIndex] = value;

writeIndex = IncrementCircular(writeIndex);

}

++value;

}

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?

CODE 4 BILL CONTEST

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?

## Leave a Reply