Karat interview questions & answers

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

CodingEasyKaratSoftware Engineer

1. Find Words That Can Be Formed by Characters (LeetCode)

Model answer

The task

Given a list of words and a collection of available characters, return the total length of the words that can be formed using those characters. Each character can be used only as many times as it appears in the collection.

Key idea

Count the available characters once. A word is formable exactly when its count for every character does not exceed the available count.

Approach

  1. Build a frequency counter for the available characters.
  2. For each word, count its characters.
  3. Check whether every needed count is available.
  4. Add the word’s length to the total when it passes the check.
  5. Return the total.
from collections import Counter
from typing import List

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        available = Counter(chars)
        total_length = 0

        for word in words:
            needed = Counter(word)

            if all(needed[ch] <= available[ch] for ch in needed):
                total_length += len(word)

        return total_length

Complexity:

  • Time: O(C + S), where C is the length of chars and S is the total length of all words.
  • Space: O(U + M), where U is the number of distinct characters in chars and M is the maximum word length, for the counters.

Common follow-ups

  • What if many word lists use the same characters? Reuse the available-character counter across all lists.
  • How could you avoid counting each word’s characters from scratch? Precompute word counters if the same words are checked repeatedly.
  • What if the character collection is updated between queries? Update its frequency counts and evaluate words against the current counts.
CodingEasyKaratSoftware Engineer

2. Check if Every Row and Column Contains All Numbers (LeetCode)

Model answer

The task

Determine whether an \(n \times n\) matrix contains each number from 1 through \(n\) exactly once in every row and every column.

Key idea

A row or column is valid if its set of values equals the set \(\{1, 2, \ldots, n\}\). Check rows and columns separately, reusing one set to keep extra space linear.

Approach

  1. Build the expected set of values.
  2. Compare each row’s set with the expected set; return False if any differs.
  3. For each column, collect its values into a set and compare it with the expected set.
  4. Return True if all checks pass.
from typing import List

class Solution:
    def checkValid(self, matrix: List[List[int]]) -> bool:
        n = len(matrix)
        expected = set(range(1, n + 1))

        # Every row must contain each expected value once.
        for row in matrix:
            if set(row) != expected:
                return False

        # Every column must also contain each expected value once.
        for col in range(n):
            column_values = {matrix[row][col] for row in range(n)}
            if column_values != expected:
                return False

        return True

Complexity:

  • Time: O(n²), to inspect all matrix entries.
  • Space: O(n), for the expected set and one row or column set.

Common follow-ups

  • Can you detect duplicates in one pass? Track seen values for each row and column as you scan.
  • What if values are not restricted to 1 through \(n\)? Compare against the required value set, or validate the allowed range separately.
  • How would you handle a non-square matrix? Define the required values per row and column based on the intended dimensions and rules.
CodingEasyKaratSoftware Engineer

3. Ransom Note (LeetCode)

Model answer

The task

Determine whether the characters in one string can be assembled from the characters in another. Each available character can be used at most once.

Key idea

Count how many times each character is available, then check that the required count for every character does not exceed its available count.

Approach

  1. Count the characters in the available string.
  2. Count the characters needed for the target string.
  3. If any required count is greater than the available count, return False.
  4. Otherwise, return True.
from collections import Counter

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        available = Counter(magazine)
        needed = Counter(ransomNote)

        # Every required character must be available in sufficient quantity.
        for char, count in needed.items():
            if available[char] < count:
                return False

        return True

Complexity:

  • Time: O(m + n), where m and n are the string lengths; counting and checking take linear time.
  • Space: O(k), where k is the number of distinct characters stored in the counters.

Common follow-ups

  • What if characters are case-insensitive? Normalize both strings, such as with .lower(), before counting.
  • What if the character set is fixed and small? Use a fixed-size array instead of a hash map.
  • Can you stop early while counting? Yes; decrement available counts as you scan the target and return False if a count goes below zero.
CodingMediumKaratSoftware Engineer

4. Word Search (LeetCode)

Model answer

The task

