Rubrik interview questions & answers

20 real Rubrik interview questions with full model answers — Coding. Drawn from the same verified bank ChannelPulse drills from (32 Rubrik questions in total).

CodingEasyRubrikSoftware Engineer

1. Distribute Candies Among Children I (LeetCode)

Model answer

The task

Count the ways to give all n candies to three children, where each child receives a whole number of candies between zero and limit, inclusive.

Key idea

Choose how many candies the first two children receive; the third child’s amount is then determined. Count the choice if that amount is also within the allowed range.

Approach

  1. Enumerate the first child’s amount from zero to min(n, limit).
  2. For each choice, enumerate the second child’s amount over the same range.
  3. Compute the remaining candies for the third child.
  4. Increment the count if the remainder is between zero and limit.
class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        ways = 0

        # Choose amounts for the first two children.
        for first in range(min(n, limit) + 1):
            for second in range(min(n, limit) + 1):
                third = n - first - second

                if 0 <= third <= limit:
                    ways += 1

        return ways

Complexity:

  • Time: O(min(n, limit)²), for enumerating pairs of amounts.
  • Space: O(1), using only a few variables.

Common follow-ups

  • How could you avoid enumeration? Use counting formulas or inclusion-exclusion to count bounded nonnegative solutions.
  • What if there are more than three children? Count assignments across k children, using dynamic programming or a generalized counting formula.
  • What if children have different limits? Enumerate choices while checking each child’s individual bound.
CodingEasyRubrikSoftware Engineer

2. Existence of a Substring in a String and Its Reverse (LeetCode)

Model answer

The task

Determine whether the string contains a two-character substring whose reversed form also appears as a substring. A substring is allowed to be its own reverse.

Key idea

Store every adjacent pair in a set. For each pair, check whether its reverse is in that set; set membership is constant time on average.

Approach

  1. Create a set of all length-two substrings.
  2. Scan the set of pairs.
  3. Return True if any pair’s reverse is also present.
  4. If none qualifies, return False.
class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        # Collect each adjacent pair of characters.
        pairs = {s[i:i + 2] for i in range(len(s) - 1)}

        # Check whether any pair appears in reversed order too.
        return any(pair[::-1] in pairs for pair in pairs)

Complexity:

  • Time: O(n), where n is the length of the string.
  • Space: O(n), for storing the distinct adjacent pairs.

Common follow-ups

  • What if the required substring length is k? Store length-k substrings and check each one’s reversal.
  • Can this use less memory? Scan pairs directly and check their reversals against the original string, though this can take O(n²) time.
  • What happens for a string shorter than two characters? The set is empty, so the result is False.
CodingMediumRubrikSoftware Engineer

3. Smallest String With Swaps (LeetCode)

Model answer

The task

Given a string and pairs of indices that may be swapped any number of times, return the lexicographically smallest string reachable through those swaps.

Key idea

Swaps connect indices into independent groups: within each connected component, every character can reach every index. Sort the characters and indices in each group, then place the smallest characters at the smallest indices.

Approach

  1. Initialize a disjoint-set union (DSU), with one set per string index.
  2. For each allowed pair, union its two indices.
  3. Group indices by their DSU root.
  4. For each group, sort its indices and the characters at those indices.
  5. Assign the sorted characters back to the sorted indices.
from collections import defaultdict
from typing import List

class Solution:
    def smallestStringWithSwaps(
        self, s: str, pairs: List[List[int]]
    ) -> str:
        n = len(s)
        parent = list(range(n))
        size = [1] * n

        def find(x: int) -> int:
            # Path compression keeps future lookups efficient.
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(a: int, b: int) -> None:
            root_a = find(a)
            root_b = find(b)
            if root_a == root_b:
                return

            # Union by size keeps the DSU trees shallow.
            if size[root_a] < size[root_b]:
                root_a, root_b = root_b, root_a
            parent[root_b] = root_a
            size[root_a] += size[root_b]

        for a, b in pairs:
            union(a, b)

        components = defaultdict(list)
        for i in range(n):
            components[find(i)].append(i)

        result = list(s)
        for indices in components.values():
            indices.sort()
            chars = sorted(s[i] for i in indices)

            for i, char in zip(indices, chars):
                result[i] = char

        return "".join(result)

Complexity:

  • Time: O(n log n + p α(n)), where n is the string length, p is the number of pairs, and α is the inverse Ackermann function.
  • Space: O(n) for the DSU, component groups, and result.

