techInterview Discussion

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

Designing a structure for a pool of MRU processes

I got this question before from an interview. Haven't really got an answer for it. I have an idea but not sure if it's good.

Suppose in a system, there is a pool of processes, say you have 1 calculator running, 1 outlook express running, 1 MSN messenger and 1 Netmeeting.

You are to manage this system of processes in a Most-Recently-Used format. If this is a stack it would look like:

A (top)
B
C
D (bottom)

Every time a process is referenced/touched it moves to the top. Say if D is touched by user, it moves to the top of the structure now:

D
A
B
C

3 procedures to implement:
- add (int pid) simple, like push for stack
- get (int ii), where ii is the # of processes to return
- touch (int pid), you need to find the right process, remove it, and put it as most recently used

The tricky part is how to efficiently browse through the pool of processes fast enough so that you can remove it and put it to the top of this structure? Coz right now for a stack you need to pop everything to access C, worst case  you need to go though each element to find your process.
nicky Send private email
Thursday, March 16, 2006
 
 
The splay tree data structure fits really well for touch operation. It gives you O(1) complexity for touch. Add would go to O(n) in the worst case. As far as get is concerned I'm thinking of some modification to splay tree. Any ideas?

Friday, March 17, 2006
 
 
how about using hashes, insertion and lookup would be very easy
misty Send private email
Friday, April 14, 2006
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz