Author |
Topic: MS/Google interview questions (I) (Read 9288 times) |
|
Ivan
Junior Member
Gender: 
Posts: 70
|
 |
MS/Google interview questions (I)
« on: Sep 26th, 2006, 1:10am » |
 Quote  Modify
|
Here are some questions I met recently during MS/Google interviews. I'd share some interesting ones with you, with the last one being the most difficult.
Q1. Write a C program which measures the the speed of a context switch on a Linux system.
Q2. A string contains a simple arithmetic expression. All numbers are one-digit, no spaces allowed, only two operations: * and +. Write a program to evaluate the expression with one scan.
For example, "3+2*3+1" would return 10.
Q3. John and Mary have agreed to meet for a date sometime between 9pm and 10pm. Each of them randomly picks a time within this interval and shows up and waits for the other for fifteen minutes. What is the probability that they will actually meet?
Q4. Given a pointer to a string, how to print it out without defining any variable?
Q5. Find ALL the palindrome in a string. How to do that in
1) O(n log n)
2) O(n)
3) O(log n)
You do not have to output all the palindromes that contained in a palindromes.
For example, for "abcbaabc", you need to indicate two palindromes: "abcba" and "cbaabc".
Any thoughts.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: MS/Google interview questions (I)
« Reply #1 on: Sep 26th, 2006, 2:48am » |
Quote Modify
|
for Q2 (in javascript, you can just copy-paste it to the browser in linux, or as one line in windows.):
Code:
javascript:
a="3+2*3+1";
s=0.0;
i=0;
while(i < a.length)
{
m=a[i];
while(i < a.length-2 && a[i+1] == "*")
{
i=i+2;
m*=a[i];
}
s+=1.0*m;
i=i+2;
}
alert(s);
|
|
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: MS/Google interview questions (I)
« Reply #2 on: Sep 26th, 2006, 2:51am » |
Quote Modify
|
Q2. Design it as an finite state automata where there are 2 nodes, one + and one * and one start node.
Assume that there is an accumulator which is accumulating the result.
+ transits to + --> add arguments
+ transits to * --> subtract first argument from accumulator, multiply first with second and add the result to accumulator
* transits to + --> add the arguments
* transits to * --> multiply the arguments
Q3. Already there in the forum (not in CS section though) just search the forum for "meeting time" IIRC.
Q4. What was the point of this question?
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: MS/Google interview questions (I)
« Reply #4 on: Sep 26th, 2006, 5:28am » |
Quote Modify
|
Q4: well, assuming a function which accepts a single parameter but defines no variables of its own, there's the obvious:
void print_string(const char * p) { printf("%s", p); },
and the simple:
void print_string(const char * p) { while (*p) putc(*p++); }
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: MS/Google interview questions (I)
« Reply #5 on: Sep 26th, 2006, 5:52am » |
Quote Modify
|
on Sep 26th, 2006, 1:10am, Ivan wrote:
Q5. Find ALL the palindrome in a string. How to do that in
<..>
3) O(log n) |
|
Unless n is something other than the number of characters in the string, O(log n) isn't possible, because you have to look at all characters.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Margit
Junior Member
Gender: 
Posts: 54
|
|
Re: MS/Google interview questions (I)
« Reply #6 on: Sep 27th, 2006, 10:16am » |
Quote Modify
|
Q1: Can't be done.
See http://en.wikipedia.org/wiki/Context_switch
How can you measure (and in what units) a hardware switch ?
Not possible from user space.
On what architecture ?
(Geez it's MS - Got to be Intel)
In fact this question is answered by the last paragraph in Wikipedia.
This is just an MS slant at Linux.
Linux takes into account FP operations.
|
|
IP Logged |
|
|
|
Margit
Junior Member
Gender:
Posts: 54
|
|
Re: MS/Google interview questions (I)
« Reply #7 on: Sep 27th, 2006, 11:21am » |
Quote Modify
|
And if you think I am not qualified to say this,then I would recommend checking the Linux source
- specifically
drivers/hwmon/lm85.c
- and
net/wireless/prism54
for 2.6 kernels.
|
|
IP Logged |
|
|
|
KWillets
Junior Member
Posts: 84
|
|
Re: MS/Google interview questions (I)
« Reply #8 on: Sep 27th, 2006, 1:40pm » |
Quote Modify
|
Q5 is an application of suffix trees and constant-time lca lookups.
| hidden: |
Given string S, insert S and reverse(S) in a suffix tree T.
Compute O(1) lca (lowest common ancestor) info on T (O(n) precalculation step).
Having the lca available on T means that given any two suffixes from S and Reverse(S), we can find their longest common prefix (which ends at the lca of their leaf nodes in T), in constant time.
Specifically, given a position q in S, we can find how far characters match in each direction by looking up the suffix starting at q and going right (in S), and the suffix starting just to the left of q and going left (from Reverse(S)). The lca of these two suffixes corresponds to the maximal palindrome centered at q.
n values of q, and O(1) lookups at each one gives O(n) complexity.
(This is in Gusfield's string algo. book; the lca problem has been discussed here before also.)
|
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: MS/Google interview questions (I)
« Reply #9 on: May 16th, 2010, 8:49am » |
Quote Modify
|
Note: I just removed an irrelevant post ("very interesting i long tome search this") just to avoid this page linking to the poster's profile page which in turn links to a commercial site.
|
| « Last Edit: May 16th, 2010, 9:01am by Grimbal » |
IP Logged |
|
|
|
wangzhen
Newbie
Posts: 21
|
For Q3:
The probobality of not meeting is:
|
|
IP Logged |
 |
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: MS/Google interview questions (I)
« Reply #11 on: Dec 17th, 2010, 10:39pm » |
Quote Modify
|
on May 17th, 2010, 4:15am, wangzhen wrote:For Q3:
The probobality of not meeting is:
|
|
This is the probability of meeting.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: MS/Google interview questions (I)
« Reply #12 on: Mar 8th, 2011, 6:20pm » |
Quote Modify
|
on Sep 26th, 2006, 1:10am, Ivan wrote:Q1. Write a C program which measures the the speed of a context switch on a Linux system.
|
|
yield.c:
#include <sched.h>
main() {
int i;
for (i = 0; i < 1000000; i++) sched_yield();
}
make yield
time yield # on an unloaded machine
1000000/wallclock_time will approximate the number of context switches per second. On my 3 GHz Core Duo I get about 6400.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print