In comp.os.linux.advocacy, Roy Schestowitz
<newsgroups@xxxxxxxxxxxxxxx>
wrote
on Wed, 20 Dec 2006 18:21:08 +0000
<1801258.uXVHFeri7q@xxxxxxxxxxxxxxx>:
> Have a look at these...
>
> Microsoft Interview Questions
>
> ,----[ Quote ]
> | The following are actual questions from actual interviews
> | conducted by Microsoft employees on the main campus.
> `----
>
> http://www.sellsbrothers.com/fun/msiview/default.aspx?content=question.htm
>
> The standard seems hugely lower than that of Google for example...
* Why is a manhole cover round?
So it doesn't drop in the hole. An interesting variant of this Q
might be to ask what shapes protect the hole.
* How many cars in the USA/gas stations in the USA?
A trivia question.
* How many manhole covers in the USA?
Another trivia question.
* A gold bar payment.
There is no mention about taking, only giving. A simple solution
would be 1+2+4; this would allow the following payment schedule.
Day 1: give him 1.
Day 2: give him 2, take back 1 in change.
Day 3: give him 1 again.
Day 4: give him 4, take back 1 and 2 in change.
Day 5: give him 1.
Day 6: give him 2, take back 1 in change.
Day 7: give him 1; no gold left.
* LA/NY collision.
Until he's squished. :-) Did something go missing in the
specification?
If one assumes 3500 miles the trains will collide in 100
hours and the bird will travel a total of 2500 miles.
*Where* he is squished, of course, will be 1500 miles
east of LA.
* Disk spinning.
Why is this relevant? An interesting question. I'd say 3 sensors
if one requires symmetric, 2 if one goes asymmetric. If one allows
esoteric technology such as a triangularly-shaped light sensor, one
could do it in 1 with sophisticated analysis of the light curve going
into that sensor.
* Analog clock.
The hands come together 22 times a day.
Minute hand: angle = 2*Pi*t/3600
Hour hand: angle = 2*Pi*t/43200
Delta: angle = 2*Pi*t/3600 - 2*Pi*t/43200
= 2*Pi*t*11/43200
and the hands come together whenever the angle is a multiple of 2*Pi.
* Two jars, 50 red and 50 blue.
Place one red marble in one jar and all other marbles in the other
jar. The probability of picking a red marble is therefore
(1/2) * 1 + (1/2) * (49/100) = 149/200, or almost 3/4.
Clearly this is the best one can do.
* Prime pairs.
A prime can never be divisible by 2 or 3 (unless it's
2 or 3). Therefore, if p > 3 is a prime then p = 6n+1 or
p = 6n-1 for some positive integer n >= 1. If there's
a triplet then one has the case that k0,k1,k2 are 6n+u,
6n+u+2, 6n+u+4 for some n and u; if u is even none of
these are prime. If u is odd, either u is divisible by
3, (u mod 3 == 1) or u+2 is divisible by 3, or (u mod
3 == 2) or u+1 is divisible by 3, and therefore u+1+3 =
u+4 is also divisible by 3.
* Door/switches.
This is a badly specified problem. Assuming the
problem is that the switches are locked in place (or
inaccessible) once the door is opened, but the user
can manipulate the switches with the door locked, that
the switches are not three-way or four-way units, but
two-way units, and no funny business (e.g., a gremlin
rewiring things) is going on, the user need merely do
the following sequence:
all switches off
all switches on
for each switch, that switch on
for each switch, that switch off
The user can then deduce from which lights were on with
which pattern which bulb is identified with which switch,
and whether it's mounted upside down or right side up.
If one knows the switches are also all right side up three
flips suffice.
* 8 billiard balls, one weighted heavier.
This is a variant of the old "counterfeit coin" problem and can be
solved in the same fashion. One weighing schedule might do the
following, based on binary:
1234 : 5678
1256 : 3478
1357 : 2468
so it's a maximum of 3. Of course it's a minimum of 2 if one gets
lucky enough.
* Mirror problem.
The mirror reverses front to back, and if one interprets the mirror
image as someone standing there, our interpretation flips hands.
* Pills.
Another badly specified problem -- do the jars all have the same
number of pills? Assuming they do, the "one weight" requirement
is interesting, as the standard solution requires two:
12 : 34
13 : 24
If one is allowed to pick pills one could take 1 from jar
#1, 2 from jar #2, 3 from jar #3, and *none* from jar #4.
One then weighs:
122 : 333
and determines the bad pills from the pointer deflection,
if the scale is equipped with such (if there is no
pointer deflection #4 is odd man out). If not, one may
be out of luck.
* Wordscramble.
Depends on the word. If all letters are different one has
120 possibilities. Badly specified problem, although one
might try dipthong matching.
* 4 women crossing.
The trick is to leave a woman in the dark on the far side.
1+2 cross
1 back
5+10 cross
2 back
1+2 cross again
tot: 17
1+2 cross
2 back
5+10 cross
1 back
1+2 cross again
tot: 17
* 5+3 = 4.
Fill 3.
Dump 3 into 5.
Fill 3.
Dump 3 into 5 transferring 2 leaving 1.
Discard 5.
Dump 3 into 5 transferring 1.
Fill 3.
Dump 3 into 5, leaving 4.
* Buckets of jellybeans.
A maximum of four, since there are three types of jellybeans.
* Two buckets.
The two are the same.
Initial: (1,0), (0,1)
After first transfer: (1,c), (0,1-c)
or [1+c](1/(1+c), c/(1+c)), [1-c](0,1)
After second transfer:
(1/(1+c),c/(1+c)), (0,1-c) + [c](1/(1+c),c/(1+c))
= (1/(1+c),c/(1+c)), (c/(1+c), 1-c+c^2/(1+c))
= (1/(1+c),c/(1+c)), (c/(1+c), (1-c^2+c^2)/(1+c))
= (1/(1+c),c/(1+c)), (c/(1+c), 1/(1+c))
* Linked list/array: An array is indexable, a linked list must be
walked.
* Badly specified question. What operations are desired for the list?
* Quicksort or insertion sort would both use O(n log n) time.
I'm not sure there *is* a sort that takes O(n).
* Which stock algorithms?
* Badly specified question.
Nonrecursive: create new list; for each element
pull head, stick on tail.
Recursive: construct rev(listhead->next), then tack on first element
on the head.
* Badly specified question. I can do it if I'm allowed to go forward
once:
n1 = head
n2 = head->next
n1->next = n
n->next = n2
this of course inserts n into the second position of the list.
* Quicksort, because it's easy.
* Badly specified question. I'd use a nondeterministic finite state
acceptor, mostly because I know it.
* int strlen(const char * p)
{ const char * q = p; while(*q) q++; return q-p; }
(OK, so I'm cheating.)
* int rev(char * p)
{ char * q = p; while(*q) q++;
while(--q > p) { char t = *p; *p = *q; *q = t; p++; }
* I'd probably have to tokenize and rev the pointers to do this
properly.
* Skipped.
* int comp(const char *p, const char * q)
{ while(*p && *q) { if(*p != *q) return 0; p++; q++; }
return *p == *q; }
* Badly specified question: what is "access"?
* int nbits(int n)
{
int c = 0;
while(n) { c++; n &= (n-1); }
return c;
}
* n << 3
(n << 3) - n
* If one assumes bases >= 2 only, nonnegative numbers only,
and associates d[i] with the digit in b^i, a
straightforward implementation is possible along the following lines:
int* add(int a[], int b[], int n, int base)
{
int c = 0;
int* r = new int[n+1];
for(int i = 0; i < n; i++)
{
int t = a[i] + b[i] + c;
if(t >= base)
{
c = 1;
r[i] = t - base;
}
else
{
c = 0;
r[i] = t;
}
}
r[n] = c;
return r;
}
* FILE * readBounded(char * b, int o, int n, FILE * fp)
{ return fread(b+o, n, 1, fp); }
* Badly specified question.
* Sort the array then pick.
* Sort the strings using the previous, then merge.
* Standard diropen recursive search.
* Badly specified question. I'd use a ringbuffer.
* I'd clear each node in the space (used or unused), then walk the list,
marking nodes. If I come to a node already marked, I've got a cycle.
One can also use an associative array.
* void shuffle(int * cards, int ncards)
{
for(int i = ncards-1; i > 1; i--)
{
int x = nextInt(i+1); // random picker from 0 to i inclusive
swap(cards[i], cards[x]);
}
}
* cwd: dx = sgn(AX)
xor ax, dx: ax = AX or ax = -AX-1
sub ax, dx: ax = -1 or ax = 2 * AX
* Wow. That's an interesting one. I'd have to use a thread semaphore.
* int atoi(char * p) {
int d = 0; while(*p && isdigit(*p)) { d = d*10 + *p-'0'; }
return d;
}
* A modified version of the shuffle algorithm above would do it, if it
has a count scratchpad. One can also attempt recursion.
* You're kidding, right?
A variant of the buddy system might work here.
* int fib(int n) { if(n < 2) return 1; return fib(n-1) + fib(n-2); }
void printfib(int n) {
for(int i =0; i < n; i++) printf("%d\n", fib(i)); }
}
* If one assumes nul termination one is going to have problems.
If one has lengths one simply copies backwards.
* Quickly? :-)
* void printTree(TreeNode * n, int lev)
{
indent(lev); printNode(n);
for(TreeNode * c = n->children().firstchild(); c; c =
c->nextChild())
printTree(c, lev+1);
}
Wow. I'm not going to do the rest. :-)
>
>
> As the former Project Manager of Excel said:
>
> ,----[ Quote ]
> | The only way Microsoft has managed to hire so many people
> | has been by lowering their hiring standards significantly...
> `----
>
> http://www.joelonsoftware.com/items/2006/11/24.html
--
#191, ewill3@xxxxxxxxxxxxx
Useless C++ Programming Idea #23291:
void f(item *p) { if(p != 0) delete p; }
--
Posted via a free Usenet account from http://www.teranews.com
|
|
