wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> microsoft >> Interview Questions
        
(Message started by: raj1 on Jan 31st, 2008, 5:17am)
Title: Interview Questions
Post by raj1 on Jan 31st, 2008, 5:17am
Q.1 What is the minimum number of queues needed to implement the priority queue?

Q.2 How would you find out if a machine’s stack grows up or down in memory?

Q.3 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)?
Title: Re: Interview Questions
Post by FiBsTeR on Jan 31st, 2008, 6:30am

on 01/31/08 at 05:17:30, raj1 wrote:
Q.3 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)?


Let p be the probability of seeing a car in a given 10 minutes. Then (1-p) is the probability of not seeing a car in 10 minutes, and (1-p)3 is the probability of not seeing a car in 30 minutes. But:

    (1-p)3 = 0.05
--> p = 0.63159...
Title: Re: Interview Questions
Post by Grimbal on Jan 31st, 2008, 7:04am
Q1. If you don't care about performance, you need just one.

Add: insert at the end.

Get: insert a marker in the queue, cycle the whole queue by feeding the head back to the end until you find the marker, remember the highest priority element, cycle a second time to remove that element and return it.
Title: Re: Interview Questions
Post by towr on Jan 31st, 2008, 7:13am

on 01/31/08 at 05:17:30, raj1 wrote:
Q.1 What is the minimum number of queues needed to implement the priority queue?
0?
You could implement it as a balanced binary threaded tree, to name an alternative.


Quote:
Q.2 How would you find out if a machine’s stack grows up or down in memory?
Read the machine's specification.
There is really no reliable way to tell from a program, because both compilers and OS may reverse, or not, the way they address memory. So the typical solution of adding two variables to the stack and comparing their addresses doesn't really solve the problem.
Title: Re: Interview Questions
Post by Grimbal on Jan 31st, 2008, 8:47am
Q2. I'd like to know in what situation you possibly could need that information.
OK, I can think of some, but they involve such low-level programming that you can assume you know the target hardware or you have a header file describing it.
Title: Re: Interview Questions
Post by srikanth on Jul 17th, 2008, 2:08am

on 01/31/08 at 05:17:30, raj1 wrote:

Q.2 How would you find out if a machine’s stack grows up or down in memory?


There's probably a simpler way to figure this out, but here's one way of doing it.

Local variables would be on the stack , so you could compare the address of two successive local variables.

Something like this

Code:
func1(){
   int a = 1;
   int b = 2

   if (&b - &a) > 0){
       printf("Stack grows towards larger addresses");
   }
   else{
       printf("Stack grows towards smaller addresses");
   }
}
Title: Re: Interview Questions
Post by Leonid Broukhis on Sep 17th, 2008, 5:42pm

on 01/31/08 at 07:13:41, towr wrote:
Read the machine's specification.
There is really no reliable way to tell from a program, because both compilers and OS may reverse, or not, the way they address memory. So the typical solution of adding two variables to the stack and comparing their addresses doesn't really solve the problem.

How about:

int * f(int flag) {
int * q;
if (flag == 0)  {
q = f(1);
printf("Stack grows %s\n",  q < &flag ? "downwards" : "upwards");
return NULL;
} else
return &flag;
}
Title: Re: Interview Questions
Post by towr on Sep 18th, 2008, 12:15am

on 09/17/08 at 17:42:31, Leonid Broukhis wrote:
How about:
It still falls victim to any intermediate architecture abstraction that changes memory addressing.
For example, consider ASLR (Address Space Layout Randomization), a technique used by the OS to mitigate problems such as buffer overflow attacks (I think). As the name suggests, the layout of the address space is 'randomized'; but as far as the compiler/program is concerned it doesn't notice.
Title: Re: Interview Questions
Post by Leonid Broukhis on Sep 18th, 2008, 12:38am
towr,
ASLR randomizes the positions of  the heap, stack, and dynamic libraries. It does not affect the way stack frames are allocated within the stack segment (the absolute position of which is random. The actual values of the stack/frame pointer do not matter, as far as the stack does not straddle address 0 which is unlikely to happen as most modern OSes reserve page 0 to catch dereferences of NULL.
Title: Re: Interview Questions
Post by towr on Sep 18th, 2008, 1:18am
Well, ok, so I don't know enough about ASLR. Regardless, you don't know what happens between the compiler and the hardware to the address mapping. Your program might run in a virtual machine which does all sorts of weird things behind the scenes just because its creator was on drugs.
Title: Re: Interview Questions
Post by Leonid Broukhis on Sep 18th, 2008, 12:17pm

on 09/18/08 at 01:18:51, towr wrote:
Well, ok, so I don't know enough about ASLR. Regardless, you don't know what happens between the compiler and the hardware to the address mapping. Your program might run in a virtual machine which does all sorts of weird things behind the scenes just because its creator was on drugs.


Then we'll find out the direction of stack growth in the virtual machine. Don't forget that this is an interview question.  :P


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board