SyntaxPilot
Courses/Python Coding Questions/Lesson 5
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Python Coding Questions · Lesson 5 of 30

List questions I

largest and second largest (with duplicates)min and max in one passwhy sorted() just to find the max is O(n log n)

These are the notes for Python Coding Questions, episode 5, the first list episode. Three questions every fresher is asked: the largest element, the second largest, and the minimum and maximum. They are easy to write and easy to get wrong with negative numbers, duplicates and empty lists, and they're a good place to see what sorting really costs.

Every program was run with Python 3.13 (python3 main.py), the SyntaxPilot compiler's Python command. Every output below is real; timings depend on the machine, so compare them, don't copy them.

Q1: The largest element

Input Output
[3, 9, 4] 9
[12, 35, 1, 10, 34] 35
[-3, -7, -1] (night temperatures in Leh in January, °C) -1
[] ? (ask the interviewer)

The obvious attempt: start at 0

def largest(nums):
    best = 0
    for x in nums:
        if x > best:
            best = x
    return best

print(largest([3, 9, 4]), largest([12, 35, 1, 10, 34]))
print(largest([-3, -7, -1]))         # Leh in January
print(largest([]))

Output:

9 35
0
0

Why it's wrong: best = 0 quietly adds a fake element, 0, to the list. Every negative number loses to it, so Leh's warmest night comes out as 0 °C, a temperature that never happened, and the empty list also says 0.

The fix: start from a real element

def largest(nums):
    best = nums[0]                    # the first one so far
    for x in nums[1:]:
        if x > best:
            best = x
    return best

print(largest([3, 9, 4]), largest([-3, -7, -1]))
print(max([-3, -7, -1]), max([], default=None))
print(max([]))

Output:

9 -1
-1 None
Traceback (most recent call last):
  File "main.py", line 10, in <module>
    print(max([]))
          ~~~^^^^
ValueError: max() iterable argument is empty
  • best = nums[0], then loop over nums[1:] (slicing copies the list; for x in nums: from the start also works and avoids the copy).
  • max() does the same in C. max([]) raises ValueError: max() iterable argument is empty, which is better than a made-up 0. max(nums, default=None) returns None instead.
  • Our own version raises IndexError on nums[0] for an empty list. In an interview, ask what an empty list should return, then check if not nums: first.
  • Time O(n), space O(1).

Q2: The second largest element

Real-life example: a race scored 5, 5, 3. Two runners tie for gold; silver goes to the next different value, 3. "Second largest" usually means the largest value smaller than the maximum; if all values are equal, there is none. Always confirm this definition.

Input Output
[12, 35, 1, 10, 34, 1] 34
[5, 5, 3] 3
[10, 10, 10] None
[7], [] None
[-3, -7, -1] -3

Attempt 1: sort and take index -2

def second_largest(nums):
    return sorted(nums)[-2]

print(second_largest([12, 35, 1, 10, 34, 1]))
print(second_largest([5, 5, 3]))
print(second_largest([7]))

Output:

34
5
Traceback (most recent call last):
  File "main.py", line 6, in <module>
    print(second_largest([7]))
          ~~~~~~~~~~~~~~^^^^^
  File "main.py", line 2, in second_largest
    return sorted(nums)[-2]
           ~~~~~~~~~~~~^^^^
IndexError: list index out of range

sorted([5, 5, 3]) is [3, 5, 5]: index −2 is the other 5. A one-element list has no index −2: IndexError: list index out of range. And sorting costs O(n log n).

Attempt 2: one pass with float("-inf")

float("-inf") (minus infinity) is smaller than every number, so it's a safe starting value.

def second_largest(nums):
    first = second = float("-inf")
    for x in nums:
        if x > first:
            first, second = x, first
        elif x > second:
            second = x
    return second

for nums in [[12, 35, 1, 10, 34, 1], [5, 5, 3], [7]]:
    print(nums, "->", second_largest(nums))

