Solve queue switch and coin change puzzles

This entry contains two separate interview-style quantitative/algorithmic questions.

1. Queue switching decision problem

You are standing in a single FIFO queue of 100 customers waiting for service at a checkout counter. Customers are served one at a time, and each service takes the same fixed amount of time (say, one time unit). Positions are numbered 1 (front of the line, served next) through 100 (back of the line).

At time 0, a second identical checkout counter opens. Each of the other 99 customers independently decides to move to the new queue with probability 1/2. All those who choose to move (possibly including you) are randomly ordered in the new queue; every ordering of the movers is equally likely. Both checkout counters start serving at the same time and serve at the same rate (one customer per time unit) from their respective queues.

You are currently at position k in the original queue (1 ≤ k ≤ 100). You must decide once at time 0 whether to stay in the original queue or move to the new one.

1. Derive an expression for your expected waiting time until service if you stay in the original queue as a function of k .
2. Derive an expression for your expected waiting time until service if you switch to the new queue, taking into account that:
   • Each of the other 99 customers moves independently with probability 1/2.
   • If you move, your position among all movers is uniformly random.
   • Both queues are then served in parallel at the same rate.
3. For which values of k is it better in expectation (i.e., gives a lower expected waiting time) to switch rather than stay? Give the threshold value(s) of k where your preference changes.

You may assume that everyone else’s decision to move or stay is independent of your own and of their position; you are not required to model strategic behavior.

2. Coin change combinations with US-style denominations

You are given an integer amount n representing a value in cents and you have an unlimited supply of the following coin denominations:

• 1 cent
• 5 cents
• 10 cents
• 25 cents
• 100 cents (i.e., 1 dollar)

You want to know in how many distinct combinations (multisets) you can make exactly n cents using these coins. The order of coins does not matter; for example, 1 + 5 is the same combination as 5 + 1.

Task:

1. Define the problem formally in terms of counting integer solutions.
2. Design an algorithm that, given n (say up to 10,000), returns the number of distinct combinations of coins whose total value is exactly n .
3. Analyze the time and space complexity of your algorithm.

You do not need to print the actual combinations, only their count.