What is the best way to answer this scenario of the planning algorithm?

Question

This is a question I received in an interview. It is difficult to explain, please bear with me.

Imagine a train ticket counter.

• First there are three counters.
• There is a guard who keeps a check on people so that no one breaks the line.
• Each counter has 2 people in line. People waiting in line entered in alphabetical order.
• A new 4th counter opens. And there are two new people G and H who are going to join this line.

You are a security guard, now you can choose who can be processed on the new counter.

Counters are marked 1, 2, 3 and 4 (blue squares). People waiting in line are marked A, B, C, etc. First came A, then B, then C, etc.

I was asked to give an answer and the logic of the answer. The interviewer continued to ask more questions about my answers.

For example, when I said

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

The interviewer claimed that this means that E and G are given the same preference (priority).

After several minutes of such arguments, I said that this seems like a simple scheduling problem that can be easily solved if there is a common queue, and the guard sends the next person to the queue to an empty counter after FCFS.

However, the interviewer was not impressed.

Is there any other approach that I skipped? What is the correct answer to such questions?

PS: I did not go through this round :(

Answer 1

Given my experience in this topic and more years in the industry than I admit here ... :-) ... I have a hypothesis about why you did not make the next round: this is not a question about program design as a question about behavior.

This interview question is often not related to a solution, but to your problem solving. I (the interviewer) gave you a problem with several open possibilities. First of all, this is an “obvious” metaphor for the multiprocessor OS situation. I want the perfect candidate for

• The question of the applicability of the ticket counter paradigm to the OS situation: what assumptions exist in the real world that do not belong to the process queue?
• Define a rubric to evaluate the solution.
• Request additional information about permitted operations.
• Request distribution of service times, arrival times, etc., to demonstrate knowledge of the planning paradigm.
• Learn about costs and compromises.

Armed with a better description of the problem, now I want you to work through the solution, consistently attracting your client (me) to the general approach and specifics. For example, this is a critical part of the Agile approach. In addition, I want to see how you explain things that I do not understand.

Please note that element number 2 is very important: if your true client is a corrupt guard who resigns at the end of the shift, then a war on bribery to gain access to an open counter might be the right decision.

Here is your homework for the next interview: what assumptions are necessary for your decision to be good? How can you confirm these assumptions with your client?

My immediate questions include those that were higher, and ...

• What determines a good decision? the best solution? unacceptable?
• What is the cost of moving a person from where he is in another place?
  • Is it possible to take someone from the window line and return to the queue?
  • Is it possible to change the order in the queue (ie, use the "queue" rather than the canonical data structure)?
  • Is it possible to switch someone directly from one window line to another?
• Do I have to serve each customer?
• Is this a whole queue, or is it an ongoing process?

That's where my typing caught up with my thought processes, a fair moment to stop.

Answer 2

If people act in alphabetical order, and each of them will be served at about the same time, then IMO the most “fair” solution would be for mode D for the new counter, move E after A , move F after B , then let G and H move, i.e.

 1 2 3 4 1 2 3 4 ---------- ---------- ABC >> ABCD DEFEFGH 

The logic is that since A came first, it must be served first, so E will receive a counter faster than standing after A , and not stand after B

Update comments: To avoid many movements:

 1 2 3 4 1 2 3 4 1 2 3 4 ---------- ---------- ---------- ABC >> ABCD >> ABCD DEFEFGEFH GH 

For four people in line:

 1 2 3 4 1 2 3 4 1 2 3 4 ---------- ---------- ---------- ABCABCDABCD DEF >> EFH >> GEFH GHIGILJKIL JKLJKMNOP MNOP 

Answer 3

My suggestion would be

D-> 4, E-> 1, F-> 2, G-> 3, H-> 4

on the assumption that each person will take the same amount of time in the rack. This way everything will be processed in the correct order.

If each user will take another unknown time on the counter, then the queue is the only valid solution (in addition to switching lines every time someone is processed, which is practically the same).