Zenefits interview questions & answers

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

CodingEasyZenefitsSoftware Engineer

1. Valid Palindrome (LeetCode)

Model answer

The task

Determine whether a string reads the same forward and backward after disregarding characters that are not letters or digits and treating uppercase and lowercase as equivalent.

Key idea

Compare characters from both ends, skipping anything that should be ignored. If every remaining pair matches, the string is a palindrome.

Approach

  1. Initialize pointers at the start and end of the string.
  2. Move the left pointer past non-alphanumeric characters.
  3. Move the right pointer past non-alphanumeric characters.
  4. Compare the lowercase forms of the characters at the pointers; return False if they differ.
  5. Move both pointers inward and continue. If they meet or cross, return True.
class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1

        while left < right:
            # Ignore characters that are not letters or digits.
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1

            # Compare without regard to letter case.
            if s[left].lower() != s[right].lower():
                return False

            left += 1
            right -= 1

        return True

Complexity:

  • Time: O(n), where n is the string length; each pointer moves only inward.
  • Space: O(1), since the comparisons use no additional data structure.

Common follow-ups

  • What if the input contains no letters or digits? It is considered a palindrome, since there are no mismatching characters.
  • Can you avoid creating a normalized copy of the string? Yes; the two-pointer scan uses constant extra space.
  • How would you handle Unicode normalization? Normalize the string first if canonically equivalent characters should compare as equal; that may require additional space.
CodingEasyZenefitsSoftware Engineer

2. Valid Parentheses (LeetCode)

Model answer

The task

Determine whether a string of opening and closing round, square, and curly brackets is correctly nested and matched. Return a boolean.

Key idea

A closing bracket must match the most recent unmatched opening bracket. A stack captures that order: push openings, and check each closing bracket against the stack’s top.

Approach

  1. Return False if the string has odd length.
  2. Map each closing bracket to its matching opening bracket.
  3. Scan the string from left to right.
  4. Push opening brackets onto the stack.
  5. For a closing bracket, return False if the stack is empty or its top does not match; otherwise pop.
  6. Return True only if the stack is empty after the scan.
class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {")": "(", "]": "[", "}": "{"}
        openings = set(pairs.values())
        stack = []

        for char in s:
            if char in openings:
                stack.append(char)
            else:
                # A closing bracket must match the latest unmatched opening.
                if not stack or stack[-1] != pairs.get(char):
                    return False
                stack.pop()

        # Unmatched opening brackets make the sequence invalid.
        return not stack

Complexity:

  • Time: O(n), where n is the string length; each character is processed once.
  • Space: O(n) in the worst case, when all characters are opening brackets.

Common follow-ups

  • How would you support additional bracket types? Add their matching pairs to the map.
  • Can you stop early? Yes; return False as soon as a closing bracket mismatches or has no opening bracket.
  • What if the input includes non-bracket characters? Define how to handle them, then either ignore them or reject them during the scan.
CodingEasyZenefitsSoftware Engineer

3. Excel Sheet Column Title (LeetCode)

Model answer

The task

Convert a positive column number into its Excel-style column label, where labels use uppercase letters and continue past Z with combinations such as AA.

Key idea

This is a base-26 representation with digits 1 through 26, rather than the usual 0 through 25. Subtract one before each division so the remainder maps directly to A through Z.

Approach

  1. Start with the given column number.
  2. Subtract one to shift its range to 0 through 25.
  3. Use division and remainder by 26 to find the next letter.
  4. Append that letter and continue with the quotient.
  5. Reverse the collected letters to form the label.
class Solution:
    def convertToTitle(self, columnNumber: int) -> str:
        letters = []

        while columnNumber > 0:
            # Shift to a zero-based range so the remainder maps to A-Z.
            columnNumber -= 1
            remainder = columnNumber % 26
            letters.append(chr(ord("A") + remainder))
            columnNumber //= 26

        return "".join(reversed(letters))

Complexity:

  • Time: O(log n), where n is the column number; each iteration processes one base-26 digit.
  • Space: O(log n) for the output letters.

Common follow-ups

  • How would you convert a column label back to a number? Accumulate digits in base 26, mapping A to 1 through Z to 26.
  • What changes if labels use a different alphabet size? Replace 26 with the alphabet size and map remainders to its characters.
  • What if the input is zero or negative? The stated conversion is for positive column numbers; define input validation behavior if those values must be handled.
CodingEasyZenefitsSoftware Engineer

4. Majority Element (LeetCode)

Model answer

The task

Given an integer array with a value appearing more than half the time, return that value.

Key idea

Use Boyer–Moore majority vote: pair off different values, which cannot eliminate the majority completely. Track a candidate and a balance; the majority remains the candidate after one pass.

Approach

  1. Start with no candidate and a zero balance.
  2. For each value, choose it as the candidate if the balance is zero.
  3. Add one if it matches the candidate; otherwise subtract one.
  4. Return the final candidate.
class Solution:
    def majorityElement(self, nums: list[int]) -> int:
        candidate = None
        balance = 0

        for value in nums:
            if balance == 0:
                candidate = value

            if value == candidate:
                balance += 1
            else:
                balance -= 1

        # A majority is guaranteed to exist, so the final candidate is the answer.
        return candidate

Complexity:

  • Time: O(n), for one pass through the array.
  • Space: O(1), using only a candidate and a counter.

Common follow-ups

  • What if a majority is not guaranteed? Run a second pass to count the candidate and check whether its frequency exceeds half the array length.
  • How would you find values occurring more than one-third of the time? Track up to two candidates with Boyer–Moore’s generalized voting method, then verify their counts.
  • Can sorting solve it? Yes. Sort the array; the majority must occupy the middle position, giving O(n log n) time and typically extra space depending on the sort.
CodingEasyZenefitsSoftware Engineer

5. Reverse Linked List (LeetCode)

Model answer

The task

Given the head of a singly linked list, reverse its links in place and return the new head.

Key idea

Recursively reverse the list starting at the second node. As the recursion unwinds, point each node’s successor back to it, then clear its old forward link.

Approach

  1. If the list has zero or one node, it is already reversed.
  2. Recursively reverse the list after the head and save its new head.
  3. Point the next node back to the current node.
  4. Set the current node’s next pointer to None to finish the reversed list.
  5. Return the saved new head.
class Solution:
    def reverseList(self, head):
        # An empty or single-node list is already reversed.
        if head is None or head.next is None:
            return head

        # Reverse the remainder of the list.
        new_head = self.reverseList(head.next)

        # Put the current node after its former successor.
        head.next.next = head
        head.next = None

        return new_head

Complexity:

  • Time: O(n), where n is the number of nodes.
  • Space: O(n), for the recursive call stack.

Common follow-ups

  • Can you do it iteratively with O(1) extra space? Use previous, current, and next_node pointers to reverse links while traversing.
  • What if the list is empty or has one node? The base case returns it unchanged.
  • Can you reverse only a portion of the list? Track the sublist boundaries and reconnect them after reversing that segment.
CodingMediumZenefitsSoftware Engineer

6. Number of Islands (LeetCode)

Model answer

The task

Given a grid of land and water, count the groups of connected land cells. Cells connect horizontally or vertically, not diagonally.

Key idea

Each group is one island. Scan the grid, and whenever an unvisited land cell is found, count a new island and explore its entire connected region. Mark cells as visited when adding them to the search queue so no cell is processed more than once.

Approach

  1. Return 0 if the grid is empty.
  2. Scan every cell in the grid.
  3. When a land cell is found, increment the island count and start a breadth-first search from it.
  4. During the search, mark each discovered land cell as water and add its in-bounds land neighbors to the queue.
  5. Return the island count after the scan is complete.
