← Back to blog IMC OA SWE Debrief: Grid Pass DP + Weighted LFU Cache
OA IMC

IMC OA SWE Debrief: Grid Pass DP + Weighted LFU Cache

2026-08-15

I ran through the IMC SWE OA for a candidate. The volume is small but the difficulty is real, so here's a debrief for anyone prepping. It's 2 coding problems in 120 minutes on HackerRank with your language of choice, medium-to-hard, mainly testing algorithm fundamentals, engineering sense, and efficient implementation. If you want OA assist or OA live support, you can align your pacing with this debrief.

OA Overview and Time Allocation

Aspect Details
Platform HackerRank, language of your choice
Time 120 minutes
Volume 2 coding problems
Difficulty Medium-to-hard
Focus Algorithm fundamentals, engineering sense, efficient implementation

Two problems, 120 minutes. The key is to avoid getting stuck in problem 1 for the first half hour, which leaves no time to read and shore up edge cases on problem 2. A suggested rhythm:

  1. Read both problems fully first, and judge which has the clearer state.
  2. Aim to write a version of problem 1 that passes samples and the main tests within 35 to 45 minutes.
  3. On problem 2, get the correct state first, then handle space compression, pruning, or complexity optimization.
  4. Reserve the last 10 minutes to check empty input, extreme values, duplicate elements, integer overflow, and initialization.

Q1: Grid Path Counting with Passes

Problem

Given a grid of 0s and 1s, a robot starts at the top-left (0,0), can only move right or down, and aims to reach the bottom-right. 1 means passable normally, 0 means an obstacle, but the robot may use up to k passes, each consuming one to cross an obstacle — including the start and end cells. Count all valid paths, modulo 10^9 + 7.

Approach

Use 3D dynamic programming. Define dp[i][j][t] as the number of paths reaching (i,j) having used t passes:

Finally sum all end-cell states using 0 through k passes. Time complexity O(nmk), space O(nmk), reducible to O(mk) with a rolling array.

Python Implementation

MOD = 10**9 + 7


def count_paths(grid, k):
    """grid: 0/1 matrix; k: pass budget (obstacles, start, and end all consume).
    Returns valid right/down path count from top-left to bottom-right % 1e9+7."""
    n, m = len(grid), len(grid[0])
    # dp[j][t]: paths reaching column j in the current row having used t passes (rolling)
    dp = [[0] * (k + 1) for _ in range(m)]

    start_cost = 0 if grid[0][0] == 1 else 1
    if start_cost <= k:
        dp[0][start_cost] = 1

    for i in range(n):
        for j in range(m):
            if i == 0 and j == 0:
                continue
            cost = 0 if grid[i][j] == 1 else 1   # an obstacle consumes one pass
            ndp = [0] * (k + 1)
            for t in range(cost, k + 1):
                total = 0
                if j > 0:
                    total += dp[j - 1][t - cost]  # coming from the left (already this row)
                if i > 0:
                    total += dp[j][t - cost]      # coming from above (dp[j] still prev row)
                ndp[t] = total % MOD
            dp[j] = ndp
    return sum(dp[m - 1]) % MOD

Mind the timing of the "left" and "above" references in the rolling array: when processing (i,j), dp[j-1] should already hold this row's value while dp[j] still holds the previous row's. If the timing feels error-prone, use a full 3D dp[i][j][t] in the exam — it's the safest; compress space only after it passes.

Time complexity: O(nmk). Space complexity: O(mk) with a rolling array, O(nmk) for the full version.

Q2: Capacity-Limited Weighted LFU Cache

Problem

Implement a weighted LFU cache limited by total capacity. Each entry has key, value, size, and the sum of all size cannot exceed capacity:

Approach

Use a hash map from key to a cache node, plus frequency buckets each ordered by recency, tracking min_freq and the running total size:

With a hash map plus frequency buckets, each access, update, and eviction runs in amortized O(1). Here Python's OrderedDict per frequency bucket naturally maintains LRU order within the bucket, keeping the code short and equivalent to hand-writing a doubly linked list.

Python Implementation

from collections import defaultdict, OrderedDict


