Stack Bash - Master data structures and algorithms

Python for interviews

This is not a full Python course. It's the subset that shows up in coding interviews, and in AI-written Python you're asked to review.
This course uses Python 3. The editors below run in the browser. Plain code blocks are just there to read.

What runs in the editor

The in-browser runner can execute the Python this course already uses:
  • lists, dicts, sets, strings
  • for, while, range, enumerate
  • f-strings, slicing, "".join
  • type hints like list[int]
If you can write Find the smallest or Two sum, you can write in this editor.

Lists

In Python, a list is a dynamic array.
colors = ['blue', 'purple', 'red']
print(colors[1]) # purple
Lookup by index is constant time, O(1). Walking the whole list is linear, O(n).
Appending to the end is usually O(1). Inserting or deleting in the middle takes O(n), because everything after that index has to scoot over.
nums[-1] is the last item. nums[1:3] is a slice — a new list from index 1 up to, but not including, 3.
Slicing copies, so it takes O(k) time and O(k) space, where k is the length of the slice.

Dictionaries and sets

A hash table in Python is a dict or a set.
Lookups, inserts, and deletes are average O(1).
ages = {
'alice': 24,
'rohit': 33,
'bob': 27
}
print(ages['bob']) # 27
A set only stores keys. Use it when you care about have I seen this and not a value.
in on a dict or set is average O(1). in on a list is O(n), because it may scan the whole list.

Strings

A string is an array of characters. In Python, strings are immutable. You can't assign to s[0].
Concatenating with + builds a new string each time. In a loop, that can get expensive.
It's often better to append to a list, then "".join(...) at the end. join runs in linear time.
s[::-1] reverses a string. Under the hood that's still O(n) time and O(n) space, because a new string gets allocated.
Tip: Built-in methods like sorted, min, and "".join are fine in an interview as long as you can say what they do under the hood and give the time and space cost.

Loops

range(n) is 0 through n - 1. enumerate gives you the index and the value together.
None is Python's empty value. An empty list, empty string, and 0 are all falsy in an if.

Read / recognize (newer Python)

AI drafts often use Python 3.10+ syntax. You should know what it means so you can review it. You don't need to write it in this editor. It may not run here.
# match / case — same idea as if / elif
match n:
case 0:
return 'zero'
case 1 | 2:
return 'small'
case _:
return 'other'
# int | None — an int, or None
def lookup(name: str) -> int | None:
return ages.get(name)
# := (walrus) — assign and use in one line
while (line := get_line()):
print(line)
A few more you'll see:
  • @dataclass builds __init__ for you. In an interview, a plain class or a tuple is usually enough.
  • list[int] is the same idea as the older List[int]. The editor does accept list[int].
  • Optional[int] is the older way to write int | None.
If a draft uses match or := and you want to run it here, rewrite it as a regular if or assignment first.

Two short exercises

Then the DSA problems in this chapter.

7 Essential DSA in the AI era Coding Interview Problems

Master DSA in the AI era by trying the coding challenges below.
  1. 1.Count occurrencesEasy
  2. 2.Fix the default listEasy
  3. 3.Move zeroesEasy
  4. 4.Is subsequenceEasy
  5. 5.First unique characterEasy
  6. 6.Group anagramsMedium
  7. 7.Climb stairsEasy