from collections import deque
from typing import List

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0

        rows, cols = len(grid), len(grid[0])
        islands = 0

        for row in range(rows):
            for col in range(cols):
                if grid[row][col] != "1":
                    continue

                islands += 1
                grid[row][col] = "0"
                queue = deque([(row, col)])

                while queue:
                    current_row, current_col = queue.popleft()

                    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        next_row = current_row + dr
                        next_col = current_col + dc

                        if (
                            0 <= next_row < rows
                            and 0 <= next_col < cols
                            and grid[next_row][next_col] == "1"
                        ):
                            # Mark when enqueuing to avoid duplicate work.
                            grid[next_row][next_col] = "0"
                            queue.append((next_row, next_col))

        return islands

Complexity: Time: O(rows * cols), since each cell is examined at most a constant number of times.

Complexity: Space: O(rows * cols) in the worst case for the BFS queue.

Common follow-ups

  • Preserve the input grid? Track visited cells in a separate set instead of changing land cells to water.
  • Use depth-first search instead? Recursively or iteratively explore the four neighbors; iterative DFS avoids recursion-depth concerns.
  • Count diagonally connected land as part of the same island? Include the four diagonal directions in the neighbor list.
CodingMediumZenefitsSoftware Engineer

7. Course Schedule (LeetCode)

Model answer

The task

Given a number of courses and prerequisite pairs, decide whether it’s possible to complete every course. A prerequisite pair means one course must be taken before another.

Key idea

Represent courses as a directed graph, with an edge from each prerequisite to the course that depends on it. A cycle means the courses in that cycle depend on one another, so not all courses can be completed.

Use Kahn’s topological-sort algorithm: repeatedly take courses with no remaining prerequisites and remove their outgoing edges.

Approach

  1. Create an adjacency list and count each course’s prerequisites (its indegree).
  2. Add every course with indegree zero to a queue.
  3. Remove courses from the queue, counting each as completed.
  4. Decrease the indegree of each dependent course; enqueue it when its indegree reaches zero.
  5. Return whether the number completed equals the total number of courses.
from collections import deque
from typing import List

class Solution:
    def canFinish(
        self, numCourses: int, prerequisites: List[List[int]]
    ) -> bool:
        # Edges point from prerequisite to the course that depends on it.
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses

        for course, prerequisite in prerequisites:
            graph[prerequisite].append(course)
            indegree[course] += 1

        # Begin with courses that have no prerequisites.
        ready = deque(
            course
            for course in range(numCourses)
            if indegree[course] == 0
        )

        completed = 0

        while ready:
            course = ready.popleft()
            completed += 1

            for dependent in graph[course]:
                indegree[dependent] -= 1
                if indegree[dependent] == 0:
                    ready.append(dependent)

        return completed == numCourses

Complexity:

  • Time: O(V + E), where V is the number of courses and E is the number of prerequisite pairs.
  • Space: O(V + E) for the graph, indegrees, and queue.

Common follow-ups

  • How can you return a valid course order? Record courses as they are removed from the queue; return the order if it includes every course.
  • How can DFS detect a cycle? Track nodes as unvisited, visiting, or finished; reaching a visiting node reveals a cycle.
  • What if there are no courses? The algorithm returns True, since zero courses can all be completed.
CodingMediumZenefitsSoftware Engineer

8. Course Schedule II (LeetCode)

Model answer

The task

Return an ordering of all courses that satisfies the prerequisite relationships. If no such ordering exists because the relationships contain a cycle, return an empty list.

Key idea

Model each course as a graph node, with an edge from a prerequisite to the course that depends on it. Kahn’s topological-sort algorithm repeatedly takes courses with no remaining prerequisites; if it cannot take every course, the graph contains a cycle.

Approach

  1. Build an adjacency list and count each course’s prerequisites as its indegree.
  2. Add all zero-indegree courses to a queue.
  3. Remove courses from the queue, adding each to the result and reducing the indegree of its dependent courses.
  4. Add a dependent course to the queue when its indegree reaches zero.
  5. Return the result if it includes every course; otherwise, return an empty list.
from collections import deque
from typing import List