Common follow-ups

  • What if only one swap is allowed? Apply that swap directly; connected components no longer describe all reachable arrangements.
  • Can sorting be avoided for a small character set? Count each character per component and assign characters in order.
  • What if swaps arrive incrementally? Maintain the DSU as pairs arrive; recompute affected component characters when a result is requested.
CodingMediumRubrikSoftware Engineer

4. Snapshot Array (LeetCode)

Model answer

The task

Implement an array that supports updates, saving snapshots, and reading an index’s value as it was at a particular snapshot.

Key idea

For each index, store only the values that were explicitly set, tagged with the current snapshot ID. These IDs are ordered, so a binary search finds the most recent update no later than the requested snapshot.

Approach

  1. Keep a history list for each index and a counter for the next snapshot ID.
  2. On set, overwrite that index’s last history entry if it belongs to the current snapshot; otherwise, append a new entry.
  3. On snap, return the current ID and advance the counter.
  4. On get, binary-search the index’s history for the last entry whose ID is at most the requested ID.
  5. Return 0 if that index has no earlier recorded update.
class SnapshotArray:
    def __init__(self, length: int):
        self.histories = [[] for _ in range(length)]
        self.current_snap_id = 0

    def set(self, index: int, val: int) -> None:
        history = self.histories[index]

        # Only the final value set in a snapshot needs to be recorded.
        if history and history[-1][0] == self.current_snap_id:
            history[-1] = (self.current_snap_id, val)
        else:
            history.append((self.current_snap_id, val))

    def snap(self) -> int:
        snap_id = self.current_snap_id
        self.current_snap_id += 1
        return snap_id

    def get(self, index: int, snap_id: int) -> int:
        history = self.histories[index]

        # Find the first history entry with an ID greater than snap_id.
        low, high = 0, len(history)
        while low < high:
            mid = (low + high) // 2
            if history[mid][0] <= snap_id:
                low = mid + 1
            else:
                high = mid

        # The preceding entry is the latest update visible in this snapshot.
        return history[low - 1][1] if low > 0 else 0

Complexity:

  • Time: set and snap are O(1); get is O(log H), where H is the history length for that index.
  • Space: O(W), where W is the number of recorded writes across all indices.

Common follow-ups

  • How can memory be reduced when values often repeat? Skip recording a set when it matches the most recent value.
  • How would you support undoing snapshots? Use a persistent structure or retain version roots so earlier states remain addressable.
  • What if reads are much more frequent than writes? The per-index histories already make reads efficient, with logarithmic lookup.
CodingMediumRubrikSoftware Engineer

5. Design Circular Queue (LeetCode)

Model answer

The task

Implement a fixed-capacity queue that wraps around its storage instead of shifting elements. It must support insertion, removal, checking whether it is empty or full, and reading the front and rear values.

Key idea

Store elements in a fixed-size array and track the front index and number of stored elements. Compute positions modulo the capacity so the queue reuses slots at the beginning of the array after reaching its end.

Approach

  1. Initialize an array of capacity k, a front index of 0, and a size of 0.
  2. On insertion, fail if full; otherwise write at (front + size) % capacity and increase the size.
  3. On removal, fail if empty; otherwise advance the front index modulo capacity and decrease the size.
  4. Read the front at the front index and the rear at (front + size - 1) % capacity.
  5. Return -1 for front or rear queries when the queue is empty.
class MyCircularQueue:
    def __init__(self, k: int):
        self.capacity = k
        self.values = [0] * k
        self.front_index = 0
        self.size = 0

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False

        rear_index = (self.front_index + self.size) % self.capacity
        self.values[rear_index] = value
        self.size += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False

        self.front_index = (self.front_index + 1) % self.capacity
        self.size -= 1
        return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.values[self.front_index]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        rear_index = (self.front_index + self.size - 1) % self.capacity
        return self.values[rear_index]

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == self.capacity

Complexity:

  • Time: O(1) per operation; each operation updates or reads a constant number of values.
  • Space: O(k); the fixed-size array stores up to k elements.

Common follow-ups

  • How can the queue distinguish full from empty without a size field? Reserve one array slot, or track a separate full flag.
  • What changes for a dynamically growing queue? Allocate a larger array when full and copy elements in queue order.
  • How would you make it thread-safe? Protect operations with a lock, or use a suitable concurrent queue implementation.
CodingMediumRubrikSoftware Engineer

6. Count Zero Request Servers (LeetCode)

Model answer

The task

Given request records for numbered servers and several query times, count how many servers had no requests during the x time units ending at each query time.

Key idea

Sort the requests and queries by time, then sweep through queries in increasing order. Maintain the number of requests in the current inclusive time window for each server, along with how many servers currently have at least one request.

