Interview Questions « Antimatroid, The

Posts Tagged ‘Interview Questions’

Solutions to some Microsoft interview questions

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:

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

Other way:

Woman 1 and 2 Cross, woman 2 returns. 4 minutes total.
Woman 3 and 4 Cross, woman 1 returns. 11 minutes total.
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?

Fill 5 quart pail with 5 quarts of water from source.
Fill 3 quart pail with 3 quarts of water from 5 quart pail.
Empty 3 quart pail.
Empty 5 quart pail containing 2 quarts of water into 3 quart pail.
Fill 5 quart pail with 5 quarts of water from source.
Fill 3 quart pail with water from 5 quart pail.
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

Posted in Uncategorized

Tagged with Brain Teaser, Interview Questions, Microsoft

Problem with an interesting little problem

without comments

A Simple Problem

$\displaystyle{B_{i} = \prod_{j \neq i} A_{j}}$

Rules:

Solutions must be $\\O(n)$ in time complexity
Solutions must not use the division operator

fsharp.it posted the above simple Google interview question on their site a few weeks ago and subsequently the problem was referenced by OJ’s rants and later posted to the programming subreddit on reddit.com. Like everyone else, I sat down and wrote some quick code to solve the problem. After looking a the solution, it seemed to me that this was a rather poorly conceived problem- if not contrived at heart. It doesn’t ring to the tune of scalability, performance and quality that one thinks of when the word Google is thrown into the mix.

In the following, we’ll explore why this this problem isn’t a well designed interview question for a software engineering position. For software engineering, a problem should test a candidates ability to deliver simple and optimal solutions under non-ideal situations.

A Complex Solution

Rule (1) is simple enough to deal with, Rule (2) is a little more unexpected, and one can devise any number of reasons why it would be advantageous:

Most CPUs require 4x the number of cycles to perform a division vs a multiplication on a set of 32-bit registers
The rare event that a CPU doesn’t offer a division instruction
Google want to see the candidate solve a simple problem with only a subset of tools
And so on…

After some thinking, one eventually devises the following imperative solution:

public int[] exteriorProduct(int[] A) {
	int[] L = new int[A.Length], R = new int[A.Length];
	for (int n = 0, m = A.Length - 1; n < A.Length && m >= 0; n++, m-– ) {
		L[n] = n == 0 ? 1 : A[n - 1] * L[n - 1];
		R[m] = m == A.Length - 1 ? 1 : R[m + 1] * A[m + 1];
	}

	int[] B = new int[A.Length];
	for (int n = 0; n < A.Length; n++)
		B[n] = L[n] * R[n];
}

Given the input A, we instruct the machine to memoize the partial product from 0 to i – 1 and store said value into L[i]; likewise, from |A| – 1 to i + 1 we store the partial product into R[i]. The desired product is the product of L[i] and R[i].

Some quick time complexity analysis reveals the following:

$U(N) = \alpha (2 N)$

$V(0) = 0$
$V(N) = 2 (\tau + \max(0, \mu)) + V(N - 1)$
$V(N) = 2 (\tau + \mu) N$

$W(0) = 0$
$W(N) = \mu + W(N-1)$
$W(N) = \mu N$

$T(N) = U(N) + V(N) + W(N)$
$T(N) = \alpha (2 N) + 2 (\tau + \mu) N + \mu N$
$T(N) = (\alpha + \tau + \mu) (2 N) + \mu N$

Where $\alpha$ is the memory allocation time, $\tau$ is the time required to perform a boolean test and $\mu$ is the time required to perform a multiplication. Lookup is assumed to be constant- however this is unrealistic as N increases (more on this later). Nonetheless, we’ve satisfied Rules (1 & 2).

The solution is elegant, but it is not obvious to the passerby what it is doing. One must dissect the solution to fully grok the simplicity of the problem. This is not a desirable software trait.

A Simple Solution