class Solution:
    def findOrder(
        self, numCourses: int, prerequisites: List[List[int]]
    ) -> List[int]:
        # Edges point from prerequisite to dependent course.
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses

        for course, prerequisite in prerequisites:
            graph[prerequisite].append(course)
            indegree[course] += 1

        ready = deque(
            course
            for course in range(numCourses)
            if indegree[course] == 0
        )
        order = []

        while ready:
            course = ready.popleft()
            order.append(course)

            for dependent in graph[course]:
                indegree[dependent] -= 1
                if indegree[dependent] == 0:
                    ready.append(dependent)

        # A cycle prevents all courses from being added.
        return order if len(order) == numCourses else []

**Complexity:**

- Time: O(V + E), where V is the number of courses and E is the number of prerequisite relationships.
- Space: O(V + E) for the graph, indegrees, queue, and result.

**Common follow-ups**

- How can DFS solve this? Use three node states—unvisited, visiting, and visited—to detect cycles while building a topological order.
- How can the algorithm return the number of courses that can be completed? Return the length of the processed order.
- How can you choose the smallest-numbered available course at each step? Use a min-heap instead of a queue, giving O((V + E) log V) time.
CodingMediumZenefitsSoftware Engineer

9. Majority Element II (LeetCode)

Model answer

The task

Return every value that occurs more than one third of the time in an integer array. The result can contain at most two values.

Key idea

At most two distinct values can each appear more than n // 3 times. Boyer–Moore’s extended voting algorithm finds up to two candidates in one pass; a second pass verifies their actual frequencies.

Approach

  1. Track two candidate values and their vote counts.
  2. For each number, add a vote if it matches a candidate.
  3. Otherwise, assign it to an empty candidate slot, or decrement both counts.
  4. Count the candidates in a second pass.
  5. Return only candidates whose counts exceed len(nums) // 3.
from typing import List

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        candidate1 = candidate2 = 0
        count1 = count2 = 0

        # Find up to two possible majority candidates.
        for value in nums:
            if value == candidate1:
                count1 += 1
            elif value == candidate2:
                count2 += 1
            elif count1 == 0:
                candidate1 = value
                count1 = 1
            elif count2 == 0:
                candidate2 = value
                count2 = 1
            else:
                count1 -= 1
                count2 -= 1

        # Candidates are not guaranteed to meet the required frequency.
        count1 = count2 = 0
        for value in nums:
            if value == candidate1:
                count1 += 1
            elif value == candidate2:
                count2 += 1

        threshold = len(nums) // 3
        result = []

        if count1 > threshold:
            result.append(candidate1)
        if count2 > threshold:
            result.append(candidate2)

        return result

Complexity:

  • Time: O(n), for two passes over the array.
  • Space: O(1) extra space, excluding the returned list.

Common follow-ups

  • Why are there at most two answers? Three values each appearing more than n / 3 times would require more than n elements.
  • What if the threshold is n / k? Track up to k - 1 candidates, then verify their frequencies.
  • Can sorting solve it? Yes, in O(n log n) time; the voting approach achieves O(n) time with O(1) extra space.
CodingMediumZenefitsSoftware Engineer

10. 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.
CodingMediumZenefitsSoftware Engineer

11. Convert Sorted List to Binary Search Tree (LeetCode)

Model answer

The task

Convert a sorted singly linked list into a height-balanced binary search tree. The tree’s inorder traversal should preserve the list’s order.

Key idea

A list does not support efficient midpoint lookup, so repeatedly finding the middle node would be wasteful. Instead, build the tree in inorder while advancing one shared list pointer, using the known list length to decide each subtree’s size.

Approach

  1. Count the nodes in the list.
  2. Keep a pointer to the next list node to consume.
  3. Recursively build a subtree for a range of size nodes.
  4. Build its left subtree with size // 2 nodes.
  5. Use the current list node as the root, advance the pointer, then build the remaining right subtree.
# ListNode and TreeNode are provided by the platform.

class Solution:
    def sortedListToBST(self, head):
        length = 0
        node = head

        while node:
            length += 1
            node = node.next

        current = head

        def build(size):
            nonlocal current

            if size == 0:
                return None

            left_size = size // 2
            left = build(left_size)

            # Consume the next list node as the root.
            root = TreeNode(current.val)
            current = current.next

            root.left = left
            root.right = build(size - left_size - 1)
            return root

        return build(length)