Approach

  1. Sort the request records by timestamp and sort queries while retaining their original indices.
  2. As each query time advances, add requests with timestamps at most the query time.
  3. Remove requests with timestamps strictly less than query_time - x, keeping the window inclusive at its left edge.
  4. The answer is the total number of servers minus the number with requests in the window.
  5. Restore answers to the original query order.
class Solution:
    def countServers(self, n: int, logs: list[list[int]],
                     x: int, queries: list[int]) -> list[int]:
        logs.sort(key=lambda log: log[1])
        ordered_queries = sorted(
            (time, index) for index, time in enumerate(queries)
        )

        request_counts = [0] * (n + 1)
        servers_with_requests = 0
        answers = [0] * len(queries)
        left = right = 0

        for query_time, query_index in ordered_queries:
            # Include all requests up to and including this query time.
            while right < len(logs) and logs[right][1] <= query_time:
                server_id = logs[right][0]
                if request_counts[server_id] == 0:
                    servers_with_requests += 1
                request_counts[server_id] += 1
                right += 1

            # Keep requests at query_time - x; the window is inclusive.
            window_start = query_time - x
            while left < right and logs[left][1] < window_start:
                server_id = logs[left][0]
                request_counts[server_id] -= 1
                if request_counts[server_id] == 0:
                    servers_with_requests -= 1
                left += 1

            answers[query_index] = n - servers_with_requests

        return answers

Complexity:

  • Time: O((m + q) log(m + q)), for sorting m requests and q queries; the sweep is linear.
  • Space: O(n + q), for per-server counts, sorted queries, and answers.

Common follow-ups

  • What if server IDs are sparse? Use a hash map for request counts instead of an array.
  • What if queries arrive online? Maintain a time-ordered data structure; arbitrary query order prevents this simple offline sweep.
  • What if the interval excludes its left endpoint? Remove requests with timestamps less than or equal to query_time - x.
CodingMediumRubrikSoftware Engineer

7. 3Sum (LeetCode)

Model answer

The task

Given an integer array, return every distinct triplet of values whose sum is zero. Triplets are considered the same if they contain the same values, regardless of order.

Key idea

Sort the array, then fix each value in turn and use two pointers to find pairs that complete its sum to zero. Skipping repeated values prevents duplicate triplets.

Approach

  1. Sort the input array.
  2. For each index, treat its value as the first element of a triplet.
  3. Skip the index if its value is the same as the previous value.
  4. Set two pointers immediately after the fixed index and at the end of the array.
  5. Move a pointer according to whether the current sum is too small or too large.
  6. When a triplet is found, record it and advance past duplicate pointer values.
from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        triplets = []
        n = len(nums)

        for i in range(n - 2):
            # Only use the first occurrence of each fixed value.
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left, right = i + 1, n - 1

            while left < right:
                total = nums[i] + nums[left] + nums[right]

                if total < 0:
                    left += 1
                elif total > 0:
                    right -= 1
                else:
                    triplets.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1

                    # Avoid repeating the same pair for this fixed value.
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1

        return triplets

Complexity:

  • Time: O(n²), from fixing each value and scanning with two pointers.
  • Space: O(n) for Python's in-place sort; excludes the returned triplets.

Common follow-ups

  • How would you return unique index triplets instead of value triplets? Track original indices while sorting, then return the corresponding index triples.
  • What if the target sum is a variable? Replace the zero-sum check with a comparison against the target.
  • Can the approach be extended to four values? Fix two values and use two pointers for the remaining pair, giving O(n³) time.
CodingMediumRubrikSoftware Engineer

8. Web Crawler Multithreaded (LeetCode)

Model answer

The task

Starting from a URL, discover every URL reachable through the parser while staying on the same host. Fetch URLs concurrently and return the discovered URLs without duplicates.

Key idea

Process discovered URLs in BFS layers, submitting each layer’s fetches to a thread pool. Keep the visited set in the main thread, so worker threads only fetch links and no lock is needed for set updates.

Approach

  1. Record the starting URL’s authority (host and optional port).
  2. Initialize visited and the BFS frontier with the starting URL.
  3. Submit every URL in the frontier to the thread pool.
  4. Collect results, adding unseen URLs with the same authority to the next frontier.
  5. Repeat until there are no more URLs to fetch.
from concurrent.futures import ThreadPoolExecutor
from typing import List
from urllib.parse import urlsplit

