Upstart·Data Scientist·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Coding screen for a Data Scientist role at Upstart, two Python questions both centered on factorials. Pretty math-heavy for a DS interview, felt more like a software engineering warmup than anything ML-related.

Questions Asked (2)

Implement a factorial function in Python. Walk through at least two approaches and discuss their tradeoffs, including things like recursion limits and handling large numbers.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Started with recursion because it felt clean, then they pushed me on what happens with large n.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements (e.g., input constraints, expected output type, performance needs) and then present two distinct implementations: an iterative loop and a recursive function. Compare them on readability, performance, memory usage, recursion depth limits, and handling of large numbers, noting Python's arbitrary-precision integers.

Pro tip: Mention that Python's recursion limit can be adjusted but is generally not advisable for factorial due to stack overflow risk; instead, highlight that iterative or math.factorial is preferred for large n. Also, note that factorial grows extremely fast, so for very large n, you might need to consider memory and time constraints.

1. Clarify requirements

Ask about input constraints (e.g., non-negative integer, maximum value), expected output type (int, float, string), and performance considerations. This shows you think about edge cases and practical use.

2. Present iterative approach

Write a simple loop that multiplies from 1 to n. Discuss its O(n) time complexity, O(1) space, and no recursion limit issues.

3. Present recursive approach

Write a recursive function with base case n=0 or 1. Discuss its O(n) time and O(n) space due to call stack, and the risk of hitting Python's recursion limit (default ~1000).

4. Compare tradeoffs

Contrast readability, performance, memory usage, and scalability. Mention that recursion is elegant but impractical for large n; iteration is more robust. Also note Python's arbitrary-precision integers handle large results but may be slow.

5. Discuss optimizations and alternatives

Mention using math.factorial (C implementation) for speed, memoization for repeated calls, or tail recursion (not optimized in Python). Also consider iterative with early termination if n is huge and exact value not needed.

Key Points to Mention

Python's recursion limit (sys.getrecursionlimit()) and how to adjust it, but caution against it.
Time and space complexity of both approaches: O(n) time, O(1) vs O(n) space.
Handling large numbers: Python's int is arbitrary precision, so no overflow, but factorial grows fast and may consume memory.
Edge cases: n=0 (factorial is 1), negative input (raise ValueError).
Alternative: math.factorial for performance and simplicity.
Memoization for repeated factorial calls in dynamic programming contexts.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Given n, how many trailing zeros does n factorial have? Write an efficient solution without computing the factorial directly, and state the time complexity.

Algorithms & Data Structures

Author's notes

This one I actually liked.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Explain that trailing zeros come from factors of 10, i.e., pairs of 2 and 5, and since 2s are more abundant, count the factors of 5. Use Legendre's formula: sum of floor(n/5^k) for k=1,2,... until 5^k > n. This gives an O(log n) time and O(1) space solution.

Pro tip: Mention that this is a classic problem and that the same technique generalizes to counting prime factors in n!; also note that for very large n, the sum can be computed iteratively by dividing n by 5 repeatedly, which is efficient and avoids overflow.

1. Understand the source of trailing zeros

Trailing zeros in n! are produced by factors of 10, which come from pairs of 2 and 5. Since multiples of 2 are more frequent, the number of trailing zeros equals the number of times 5 appears as a factor in n!.

2. Derive the counting method

Count multiples of 5, 25, 125, etc., because numbers like 25 contribute two factors of 5. Use Legendre's formula: sum_{k=1}^{∞} floor(n / 5^k).

3. Implement efficiently

Iteratively divide n by 5 and accumulate the quotient: while n > 0, n = n // 5, count += n. This avoids computing the factorial and runs in O(log_5 n) time.

4. State complexity and edge cases

Time complexity is O(log n) (base 5), space O(1). Handle n < 5 (returns 0) and large n without overflow.

Key Points to Mention

Trailing zeros = number of factors of 10 = min(count of 2s, count of 5s) = count of 5s.
Legendre's formula: sum of floor(n/5^k) for k=1,2,...
Iterative division by 5 is efficient and avoids computing n!.
Time complexity: O(log n) base 5; space complexity: O(1).
Edge cases: n=0, n<5, and very large n.
Generalization: counting any prime factor p in n! uses sum floor(n/p^k).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.