← Back to blog IMC SWE OA: Grid Paths + Weighted LFU Cache
OA IMC

IMC SWE OA: Grid Paths + Weighted LFU Cache

2026-08-09

I recently took IMC's SWE OA: two coding problems, 120 minutes, on HackerRank, with your choice of language. Overall it sits at medium-to-hard, and it isn't about flashy tricks. It tests algorithm fundamentals, engineering thinking, and efficient implementation. This debrief lays out the approach, Python solutions, and complexity for both problems, plus how to budget your time. If you're in line for IMC's OA too, I hope this note helps you dial in your pace and mindset.

Environment and Format Overview

The whole OA runs on HackerRank, any language allowed. Both problems ship with a handful of visible samples plus hidden test cases, and your score comes from the pass rate. The prompts read like engineering specs: edge conditions are stated sparingly, so you have to think through the corner cases yourself.

Item Details
Platform HackerRank (choose your own language)
Format Online coding, graded on samples plus hidden test cases
Total time 120 minutes
Count 2 problems
Difficulty Medium-to-hard
Focus Algorithm fundamentals, engineering thinking, efficient implementation, edge cases

Time-Management Advice

Two problems in 120 minutes looks roomy, but the second one can eat all your time if you over-engineer it. Here's what worked for me:

Problem 1: Counting Grid Paths with Passes

Background

Given a grid of 0s and 1s, a robot starts at the top-left (0, 0), moves only right or down, and targets the bottom-right. 1 is passable, 0 is an obstacle, but the robot holds at most k passes, and each pass lets it force its way through one obstacle cell (including the start and end cells). Count all valid paths, modulo 1e9+7.

Approach

This is a beefed-up grid path count with an extra "passes" dimension, which naturally suggests a 3D DP:

Abstract "passes spent on entry" into a cost (0 for a 1 cell, 1 for a 0 cell) and the transition unifies to dp[i][j][t] = dp[i-1][j][t-cost] + dp[i][j-1][t-cost].

Python Solution

from typing import List

MOD = 10**9 + 7


