Level 21 — Placement Problems

LEARNING OBJECTIVES

🎯 What You Will Master

Recognize patterns

Map a problem statement to heaps, hashing, DSU, segment trees or graph search.

Defend the choice

Explain why the chosen structure beats sorting, rescanning or brute force.

Trace correctly

Follow reads, comparisons, updates, rebalancing and termination without skipping loop movement.

Write interview C

Use bounded arrays and explicit structures to produce complete, explainable C solutions.

PATTERN SELECTION

🧭 Choose the Right Structure

Repeated best element Heap

Kth largest, running median, merge K lists and top-K frequency.

Fast lookup + order Hash + linked order

LRU cache needs O(1) lookup and O(1) recency updates.

Many range queries Segment Tree

Preprocess once, then answer range minimum queries in O(log n).

Growing components Disjoint Set

Union and find answer dynamic connectivity efficiently.

Minimum transformations BFS

Word Ladder is an unweighted shortest-path problem.

HEAP INTERVIEW PATTERN

1. Kth Largest Element in a Stream

Keep a min-heap containing only the largest k values seen so far. Its root is the current kth largest value.

Algorithm

Create an empty min-heap of capacity k.
Insert values until the heap contains k items.
For each later value, compare it with the root.
If it is larger, replace the root and restore heap order.
Return the root.

Why it works

Every discarded value is no larger than the k values retained. The smallest retained value is therefore exactly the kth largest.

Time O(n log k) Space O(k)

#include <stdio.h>

#define MAX 50

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapifyUp(int heap[], int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;

        if (heap[parent] <= heap[index])
            break;

        swap(&heap[parent], &heap[index]);
        index = parent;
    }
}

void heapifyDown(
    int heap[],
    int size,
    int index
) {
    while (1) {
        int left = 2 * index + 1;
        int right = left + 1;
        int smallest = index;

        if (
            left < size &&
            heap[left] < heap[smallest]
        )
            smallest = left;

        if (
            right < size &&
            heap[right] < heap[smallest]
        )
            smallest = right;

        if (smallest == index)
            break;

        swap(
            &heap[index],
            &heap[smallest]
        );

        index = smallest;
    }
}

int kthLargest(
    int values[],
    int n,
    int k
) {
    int heap[MAX];
    int size = 0; /* kth initialize */

    for (int i = 0; i < n; i++) { /* kth loop */
        int value = values[i]; /* kth read */

        if (size < k) {
            heap[size] = value; /* kth insert */
            heapifyUp(heap, size);
            size++;
        } else if (value > heap[0]) { /* kth compare */
            heap[0] = value; /* kth replace */
            heapifyDown(heap, size, 0);
        }
    }

    return heap[0]; /* kth result */
}

int main(void) {
    int values[] = {
        4, 5, 8, 2, 10, 9
    };

    int n =
        sizeof(values) /
        sizeof(values[0]);

    int k = 3;

    printf(
        "%dth largest = %d\n",
        k,
        kthLargest(values, n, k)
    );

    return 0;
}

TWO-HEAP PATTERN

2. Running Median

Use a max-heap for the lower half and a min-heap for the upper half. Balance their sizes after each insertion.

Algorithm

Compare the new value with the maximum of the lower half.
Insert it into the proper heap.
Move one root if the size difference exceeds one.
Use one root for odd size or average both roots for even size.

Invariant

Every lower-half value is at most every upper-half value, and heap sizes differ by at most one.

Insert O(log n) Median O(1)

#include <stdio.h>

#define MAX 50

void insertSorted(
    int data[],
    int *size,
    int value,
    int ascending
) {
    int index = (*size)++;

    while (index > 0) {
        int shouldMove = ascending
            ? data[index - 1] > value
            : data[index - 1] < value;

        if (!shouldMove)
            break;

        data[index] = data[index - 1];
        index--;
    }

    data[index] = value;
}

