DSA in Python Interviews Checkpoint

45 min · Advanced

Fix the mistakes

The slips that cost marks in this module. Spot each one, then check the fix.

Put the whole module together: say your approach in order, match the clue to a pattern, solve a tree, graph or DP question, and handle a follow-up. Finish the checkpoint without notes, then pick problems from the Python DSA 150 sheet at /learn/python/dsa-sheet and say your answer aloud.

Say it in order

A strong answer has the same shape every time: restate, brute force with cost, repeated work, better idea, code, test, final cost. Revise: Explaining your approach and its cost (opens in a new tab)

Python

1def has_pair(sorted_nums, target):2    left, right = 0, len(sorted_nums) - 13    while left < right:4        total = sorted_nums[left] + sorted_nums[right]5        if total == target:6            return True7        if total < target:8            left += 19        else:10            right -= 111    return False

Example 1 · Longest consecutive sequence: brute force, then a set

Python

1def longest_brute(nums):2    # Sort first: O(n log n).3    best = run = 04    previous = None5    for value in sorted(set(nums)):6        run = run + 1 if previous is not None and value == previous + 1 else 17        best = max(best, run)8        previous = value9    return best10
11
12def longest_set(nums):13    # O(n): only start counting at the beginning of a run.14    values = set(nums)15    best = 016    for value in values:17        if value - 1 not in values:18            length = 119            while value + length in values:20                length += 121            best = max(best, length)22    return best23
24
25nums = [100, 4, 200, 1, 3, 2]26print(longest_brute(nums), longest_set(nums))27print(longest_brute([]), longest_set([]))

Output

4 4
0 0

What this code does

Sorting works in O(n log n). The set version starts counting only from a value with no smaller neighbour, so each value is visited at most twice: O(n).
Test the empty list. Say that duplicates are harmless because of the set.

Say: "The list is sorted, so a too-small sum moves the left pointer and a too-big sum moves the right one. Each step discards a value: O(n) time, O(1) space."

Pick the pattern and the tool from the clue

Name the clue first, then the pattern. Revise any of them in the previous lessons. Revise: Common pattern and data structure questions (opens in a new tab)

Sorted pair: two pointers. Window with a condition: sliding window. Range sums: prefix sums.
Counting or 'seen before': dict, Counter or set. Top k: heap. Next greater: monotonic stack.
Fewest edges: BFS. Explore or count regions: DFS with a visited set. Order with prerequisites: topological sort.
Best value or count with repeated subproblems: DP, with state, base case and transition.

Example 2 · Right side view of a tree, then house robber with O(1) space

Python

1class TreeNode:2    def __init__(self, val, left=None, right=None):3        self.val = val4        self.left = left5        self.right = right6
7
8from collections import deque9
10
11def right_view(root):12    view = []13    queue = deque([root] if root else [])14    while queue:15        view.append(queue[-1].val)16        for _ in range(len(queue)):17            node = queue.popleft()18            for child in (node.left, node.right):19                if child:20                    queue.append(child)21    return view22
23
24def rob(houses):25    skip, take = 0, 026    for money in houses:27        skip, take = max(skip, take), skip + money28    return max(skip, take)29
30
31root = TreeNode(1, TreeNode(2, None, TreeNode(5)), TreeNode(3, None, TreeNode(4)))32print(right_view(root))33print(rob([2, 7, 9, 3, 1]))

Output

[1, 3, 4]
12

What this code does

The last node in the queue at the start of a level is the rightmost one. This is level order with one extra line, O(n) time.
House robber needs only the best with and without the previous house, so two variables replace a table: O(n) time, O(1) space.

Follow-ups: say what breaks

For each change in the problem, name the assumption it breaks. Huge input means a stream and a small state. Many queries mean preprocessing. Less memory means in place or two pointers. Revise: Following up on your solution (opens in a new tab)

Example 3 · A follow-up: the same stream, bounded memory

Python