Complexity:

  • Time: O(n), where n is the number of list nodes; each node is visited a constant number of times.
  • Space: O(log n) auxiliary space for recursion in a balanced tree; the output tree uses O(n) space.

Common follow-ups

  • How would you build a BST from a sorted array? Use midpoint indexing and recursively build both halves.
  • Why not repeatedly find the linked-list midpoint? That can take O(n log n) time because each recursive level rescans nodes.
  • Can the output be made more balanced for an even-sized range? Either middle choice works; this approach consistently chooses the upper middle.
  • What if the list is empty? The size-based helper returns None.
CodingMediumZenefitsSoftware Engineer

12. Generate Parentheses (LeetCode)

Model answer

The task

Given a nonnegative number of pairs, return every string of that many opening and closing parentheses that is correctly balanced.

Key idea

Build each string one character at a time. Add an opening parenthesis only while fewer than n have been used, and add a closing parenthesis only when it will not outnumber the openings already used.

Approach

  1. Track how many opening and closing parentheses have been added, plus the current string.
  2. If the string has length 2 * n, save it.
  3. Recurse with an opening parenthesis when fewer than n openings have been used.
  4. Recurse with a closing parenthesis when fewer closings have been used than openings.
  5. Start with an empty string and zero counts.
from typing import List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        results: List[str] = []
        current: list[str] = []

        def backtrack(open_count: int, close_count: int) -> None:
            if len(current) == 2 * n:
                results.append("".join(current))
                return

            if open_count < n:
                current.append("(")
                backtrack(open_count + 1, close_count)
                current.pop()

            if close_count < open_count:
                current.append(")")
                backtrack(open_count, close_count + 1)
                current.pop()

        backtrack(0, 0)
        return results

Complexity:

  • Time: O(Cₙ · n), where Cₙ is the number of valid strings; each is assembled in O(n) time.
  • Space: O(n) auxiliary space for the recursion and current string, excluding the returned results.

Common follow-ups

  • How can you count the results without generating them? Use the Catalan number formula, Cₙ = binomial(2n, n) / (n + 1).
  • What happens when n is zero? The algorithm returns a list containing the empty string.
  • How would you generate strings with multiple bracket types? Track each type’s balance and ensure closing brackets match the most recent unmatched opening bracket.
CodingMediumZenefitsSoftware Engineer

13. Graph Valid Tree (LeetCode)

Model answer

The task

Determine whether an undirected graph on n vertices is a tree. A valid tree must be connected and contain no cycles.

Key idea

A graph with n vertices is a tree exactly when it is connected and has n - 1 edges. Check the edge count first, then use DFS to verify every vertex is reachable.

Approach

  1. Reject an empty graph and any graph whose edge count is not n - 1.
  2. Build an adjacency list from the edges.
  3. Run DFS from vertex 0, marking visited vertices.
  4. Return true only if all vertices were visited.