void runningMedian(
    int values[],
    int n
) {
    int lower[MAX];
    int upper[MAX];

    int lowerSize = 0;
    int upperSize = 0; /* median initialize */

    for (int i = 0; i < n; i++) { /* median loop */
        int value = values[i]; /* median read */

        if (
            lowerSize == 0 ||
            value <= lower[0]
        )
            insertSorted(
                lower,
                &lowerSize,
                value,
                0
            ); /* median add lower */
        else
            insertSorted(
                upper,
                &upperSize,
                value,
                1
            ); /* median add upper */

        if (
            lowerSize >
            upperSize + 1
        ) { /* median balance */
            int moved = lower[0];

            for (
                int j = 1;
                j < lowerSize;
                j++
            )
                lower[j - 1] = lower[j];

            lowerSize--;

            insertSorted(
                upper,
                &upperSize,
                moved,
                1
            );
        } else if (
            upperSize >
            lowerSize + 1
        ) {
            int moved = upper[0];

            for (
                int j = 1;
                j < upperSize;
                j++
            )
                upper[j - 1] = upper[j];

            upperSize--;

            insertSorted(
                lower,
                &lowerSize,
                moved,
                0
            );
        }

        double median; /* median calculate */

        if (lowerSize == upperSize)
            median =
                (lower[0] + upper[0]) /
                2.0;
        else
            median =
                lowerSize > upperSize
                    ? lower[0]
                    : upper[0];

        printf(
            "After %d: %.1f\n",
            value,
            median
        ); /* median output */
    }
}

int main(void) {
    int values[] = {
        5, 15, 1, 3, 8, 7
    };

    int n =
        sizeof(values) /
        sizeof(values[0]);

    runningMedian(values, n);

    return 0;
}

HASH + RECENCY ORDER

3. LRU Cache Simulation

A production LRU cache combines a hash table with a doubly linked list. The bounded C demonstration below keeps the same recency rule using an ordered array.

GET

Find the key.
If absent, return −1.
If present, move the entry to the front.
Return its value.

PUT

Update and move an existing key.
Otherwise evict the last entry when full.
Insert the new entry at the front.

Production O(1) Demo O(capacity)

#include <stdio.h>

#define MAX 10

typedef struct {
    int key;
    int value;
} Entry;

Entry cache[MAX];

int size = 0;
int capacity = 2; /* lru initialize */

int findKey(int key) {
    for (int i = 0; i < size; i++)
        if (cache[i].key == key)
            return i;

    return -1;
}

void moveToFront(int position) {
    Entry selected =
        cache[position];

    for (
        int i = position;
        i > 0;
        i--
    )
        cache[i] = cache[i - 1];

    cache[0] = selected;
}

int get(int key) { /* lru get */
    int position = findKey(key);

    if (position == -1)
        return -1; /* lru miss */

    int value =
        cache[position].value;

    moveToFront(position); /* lru move */

    return value;
}

void put(
    int key,
    int value
) { /* lru put */
    int position = findKey(key);

    if (position != -1) {
        cache[position].value =
            value; /* lru update */

        moveToFront(position);

        return;
    }

    if (size == capacity)
        size--; /* lru evict */

    for (
        int i = size;
        i > 0;
        i--
    )
        cache[i] = cache[i - 1];

    cache[0].key = key; /* lru insert */
    cache[0].value = value;

    size++;
}

int main(void) {
    put(1, 10);
    put(2, 20);

    printf(
        "get(1) = %d\n",
        get(1)
    ); /* lru output */

    put(3, 30);

    printf(
        "get(2) = %d\n",
        get(2)
    );

    put(4, 40);

    printf(
        "get(1) = %d\n",
        get(1)
    );

    return 0;
}

MULTI-SOURCE HEAP

4. Merge K Sorted Arrays

Place the first value from every non-empty array in a min-heap. Each extraction contributes one output and introduces at most one successor.

Algorithm

