# Antimatroid, The

thoughts on computer science, electronics, mathematics

## Solutions to some Microsoft interview questions

with one comment

A couple of weeks ago, someone on reddit posted a link to a collection of Microsoft Interview Questions. As someone who interviewed with them while in college, I was curious to see what kind question they were asking folks. After reviewing the list, I thought I’d work out a few that looked interesting:

Imagine an analog clock set to 12 o’clock. Note that the hour and minute hands overlap. How many times each day do both the hour and minute hands overlap? How would you determine the exact times of the day that this occurs?

$\displaystyle \text{Let } \theta_{h}(t) = \frac{2\pi}{43200}t , \theta_{m}(t) = \frac{2\pi}{3600} t \in \mathbb{R} \to \mathbb{R}, t \in [0, 86400)$

$\displaystyle \lvert \theta_{h}(t) - \theta_{m}(t) \rvert \equiv 0 \pmod{2\pi} \Rightarrow \frac{39600}{155520000} 2\pi t \equiv 0 \pmod{2\pi}$

$\displaystyle \Rightarrow t_{k} = \frac{43200}{11} k, k \in [0, 22)$

Thus*: 12:00:00 AM, 01:05:27 AM, 02:10:54 AM, 03:16:21 AM, 04:21:49 AM, 05:27:16 AM, 06:32:43 AM, 07:38:10 AM, 08:43:38 AM, 09:49:05 AM, 10:54:32 AM, 12:00:00 PM, 01:05:27 PM, 02:10:54 PM, 03:16:21 PM, 04:21:49 PM, 05:27:16 PM, 06:32:43 PM, 07:38:10 PM, 08:43:38 PM, 09:49:05 PM and 10:54:32 PM.

* Floor the conversion from $t$ to hour, minute and second of day.

Pairs of primes separated by a single number are called prime pairs. Examples are 17 and 19. Prove that the number between a prime pair is always divisible by 6 (assuming both numbers in the pair are greater than 6). Now prove that there are no ‘prime triples.’

Assuming:
$\text{Let } n, r \in \mathbb{N}$
$p = 6n \pm r , r \in \{ 0, 2 \} \Rightarrow 3|p$
$p = 6n \pm r , r \in \{ 3, 4 \} \Rightarrow 2|p$
$p = 6n \pm r , r \in \{1, 5 \} \Rightarrow 1|p \wedge p|p$
$\therefore (\forall p > 3) \in \mathbb{P}, p = 6n \pm r, r \in \{1, 5\}$

Twin Primes:
$\displaystyle \text{Let } p = 6n - 1, q = 6n + 1 \in \mathbb{P}$
$\displaystyle n, r = \frac{p+q}{2} \in \mathbb{N}$
$\displaystyle\Rightarrow r = \frac{6n - 1 + 6n + 1}{2}$
$\Rightarrow r = 6n$
$\therefore 6|r$

Prime Triples:
$\displaystyle \text{Let } u = 6n - 1, v = 6n + 1, v = 6m - 1, w = 6m + 1 \in \mathbb{P}$
$\displaystyle n < m \in \mathbb{N}$
$\displaystyle 6n + 1 = 6m - 1 \Rightarrow m - n = \frac{1}{3}$
$\displaystyle \frac{1}{3} \notin \mathbb{N}$
$\displaystyle \therefore \not \exists u, v, w \in \mathbb{P}$

There are 4 women who want to cross a bridge. They all begin on the same side. You have 17 minutes to get all of them across to the other side. It is night. There is one flashlight. A maximum of two people can cross at one time. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each woman walks at a different speed. A pair must walk together at the rate of the slower woman’s pace.

For example if Woman 1 and Woman 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Woman 4 then returns with the flashlight, a total of 20 minutes have passed and you have failed the mission. What is the order required to get all women across in 17 minutes? Now, what’s the other way?

One way:

1. Woman 1 and 2 Cross, woman 1 returns. 3 minutes total.
2. Woman 3 and 4 Cross, woman 2 returns. 15 minutes total.
3. Woman 1 and 2 Cross. 17 Minutes total.

Other way:

1. Woman 1 and 2 Cross, woman 2 returns. 4 minutes total.
2. Woman 3 and 4 Cross, woman 1 returns. 11 minutes total.
3. Woman 1 and 2 Cross. 17 minutes total.

If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?

1. Fill 5 quart pail with 5 quarts of water from source.
2. Fill 3 quart pail with 3 quarts of water from 5 quart pail.
3. Empty 3 quart pail.
4. Empty 5 quart pail containing 2 quarts of water into 3 quart pail.
5. Fill 5 quart pail with 5 quarts of water from source.
6. Fill 3 quart pail with water from 5 quart pail.
7. 5 quart pail now contains 4 quarts of water.

Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array, except for one number, which occurs twice. Assume that you can access each element of the array only once. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it?

$f(A) = \displaystyle\sum_{k = 0}^{|A| - 1} A_{k} -\frac{|A|(|A|-1)}{2}$

public int duplicateNumber(int[] A) {
int count = 0;
for(int k = 0; k < A.Length; k++)
count += A[k];
return count - (A.Length * (A.Length - 1) >> 1);
}


Count the number of set bits in a number. Now optimize for speed. Now optimize for size.

$\displaystyle \text{Let } m = \sum_{k = 0}^{\infty} A_{k} 2^{k}, A_{k} \in [0,1], m \in \mathbb{N}_{0}$
$\displaystyle f(n) = \sum_{k=0}^{\infty}A_{k}$
$\displaystyle f(n) = \begin{cases} \left( n - n \oslash 2 \right) + f\left( n \oslash 2 \right) & n \neq 0 \\ 0 & \text{otherwise} \end{cases}$

public int bitsUsed(int n) {
int count = 0;
while(n != 0) {
count += n & 1;
n >>= 1;
}

return count;
}


Written by lewellen

2008-08-24 at 6:00 pm