from typing import List

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        # A tree must have exactly n - 1 edges.
        if n == 0 or len(edges) != n - 1:
            return False

        graph = [[] for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        visited = set()
        stack = [0]

        while stack:
            node = stack.pop()
            if node in visited:
                continue

            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

        # With n - 1 edges, connectivity also rules out cycles.
        return len(visited) == n

Complexity:

  • Time: O(n + m), where m is the number of edges; building and traversing the adjacency list takes linear time.
  • Space: O(n + m), for the adjacency list, visited set, and DFS stack.

Common follow-ups

  • Can you detect a cycle directly? Use DFS while tracking each node’s parent; a visited neighbor other than the parent indicates a cycle.
  • How would you solve this with Union-Find? Join each edge’s endpoints; a failed union signals a cycle, and the final component count must be one.
  • What if the graph is directed? Define the required tree properties first; directed trees need different connectivity and cycle checks.
CodingMediumZenefitsSoftware Engineer

14. Verify Preorder Sequence in Binary Search Tree (LeetCode)

Model answer

The task

Determine whether an array could be the preorder traversal of a binary search tree (BST). The standard version assumes all values are distinct.

Key idea

As preorder moves from a node’s left subtree into its right subtree, values must rise past that node, and they can never later fall below it. Track the smallest allowed value and use a stack to represent the ancestors whose left subtrees are being processed.

Approach

  1. Start with no lower bound and an empty stack.
  2. For each value, reject it if it is below the current lower bound.
  3. Pop ancestors while the value is greater than the stack top; each popped ancestor becomes the new lower bound.
  4. Push the value and continue. If no value violates the bound, the sequence is valid.
from typing import List

class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        stack = []
        lower_bound = float("-inf")

        for value in preorder:
            # We have already moved into a right subtree, so
            # subsequent values cannot be smaller than its root.
            if value < lower_bound:
                return False

            # Move from left subtrees into right subtrees.
            while stack and value > stack[-1]:
                lower_bound = stack.pop()

            stack.append(value)

        return True

Complexity:

  • Time: O(n), since each value is pushed and popped at most once.
  • Space: O(n) in the worst case for the stack.

Common follow-ups

  • How should duplicates be handled? Define whether equal values go left or right, then adjust comparisons consistently.
  • Can this be solved recursively? Yes; recursively consume values while enforcing valid lower and upper bounds.
  • What if the input is extremely large? The stack solution is iterative and processes the sequence in one pass.
CodingMediumZenefitsSoftware Engineer

15. Flatten 2D Vector (LeetCode)

Model answer

The task

Create an iterator over a list of lists that returns the values in row order, skipping empty rows. It should support checking whether another value is available.

Key idea

Keep a row and column index. Before reading, advance past rows that are exhausted; each row is skipped at most once over the iterator’s lifetime.

Approach

  1. Store the nested list and initialize both indices to zero.
  2. In hasNext, move to the next row while the current row has no remaining values.
  3. Return whether the row index is still within the list.
  4. In next, check availability, return the current value, and advance the column.
class Vector2D:
    def __init__(self, vec):
        self.vec = vec
        self.row = 0
        self.col = 0

    def _skip_empty_rows(self):
        while self.row < len(self.vec) and self.col >= len(self.vec[self.row]):
            self.row += 1
            self.col = 0

    def hasNext(self):
        self._skip_empty_rows()
        return self.row < len(self.vec)

    def next(self):
        if not self.hasNext():
            raise StopIteration("No more values")

        value = self.vec[self.row][self.col]
        self.col += 1
        return value

Complexity:

  • Time: O(N) total across traversal, where N is the number of rows plus values; each row is skipped at most once.
  • Space: O(1) auxiliary space, excluding the input.

Common follow-ups

  • What if the input can change during iteration? Define whether mutations are supported; otherwise assume it remains stable.
  • How would you support remove? Track the last returned position and define how removal affects the underlying structure.
  • How can this be extended to iterate over nested lists of arbitrary depth? Use a stack of iterators or an explicit depth-first traversal.
CodingMediumZenefitsSoftware Engineer

16. Min Stack (LeetCode)

Model answer

The task

Design a stack that supports pushing and removing values, inspecting the top value, and retrieving the minimum value currently stored. Each operation should take constant time.

Key idea

Alongside each value, store the minimum seen at that point in the stack. The top entry then contains enough information to answer a minimum query without scanning the stack.

Approach

  1. Keep a list of (value, minimum_so_far) pairs.
  2. On push, compare the new value with the current minimum and store the smaller one.
  3. On pop, remove the top pair.
  4. Return the value or minimum from the top pair for top and getMin.
class MinStack:
    def __init__(self):
        # Each entry is (value, minimum among entries up to this one).
        self.stack = []

    def push(self, val: int) -> None:
        current_min = val
        if self.stack:
            current_min = min(val, self.stack[-1][1])
        self.stack.append((val, current_min))

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1][0]

    def getMin(self) -> int:
        return self.stack[-1][1]

