Python Data Structures and Algorithms Questions

Core Python data structure and algorithm knowledge used for manipulating collections and solving common data processing problems. Candidates should know built in types such as lists, dictionaries, sets, and tuples and their performance characteristics; be able to implement and reason about searching, sorting, counting, deduplication, and frequency analysis tasks; and choose appropriate algorithms and data structures for time and space efficiency. Familiarity with Python standard library utilities such as collections.Counter, defaultdict, deque, and heapq is expected, as is writing Pythonic, clear code that handles edge cases. Questions may include algorithmic trade offs, complexity analysis, and applying these techniques to practical data manipulation problems where custom logic is required beyond what pandas or NumPy provide.

MediumTechnical

20 practiced

Explain how Python's sort (Timsort) achieves stability and good performance on partially ordered data. Give examples of when stability is required in multi-key sorting in a data-science workflow and demonstrate with Python code how to sort by multiple keys preserving stability.

Sample Answer

Timsort achieves both stability and excellent practical speed by exploiting existing order in real data. It scans the array to find monotonic runs (ascending or descending), reverses descending runs, then merges runs using a stable merge routine. The merge decisions use run lengths and a "galloping" mode to accelerate merging when one run outpaces the other. Because merges never reorder equal elements from different runs, the algorithm is stable — equal keys preserve their original relative order — and by leveraging runs it's very fast on partially ordered data (near-linear behavior).

Why stability matters in data-science multi-key sorting- When you need to sort by multiple keys in stages (e.g., sort by timestamp then by score) and want ties on the later key to preserve an earlier ordering (like chronological order).- When preserving input or group-relative order matters (stable grouping, reproducible sampling, stable feature pipelines).- Example: you want top product per user by score but, for ties, keep the earlier purchase first.

Examples in Python

1) Using stability by sorting from least-significant to most-significant key:

python

records = [
    {"user":"A","time":"2023-01-02","score":90},
    {"user":"A","time":"2023-01-01","score":90},
    {"user":"B","time":"2023-01-01","score":95},
]

# First sort by the least significant key (time), then by score (most significant).
records.sort(key=lambda r: r["time"])      # stable: preserves original order for equal times
records.sort(key=lambda r: r["score"], reverse=True)
# Now records are sorted by score desc; ties keep earlier-time order.

2) Using a composite key (single-pass, also stable):

python

records.sort(key=lambda r: (-r["score"], r["time"]))

Notes:- Multi-pass (LSB-first) relies on stability to compose sorts; composite-key is simpler and equivalent when keys fit into one comparator.- For large datasets (pandas), pandas.sort_values uses a stable sort by default (since recent versions) — you can specify columns and ascending per-column:

python

import pandas as pd
df.sort_values(["score","time"], ascending=[False,True], kind="mergesort")

Use kind="mergesort" to force a stable algorithm if needed.

MediumTechnical

16 practiced

Given a sorted list of unique timestamps and a window length w seconds, implement in Python an efficient function that returns the maximum number of events in any sliding window of length w. Aim for O(n) time using a two-pointer approach or deque and explain the complexity.

Sample Answer

To solve this, use a two-pointer sliding window: maintain left and right indices into the sorted timestamps. For each right, advance left while the window length exceeds w, and track the max window size. This is O(n) because each pointer moves forward at most n steps.

python

def max_events_in_window(timestamps, w):
    """
    timestamps: sorted list of unique integers/floats (seconds)
    w: window length in seconds (inclusive length)
    Returns max number of events within any window of length w.
    """
    n = len(timestamps)
    if n == 0 or w < 0:
        return 0

    left = 0
    max_count = 0

    for right in range(n):
        # shrink from left while window is longer than w
        while timestamps[right] - timestamps[left] > w:
            left += 1
        # current window is [left..right] inclusive
        max_count = max(max_count, right - left + 1)

    return max_count

Key points:- Works in O(n) time and O(1) extra space.- Correct because timestamps are sorted and each index only moves forward.Edge cases:- Empty list, negative w, large gaps, identical timestamps (unique constraint handled). Alternative: use deque to store indices, but two-pointer is simpler and more efficient here.

MediumTechnical

16 practiced

Write Python code to merge overlapping intervals given as a list of [start, end] pairs. Your solution should run in O(n log n) time and handle edge cases like touching intervals, single-point intervals, and invalid ranges. Explain correctness.

Sample Answer

Approach: Sort intervals by start (O(n log n)), normalize invalid ranges (swap if start > end), then scan and merge overlapping or touching intervals (treat end >= next_start as overlap). This yields O(n log n) time and O(n) extra space.

python

from typing import List

def merge_intervals(intervals: List[List[float]]) -> List[List[float]]:
    """
    Merge overlapping or touching intervals.
    - Normalizes intervals where start > end by swapping.
    - Treats touching intervals (a.end == b.start) as overlapping and merges them.
    Returns merged, sorted, non-overlapping intervals.
    """
    if not intervals:
        return []

    # Normalize and filter invalid (e.g., None) entries
    normalized = []
    for iv in intervals:
        if not iv or len(iv) < 2:
            continue
        a, b = iv[0], iv[1]
        if a is None or b is None:
            continue
        if a > b:
            a, b = b, a  # normalize invalid ranges by swapping
        normalized.append([a, b])

    if not normalized:
        return []

    # Sort by start
    normalized.sort(key=lambda x: x[0])

    merged = [normalized[0]]
    for cur_start, cur_end in normalized[1:]:
        last_start, last_end = merged[-1]
        if cur_start <= last_end:  # overlap or touching (<=)
            merged[-1][1] = max(last_end, cur_end)
        else:
            merged.append([cur_start, cur_end])

    return merged

