A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor
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:
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:
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.
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
This topic is archived. No further replies will be accepted.Other recent topics
Powered by FogBugz