Technical Interview

Tips, questions, answers and puzzles at
www.technical-interview.com

Showing posts with label Microsoft. Show all posts
Showing posts with label Microsoft. Show all posts

Saturday, May 1, 2010

What are the advantages and disadvantages of B-star trees over Binary trees?

Ans
A1 B-star trees have better data structure and are faster in search than Binary trees, but it’s harder to write codes for B-start trees.

Thursday, April 29, 2010

Majority element

Given an array of size N ,we need to find the majority element if it exists ,as efficiently as possible. A majority element in an array of size N is any element which is present more than N/2 times.

Ans
Naive approach:

Just scan the array element wise and then make a count of the frequency of each of the distinct elements present in the array and if any element's count is more than N/2 then it is the majority element, otherwise it doesn't exist!!

One needn't ponder much on the complexity of this bruteforce approach.

This requires O(N) additional space and O(N) time.

Recursive Approach:

Here’s a divide-and-conquer algorithm:

function majority (A[1 . . . N])

if N = 1: return A[1]

let AL , AR be the first and second halves of A

ML = majority(AL ) and MR = majority(AR )

if neither half has a majority:

return ‘‘no majority’’

else:

check whether either ML or MR is a majority element of A

if so, return that element; else return ‘‘no majority’’

Sunday, February 28, 2010

Arangement of blocks

You are given N blocks of height 1…N. In how many ways can you arrange these blocks in a row such that when viewed from left you see only L blocks (rest are hidden by taller blocks) and when seen from right you see only R blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3} while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.

Friday, February 9, 2007

In a country in which people only want boys, every family continues to

In a country in which people only want boys, every family continues to have children until they have a boy. if they have a girl, they have another child. if they have a boy, they stop. what is the proportion of boys to girls in the country?

If the probability of observing a car in 30 minutes on a highway is 0.95

If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)?

Four people need to cross a rickety rope bridge to get back to their camp at night

Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it’s only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes?

Thursday, February 8, 2007

If you look at a clock and the time

If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? ( The answer to this is not zero!)

Mike has $20 more than Todd. How much does each have given that ....

Mike has $20 more than Todd. How much does each have given that combined they have $21 between them. You can’t use fractions in the answer. (Hint: This is a trick question, pay close attention to the condition)

What gives you joy?

What gives you joy?