Output:

[12, 35, 1, 10, 34, 1] -> 34
[5, 5, 3] -> 5
[7] -> -inf

The second 5 is not bigger than first (5) but is bigger than second (−inf at that moment), so it takes silver. And [7] returns -inf, not a real answer.

The fix: a chained comparison

first > x > second means first > x and x > second, written like in maths. A value equal to first is skipped.

def second_largest(nums):
    first = second = float("-inf")
    for x in nums:
        if x > first:
            first, second = x, first
        elif first > x > second:     # strictly between
            second = x
    return None if second == float("-inf") else second

for nums in [[12, 35, 1, 10, 34, 1], [5, 5, 3], [10, 10, 10],
             [7], [], [-3, -7, -1], [1, 2]]:
    print(nums, "->", second_largest(nums))

Output:

[12, 35, 1, 10, 34, 1] -> 34
[5, 5, 3] -> 3
[10, 10, 10] -> None
[7] -> None
[] -> None
[-3, -7, -1] -> -3
[1, 2] -> 1

One pass: O(n) time, O(1) space, and it works even on a stream of numbers that never fits in memory.

The readable alternative: a set

def second_largest(nums):
    distinct = sorted(set(nums))     # set drops duplicates
    return distinct[-2] if len(distinct) >= 2 else None

for nums in [[12, 35, 1, 10, 34, 1], [5, 5, 3], [10, 10, 10], [7], []]:
    print(nums, "->", second_largest(nums))

Output:

[12, 35, 1, 10, 34, 1] -> 34
[5, 5, 3] -> 3
[10, 10, 10] -> None
[7] -> None
[] -> None

Correct and short, but it builds a set and a sorted list: O(n) extra space, O(n log n) time. Give both answers in an interview and say when you'd pick each.

Q3: Min and max

Real-life example: a max-min thermometer has two markers the mercury pushes during the day; at night you read the lowest and highest. Nothing else is stored: one pass, two variables. Sorting the whole list to read its two ends is like writing down every reading of the day in order, just to read two of them.

import random, time

random.seed(1)
nums = [random.randint(-10**9, 10**9) for _ in range(2_000_000)]

start = time.perf_counter()
s = sorted(nums)
print("sorted:   ", s[0], s[-1], f"{time.perf_counter() - start:.3f} s")

start = time.perf_counter()
print("min, max: ", min(nums), max(nums), f"{time.perf_counter() - start:.3f} s")

start = time.perf_counter()
lo = hi = nums[0]
for x in nums:
    if x < lo:
        lo = x
    elif x > hi:
        hi = x
print("one loop: ", lo, hi, f"{time.perf_counter() - start:.3f} s")

Output (one run):

sorted:    -999997904 999998257 0.400 s
min, max:  -999997904 999998257 0.028 s
one loop:  -999997904 999998257 0.079 s
  • random.seed(1) makes the "random" numbers the same on every run, so the test can be repeated.
  • sorted is O(n log n): about log₂(2,000,000) ≈ 21 comparisons per number, plus a new list of 2 million items. About ten times slower than min() + max().
  • min() + max() are O(n) each: two passes, but written in C.
  • The Python loop is also O(n), and does only one pass, yet it's slower than min() + max(): each Python loop turn costs much more than a step inside a C built-in.
  • Big-O describes how time grows, not exact seconds. Two O(n) solutions can differ by a constant factor. Write the loop to show the idea; use the built-ins in real code. (min() and max() also take key= and default=.)

Follow-up: fewer comparisons, in pairs

One by one, each number is compared with lo and with hi: about 2 comparisons per number. Taking the numbers in pairs, compare the two with each other first, then only the smaller with lo and only the bigger with hi: 3 comparisons for every 2 numbers.