Determine whether a word can be traced through adjacent cells in a character grid. Each cell may be used at most once in the same trace.

Key idea

Try each cell as a starting point and use depth-first search to match the word one character at a time. Track cells used in the current path, then undo that tracking when backtracking.

Approach

  1. Return False if the grid is empty or the word is longer than the number of cells.
  2. Start a DFS from every cell matching the word’s first character.
  3. In the DFS, reject out-of-bounds cells, used cells, or character mismatches.
  4. Return True once all characters are matched.
  5. Add each matched cell to the path before exploring neighbors, and remove it afterward.
from typing import List, Set, Tuple

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not word:
            return True
        if not board or not board[0]:
            return False

        rows, cols = len(board), len(board[0])
        if len(word) > rows * cols:
            return False

        used: Set[Tuple[int, int]] = set()

        def search(row: int, col: int, index: int) -> bool:
            if (
                row < 0 or row >= rows
                or col < 0 or col >= cols
                or (row, col) in used
                or board[row][col] != word[index]
            ):
                return False

            if index == len(word) - 1:
                return True

            used.add((row, col))
            found = (
                search(row + 1, col, index + 1)
                or search(row - 1, col, index + 1)
                or search(row, col + 1, index + 1)
                or search(row, col - 1, index + 1)
            )
            used.remove((row, col))
            return found

        for row in range(rows):
            for col in range(cols):
                if search(row, col, 0):
                    return True

        return False

Complexity:

  • Time: O(RC · 4^L), where R and C are grid dimensions and L is the word length; each cell may start a search.
  • Space: O(L), for the visited path and recursive call stack.

Common follow-ups

  • What if diagonal moves are allowed? Add the four diagonal directions to the DFS.
  • How can the search be pruned? Check character frequencies before searching, or start from the rarer end of the word.
  • How would you search for many words at once? Build a trie and search the grid while matching trie prefixes.
CodingMediumKaratSoftware Engineer

5. Maximal Square (LeetCode)

Model answer

The task

Given a rectangular matrix of "0" and "1" characters, find the area of the largest square containing only "1" cells. Return 0 if no such square exists.

Key idea

For each cell containing "1", let its DP value be the side length of the largest all-"1" square ending at that cell. It is limited by the squares ending above, to the left, and diagonally above-left.

Approach

  1. Return 0 for an empty matrix.
  2. Keep one DP row, where dp[j] holds the largest square ending at the current row and column j.
  3. Save the previous row’s diagonal value before updating each cell.
  4. For a "1" cell, set its value to one plus the minimum of its top, left, and diagonal values; for a "0", set it to zero.
  5. Track the largest side length and return its square.
from typing import List

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

        rows, cols = len(matrix), len(matrix[0])
        dp = [0] * (cols + 1)
        largest_side = 0

        for i in range(rows):
            diagonal = 0  # DP value from the previous row, previous column

            for j in range(1, cols + 1):
                above = dp[j]

                if matrix[i][j - 1] == "1":
                    dp[j] = 1 + min(dp[j], dp[j - 1], diagonal)
                    largest_side = max(largest_side, dp[j])
                else:
                    dp[j] = 0

                diagonal = above

        return largest_side * largest_side

Complexity:

  • Time: O(mn), where m and n are the matrix dimensions.
  • Space: O(n), for the rolling DP row.

Common follow-ups

  • How would you reconstruct the square’s coordinates? Track the location where the largest side is found, then derive its top-left corner.
  • Can the solution use more memory to simplify the recurrence? Yes; store DP values for all cells in an m × n table.
  • What if the matrix is streamed one row at a time? The rolling-row approach already supports this, retaining only the previous row’s state.
CodingMediumKaratSoftware Engineer

6. Valid Sudoku (LeetCode)

Model answer

The task

Given a partially filled 9×9 Sudoku board, determine whether its filled cells obey the rules: no digit appears more than once in any row, column, or 3×3 box. Empty cells do not affect validity.

Key idea

Track the digits already seen in each row, column, and box. When a filled cell repeats a digit in any of its three groups, the board is invalid.

