Coding Interviews

Source: Concepts adapted from Ace the Data Science Interview — Chapter 9 (“Coding”) by Kevin Huo & Nick Singh. Rewritten in original wording for this course.

Data scientists write code constantly — wrangling frames, calling APIs, shipping pipelines. Interviews therefore often revisit data structures and algorithms: lists, trees, graphs, recursion, dynamic programming, and Big-O for time and space. Even if your day job is notebooks, shared fluency with engineers matters.

This lesson covers how coding screens usually run and how to talk about complexity. Later lessons drill data structures and algorithms.

How coding rounds are run

Remote screens often use HackerRank, Codility, or CoderPad; onsites may use a whiteboard. The same playbook applies either way.

After you hear the prompt

1. Restate the problem and confirm I/O types, ranges, and whether inputs are well-formed.
2. Walk a small example end-to-end before writing code.
3. Only then start designing a solution.

While designing

• Sketch a correct brute force first and say why it is slow.
• Improve it if you can, and explain the trade-off (time vs space, simplicity vs optimality).
• Code only after you and the interviewer agree on an approach.

While coding

• Narrate as you go; use real language (not vague pseudocode) unless they ask for high-level only.
• Prefer clear names and structure; offer to fill in deferred helpers later.

After coding

• Hunt edge cases, then dry-run tests.
• Expect follow-ups: complexity, cleanup, “do it in-place,” “no recursion,” or a harder variant.

Big-O in interviews

Asymptotic analysis describes how time and memory grow as input size $N \to \infty$. Industry interviews usually mean worst-case upper bounds when they say “Big-O.”

Common classes (fast → slow for typical array problems):

Class	Name	Typical example
$O(1)$	Constant	Index into an array
$O(\log N)$	Logarithmic	Binary search on sorted data
$O(N)$	Linear	Single pass
$O(N \log N)$	Log-linear	Mergesort
$O(N^2)$	Quadratic	Nested loops over pairs
$O(2^N)$	Exponential	Naïve recursion over binary choices
$O(N!)$	Factorial	All permutations

Space works the same way: copying an $N$-element array costs $O(N)$ extra space; an $N \times N$ adjacency matrix costs $O(N^2)$.

Binary search sketch: each step halves the remaining range → $O(\log N)$ time. The input array itself is $O(N)$ space; the algorithm needs only a few indices → $O(1)$ auxiliary space.

Complexity of simple ML algorithms

Interviewers sometimes ask you to reason about training cost.

• Naive Bayes (roughly): for $n$ points, $d$ features, $k$ classes, counting co-occurrences is about $O(nkd)$ time; storing per-class feature stats is about $O(kd)$ space.
• Logistic regression (high level): each update touches a $d$-dimensional weight vector; space for weights is $O(d)$. Exact training cost depends on iterations and solver, but the “per-example multiply by $\beta$” intuition is $O(d)$ work per point.

Use these as order-of-magnitude stories, not as claims that every library implementation matches the textbook loop.

Quiz

Interview process & Big-O

1 / 4

Right after receiving a coding prompt, the best first move is usually…

Pick an answer to see if you are right.

Practice: binary search closest index

Implement a binary search that returns the index of k if present, otherwise the index of the closest value (ties: prefer the leftmost among equally close).

Next: Data structures.