def min_max_pairs(nums):
    lo = hi = nums[0]
    comparisons = 0
    for i in range(1, len(nums) - 1, 2):
        a, b = nums[i], nums[i + 1]
        if a > b:
            a, b = b, a                  # now a <= b
        comparisons += 3
        lo = min(lo, a)                  # small one vs lo
        hi = max(hi, b)                  # big one vs hi
    if len(nums) % 2 == 0:               # one left over
        lo, hi = min(lo, nums[-1]), max(hi, nums[-1])
        comparisons += 2
    return lo, hi, comparisons

nums = [7, 2, 9, 4, 11, 3, 8, 1, 6, 5]
print(min_max_pairs(nums), "vs", 2 * (len(nums) - 1), "one by one")

Output:

(1, 11, 14) vs 18 one by one

About 1.5 n comparisons instead of 2 n. Still O(n), a smaller constant; in Python the C built-ins still win on time, but the interviewer is checking that you can count operations.

Follow-up: which day was it?

week = [("Mon", -3), ("Tue", -7), ("Wed", -1), ("Thu", -9), ("Fri", -4)]

coldest = min(week, key=lambda day: day[1])
warmest = max(week, key=lambda day: day[1])
print("coldest:", coldest, " warmest:", warmest)

temps = [t for _, t in week]
i = temps.index(min(temps))
print("coldest day index:", i, week[i][0])

Output:

coldest: ('Thu', -9)  warmest: ('Wed', -1)
coldest day index: 3 Thu
  • min(items, key=...) / max(items, key=...) compare by the key (here the temperature, day[1]) and return the whole item, so you also get the day (the same key= as sorted in episode 17).
  • temps.index(min(temps)) finds the position in a plain list of numbers: two passes, still O(n). On a tie, both min and index return the first one.

Common mistakes (and what you really see)

Mistake What you see Why Fix
best = 0 -1 list gives 0 0 is a fake element best = nums[0], or max()
max([]) ValueError: max() iterable argument is empty no elements max(nums, default=None) or check first
sorted(nums)[-2] [5, 5, 3] → 5; IndexError: list index out of range ties; one element one pass, or a set with a length check
elif x > second [5, 5, 3] → 5, [7] → -inf a duplicate of first takes silver elif first > x > second, return None
sorted() just for min and max ~10× slower on 2,000,000 numbers O(n log n) + a new list min(), max(): O(n)
assuming fewer passes = faster in Python the one-pass loop loses to min() + max() C built-ins vs Python bytecode measure with time.perf_counter()

Your turn: the third largest distinct value (solution)

[12, 35, 1, 10, 34, 1] → 12, [5, 5, 3] → None.

Solution

Three variables, each new value shifting the smaller ones down; chained comparisons skip duplicates.

import heapq

def third_largest(nums):
    a = b = c = float("-inf")
    for x in nums:
        if x > a:
            a, b, c = x, a, b
        elif a > x > b:
            b, c = x, b
        elif b > x > c:
            c = x
    return None if c == float("-inf") else c

for nums in [[12, 35, 1, 10, 34, 1], [5, 5, 3], [3, 2, 1], []]:
    print(nums, third_largest(nums), heapq.nlargest(3, set(nums)))

Output:

[12, 35, 1, 10, 34, 1] 12 [35, 34, 12]
[5, 5, 3] None [5, 3]
[3, 2, 1] 1 [3, 2, 1]
[] None []

heapq.nlargest(k, iterable) returns the k largest values in O(n log k) time; with set() they are distinct. For the k-th largest, take the last item of that list if it has k items.

Practice questions (with solutions)

1. Smallest and second smallest in one pass.

Solution
def two_smallest(nums):
    s1 = s2 = float("inf")
    for x in nums:
        if x < s1:
            s1, s2 = x, s1
        elif s1 < x < s2:
            s2 = x
    fix = lambda v: None if v == float("inf") else v
    return fix(s1), fix(s2)

print(two_smallest([12, 35, 1, 10, 34, 1]), two_smallest([4]))