1import heapq2
3
4def top_two_in_stream(stream):5    heap = []6    for value in stream:7        heapq.heappush(heap, value)8        if len(heap) > 2:9            heapq.heappop(heap)10    return sorted(heap, reverse=True)11
12
13print(top_two_in_stream(iter([4, 9, 1, 7, 3])))

Output

[9, 7]

What this code does

The function accepts any iterator, so it works on a file or generator that cannot be stored. Memory stays at two items.
If the interviewer says the input is huge, this is the one-sentence answer: time O(n log k), space O(k).

Module quiz

Questions from the whole module. Your first answer is your score.

Problems

Graded easy to hard, using everything from this module.

Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.

Exercise 1· Easy

Print the 1-based positions of the two numbers in the sorted list [2, 7, 11, 15] that add up to 9, using two pointers.

Expected output

1 2

Exercise 2· Easy

Move all zeros of [0, 1, 0, 3, 12] to the end in place, keeping the order of the others, with a read and a write pointer. Print the list.

Expected output

[1, 3, 12, 0, 0]

Exercise 3· Easy

Print whether [1, 2, 3, 1] with k = 3, [1, 2, 3, 1, 2, 3] with k = 2 contain two equal values at most k positions apart. Use a dict of last positions.

Expected output

True
False

Exercise 4· Medium

Print the length of the longest run of consecutive integers in [100, 4, 200, 1, 3, 2], and in the empty list, in O(n) with a set.

Expected output

4
0

Exercise 5· Medium

Print the right side view (the rightmost value of every level) of the tree 1 -> (2, 3) where 2 has a right child 5 and 3 has a right child 4.

Expected output

[1, 3, 4]

Exercise 6· Medium

Print the 2 most frequent numbers in [1, 1, 1, 2, 2, 3] with a Counter and heapq.nlargest.

Expected output

[1, 2]

Exercise 7· Hard

Print the most money that can be taken from houses [2, 7, 9, 3, 1] without taking two neighbours, then from [1, 2, 3, 1]. Use O(1) space.

Expected output

12
4

Exercise 8· Hard

Print the fewest steps from S to E in the grid ["S.#.", "..#E", "...."] where # is a wall and you move up, down, left or right. Print -1 for the grid ["S#E"].

Expected output

6
-1

Interview questions

Questions interviewers ask on this topic.

What's next

You finished the preview of DSA in Python Interviews

Python Programming has 21 sections, 110 modules and 609 lessons. An account opens every lesson and saves your progress.

Create account I already have an account

Finish up

Mark complete & continue

Next: Mock interview 1: Python basics and an easy problem

1def has_pair(sorted_nums, target):2 left, right = 0, len(sorted_nums) - 13 while left < right:4 total = sorted_nums[left] + sorted_nums[right]5 if total == target:6 return True7 if total < target:8 left += 19 else:10 right -= 111 return False

1def longest_brute(nums):2 # Sort first: O(n log n).3 best = run = 04 previous = None5 for value in sorted(set(nums)):6 run = run + 1 if previous is not None and value == previous + 1 else 17 best = max(best, run)8 previous = value9 return best10 11 12def longest_set(nums):13 # O(n): only start counting at the beginning of a run.14 values = set(nums)15 best = 016 for value in values:17 if value - 1 not in values:18 length = 119 while value + length in values:20 length += 121 best = max(best, length)22 return best23 24 25nums = [100, 4, 200, 1, 3, 2]26print(longest_brute(nums), longest_set(nums))27print(longest_brute([]), longest_set([]))

