Author |
Topic: Interview Questions (Read 6458 times) |
|
raj1
Newbie
Posts: 15
|
 |
Interview Questions
« on: Jan 31st, 2008, 5:17am » |
 Quote  Modify
|
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)?
|
|
 IP Logged |
|
|
|
FiBsTeR
Senior Riddler
Gender: 
Posts: 581
|
|
Re: Interview Questions
« Reply #1 on: Jan 31st, 2008, 6:30am » |
Quote Modify
|
on Jan 31st, 2008, 5:17am, 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...
|
| « Last Edit: Jan 31st, 2008, 6:32am by FiBsTeR » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Interview Questions
« Reply #2 on: Jan 31st, 2008, 7:04am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Interview Questions
« Reply #3 on: Jan 31st, 2008, 7:13am » |
Quote Modify
|
on Jan 31st, 2008, 5:17am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Interview Questions
« Reply #4 on: Jan 31st, 2008, 8:47am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Colonel Panic
Newbie
Gender:
Posts: 9
|
|
Re: Interview Questions
« Reply #5 on: Jul 17th, 2008, 2:08am » |
Quote Modify
|
on Jan 31st, 2008, 5:17am, 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");
}
}
|
|
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Interview Questions
« Reply #6 on: Sep 17th, 2008, 5:42pm » |
Quote Modify
|
on Jan 31st, 2008, 7:13am, 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;
}
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Interview Questions
« Reply #7 on: Sep 18th, 2008, 12:15am » |
Quote Modify
|
on Sep 17th, 2008, 5:42pm, Leonid Broukhis wrote: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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Interview Questions
« Reply #8 on: Sep 18th, 2008, 12:38am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Interview Questions
« Reply #9 on: Sep 18th, 2008, 1:18am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Interview Questions
« Reply #10 on: Sep 18th, 2008, 12:17pm » |
Quote Modify
|
on Sep 18th, 2008, 1:18am, 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. 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print