Approach

  1. Create a set for each row, column, and 3×3 box.
  2. Visit each cell in the board.
  3. Skip empty cells.
  4. Compute the box index from the cell’s row and column.
  5. Return False if the digit is already in any corresponding set; otherwise add it to all three.
  6. If every cell passes, return True.
from typing import List

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]

        for r in range(9):
            for c in range(9):
                digit = board[r][c]
                if digit == ".":
                    continue

                # Each 3×3 box has an index from 0 through 8.
                box = (r // 3) * 3 + (c // 3)

                if (
                    digit in rows[r]
                    or digit in cols[c]
                    or digit in boxes[box]
                ):
                    return False

                rows[r].add(digit)
                cols[c].add(digit)
                boxes[box].add(digit)

        return True

Complexity:

  • Time: O(1) for a fixed 9×9 board; more generally, O(n²) for an n×n board.
  • Space: O(1) for a fixed board; more generally, O(n²) for the stored digits.

Common follow-ups

  • How would you handle boards of arbitrary valid Sudoku size? Derive the box dimensions and index formula from the board size.
  • Could you reduce set overhead? Use bit masks to track which digits have appeared in each group.
  • Does a valid board need to be solvable? No; this check only verifies that no current row, column, or box contains duplicates.
CodingMediumKaratSoftware Engineer

7. Alert Using Same Key-Card Three or More Times in a One Hour Period (LeetCode)

Model answer

The task

Given cardholder names and corresponding swipe times, find everyone who used their card at least three times within a one-hour span. Return the names in lexicographic order.

Key idea

Group times by cardholder, convert each time to minutes after midnight, and sort them. In sorted order, any qualifying group of three consecutive swipes has a span of at most 60 minutes.

Approach

  1. Pair each name with its time and convert the time to minutes.
  2. Group those minute values by name.
  3. Sort each person’s times.
  4. Check every window of three consecutive times.
  5. Collect qualifying names and return them sorted.
from collections import defaultdict
from typing import List

class Solution:
    def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
        times_by_name = defaultdict(list)

        for name, time in zip(keyName, keyTime):
            hours, minutes = map(int, time.split(":"))
            times_by_name[name].append(hours * 60 + minutes)

        alerted = []

        for name, times in times_by_name.items():
            times.sort()

            # Three consecutive times are within one hour if their
            # earliest and latest times are at most 60 minutes apart.
            for i in range(len(times) - 2):
                if times[i + 2] - times[i] <= 60:
                    alerted.append(name)
                    break

        return sorted(alerted)

Complexity:

  • Time: O(n log n), from sorting each cardholder’s swipe times.
  • Space: O(n), for the grouped times.

Common follow-ups

  • What if the alert threshold were k swipes? Check windows of k consecutive sorted times.
  • What if the time span were configurable? Replace 60 with the specified number of minutes.
  • What if swipes could span multiple days? Include the date in each timestamp before sorting and comparing.
CodingMediumKaratSoftware Engineer

8. High-Access Employees (LeetCode)

Model answer

The task

Given employee access records with times in HHMM format, return the employees who accessed the system at least three times within a one-hour period.

Key idea

Group access times by employee and sort each group. Three accesses fit within one hour exactly when some three consecutive sorted times differ by less than 60 minutes from first to last.

Approach

  1. Convert each HHMM time to minutes after midnight.
  2. Group the converted times by employee.
  3. Sort each employee’s times.
  4. Check every consecutive group of three; include the employee if its span is under 60 minutes.
  5. Return the matching employee names.
from collections import defaultdict
from typing import List

class Solution:
    def findHighAccessEmployees(
        self, access_times: List[List[str]]
    ) -> List[str]:
        times_by_employee = defaultdict(list)

        for employee, time in access_times:
            hour = int(time[:2])
            minute = int(time[2:])
            times_by_employee[employee].append(hour * 60 + minute)

        result = []

        for employee, times in times_by_employee.items():
            times.sort()

            for i in range(len(times) - 2):
                if times[i + 2] - times[i] < 60:
                    result.append(employee)
                    break

        return result

Complexity:

  • Time: O(n log n), from sorting each employee’s access times; across all employees, the total is at most O(n log n).
  • Space: O(n), to store the grouped access times.

Common follow-ups

  • What if the threshold is a parameter? Compare each consecutive group’s span against that threshold.
  • What if the requirement is more than three accesses? Check a window of the required size.
  • What if times can span multiple days? Parse dates too, and compare full timestamps rather than minutes after midnight.
CodingMediumKaratSoftware Engineer

9. Jump Game (LeetCode)

Model answer

The task

Given an array where each value is the maximum distance you may jump forward from that position, determine whether you can reach the final position starting at the first.

Key idea

Track the farthest position reachable so far. If you encounter an index beyond that boundary, it cannot be reached; otherwise, use its jump length to extend the boundary.

Approach

  1. Initialize the farthest reachable index to zero.
  2. Scan the array from left to right.
  3. If the current index is beyond the farthest reachable index, return False.
  4. Extend the farthest reachable index using the current jump.
  5. Return True once the final index is reachable.
from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        farthest = 0

        for index, jump in enumerate(nums):
            # This position cannot be reached from any earlier position.
            if index > farthest:
                return False

            farthest = max(farthest, index + jump)

            # No need to inspect positions beyond the destination.
            if farthest >= len(nums) - 1:
                return True

        return True

Complexity:

  • Time: O(n), where n is the number of positions scanned.
  • Space: O(1), using only a few variables.

Common follow-ups

  • What if you need the minimum number of jumps? Track the current jump range and the farthest reach of the next range.
  • How would you return an actual path of positions? Store predecessor information as positions first become reachable.
  • What if jumps can go both forward and backward? The reachable set may no longer be represented by a single forward boundary; use graph traversal or a suitable interval-based method.
CodingHardKaratSoftware Engineer

10. Text Justification (LeetCode)

Model answer

The task

Format a sequence of words into lines of a fixed width. Fully justify each line except the final line, which is left-justified.

Key idea

Greedily place as many words as possible on each line, counting at least one space between adjacent words. Once a line is chosen, distribute its remaining spaces as evenly as possible; any extras go into the leftmost gaps.

Approach

  1. Start a line with the next unformatted word and keep adding words while they fit with one space between each pair.
  2. If the line is the final line, or contains just one word, join with single spaces and pad on the right.
  3. Otherwise, divide the available spaces evenly across the gaps.
  4. Give one additional space to each of the leftmost gaps until the remainder is used.
  5. Repeat until all words are formatted.
from typing import List

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        result = []
        i = 0

        while i < len(words):
            # Find the largest group of words that fits on this line,
            # counting one mandatory space between each pair.
            j = i
            letters = 0

            while j < len(words) and letters + len(words[j]) + (j - i) <= maxWidth:
                letters += len(words[j])
                j += 1

            gaps = j - i - 1
            is_last_line = j == len(words)

            if is_last_line or gaps == 0:
                # The final line and single-word lines are left-justified.
                line = " ".join(words[i:j])
                line += " " * (maxWidth - len(line))
            else:
                total_spaces = maxWidth - letters
                spaces_per_gap, extra_spaces = divmod(total_spaces, gaps)

                parts = []
                for gap in range(gaps):
                    parts.append(words[i + gap])
                    # Earlier gaps receive any leftover spaces.
                    spaces = spaces_per_gap + (1 if gap < extra_spaces else 0)
                    parts.append(" " * spaces)

                parts.append(words[j - 1])
                line = "".join(parts)

            result.append(line)
            i = j

        return result

Complexity:

  • Time: O(n + L × W), where n is the total number of input characters, L is the number of output lines, and W is the line width.
  • Space: O(L × W) for the returned lines; O(W) additional space to build a line.

Common follow-ups

  • What if words may be hyphenated? Split long words into width-limited pieces before packing.
  • What if the last line must also be fully justified? Apply the regular gap-distribution rule to it.
  • How can this handle a streaming word source? Buffer words for the current line, then emit it as soon as the next word no longer fits.

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