Seed the heap with each array’s first element.
Extract the smallest heap item.
Append it to the result.
Insert the next value from the same source array.
Repeat until the heap is empty.

Complexity

For N total values across K arrays, the heap never contains more than K items.

Time O(N log K) Space O(K)

#include <stdio.h>

#define K 3
#define COLS 3

typedef struct {
    int value;
    int array;
    int index;
} Item;

void sortHeap(
    Item heap[],
    int size
) {
    for (int i = 0; i < size; i++)
        for (
            int j = i + 1;
            j < size;
            j++
        )
            if (
                heap[j].value <
                heap[i].value
            ) {
                Item temp = heap[i];
                heap[i] = heap[j];
                heap[j] = temp;
            }
}

int main(void) {
    int data[K][COLS] = {
        {1, 4, 7},
        {2, 5, 8},
        {3, 6, 9}
    };

    Item heap[K];

    int heapSize = 0; /* merge initialize */

    for (
        int row = 0;
        row < K;
        row++
    ) { /* merge seed loop */
        heap[heapSize++] =
            (Item){
                data[row][0],
                row,
                0
            }; /* merge seed */
    }

    sortHeap(heap, heapSize);

    while (heapSize > 0) { /* merge loop */
        Item smallest =
            heap[0]; /* merge pop */

        printf(
            "%d ",
            smallest.value
        ); /* merge output */

        for (
            int i = 1;
            i < heapSize;
            i++
        )
            heap[i - 1] = heap[i];

        heapSize--;

        if (
            smallest.index + 1 <
            COLS
        ) {
            int nextIndex =
                smallest.index + 1;

            heap[heapSize++] =
                (Item){
                    data[
                        smallest.array
                    ][nextIndex],
                    smallest.array,
                    nextIndex
                }; /* merge advance */

            sortHeap(
                heap,
                heapSize
            );
        }
    }

    printf("\n");

    return 0;
}

RANGE QUERY PATTERN

5. Range Minimum Query

A segment tree stores the minimum of every interval. A query ignores disjoint segments, accepts fully covered segments and splits partially covered segments.

Build

Store each array value at a leaf.
Recursively build left and right halves.
Store the smaller child value in the parent.

Query

Return infinity for no overlap.
Return the node value for total overlap.
Query both children for partial overlap.

Build O(n) Query O(log n)

#include <stdio.h>

#define MAX 50
#define INF 1000000000

int tree[4 * MAX];

int minimum(int a, int b) {
    return a < b ? a : b;
}

void build(
    int values[],
    int node,
    int left,
    int right
) { /* range build call */
    if (left == right) {
        tree[node] =
            values[left]; /* range build leaf */

        return;
    }

    int middle =
        (left + right) /
        2; /* range split */

    build(
        values,
        node * 2,
        left,
        middle
    );

    build(
        values,
        node * 2 + 1,
        middle + 1,
        right
    );

    tree[node] = minimum(
        tree[node * 2],
        tree[node * 2 + 1]
    ); /* range combine */
}

int query(
    int node,
    int left,
    int right,
    int queryLeft,
    int queryRight
) { /* range query call */
    if (
        queryRight < left ||
        right < queryLeft
    )
        return INF; /* range no overlap */

    if (
        queryLeft <= left &&
        right <= queryRight
    )
        return tree[node]; /* range total overlap */

    int middle =
        (left + right) /
        2; /* range query split */

    int first = query(
        node * 2,
        left,
        middle,
        queryLeft,
        queryRight
    );

    int second = query(
        node * 2 + 1,
        middle + 1,
        right,
        queryLeft,
        queryRight
    );

    return minimum(
        first,
        second
    ); /* range query combine */
}

int main(void) {
    int values[] = {
        5, 2, 6, 3, 1, 7, 4
    };

    int n =
        sizeof(values) /
        sizeof(values[0]);

    build(
        values,
        1,
        0,
        n - 1
    );

    printf(
        "Minimum [1, 5] = %d\n",
        query(
            1,
            0,
            n - 1,
            1,
            5
        )
    ); /* range output */

    return 0;
}