Correctness:- Sorting ensures we only need one linear pass to merge adjacent overlaps.- Normalization guarantees valid ranges; merging condition cur_start <= last_end handles touching and single-point intervals.Time complexity: O(n log n) due to sort. Space: O(n) for normalized/merged lists.Edge cases handled: empty input, malformed intervals, single-point intervals (e.g., [2,2]), touching intervals ([1,2] & [2,3]) and intervals given in reverse order ([5,1]).

EasyTechnical

19 practiced

You have a list of strings representing event types. Using collections.Counter in Python 3, write code to produce the top 5 most common events and explain its time complexity. When is Counter.most_common more convenient than manual heap approaches for top-k frequency extraction?

Sample Answer

To get the top-5 most common events from a list of event-type strings, use collections.Counter which counts in one pass and provides a convenient most_common(k) API.

python

from collections import Counter

events = [
    "click", "view", "purchase", "click", "view", "click",
    "signup", "purchase", "view", "view", "signup", "click"
]

# Count frequencies (O(n) time)
counter = Counter(events)

# Get top-5 most common (if fewer than 5 unique keys, returns all)
top5 = counter.most_common(5)

print(top5)  # [('click', 4), ('view', 4), ('purchase', 2), ('signup', 2)]

Key points and complexity:- Building Counter: single pass over list, O(n) time, O(u) additional space where u = number of unique event types.- most_common(k): implemented in C; for small k it uses selection algorithms and is typically O(u + k log u) or effectively O(u) in practice; overall dominated by counting O(n).- Total: O(n) time and O(u) space.

When most_common is more convenient than manual heaps:- You want concise, readable code and acceptable memory for the unique-key set.- u (unique keys) is moderate (fits in memory) and you need top-k for exploratory analysis or reporting.- It’s implemented and optimized in C (fast) and handles ties deterministically by first-seen order.Use a heap (heapq.nlargest or manual min-heap) when u is huge and you must strictly limit memory usage tracking only k items, or when streaming and you cannot store all unique keys.

HardTechnical

24 practiced

Given a Python list of potentially millions of small lists (e.g., feature vectors), design a memory-efficient representation and access pattern in pure Python (no pandas/numpy) to reduce overhead. Discuss the trade-offs between storing as list-of-lists, flat list with offsets, and using array.array or memoryview structures.

Sample Answer

To store millions of small feature vectors in pure Python with low memory overhead, prefer a flat contiguous representation plus offsets rather than list-of-lists. Below I explain three options, trade-offs, and give a compact example.

Approaches and trade-offs- List-of-lists (naive) - Pros: simple, direct indexing, flexible lengths. - Cons: huge overhead: each inner list is a PyObject with pointer array; memory and GC cost explode for millions of small lists.

- Flat list with offsets (pure Python) - Representation: one flat list of values and a parallel list/array of start indices (or lengths). - Pros: drastically fewer Python objects; simple to slice using start/end indices; fast iteration with contiguous memory of Python objects. - Cons: still stores Python objects for values (ints/floats) — per-value overhead remains; occasional reallocation when appending.

- array.array / bytearray + memoryview - Representation: store numeric data in array.array('f') or array('d') or in a single bytearray; offsets in array('I') or list. - Pros: compact C-level storage (no per-value PyObject), very memory efficient, fast numeric iteration via memoryview; good for fixed numeric types. - Cons: fixed dtype required; random insertions/variable-length writes are trickier; converting to/from Python floats has cost but storage is minimal.

Sample pattern: flat array.array with offsets

python

from array import array

# flatten feature vectors to float array and store offsets
vecs = [[0.1,0.2],[0.3,0.4,0.5],[0.6]]
data = array('d')    # double precision floats
offsets = array('I') # unsigned ints for start positions
lengths = array('I') # optional lengths

pos = 0
for v in vecs:
    offsets.append(pos)
    lengths.append(len(v))
    data.extend(v)
    pos += len(v)
# Access i-th vector:
def get_vector(i):
    s = offsets[i]; l = lengths[i]
    return data[s:s+l]           # returns array('d') slice (copy in CPython pre-3.11)

Access patterns and best practices- Sequential streaming: iterate with offsets and memoryview for lowest overhead.- Random access: offsets enable O(1) locate, but slicing array may copy; use memoryview(data) and slice the memoryview to avoid copies where supported.- Mutability: appending is efficient; inserting in middle requires shifting.- Dtype choice: pick 'f' (float32) vs 'd' (float64) based on precision vs memory.

Performance notes- Memory: array.array stores raw C doubles (8 bytes each) vs Python float object (~24+ bytes).- CPU: converting between Python objects and C arrays has cost when creating or reading; benchmark for your workload.- GC: fewer Python objects reduces GC overhead and improves cache locality.

When to use which- If vectors are numeric and dtype-fixed: use array.array or bytearray+memoryview.- If vectors are heterogeneous or need Python objects: use flat list + offsets to reduce per-list overhead.- If you need vectorized operations: consider moving to numpy (outside constraint) or to C extensions.

Edge cases- Very large total length: ensure offsets dtype can hold indices (use array('Q') for >4GB).- Mixed-length huge variability: consider storing lengths and compressing small vectors into one big buffer to reduce fragmentation.

This pattern yields orders-of-magnitude memory savings vs list-of-lists while keeping O(1) indexing and efficient iteration for data-science workflows.

Unlock Full Question Bank

Get access to hundreds of Python Data Structures and Algorithms interview questions and detailed answers.

Join thousands of developers preparing for their dream job.