FastPrepFIFO Pipeline IPC with Stalls
Problems/FIFO Pipeline IPC with Stalls

FIFO Pipeline IPC with Stalls

AMD logoAMD● MediumFULLTIMEONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The C++ exercise reports A FIFO capacity10, B capacity1, one incoming and one consumed instruction per cycle, memory stalls and an API for both IPCs. It omits the time window, stall schedule, same-cycle ordering and IPC numerators. This model defines consume→transfer→admit ordering, rejected offers and exact rational IPC output. Approximate source match: 80%.

Model two pipeline modules. A has a FIFO capacity of 10 instructions; B has capacity 1. Both start empty. There is one offered instruction per cycle. An instruction cannot bypass either queue.

stalled[t] is 1 when B cannot consume during cycle t and 0 otherwise. Perform these events in this exact order in each cycle:

  1. If B contains an instruction and is not stalled, consume it and increase the completed count.
  2. If B is now empty and A is not empty, move exactly one oldest instruction from A to B.
  3. If A now has room, admit the offered instruction into A. Otherwise reject that cycle's offer; rejected offers are not retried.

Let T be the number of cycles. Define A's IPC as admitted/T and B's IPC as completed/T. Return the exact fractions as four integers [admitted, T, completed, T], without reducing them. Do not drain the queues after the last cycle.

Function

pipelineIpc(stalled: int[]) → int[]

Examples

Example 1

stalled = [0,0,0]return = [3,3,1,3]

Cycle 1 admits the first instruction into A. Cycle 2 moves it to B and admits another. Cycle 3 consumes the first instruction, then transfers and admits again. A admits 3 instructions and B completes 1 in 3 cycles.

Example 2

stalled = [1,1,1,1,1,1,1,1,1,1,1,1]return = [11,12,0,12]

B fills on cycle 2 and never consumes. A fills its 10 slots by cycle 11; the offer in cycle 12 is rejected. In total 11 instructions are admitted and none completes.

Example 3

stalled = [0,0,1,0]return = [4,4,1,4]

The stall in cycle 3 keeps B occupied, while A still has room to accept. B consumes once in cycle 4. All four offers fit in A over the window.

Constraints

  • 1 <= stalled.length <= 10000.
  • Every entry of stalled is 0 or 1.

More AMD problems

  • Insert After a Linked-List NodeONSITE INTERVIEW · Seen Oct 2026
  • LRU CacheONSITE INTERVIEW · Seen Oct 2026
  • Lowest Common Ancestor of a Binary TreePHONE SCREEN · Seen Oct 2026
All AMD interview questionsSee AMD hiring insights
Saved
public int[] pipelineIpc(int[] stalled) {
    return new int[0];
}
Checking account…