How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Optiver.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Optiver during technical interviews.

Identify OS component causing process starvation

Company: Optiver

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

A system with 2 CPU cores runs 5 identical processes continuously. Four processes get equal CPU time, but the fifth appears to get none. Which part of the operating system should be examined to understand and fix why the fifth process is not running as it should, and what issues there could cause this behavior?

Quick Answer: This question evaluates understanding of process scheduling, kernel-level resource allocation, and starvation-related concurrency issues within the operating systems domain.

You are given a snapshot of processes observed on a multicore machine. Your task is to find every RUNNABLE process that appears starved and report which OS component should be inspected and the most likely issue. In this model, any reported starvation means the scheduler is the OS component to inspect. Each process is represented as (pid, state, priority, affinity_mask, runtime). A bit i in affinity_mask means the process may run on core i. Only bits 0 through cores-1 are valid; higher bits are ignored. A RUNNABLE process with runtime == 0 is suspicious only if at least one other RUNNABLE process with valid affinity received positive runtime. Classify each suspicious process as follows: issue = 'affinity' if its valid affinity mask becomes empty after masking invalid cores; issue = 'priority' if the set of other RUNNABLE processes with positive runtime, strictly higher priority, and overlapping affinity both (1) contains at least min(cores, number of valid allowed cores) processes and (2) their combined valid affinity covers every core the starved process could use; otherwise issue = 'fairness'. Return all suspicious processes as (pid, 'scheduler', issue), sorted by pid.

Constraints

0 <= len(processes) <= 2000
1 <= cores <= 30
Each pid is unique
state is either 'RUNNABLE' or 'BLOCKED'; priority, affinity_mask, and runtime are non-negative integers

Examples

Input: ([(1, 'RUNNABLE', 5, 3, 10), (2, 'RUNNABLE', 5, 3, 10), (3, 'RUNNABLE', 5, 3, 10), (4, 'RUNNABLE', 5, 3, 10), (5, 'RUNNABLE', 5, 3, 0)], 2)

Expected Output: [(5, 'scheduler', 'fairness')]

Explanation: Process 5 is runnable and can run on both cores, but it got no runtime while identical peers did. No higher-priority process explains the starvation, so this points to scheduler fairness or run-queue behavior.

Input: ([(1, 'RUNNABLE', 9, 1, 15), (2, 'RUNNABLE', 8, 2, 15), (3, 'RUNNABLE', 7, 3, 15), (4, 'RUNNABLE', 5, 3, 0)], 2)

Expected Output: [(4, 'scheduler', 'priority')]

Explanation: Process 4 can use both cores, but higher-priority runnable processes with positive runtime cover both cores and are numerous enough to keep it from running.

Input: ([(1, 'RUNNABLE', 5, 1, 10), (2, 'RUNNABLE', 5, 2, 10), (3, 'RUNNABLE', 5, 4, 0)], 2)

Expected Output: [(3, 'scheduler', 'affinity')]

Explanation: On a 2-core system, affinity bit 4 refers to a non-existent core. After masking invalid bits, process 3 has no real CPU it can run on.

Input: ([(10, 'RUNNABLE', 5, 3, 12), (11, 'RUNNABLE', 5, 3, 12), (12, 'RUNNABLE', 5, 3, 0), (13, 'RUNNABLE', 1, 4, 0)], 2)

Expected Output: [(12, 'scheduler', 'fairness'), (13, 'scheduler', 'affinity')]

Explanation: Process 12 is runnable with valid affinity but got no time despite equal-priority peers running, so it is a fairness issue. Process 13 has no valid core after masking, so it is an affinity issue.

Input: ([(1, 'RUNNABLE', 5, 3, 10), (2, 'BLOCKED', 5, 3, 0)], 2)

Expected Output: []

Explanation: The zero-runtime process is BLOCKED, not RUNNABLE, so it is not considered starvation in this model.

Input: ([(1, 'RUNNABLE', 5, 1, 0)], 1)

Expected Output: []

Explanation: With only one runnable process and no other process receiving CPU time, there is no evidence of starvation.

Hints

Mask every affinity with (1 << cores) - 1 first, so invalid core bits disappear.
Precompute the RUNNABLE processes that actually got CPU time; then compare each zero-runtime RUNNABLE process against that active set.

Quick Overview

This question evaluates understanding of process scheduling, kernel-level resource allocation, and starvation-related concurrency issues within the operating systems domain.