For the sake of argument, let’s take a look at the straight forward solution:

public int[] exteriorProduct(int[] A) {
	int[] B = new int[A.Length];
	int p = 1;

	for(int n = 0; n < A.Length; n++)
		p *= A[n];

	for(int n = 0; n < A.Length; n++)
		B[n] = p / A[n];

	return B;
}

Given the input A, we instruct the machine to compute the product over every element and store the result into p. To get the desired answer, the product is divided by A[i]. Simple, clean and easy to understand. But alas, we used that devious division operator…

Again some quick time complexity analysis reveals the following:

$U(N) = \alpha \left(N + 1 \right)$

$V(0) = 0$
$V(N) = \mu + V(N - 1)$
$V(N) = \mu N$

$W(0) = 0$
$W(N) = \delta + W(N - 1)$
$W(N) = \delta N$

$T(N) = U(N) + V(N) + W(N)$
$T(N) = (\mu + \delta) N + \alpha (N + 1)$

Here $\delta$ is the cost of division and $\mu$ and $\alpha$ are the cost of performing multiplication and allocation, respectively.

Performance Showdown

Before we take a look at some hard numbers, lets see what the time complexity analysis says what we will should see:

$S(N) = \left( \alpha + \mu + \delta \right) N + \alpha$
$C(N) = \left( 2 \alpha + 2 \tau + 2 \mu + 1 \right) N$

$\displaystyle\lim_{N \to \infty } \frac{S(N)}{C(N)} = \frac {\left( \alpha + \mu + \delta \right) N + \alpha}{\left( 2 \alpha + 2 \tau + 2 \mu + 1 \right) N}$
$\displaystyle\lim_{N \to \infty } \frac{S(N)}{C(N)} \approx \frac {\left( \alpha + \mu + \delta \right) }{2 \left(\alpha + \tau + \mu \right) }$
$\displaystyle\lim_{N \to \infty } \frac{S(N)}{C(N)} \approx \frac {\\O(1)}{2 \cdot \\O(1)}$
$\displaystyle\lim_{N \to \infty } \frac{S(N)}{C(N)} \approx \frac {1}{2}$

So in short, the simple solution should execute twice as fast as the complex solution.

Algorithm Execution Time (ms) As a Function of N*

	10¹	10²	10³	10⁴	10⁵	10⁶	10⁷	10⁸	10⁹
Simple	0.0	0.0	0.0	0.0	0.0	15.625	125.0	1265.625	OutOfMem
Complex	0.0	0.0	0.0	0.0	0.0	31.25	312.5	2250.0	OutOfMem

* Tests conducted on Intel T2400 1.83GHz, 987 Mhz bus, 2.00 GB RAM

Just as the time complexity analysis indicated, the simple solution is approximately twice as fast as the complex solution. In addition, both solutions will become worse as N increases as lookup times no longer execute in constant time– certainly more pronounced in the complex solution.

So what…

Granted, Google is in all likelihood aiming to identify candidates who can easily produce solutions that require a tad of lateral thinking- however, this isn’t a good question to ask for a software engineering position for a number of reasons:

There is no performance gain to be had from excluding the division operator
Unnecessary complexity is introduced into a code base which will ultimately need to be refactored out, thus wasting time
And many more…

Interview questions need to focus on problems that require ingenuity, not ones that require candidates to go against common sense software engineering practices. This problem, and many like it, ignore the software engineering aspect of a job which is just as important as being clever at devising algorithms.

Written by lewellen

2008-06-22 at 7:29 pm

Posted in Uncategorized

Tagged with Brain Teaser, Google, Interview Questions

Antimatroid, The

Posts Tagged ‘Interview Questions’

Solutions to some Microsoft interview questions

Problem with an interesting little problem

A Simple Problem

A Complex Solution

A Simple Solution

Performance Showdown

So what…

Pages

Tags

Archives

Aesthetics

Computer Science

Mathematics

Security

Meta