class WeightedLFU:
    def __init__(self, capacity):
        self.capacity = capacity
        self.size_used = 0
        self.node = {}                          # key -> [value, size, freq]
        self.freq = defaultdict(OrderedDict)    # freq -> OrderedDict[key]; head = LRU
        self.min_freq = 0

    def _remove_from_bucket(self, key, f):
        """Pull key out of frequency bucket f; if empty, clear it and raise min_freq."""
        del self.freq[f][key]
        if not self.freq[f]:
            del self.freq[f]
            if self.min_freq == f:
                self.min_freq = f + 1           # this bucket is empty; min freq moves up

    def _bump(self, key):
        """Cache hit: move key from bucket f to the tail of bucket f+1 (most recent)."""
        item = self.node[key]
        f = item[2]
        self._remove_from_bucket(key, f)
        item[2] = f + 1
        self.freq[f + 1][key] = None            # tail = most recently used

    def get(self, key):
        if key not in self.node:
            return -1
        self._bump(key)
        return self.node[key][0]

    def _evict(self, need):
        """Evict until there is room for need: pop the head (LRU) of the min_freq bucket."""
        while self.size_used + need > self.capacity and self.node:
            bucket = self.freq[self.min_freq]
            old_key, _ = bucket.popitem(last=False)   # head = least recently used
            self.size_used -= self.node[old_key][1]
            del self.node[old_key]
            if not bucket:
                del self.freq[self.min_freq]
                # next iteration continues from the new min_freq bucket if needed

    def put(self, key, value, size):
        if size > self.capacity:
            return                              # single entry over capacity: ignore
        if key in self.node:                    # update: value/size change, freq unchanged
            item = self.node[key]
            f = item[2]
            self._remove_from_bucket(key, f)    # pull out first, avoid evicting itself
            self.size_used += size - item[1]
            item[0], item[1] = value, size
            self._evict(0)                      # after growing, it may overflow
            self.freq[f][key] = None            # back into bucket f tail (most recent)
            if f < self.min_freq or not self.freq.get(self.min_freq):
                self.min_freq = min(self.freq) if self.freq else f
            return
        self._evict(size)                       # insert: make room
        self.node[key] = [value, size, 1]
        self.freq[1][key] = None
        self.size_used += size
        self.min_freq = 1

The key point when updating an existing key: pull the old node out of its frequency bucket before triggering eviction so the just-updated key isn't wrongly removed; then put it back into bucket f (frequency unchanged), refresh it as most recent, and fix min_freq by the smallest remaining bucket.

Complexity: get / put are amortized O(1) (hash lookup plus head/tail operations on the bucket's OrderedDict are O(1)); evicting one node is O(1), and fixing min_freq with min(self.freq) is effectively constant when the number of buckets is small.

Prep Strategy

FAQ

Q1: How hard is the IMC SWE OA? How does it compare to LeetCode?

Two problems, 120 minutes, medium-to-hard. The algorithms aren't the hardest tier, but the emphasis is on complete engineering implementation and edge handling — the counting DP must handle pass consumption and the modulo cleanly, and the LFU must maintain frequency buckets, LRU, and capacity eviction correctly, so it's more meticulous than a pure LeetCode medium.

Q2: What platform, how long, and how many problems for the IMC SWE OA?

HackerRank, language of your choice, 120 minutes, 2 coding problems. Time is relatively generous, but both problems need modeling and edge-case work, so pacing matters.

Q3: Does Q1's pass-based path counting have to use 3D DP?

Yes, because "how many passes used" is a state dimension you must track. dp[i][j][t] is the most intuitive; after it passes, a rolling array can drop the row dimension to O(mk) space. Note that obstacles, the start, and the end all consume passes.

Q4: How does a weighted LFU differ from a plain LFU?

A plain LFU evicts by count; a weighted LFU accumulates each entry's size, and the total cannot exceed capacity, so one PUT may evict several entries to make room. Additionally, "updating an existing key doesn't change frequency" and "a single entry over capacity is ignored" are two rules specific to the weighted version.

Q5: How do I prep for an engineering-heavy OA like IMC's?

Focus on two types: DP with an extra state dimension (like the passes here), and system-simulation problems like LRU/LFU that need a hash map plus linked list. When practicing, force yourself to get the correct state before optimizing, and build the habit of a final edge-case walkthrough.

Preparing for the IMC SWE OA or another quant/trading firm's OA? We're familiar with this rhythm — HackerRank, your choice of language, two problems in 120 minutes — and can help you nail the modeling and edge cases for DP with extra state dimensions and LRU/LFU system-simulation problems, with full OA assist and OA live support.

Add WeChat Coding0201 now to get a one-on-one custom prep plan.

Contact