def count_paths(grid: List[List[int]], k: int) -> int:
    """Count paths from top-left to bottom-right using at most k passes, mod 1e9+7.

    dp[i][j][t] = number of paths reaching (i, j) having used t passes.
    Entering a 1 cell spends no pass; entering a 0 cell spends one pass.
    """
    n, m = len(grid), len(grid[0])

    # dp[i][j][t], with t ranging over 0..k
    dp = [[[0] * (k + 1) for _ in range(m)] for _ in range(n)]

    # Init the start: if the start is an obstacle, entering it spends a pass
    start_cost = 0 if grid[0][0] == 1 else 1
    if start_cost <= k:
        dp[0][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
            # States with fewer than cost passes are impossible; start at cost
            for t in range(cost, k + 1):
                total = 0
                if i > 0:
                    total += dp[i - 1][j][t - cost]  # coming from above
                if j > 0:
                    total += dp[i][j - 1][t - cost]  # coming from the left
                dp[i][j][t] = total % MOD

    # Sum over t = 0..k at the end cell
    return sum(dp[n - 1][m - 1][t] for t in range(k + 1)) % MOD

Time complexity: O(nmk), each cell computed once per pass count. Space complexity: O(nmk). Since row i only depends on row i-1, a rolling array reduces this to O(m*k).

Dry Run Walkthrough

A 2x2 grid shows the role of passes best: grid = [[1, 0], [0, 1]], k = 1. The start (0,0) is 1, so dp[0][0][0] = 1.

Cell Type cost Transition Result
(0,1) 0 1 dp[0][1][1] = dp[0][0][0] (left) dp[0][1][1] = 1
(1,0) 0 1 dp[1][0][1] = dp[0][0][0] (up) dp[1][0][1] = 1
(1,1) 1 0 t=0: up 0 + left 0; t=1: up 1 + left 1 dp[1][1][0]=0, dp[1][1][1]=2

Summing the end cell over t = 0..1 gives 0 + 2 = 2. That matches two paths: right-then-down (through obstacle (0,1)) and down-then-right (through obstacle (1,0)), each spending one pass.

Boundaries to raise proactively:

Problem 2: A Size-Weighted LFU Cache

Background

Implement a size-weighted LFU cache. Each entry has a key, value, and size, and the sum of all sizes cannot exceed the total capacity. It supports two operations:

Approach

A weighted twist on classic LFU, with the same core structures:

  1. A hash map key -> Node for O(1) lookup.
  2. Per-frequency doubly linked lists ordered by recency: head is newest, tail is oldest.
  3. Tracking min_freq (the current lowest frequency) and total (the currently used capacity).

Key points per operation:

Python Solution

from collections import defaultdict


class Node:
    """A cache node that doubles as a doubly linked list node."""

    __slots__ = ("key", "value", "size", "freq", "prev", "next")

    def __init__(self, key=None, value=None, size=0):
        self.key = key
        self.value = value
        self.size = size
        self.freq = 1
        self.prev = None
        self.next = None


class DoublyLinkedList:
    """Holds nodes of one frequency, ordered by recency: head newest, tail oldest."""

    def __init__(self):
        self.head = Node()  # sentinel head
        self.tail = Node()  # sentinel tail
        self.head.next = self.tail
        self.tail.prev = self.head
        self.count = 0  # number of nodes in the list

    def add_front(self, node: Node) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
        self.count += 1

    def remove(self, node: Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev
        self.count -= 1

    def remove_last(self) -> Node:
        node = self.tail.prev  # least recently used
        self.remove(node)
        return node

    def is_empty(self) -> bool:
        return self.count == 0


class WeightedLFUCache:
    """A size-weighted LFU cache with average O(1) get / put."""

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.total = 0          # currently used capacity
        self.min_freq = 0       # current lowest frequency
        self.nodes = {}         # key -> Node
        self.freqs = defaultdict(DoublyLinkedList)  # freq -> list

    def _bump(self, node: Node) -> None:
        """Increment frequency and move the node from the old list to the new one's head."""
        old = node.freq
        self.freqs[old].remove(node)
        if self.freqs[old].is_empty() and old == self.min_freq:
            self.min_freq += 1
        node.freq += 1
        self.freqs[node.freq].add_front(node)

    def _evict_until(self, need: int) -> None:
        """Free enough room for need: evict from the min-freq list's tail one by one."""
        while self.nodes and self.total + need > self.capacity:
            while self.freqs[self.min_freq].is_empty():
                self.min_freq += 1
            victim = self.freqs[self.min_freq].remove_last()
            del self.nodes[victim.key]
            self.total -= victim.size

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

    def put(self, key, value, size: int) -> None:
        # A single entry larger than the whole capacity: ignore
        if size > self.capacity:
            return

        if key in self.nodes:
            # Update an existing entry: frequency unchanged, only value / size and recency
            node = self.nodes[key]
            old_freq = node.freq
            self.freqs[old_freq].remove(node)
            self.total -= node.size
            del self.nodes[key]           # pull it out temporarily so it can't evict itself
            self._evict_until(size)
            node.value, node.size = value, size
            self.freqs[old_freq].add_front(node)
            self.nodes[key] = node
            self.total += size
            self.min_freq = min(self.min_freq, old_freq)
            return

        # New entry: make room first, then insert at frequency 1
        self._evict_until(size)
        node = Node(key, value, size)     # new node starts at frequency 1
        self.freqs[1].add_front(node)
        self.nodes[key] = node
        self.total += size
        self.min_freq = 1

Time complexity: average O(1) for both get and put (eviction is amortized O(1)). Space complexity: O(number of entries in the cache), for the hash map and per-frequency lists.

Dry Run Walkthrough

Let capacity = 6 and run these operations in order:

Operation Result total Cache state (frequency)
put(a, 1, 3) — 3 a@1
put(b, 2, 3) — 6 a@1, b@1
get(a) returns 1 6 b@1, a@2
put(c, 3, 3) not enough room, evict b 6 a@2, c@1
get(b) returns -1 6 a@2, c@1

The key moment: after get(a), a rises to frequency 2; inserting c needs 3 units but the cache is full, min_freq = 1, and the only node at frequency 1 is b, so b is evicted (not the higher-frequency a). That is exactly the "lowest frequency first, then least recently used on ties" rule.

Boundaries to raise proactively:

Prep Strategy

IMC's OA doesn't play tricks. It tests solid fundamentals plus clean engineering implementation. The two problems land on two high-frequency areas:

On top of that, edge handling and integer overflow are regulars on hidden tests, so always dry-run concrete data once you're done.

FAQ

Q1: How many problems is IMC's SWE OA, and how long?

Two coding problems, 120 minutes total, on HackerRank, with your choice of language. Difficulty is medium-to-hard, testing algorithm fundamentals, engineering thinking, and efficient implementation.

Q2: Two problems in 120 minutes, how should I pace myself?

Read both problems first and start with the clearer one. Aim to land a version of problem 1 that passes samples and main tests in 35-45 minutes; for problem 2, write a correct plain version first, then optimize space and complexity; reserve the last 10 minutes for edge cases.

Q3: Why does the grid-paths-with-passes problem need a 3D DP?

Because beyond position you also have to track "how many passes have been used" as an extra state. dp[i][j][t] encodes position and pass count together: entering a 0 cell spends one pass (transition from t-1), entering a 1 cell spends none (transition from t), and you sum over t = 0..k at the end. A rolling array can cut the space to O(m*k).

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

A plain LFU caps capacity by entry count; the weighted version caps it by the sum of each entry's size. Eviction may have to kick out several low-frequency entries in a row before there's room, so the eviction logic is written as "loop, evicting from the min_freq tail, until there's enough room."

Q5: Does updating an existing key in the LFU change its frequency?

No. An update only changes value and size and refreshes recency, leaving frequency unchanged. In the implementation, note that a larger size may require evicting other entries, so to avoid evicting the node itself you can pull it out of the map temporarily, free the room, then put it back at the head of its original frequency list.

Q6: What should the final 10-minute check focus on?

Empty input, extreme sizes, duplicates, integer overflow, and variable initialization. These are the most likely to fail on hidden tests, and walking through concrete data is the safest way to catch them.

Prepping for IMC's SWE OA? We know how HackerRank grades and where these medium-to-hard problems bite, and can help you polish your high-frequency DP and data structure design types.

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

Contact