Output:

(1, 10) (4, None)

2. The index of the largest element (the first one if tied).

Solution
nums = [3, 9, 4, 9]
print(nums.index(max(nums)), max(range(len(nums)), key=nums.__getitem__))

Output:

1 1

nums.index(max(nums)) makes two passes; max(range(len(nums)), key=...) compares indexes by their values in one pass. Both return the first index on a tie.

3. The largest value in each row of a table.

Solution
grid = [[3, 8, 1], [-2, -5, -1], [7, 7, 0]]
print([max(row) for row in grid])

Output:

[8, -1, 7]

Quick quiz

What does this print?

nums = [4, 8, 8, 2]
a = sorted(nums)[-2]
b = sorted(set(nums))[-2]
c = max(nums[:0], default=-1)
print(a, b, c)

(A) 8 4 -1 (B) 4 4 -1 (C) 8 8 2 (D) 8 4 ValueError

Answer

(A). sorted(nums) is [2, 4, 8, 8], so [-2] is the other 8. The set removes the duplicate: [2, 4, 8] → 4. nums[:0] is an empty list, so max returns the default, −1.

8 4 -1

Interview questions

  1. Why is best = 0 wrong for the largest element? It invents an element; all-negative lists return 0. Start from nums[0] or use max().
  2. What does max([]) do? Raises ValueError; pass default= to return a value instead.
  3. What does "second largest" mean with duplicates? Usually the largest value strictly smaller than the maximum; clarify with the interviewer.
  4. Second largest in one pass? Track first and second from -inf; update with x > first, else first > x > second.
  5. What is float("-inf")? Negative infinity: smaller than every number, a safe initial value for a maximum.
  6. What is a chained comparison? a > b > c means a > b and b > c, evaluated left to right, with b computed once.
  7. Complexity of sorted()? O(n log n) time, O(n) extra space (it returns a new list; list.sort() sorts in place).
  8. Why can a one-pass Python loop be slower than two built-in passes? Built-ins run in C; same Big-O, smaller constant factor.
  9. How do you get the k largest values efficiently? heapq.nlargest(k, nums), O(n log k).
  10. How would you find the min and max with fewer than 2n comparisons? Compare elements in pairs: about 1.5 n comparisons.

Glossary

Term Meaning Example
Largest / maximum The biggest element max([3, 9, 4]) → 9
Empty list A list with no elements []
default= What max/min return for an empty input max([], default=None) → None
ValueError Raised for a value that can't be used max([])
IndexError Raised for an index outside the list [7][-2]
Distinct Different values (duplicates counted once) set([5, 5, 3]) → {3, 5}
float("-inf") Minus infinity, smaller than every number initial first
Chained comparison a > b > c = a > b and b > c first > x > second
Tuple assignment Update several variables at once first, second = x, first
sorted() Returns a new sorted list sorted([3, 1, 2]) → [1, 2, 3]
set() Unordered collection without duplicates set([4, 8, 8])
random.seed() Makes random numbers repeatable random.seed(1)
time.perf_counter() High-resolution stopwatch timing sorted()
O(n log n) Sorting-level growth sorted()
Constant factor The fixed cost per step that Big-O ignores C built-ins vs a Python loop
heapq.nlargest The k largest items, O(n log k) heapq.nlargest(3, nums)
Stream Values that arrive one at a time sensor readings

Summary

  • Largest: start from a real element (nums[0], max()), never from 0; decide what an empty list returns (default=).
  • Second largest = the next distinct value: one pass from -inf with first > x > second, returning None when there isn't one; or sorted(set(nums)) with a length check (shorter, but O(n log n) time and O(n) space).
  • Min and max: sorted() is O(n log n) and builds a new list; min()/max() are O(n). Same Big-O can still mean different real times: measure.

Next episode: List questions II: reverse in place, rotate by k (k larger than n), remove duplicates while keeping the order.