DISJOINT-SET PATTERN

6. Dynamic Connectivity

Union–Find maintains changing connected components using path compression and union by rank.

Algorithm

Initially make every vertex its own parent.
Find the representative of both endpoints.
If different, attach the lower-rank tree.
Compress paths during later finds.
Two vertices are connected when their roots match.

Complexity

With both optimizations, a sequence of operations is almost linear.

Amortized O(α(n)) Space O(n)

#include <stdio.h>

#define N 6

int parent[N];
int rankValue[N];

void initialize(void) { /* dsu initialize */
    for (int i = 0; i < N; i++) {
        parent[i] = i;
        rankValue[i] = 0;
    }
}

int findSet(int value) { /* dsu find */
    if (parent[value] != value)
        parent[value] =
            findSet(
                parent[value]
            ); /* dsu compress */

    return parent[value];
}

void unionSets(
    int first,
    int second
) { /* dsu union */
    int rootA =
        findSet(first);

    int rootB =
        findSet(second); /* dsu roots */

    if (rootA == rootB)
        return;

    if (
        rankValue[rootA] <
        rankValue[rootB]
    )
        parent[rootA] =
            rootB; /* dsu attach */
    else if (
        rankValue[rootA] >
        rankValue[rootB]
    )
        parent[rootB] = rootA;
    else {
        parent[rootB] = rootA;
        rankValue[rootA]++;
    }
}

int main(void) {
    initialize();

    int edges[][2] = {
        {0, 1},
        {2, 3},
        {1, 2},
        {4, 5},
        {3, 4}
    };

    int count =
        sizeof(edges) /
        sizeof(edges[0]);

    for (
        int i = 0;
        i < count;
        i++
    ) { /* dsu edge loop */
        unionSets(
            edges[i][0],
            edges[i][1]
        );
    }

    printf(
        "A and F connected: %s\n",
        findSet(0) == findSet(5)
            ? "Yes"
            : "No"
    ); /* dsu output */

    return 0;
}

HASH + HEAP PATTERN

7. Top K Frequent Elements

Count occurrences with a frequency table, then keep only the k most frequent candidates in a min-heap.

Algorithm

Count the frequency of each distinct value.
Insert candidates until the heap size reaches k.
Compare later frequencies with the heap root.
Replace the root when a stronger candidate appears.
Return the retained values.

Complexity

For n values and u distinct values, counting is O(n) and heap selection is O(u log k).

Time O(n + u log k) Space O(u + k)

#include <stdio.h>

#define MAX 50

typedef struct {
    int value;
    int frequency;
} Frequency;

void sortByFrequency(
    Frequency heap[],
    int size
) {
    for (int i = 0; i < size; i++)
        for (
            int j = i + 1;
            j < size;
            j++
        )
            if (
                heap[j].frequency <
                heap[i].frequency
            ) {
                Frequency temp =
                    heap[i];

                heap[i] = heap[j];
                heap[j] = temp;
            }
}

int main(void) {
    int values[] = {
        1, 1, 1,
        2, 2,
        3, 3, 3, 3,
        4
    };

    int n =
        sizeof(values) /
        sizeof(values[0]);

    Frequency counts[MAX];

    int unique = 0; /* topk initialize */

    for (int i = 0; i < n; i++) { /* topk count loop */
        int position = -1;

        for (
            int j = 0;
            j < unique;
            j++
        )
            if (
                counts[j].value ==
                values[i]
            )
                position = j;

        if (position == -1)
            counts[unique++] =
                (Frequency){
                    values[i],
                    1
                }; /* topk new count */
        else
            counts[position]
                .frequency++; /* topk increase count */
    }

    int k = 2;

    Frequency heap[MAX];

    int heapSize = 0;

    for (
        int i = 0;
        i < unique;
        i++
    ) { /* topk candidate loop */
        if (heapSize < k)
            heap[heapSize++] =
                counts[i]; /* topk insert */
        else if (
            counts[i].frequency >
            heap[0].frequency
        )
            heap[0] =
                counts[i]; /* topk replace */

        sortByFrequency(
            heap,
            heapSize
        );
    }

    for (
        int i = heapSize - 1;
        i >= 0;
        i--
    )
        printf(
            "%d(%d) ",
            heap[i].value,
            heap[i].frequency
        ); /* topk output */

    printf("\n");

    return 0;
}