Complexity:

  • Time: O(1) per operation; each method accesses or updates only the top entry.
  • Space: O(n); each stack entry stores its value and the minimum so far.

Common follow-ups

  • Can you reduce the extra space? Store only values and keep a second stack of minimums, pushing a minimum when it is no greater than the current one.
  • How should duplicate minimums be handled? Track duplicates in the minimum stack too, so popping one leaves the other available.
  • What if the stack can be empty when queried? Define the API’s empty-stack behavior, such as raising an exception or returning a sentinel.
CodingHardZenefitsSoftware Engineer

17. Median of Two Sorted Arrays (LeetCode)

Model answer

The task

Given two sorted arrays, find the median of the values they contain together, without merging the arrays.

Key idea

Choose a partition in each array so the combined left side has half the values and every value on the left is no greater than every value on the right. Binary-search the partition in the shorter array; the other partition is determined by the required left-side size.

Approach

  1. Swap the arrays if needed so the first is shorter.
  2. Binary-search how many elements to take from the first array’s left partition.
  3. Derive the second partition’s size so the left partitions contain half the total elements.
  4. Check whether the partition boundaries are correctly ordered. If not, move the first partition left or right.
  5. For an odd total, return the largest value on the left; otherwise, average that value and the smallest value on the right.
from typing import List

class Solution:
    def findMedianSortedArrays(
        self, nums1: List[int], nums2: List[int]
    ) -> float:
        # Binary-search the shorter array.
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1

        m, n = len(nums1), len(nums2)
        total_left = (m + n + 1) // 2
        low, high = 0, m

        while low <= high:
            take1 = (low + high) // 2
            take2 = total_left - take1

            left1 = float("-inf") if take1 == 0 else nums1[take1 - 1]
            right1 = float("inf") if take1 == m else nums1[take1]
            left2 = float("-inf") if take2 == 0 else nums2[take2 - 1]
            right2 = float("inf") if take2 == n else nums2[take2]

            if left1 <= right2 and left2 <= right1:
                # The partition is valid; compute the median from its edges.
                left_max = max(left1, left2)
                if (m + n) % 2 == 1:
                    return float(left_max)

                right_min = min(right1, right2)
                return (left_max + right_min) / 2.0

            if left1 > right2:
                high = take1 - 1
            else:
                low = take1 + 1

        # For sorted input, a valid partition is always found.
        raise ValueError("Input arrays must be sorted")

Complexity:

  • Time: O(log min(m, n)), from binary-searching the shorter array.
  • Space: O(1), using a fixed number of variables.

Common follow-ups

  • How would you find the k-th smallest value instead? Binary-search a partition with exactly k values on its left.
  • What if one array is empty? The boundary sentinels let the same partition logic handle it.
  • What if the arrays are not sorted? The method relies on sorted inputs; sorting first costs O(N log N) time.
CodingHardZenefitsSoftware Engineer

18. Trapping Rain Water (LeetCode)

Model answer

The task

Given an array of nonnegative bar heights, compute how much water remains trapped between the bars after rainfall. Each bar has unit width.

Key idea

Water above a position is limited by the shorter of the tallest bars to its left and right. With two pointers, process the side whose current height is lower: its boundary already determines the maximum water that position can hold, so no arrays of prefix and suffix maxima are needed.

Approach

  1. Start pointers at both ends and track the greatest height seen from each side.
  2. While the pointers have not crossed, compare their current heights.
  3. If the left height is lower, update the left maximum and add any water above the left bar, then advance the left pointer.
  4. Otherwise, do the symmetric operation on the right.
  5. Return the accumulated water.
from typing import List

