What is the best way to answer this scheduling algorithm scenario?

Question

This is a question I got in an interview. It is little hard to explain, please bear with me.

Imagine a Railway Ticketing Counter.

• Initially there are 3 counters.
• There is a security guard who keeps a check on the people so that no one breaks the line.
• Each counter has 2 people waiting in line. The people waiting in line came in as per the alphabetical order.
• A new 4th counter is being opened. And there are two new persons G and H about to join the line.

You are the security guard, now you get to choose who can be processed at the new counter.

Counters are marked 1, 2, 3 and 4 (blue boxes). People waiting in line are marked A, B, C and so on. Here A came first, followed by B and then C etc.

I was asked to give the answer and the logic behind the answer. The interviewer kept on asking more questions on my answers.

For example - when I said,

• I will ask D and E to move to the 4th counter;
• G will stand behind A and H will stand behind B

The interviewer argued saying how is it that E and G get the same preference (priority).

After few minutes of such arguments, I told like this seems to be a simple scheduling problem which can easily be solved if there was a common queue and the security guard sends the next person on the queue to a vacant counter following FCFS.

However, the interviewer was not impressed.

Is there a different approach which I missed? What is the right way to answer such questions?

PS: I didn't get through this round :(

Answer 1

Given my background in the topic and more years in the industry than I'll admit here ... :-) ... I have a hypothesis as to why you didn't make the next round: this is not so much a program design question as a behaviour question.

This class of interview question is often not about the solution, but about your problem-solving approach. I (interviewer) gave you a problem with several open possibilities. First of all, this is "obviously" a metaphor for an OS multi-processing situation. I want an ideal candidate to

1. Question the ticket-counter paradigm's applicability to the OS situation: what assumptions exist in the real world that don't apply to a process queue?
2. Determine the rubric for evaluating a solution.
3. Ask for more information on permitted operations.
4. Ask for a distribution of service times, arrival times, etc. to demonstrate knowledge of the scheduling paradigm.
5. Inquire about costs & trade-offs.

Armed with a better description of the problem, now I want you to work through a solution, consistently engaging your customer (me) in the general approach and the specifics. This is a critical part of the Agile approach, for instance. Also, I want to see how you explain things I don't understand.

Note that item #2 is very important: if your true customer for this is a corrupt security guard retiring at the end of the shift, then the correct solution might be to hold a bribery bidding war for access to the open counter.

Here's your homework for the next interview: what assumptions are necessary to make your given solution a good one? How can you validate those assumptions with your customer?

My immediate questions include the ones above, and ...

• What defines a good solution? best solution? unacceptable?
• What's the cost of moving a person from where they are to another place?
  • Can I take someone out of a window line and back into the queue?
  • Can I change order in the queue (i.e. common usage of "queue" rather than the canonical data structure)?
  • Can I switch someone directly from one window line to another?
• Do I have to serve every customer?
• Is that the entire queue, or is this a continuous process?

This is where my typing caught up with my thought processes, a fair point to stop.