IMPLICIT GRAPH BFS

8. Word Ladder

Every valid word is a vertex. Two words are adjacent when they differ in exactly one position. BFS finds the minimum transformation length.

Algorithm

Enqueue the start word at level one.
Dequeue one word.
Generate or inspect one-letter neighbors.
Mark each unseen dictionary neighbor and enqueue it.
Stop when the target is dequeued or discovered.

Complexity

For D dictionary words of length L, the simple pairwise demonstration takes O(D²L). Pattern buckets can reduce neighbor discovery.

BFS shortest path Space O(D)

#include <stdio.h>
#include <string.h>

#define MAX_WORDS 20
#define LENGTH 10

int oneLetterApart(
    const char first[],
    const char second[]
) {
    if (
        strlen(first) !=
        strlen(second)
    )
        return 0;

    int differences = 0;

    for (
        int i = 0;
        first[i] != '\0';
        i++
    )
        if (
            first[i] !=
            second[i]
        )
            differences++;

    return differences == 1;
}

int wordLadder(
    char words[][LENGTH],
    int count,
    const char start[],
    const char target[]
) {
    char queue[MAX_WORDS][LENGTH];
    int level[MAX_WORDS];
    int visited[MAX_WORDS] = {0};

    int front = 0;
    int rear = 0; /* ladder initialize */

    strcpy(
        queue[rear],
        start
    );

    level[rear++] = 1; /* ladder enqueue start */

    while (front < rear) { /* ladder queue loop */
        char current[LENGTH];

        strcpy(
            current,
            queue[front]
        ); /* ladder dequeue */

        int currentLevel =
            level[front++];

        if (
            strcmp(
                current,
                target
            ) == 0
        )
            return currentLevel; /* ladder found */

        for (
            int i = 0;
            i < count;
            i++
        ) { /* ladder neighbor loop */
            if (
                !visited[i] &&
                oneLetterApart(
                    current,
                    words[i]
                )
            ) { /* ladder neighbor check */
                visited[i] = 1;

                strcpy(
                    queue[rear],
                    words[i]
                );

                level[rear++] =
                    currentLevel +
                    1; /* ladder enqueue */
            }
        }
    }

    return 0; /* ladder no path */
}

int main(void) {
    char words[][LENGTH] = {
        "hot",
        "dot",
        "dog",
        "lot",
        "log",
        "cog"
    };

    int count =
        sizeof(words) /
        sizeof(words[0]);

    printf(
        "Length = %d\n",
        wordLadder(
            words,
            count,
            "hit",
            "cog"
        )
    ); /* ladder output */

    return 0;
}

INTERACTIVE PROBLEM SOLVER

🎬 9. Premium Placement Visualizer

Choose a problem, load its example and follow every read, comparison, structural update and result.

PRIMARY INPUT PARAMETER PROBLEM

Choose a placement problem and click Load Visualizer.

🧱 Live Structure

📈 Live State

Problem —

Phase —

Current —

Comparisons 0

Updates 0

Result —

Step 0 of 0

SELECTABLE C PROGRAM TRACER

🔍 10. Program Tracing — Placement Problems

The selected complete C source appears with line numbers, executable-line highlighting, live variables and the evolving data structure.

PRIMARY INPUT PARAMETER PROGRAM