class Solution:
    def trap(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        left_max = right_max = 0
        water = 0

        while left < right:
            if height[left] < height[right]:
                # The right side is tall enough that the left maximum
                # determines the water level at this position.
                left_max = max(left_max, height[left])
                water += left_max - height[left]
                left += 1
            else:
                # Symmetrically, the right maximum determines this level.
                right_max = max(right_max, height[right])
                water += right_max - height[right]
                right -= 1

        return water

Complexity:

  • Time: O(n), because each pointer moves across the array at most once.
  • Space: O(1), because the algorithm uses only a fixed number of variables.

Common follow-ups

  • How can this be solved with dynamic programming? Precompute the maximum height to each position from the left and right, then sum the trapped water at each position.
  • How can a monotonic stack solve it? Keep indices of decreasing bar heights; when a taller bar arrives, pop a basin bottom and calculate the bounded layer.
  • What if bars have different widths? Track each bar’s width and use area rather than unit-width contributions; the boundary logic must account for the resulting horizontal spans.
CodingHardZenefitsSoftware Engineer

19. Sliding Window Maximum (LeetCode)

Model answer

The task

Given an integer array and a window width k, return the maximum value in each contiguous window as it moves from left to right.

Key idea

Keep a deque of indices whose values are in decreasing order. Its front is the index of the current window’s maximum; indices that leave the window or are dominated by a newer, larger value can be discarded.

Approach

  1. Create a deque of indices and a list for the answers.
  2. For each index, remove indices from the front if they are outside the current window.
  3. Remove indices from the back while their values are no greater than the current value.
  4. Append the current index; it is now a candidate maximum for this and future windows.
  5. Once the first full window has been processed, append the value at the deque’s front.
from collections import deque
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums or k <= 0:
            return []

        # Store indices in decreasing order of their corresponding values.
        candidates = deque()
        result = []

        for i, value in enumerate(nums):
            # Remove the maximum candidate if it is outside this window.
            while candidates and candidates[0] <= i - k:
                candidates.popleft()

            # A newer value at least as large makes older candidates useless.
            while candidates and nums[candidates[-1]] <= value:
                candidates.pop()

            candidates.append(i)

            # The first complete window ends at index k - 1.
            if i >= k - 1:
                result.append(nums[candidates[0]])

        return result

Complexity:

  • Time: O(n), because each index is added to and removed from the deque at most once.
  • Space: O(k), for the deque of candidate indices, excluding the output.

Common follow-ups

  • How would you find window minima instead? Reverse the deque’s ordering, removing smaller values from the back.
  • What if equal values should preserve the earliest index? Remove only strictly smaller values from the back.
  • How can this be handled as a streaming input? Maintain the same bounded deque and emit a maximum whenever a full window has arrived.
CodingHardZenefitsSoftware Engineer

20. N-Queens II (LeetCode)

Model answer

The task

Count the distinct ways to place n queens on an n × n chessboard so that no two queens attack each other. Return the count, not the board layouts.

Key idea

Place one queen per row and track which columns and diagonals are already occupied. Bit masks let us find all safe columns for a row and try each option efficiently.

Approach

  1. Represent occupied columns and diagonals as bit masks.
  2. For each row, compute the available columns by excluding attacked positions.
  3. Try each available column, updating the masks for the next row.
  4. When all rows are filled, add one to the solution count.
class Solution:
    def totalNQueens(self, n: int) -> int:
        full = (1 << n) - 1

        def search(columns: int, diag_left: int, diag_right: int) -> int:
            # Every row has a queen once all n rows have been processed.
            if columns == full:
                return 1

            # Bits set in available represent safe columns for this row.
            available = full & ~(columns | diag_left | diag_right)
            count = 0

            while available:
                # Choose and remove the rightmost available column.
                queen = available & -available
                available ^= queen

                count += search(
                    columns | queen,
                    ((diag_left | queen) << 1) & full,
                    (diag_right | queen) >> 1,
                )

            return count

        return search(0, 0, 0)

Complexity:

  • Time: O(n!) search-tree upper bound, with diagonal checks pruning branches.
  • Space: O(n) recursion depth, excluding the masks.

Common follow-ups

  • How can symmetry reduce the search? Count first-row placements on half the board, double their totals, and handle the middle column separately when n is odd.
  • How would you return the actual board arrangements? Store each chosen column along the recursion path and build a board at each complete placement.
  • What if n becomes very large? The count grows rapidly; discuss symmetry, pruning, or specialized counting methods, noting that exact counting remains expensive.

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