class Solution:
    def crawl(self, startUrl: str, htmlParser: "HtmlParser") -> List[str]:
        start_authority = urlsplit(startUrl).netloc
        visited = {startUrl}
        frontier = [startUrl]

        # The main thread owns visited and frontier; workers only fetch URLs.
        with ThreadPoolExecutor() as executor:
            while frontier:
                next_frontier = []

                # Fetch all URLs at this BFS level concurrently.
                for links in executor.map(htmlParser.getUrls, frontier):
                    for url in links:
                        if urlsplit(url).netloc != start_authority:
                            continue
                        if url in visited:
                            continue

                        visited.add(url)
                        next_frontier.append(url)

                frontier = next_frontier

        return list(visited)

Complexity:

  • Time: O(V + E) parser results and URLs processed, ignoring network latency.
  • Space: O(V + E) in the worst case for discovered URLs and links returned for a BFS level.

Common follow-ups

  • How would you limit resource use? Configure a bounded max_workers for the thread pool.
  • What if fetching fails or times out? Add timeouts and define a retry or skip policy.
  • Why use BFS? It naturally processes each URL once by discovery layer; DFS could also work with concurrent scheduling.
  • What if multiple threads update visited? Protect updates with a lock, or keep deduplication in a single coordinating thread.
CodingMediumRubrikSoftware Engineer

9. Next Permutation (LeetCode)

Model answer

The task

Rearrange the array in place to produce the next lexicographically greater ordering of its values. If no greater ordering exists, wrap around to the smallest ordering.

Key idea

The suffix after the rightmost position where the sequence increases is in descending order, so it is already the largest arrangement of those values. Swap that position with the smallest value in the suffix that is still larger, then reverse the suffix to make it as small as possible.

Approach

  1. Scan from right to left to find the rightmost index whose value is smaller than the value after it.
  2. If such an index exists, scan from the end to find the rightmost value larger than the pivot, then swap them.
  3. Reverse the portion after the pivot. This also handles the case where no pivot exists: the whole array becomes ascending.
  4. Mutate the input list directly.
from typing import List

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)

        # Find the rightmost position that can be increased.
        pivot = n - 2
        while pivot >= 0 and nums[pivot] >= nums[pivot + 1]:
            pivot -= 1

        if pivot >= 0:
            # The suffix is descending; its rightmost value greater
            # than the pivot is the smallest value that can replace it.
            successor = n - 1
            while nums[successor] <= nums[pivot]:
                successor -= 1

            nums[pivot], nums[successor] = nums[successor], nums[pivot]

        # Reverse the suffix to make it the smallest possible ordering.
        left, right = pivot + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

Complexity:

  • Time: O(n), with a constant number of linear scans.
  • Space: O(1), since the rearrangement is done in place.

Common follow-ups

  • Why choose the rightmost pivot? It preserves the longest possible prefix, making the next ordering as close as possible.
  • How are duplicate values handled? The strict comparisons skip equal values and still select the correct next ordering.
  • What if the input is already in descending order? No pivot exists, so reversing the full array produces the smallest ordering.
  • How would you return a new list instead? Copy the input first, then apply the same in-place algorithm to the copy.
CodingMediumRubrikSoftware Engineer

10. Design Memory Allocator (LeetCode)

Model answer

The task

Design a fixed-size memory allocator that assigns contiguous free cells to an allocation ID and releases every cell belonging to a given ID. An allocation should use the first available contiguous region large enough, or report failure.

Key idea

Store each cell’s allocation ID in an array, using 0 to represent a free cell. Scan from left to right to find the first sufficiently long free run; freeing an ID is a single pass over the array.

Approach

  1. Initialize an array of n zeroes.
  2. For an allocation, scan for a run of size consecutive zeroes.
  3. When found, fill that run with mID and return its starting index.
  4. If no such run exists, return -1.
  5. To free an ID, replace every matching cell with zero and return how many cells were released.
class Allocator:
    def __init__(self, n: int):
        # Zero denotes an unallocated cell.
        self.memory = [0] * n

    def allocate(self, size: int, mID: int) -> int:
        run_start = -1
        run_length = 0

        for index, owner in enumerate(self.memory):
            if owner == 0:
                if run_length == 0:
                    run_start = index
                run_length += 1

                if run_length == size:
                    for cell in range(run_start, run_start + size):
                        self.memory[cell] = mID
                    return run_start
            else:
                run_length = 0

        return -1

    def free(self, mID: int) -> int:
        released = 0

        for index, owner in enumerate(self.memory):
            if owner == mID:
                self.memory[index] = 0
                released += 1

        return released

Complexity:

  • Time: O(n) per operation; allocation scans the array and may mark the selected cells, while freeing scans the entire array.
  • Space: O(n) for the memory array.