Select a C program and click Load Program Tracer.

INTERVIEW COMPLEXITY MAP

⏱️ 11. Complexity Summary

Problem	Core Structure	Time	Extra Space
Kth Largest Stream	Min-heap of k	O(n log k)	O(k)
Running Median	Max-heap + min-heap	O(n log n)	O(n)
LRU Cache	Hash + doubly linked list	O(1) average per operation	O(capacity)
Merge K Sorted Arrays	Min-heap	O(N log K)	O(K)
Range Minimum Query	Segment tree	Build O(n), query O(log n)	O(n)
Dynamic Connectivity	Disjoint set	O(α(n)) amortized	O(n)
Top K Frequent	Hash + min-heap	O(n + u log k)	O(u + k)
Word Ladder	Implicit graph + BFS	Depends on neighbor generation	O(dictionary)

PLACEMENT PRACTICE

🧪 12. Interview Problems

01

Kth Smallest in a Matrix

Use a heap without flattening the complete sorted matrix.

Treat every row as a sorted source, exactly like merge K arrays.

02

Sliding Window Median

Report the median for every window of size k.

Use two balanced multisets or heaps and support deletion of expired values.

03

LFU Cache

Evict the least frequently used key; break ties by recency.

Map keys to nodes and frequencies to recency lists.

04

Merge K Linked Lists

Merge sorted linked lists using only K heap entries.

After extracting a node, insert only its next node.

05

Range Sum with Updates

Support point updates and range sum queries.

Use a Fenwick tree or segment tree.

06

Number of Islands II

Add land dynamically and report the island count.

Create one DSU set per new land cell and union active neighbors.

07

Reorganize String

Rearrange characters so equal characters are not adjacent.

Repeatedly choose the two most frequent remaining characters.

08

Minimum Genetic Mutation

Find the minimum valid one-character mutations.

This is Word Ladder over the alphabet A, C, G and T.

09

Network Delay Time

Find when all nodes receive a signal.

Run Dijkstra and take the largest final distance.

10

Accounts Merge

Merge accounts that share at least one email.

Map each email to an account and union matching accounts.

11

Autocomplete Ranking

Return the most frequent words for a prefix.

Store top suggestions at trie nodes or search the prefix subtree with a heap.

12

Design Question

Choose structures for a real-time trending-search service.

Combine a hash table for counts, heap for top-K and time buckets for expiry.

FINAL REVISION

✅ Placement Answer Framework

1. Clarify

Confirm limits, duplicates, update frequency and required output.

2. Start simple

State the brute-force method and its bottleneck.

3. Name the pattern

Explain what must be retrieved, updated or connected repeatedly.

4. Prove an invariant

State what remains true after every operation.

5. Trace an example

Show one non-trivial input including an edge case.

6. Analyze

Give time and auxiliary-space complexity using the correct variables.

💼 Placement Problems

🎯 What You Will Master

🧭 Choose the Right Structure

1. Kth Largest Element in a Stream

Algorithm

Why it works

2. Running Median

Algorithm

Invariant

3. LRU Cache Simulation

GET

PUT

4. Merge K Sorted Arrays

Algorithm

Complexity

5. Range Minimum Query

Build

Query

6. Dynamic Connectivity

Algorithm

Complexity

7. Top K Frequent Elements

Algorithm

Complexity

8. Word Ladder

Algorithm

Complexity

🎬 9. Premium Placement Visualizer

🧱 Live Structure

🔍 10. Program Tracing — Placement Problems

PROGRAM TRACING

Complete C Source

⏱️ 11. Complexity Summary

🧪 12. Interview Problems

Kth Smallest in a Matrix

Sliding Window Median

LFU Cache

Merge K Linked Lists

Range Sum with Updates

Number of Islands II

Reorganize String

Minimum Genetic Mutation

Network Delay Time

Accounts Merge

Autocomplete Ranking

Design Question

✅ Placement Answer Framework