1class TreeNode:2 def __init__(self, val, left=None, right=None):3 self.val = val4 self.left = left5 self.right = right6 7 8from collections import deque9 10 11def right_view(root):12 view = []13 queue = deque([root] if root else [])14 while queue:15 view.append(queue[-1].val)16 for _ in range(len(queue)):17 node = queue.popleft()18 for child in (node.left, node.right):19 if child:20 queue.append(child)21 return view22 23 24def rob(houses):25 skip, take = 0, 026 for money in houses:27 skip, take = max(skip, take), skip + money28 return max(skip, take)29 30 31root = TreeNode(1, TreeNode(2, None, TreeNode(5)), TreeNode(3, None, TreeNode(4)))32print(right_view(root))33print(rob([2, 7, 9, 3, 1]))

1import heapq2 3 4def top_two_in_stream(stream):5 heap = []6 for value in stream:7 heapq.heappush(heap, value)8 if len(heap) > 2:9 heapq.heappop(heap)10 return sorted(heap, reverse=True)11 12 13print(top_two_in_stream(iter([4, 9, 1, 7, 3])))

Say it in order

What this code does

Pick the pattern and the tool from the clue

What this code does

Follow-ups: say what breaks

What this code does

Exercise 1· Easy

Exercise 2· Easy

Exercise 3· Easy

Exercise 4· Medium

Exercise 5· Medium

Exercise 6· Medium

Exercise 7· Hard

Exercise 8· Hard

You finished the preview of DSA in Python Interviews

Say it in order

What this code does

Pick the pattern and the tool from the clue

What this code does

Follow-ups: say what breaks

What this code does

What should you do right after restating the problem?

A problem asks for the shortest path in an unweighted maze. Which tool?

What is the cost of building a set of n items and testing n lookups?

What does this print, and what do the printed values mark?

Why does a graph search need a visited set?

A DP table dp[i] only uses dp[i - 1] and dp[i - 2]. How can you cut its space?

What does this print?

The interviewer says the file is larger than memory. What changes?

Many range-sum queries on a fixed list. What is the best approach?

Why does greedy fail for coin change with coins 1, 5, 6, 9 and amount 11?

What is the time cost of a monotonic stack pass?

You get stuck. What is the best thing to do?

Exercise 1· Easy

Exercise 2· Easy

Exercise 3· Easy

Exercise 4· Medium

Exercise 5· Medium

Exercise 6· Medium

Exercise 7· Hard

Exercise 8· Hard

Q1Walk me through how you would approach an unfamiliar coding question.

Q2How do you manage a 45-minute coding round?

Q3What do you do when you are stuck?

Q4How do you choose between two valid solutions?

Q5What edge cases do you always test?

Q6How do you dry run your code?

Q7Do you use built-in functions like Counter, sorted or heapq?

Q8How do you explain the cost of a recursive solution?

Q9What is the most common mistake in coding interviews?

Q10How should you handle a bug found during testing?

Q11How do you show you can write clean code?

Q12How do you talk about trade-offs?

Q13What if the interviewer hints that your solution is slow?

Q14How do you prepare for DSA interviews in Python?

Q15How many problems should you solve before interviews?

Q16When should you ask for a hint?

Q17How do you check that your answer is correct without running it?

Q18Is it fine to write the brute force and stop?

Q19How do you end a coding answer?

Q20What do interviewers look for beyond correct code?

You finished the preview of DSA in Python Interviews

What should you do right after restating the problem?

A problem asks for the shortest path in an unweighted maze. Which tool?

What is the cost of building a set of n items and testing n lookups?

What does this print, and what do the printed values mark?

Why does a graph search need a visited set?

A DP table dp[i] only uses dp[i - 1] and dp[i - 2]. How can you cut its space?

What does this print?

The interviewer says the file is larger than memory. What changes?

Many range-sum queries on a fixed list. What is the best approach?

Why does greedy fail for coin change with coins 1, 5, 6, 9 and amount 11?

What is the time cost of a monotonic stack pass?

You get stuck. What is the best thing to do?

Q1Walk me through how you would approach an unfamiliar coding question.

Q2How do you manage a 45-minute coding round?

Q3What do you do when you are stuck?

Q4How do you choose between two valid solutions?

Q5What edge cases do you always test?

Q6How do you dry run your code?