Common follow-ups

  • How could allocation be faster for frequent requests? Track free intervals in an ordered structure, merging adjacent intervals when memory is freed.
  • What if a request can span noncontiguous cells? Scan for any size free cells rather than requiring a consecutive run.
  • How would you handle very large memory spaces? Use interval-based storage so work depends more on the number of allocated regions than on total capacity.
CodingMediumRubrikSoftware Engineer

11. LRU Cache (LeetCode)

Model answer

The task

Design a cache with a fixed capacity that supports retrieving and inserting key-value pairs. When an insertion exceeds capacity, evict the item that has gone unused for the longest time.

Key idea

Use a hash map for direct key lookup and a doubly linked list to track recency. Keep the most recently used item at the front; the least recently used item is at the back.

Approach

  1. Create a map from keys to their linked-list nodes.
  2. Use dummy head and tail nodes so items can be added or removed without special cases at the ends.
  3. On a successful get, move the node to the front and return its value; return -1 if the key is absent.
  4. On put, update and promote an existing node, or add a new node at the front.
  5. If the cache is over capacity, remove the node just before the tail and delete its key from the map.
class _Node:
    def __init__(self, key: int = 0, value: int = 0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.nodes = {}

        # Items are stored between these sentinels.
        self.head = _Node()
        self.tail = _Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: _Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node: _Node) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _make_most_recent(self, node: _Node) -> None:
        self._remove(node)
        self._add_to_front(node)

    def get(self, key: int) -> int:
        node = self.nodes.get(key)
        if node is None:
            return -1

        self._make_most_recent(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        node = self.nodes.get(key)

        if node is not None:
            node.value = value
            self._make_most_recent(node)
            return

        node = _Node(key, value)
        self.nodes[key] = node
        self._add_to_front(node)

        if len(self.nodes) > self.capacity:
            least_recent = self.tail.prev
            self._remove(least_recent)
            del self.nodes[least_recent.key]

Complexity:

  • Time: O(1) for get and put; map and list operations take constant time.
  • Space: O(capacity); the map and list store at most the cache’s capacity of entries.

Common follow-ups

  • How would you make the cache thread-safe? Protect operations with a lock.
  • What if entries expire after a time-to-live? Track expiration times and remove expired entries during access or with a cleanup mechanism.
  • How would you support eviction by frequency instead of recency? Track access counts and organize entries by frequency.
CodingMediumRubrikSoftware Engineer

12. Maximum Points After Enemy Battles (LeetCode)

Model answer

The task

Given enemy energy values and your starting energy, maximize points by using each enemy at most once. You can spend energy to defeat an enemy and earn a point, or spend a point to gain energy from an enemy.

Key idea

Sort enemies by energy. Use the cheapest enemy to earn points and, when you cannot afford it, use the most expensive remaining enemy to replenish energy. Track the best score because spending a point may temporarily reduce it.

Approach

  1. Sort the energy values and set pointers to the smallest and largest.
  2. If you can afford the cheapest remaining enemy, defeat it and update the best score.
  3. Otherwise, if you have a point and at least two enemies remain, trade a point for energy from the most expensive enemy.
  4. Stop when neither action can help, and return the best score reached.
from typing import List

class Solution:
    def maximumPoints(
        self, enemyEnergies: List[int], currentEnergy: int
    ) -> int:
        enemyEnergies.sort()
        left, right = 0, len(enemyEnergies) - 1
        points = best = 0

        while left <= right:
            if currentEnergy >= enemyEnergies[left]:
                # Spend energy on the cheapest enemy to gain a point.
                currentEnergy -= enemyEnergies[left]
                left += 1
                points += 1
                best = max(best, points)
            elif points > 0 and left < right:
                # Trade a point for energy from the most expensive enemy.
                currentEnergy += enemyEnergies[right]
                right -= 1
                points -= 1
            else:
                break

        return best

Complexity:

  • Time: O(n log n), due to sorting the enemy energies.
  • Space: O(n) if sorting requires extra storage; otherwise O(1) auxiliary space.

Common follow-ups

  • What if enemy energies arrive as a stream? Sorting is unavailable, so use an ordered structure if values must be processed dynamically.
  • Why use the largest enemy for an energy trade? It gives the most energy for the point spent.
  • Why track the best score separately? A trade can lower the current score, while the answer is the highest score reached.
CodingMediumRubrikSoftware Engineer

13. Find X Value of Array I (LeetCode)

Model answer

The task

Count the contiguous subarrays whose product, taken modulo k, equals x.

Key idea

Track how many subarrays ending at the current position have each possible product remainder. Extending each such subarray by the current number updates its remainder; the current number also starts a new one-element subarray.

Approach

  1. Create a count for each remainder from 0 to k - 1.
  2. For each number, build a fresh remainder-count array for subarrays ending at that position.
  3. Add the number itself as a new subarray.
  4. Extend every previously counted subarray by multiplying its remainder by the current number modulo k.
  5. Add the count for remainder x to the answer.
from typing import List

class Solution:
    def countSubarrays(self, nums: List[int], k: int, x: int) -> int:
        # Normalize x in case it is outside the usual remainder range.
        target = x % k

        # counts[r] is the number of subarrays ending at the
        # previous position whose product has remainder r.
        counts = [0] * k
        answer = 0

        for num in nums:
            value = num % k
            current = [0] * k

            # Start a new subarray at this position.
            current[value] += 1

            # Extend every subarray that ended at the previous position.
            for remainder, frequency in enumerate(counts):
                if frequency:
                    new_remainder = (remainder * value) % k
                    current[new_remainder] += frequency

            answer += current[target]
            counts = current

        return answer

Complexity:

  • Time: O(nk), processing k remainders for each of n values.
  • Space: O(k), storing remainder counts for adjacent positions.

Common follow-ups

  • Can this use less space? The rolling arrays already use O(k) space; the counts depend only on the previous position.
  • What if the target remainder is invalid? Normalize it with x % k, as the solution does.
  • What if k is large? This approach may be too slow; look for constraints or additional structure that limits reachable remainders.
CodingMediumRubrikSoftware Engineer

14. Task Scheduler (LeetCode)

Model answer

The task

Find the fewest time slots needed to run all tasks when identical task types must be separated by at least n slots. A slot may be left idle.

Key idea

The most frequent task types determine the minimum schedule length. Put copies of a most frequent type into frames of length n + 1; other tasks can fill the gaps. If there are enough other tasks to fill every gap, no idle slots are needed.

Approach

  1. Count how many times each task type appears.
  2. Find the largest frequency, max_freq.
  3. Count how many types occur exactly max_freq times.
  4. Compute the frame-based length: (max_freq - 1) * (n + 1) + max_count.
  5. Return the larger of that length and the total number of tasks.
from collections import Counter
from typing import List

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        frequencies = Counter(tasks)
        max_freq = max(frequencies.values())
        max_count = sum(
            frequency == max_freq
            for frequency in frequencies.values()
        )

        # The most frequent tasks establish the frame-based schedule.
        frame_length = (max_freq - 1) * (n + 1) + max_count

        # Other tasks may fill idle slots, but cannot reduce below task count.
        return max(len(tasks), frame_length)

Complexity:

  • Time: O(m + k), to count m tasks and scan k task types.
  • Space: O(k), for the task-frequency counts.

Common follow-ups

  • What if n is zero? The formula returns the task count, since no cooldown is required.
  • What if several task types share the highest frequency? Include all of them in the last frame, as max_count does.
  • How could you construct an actual schedule? Greedily run the most frequent available task, tracking cooldowns with a max-heap and a queue.
  • What if tasks have different cooldowns? The simple formula no longer applies; model each task’s next available time and schedule with a priority queue.
CodingMediumRubrikSoftware Engineer

15. Candy Crush (LeetCode)

Model answer

The task

Given a grid of candies, repeatedly remove every horizontal or vertical run of at least three matching candies, then let the remaining candies fall downward. Return the grid once no more runs can be removed.

Key idea

Mark all candies to be removed before applying gravity, so intersecting runs are handled simultaneously. Use negative values as temporary marks; compare their absolute values while detecting runs.

Approach

  1. Scan each row and column to find contiguous runs of matching nonzero candies.
  2. Mark every cell in a run of length at least three, and record that a crush occurred.
  3. Compact each column downward, discarding marked cells and filling the top with zeros.
  4. Repeat the scan and gravity steps until a full scan finds no runs.
from typing import List

class Solution:
    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
        rows, cols = len(board), len(board[0])

        while True:
            crushed = False

            # Mark horizontal runs. abs() lets marked candies still match.
            for r in range(rows):
                c = 0
                while c < cols:
                    value = abs(board[r][c])
                    if value == 0:
                        c += 1
                        continue

                    end = c + 1
                    while end < cols and abs(board[r][end]) == value:
                        end += 1

                    if end - c >= 3:
                        crushed = True
                        for k in range(c, end):
                            board[r][k] = -value

                    c = end

            # Mark vertical runs.
            for c in range(cols):
                r = 0
                while r < rows:
                    value = abs(board[r][c])
                    if value == 0:
                        r += 1
                        continue

                    end = r + 1
                    while end < rows and abs(board[end][c]) == value:
                        end += 1

                    if end - r >= 3:
                        crushed = True
                        for k in range(r, end):
                            board[k][c] = -value

                    r = end

            if not crushed:
                return board

            # Apply gravity, ignoring marked (negative) candies.
            for c in range(cols):
                write = rows - 1
                for r in range(rows - 1, -1, -1):
                    if board[r][c] > 0:
                        board[write][c] = board[r][c]
                        write -= 1

                for r in range(write, -1, -1):
                    board[r][c] = 0

Complexity:

  • Time: O((mn)²), where each round scans the grid and at least one candy is removed.
  • Space: O(1) extra space, using the board itself for marks.

Common follow-ups

  • What if candies can have negative values initially? Use a separate marking grid instead of sign-based marks.
  • How would you return the number of rounds? Increment a counter after each crush-and-gravity cycle.
  • Can the algorithm stop early during marking? No; all rows and columns must be checked before gravity to preserve simultaneous removal.
CodingMediumRubrikSoftware Engineer

16. Web Crawler (LeetCode)

Model answer

The task

Starting from a URL, crawl pages by following links returned by the provided parser. Return each reachable URL whose hostname matches the starting URL, without crawling any URL more than once.

Key idea

Use breadth-first search and a set to track visited URLs. Check a link’s hostname before adding it to the queue, so pages on other hosts are never crawled.

Approach

  1. Record the starting URL’s hostname.
  2. Initialize a queue with the start URL and mark it visited.
  3. Remove URLs from the queue and ask the parser for their outgoing links.
  4. Add each unseen link with the matching hostname to the visited set and queue.
  5. Return the visited URLs.
from collections import deque
from urllib.parse import urlparse

class Solution:
    def crawl(self, startUrl, htmlParser):
        start_host = urlparse(startUrl).hostname

        visited = {startUrl}
        queue = deque([startUrl])

        while queue:
            url = queue.popleft()

            for link in htmlParser.getUrls(url):
                if link in visited:
                    continue

                if urlparse(link).hostname == start_host:
                    visited.add(link)
                    queue.append(link)

        return list(visited)

Complexity:

  • Time: O(V + E), where V is the number of crawled pages and E is the number of links returned from those pages.
  • Space: O(V) for the queue and visited set.

Common follow-ups

  • How would you use depth-first search instead? Replace the queue with a stack, keeping the same visited and hostname checks.
  • How would you handle concurrent fetching? Use a thread-safe work queue and coordinate workers so each URL is scheduled only once.
  • What if hostname comparisons should ignore case or ports? Parse URLs into normalized host components and compare those consistently.
CodingMediumRubrikSoftware Engineer

17. Count Lattice Points Inside a Circle (LeetCode)

Model answer

The task

Given circles with integer centers and radii, count the distinct integer-coordinate points that lie inside or on at least one circle.

Key idea

For each circle, enumerate the integer points in its bounding square and check whether each point is within the circle using squared distances. Store qualifying points in a set so points covered by multiple circles are counted only once.

Approach

  1. Initialize a set of covered lattice points.
  2. For each circle, compute the integer-coordinate bounds of its bounding square.
  3. Check each point in that square against the circle equation.
  4. Add points on or inside the circle to the set.
  5. Return the set’s size.
class Solution:
    def countLatticePoints(self, circles: list[list[int]]) -> int:
        covered = set()

        for cx, cy, radius in circles:
            radius_squared = radius * radius

            # Only points in this square can lie inside the circle.
            for x in range(cx - radius, cx + radius + 1):
                for y in range(cy - radius, cy + radius + 1):
                    dx = x - cx
                    dy = y - cy

                    if dx * dx + dy * dy <= radius_squared:
                        covered.add((x, y))

        return len(covered)

Complexity:

  • Time: O(∑ r²), over all circles, for checking points in their bounding squares.
  • Space: O(P), where P is the number of distinct lattice points covered.

Common follow-ups

  • How can duplicate counting be avoided without a set? Use a shared grid or boolean array if the coordinate range is small and bounded.
  • What if coordinates are very large? Enumerate points only when radii are small; for large radii, consider geometric or spatial-indexing techniques.
  • Does the boundary count? Yes; the <= check includes points exactly on the circumference.
CodingMediumRubrikSoftware Engineer

18. Paint Fence (LeetCode)

Model answer

The task

Count the ways to paint n fence posts using k colors, with no three consecutive posts painted the same color.

Key idea

Track two counts for each prefix: ways where the last two posts have the same color, and ways where they have different colors. To extend a valid arrangement, a same-color ending must come from a different-color ending; a different-color ending can use any color other than the previous post’s.

Approach

  1. Treat zero posts as one empty arrangement; handle zero colors separately.
  2. Initialize the one-post counts: no same-color pair, and k different-color arrangements.
  3. For each additional post, compute the new same and different counts from the previous counts.
  4. Return the sum of both counts.
class Solution:
    def numWays(self, n: int, k: int) -> int:
        if n == 0:
            return 1
        if k == 0:
            return 0

        # For one post, every choice has no matching adjacent pair.
        same = 0
        different = k

        for _ in range(2, n + 1):
            # Match the previous post only if the prior pair differed.
            new_same = different

            # Choose a color unlike the previous post.
            new_different = (same + different) * (k - 1)

            same, different = new_same, new_different

        return same + different

Complexity:

  • Time: O(n), with constant work per post.
  • Space: O(1), using only a few counters.

Common follow-ups

  • What if no more than m consecutive posts may share a color? Track counts by current run length, or use a DP window of run lengths.
  • What if n is extremely large? Derive a linear recurrence and use matrix exponentiation.
  • What if colors have different compatibility rules? Track the last color, updating transitions according to which colors may follow.
CodingMediumRubrikSoftware Engineer

19. Random Pick with Weight (LeetCode)

Model answer

The task

Implement a picker that returns an index at random, with each index’s chance of being selected proportional to its weight.

Key idea

Build prefix sums of the weights. Draw a uniformly random integer from the total weight’s range, then binary-search for the first prefix sum greater than the draw.

Approach

  1. Store cumulative weight sums during initialization.
  2. Keep the total weight, which is the last cumulative sum.
  3. For each pick, draw an integer in [0, total).
  4. Use binary search to find the first cumulative sum greater than that integer.
  5. Return the corresponding index.
import random
from bisect import bisect_right
from typing import List

class Solution:
    def __init__(self, w: List[int]):
        # Each index owns a range of integer outcomes proportional to its weight.
        self.prefix = []
        total = 0

        for weight in w:
            total += weight
            self.prefix.append(total)

        self.total = total

    def pickIndex(self) -> int:
        # The target is uniformly chosen from [0, total).
        target = random.randrange(self.total)

        # Find the first prefix sum strictly greater than target.
        return bisect_right(self.prefix, target)

Complexity:

  • Time: O(n) to initialize; O(log n) per pick due to binary search.
  • Space: O(n) for the cumulative sums.

Common follow-ups

  • What if weights change between picks? Use a Fenwick tree to support weight updates and weighted selection in O(log n).
  • How would you handle very frequent picks? The current approach already provides O(log n) picks; an alias table can provide O(1) picks after O(n) preprocessing if weights are static.
  • What if some weights are zero? The prefix search naturally skips indices with zero weight, so they are never selected.
CodingMediumRubrikSoftware Engineer

20. Task Scheduler II (LeetCode)

Model answer

The task

Given tasks that must be performed in order, find the earliest day the final task can be completed when identical task types need a cooldown between executions.

Key idea

Track the most recent execution day for each task type. If a task is still in its cooldown, jump the current day to its next allowed day; otherwise, perform it immediately.

Approach

  1. Initialize the current day and a map from task type to its last execution day.
  2. For each task, check whether its previous execution requires a cooldown.
  3. Advance the current day if needed, then record that day as the task’s execution day.
  4. Return the day on which the final task was performed.
from typing import List

class Solution:
    def taskSchedulerII(self, tasks: List[int], space: int) -> int:
        day = 0
        last_day = {}

        for task in tasks:
            if task in last_day:
                # The next execution must be at least space + 1 days later.
                day = max(day, last_day[task] + space + 1)

            last_day[task] = day
            day += 1

        # The loop advances once after the final task.
        return day - 1

Complexity:

  • Time: O(n), where n is the number of tasks.
  • Space: O(k), where k is the number of distinct task types stored.

Common follow-ups

  • How would you handle tasks that can be reordered? The scheduling problem changes; consider prioritizing tasks by remaining frequency.
  • What if cooldowns differ by task type? Store each task’s cooldown and use it when calculating its next allowed day.
  • Can the simulation be avoided? This method already skips idle days by jumping directly to the next legal day.

Practice these out loud, don't memorise them

Reading an answer is not the same as being able to give one under pressure. ChannelPulse plays the interviewer, asks the follow-ups, and scores each answer with feedback and a model answer so you can hear the gap between what you said and what lands.

Get ChannelPulse Browse all questions