# The Tail Finder

> Navigate to the end of a linked list using recursion.

Canonical URL: <https://datadriven.io/problems/the_tail_finder>

Domain: Python · Difficulty: medium · Seniority: L3

## Problem

Given a list representing a linked list (nodes in order), return the value of the last node. Return None if the list is empty. Implement tail-recursively.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **recursion** fundamentals. Finding the last element of a list using tail recursion probes whether a candidate understands base cases, recursive step design, and the concept of tail-call optimization.

---

### Break down the requirements

#### Step 1: Handle the empty list base case

If the list is empty, return None.

#### Step 2: Handle the single-element base case

If the list has one element, that element is the tail.

#### Step 3: Recurse on the rest of the list

Pass the sublist starting from index 1 to the recursive call.

---

### The solution

**Tail-recursive last element search**

```python
def find_tail(lst: list):
    if not lst:
        return None
    if len(lst) == 1:
        return lst[0]
    result = find_tail(lst[1:])
    return result
```

> **Time and Space Complexity**
>
> **Time:** O(n) for n recursive calls, each creating a slice.
> 
> **Space:** O(n^2) due to list slicing creating copies. Using an index parameter would reduce to O(n) space.

> **Interviewers Watch For**
>
> Awareness that Python does not optimize tail calls. The recursive approach is instructive but `lst[-1]` is the idiomatic Python solution. Mentioning this shows practical judgment.

> **Common Pitfall**
>
> List slicing `lst[1:]` creates a new list each time, using O(n) memory per call. For large lists, pass an index instead to avoid this overhead.

---

## Common follow-up questions

- How would you avoid the O(n^2) space from slicing? _(Tests passing an index parameter: `find_tail(lst, idx=0)`.)_
- Does Python support tail call optimization? _(Tests knowledge that CPython does not, unlike Scheme or certain functional languages.)_
- When would recursion be preferred over iteration for list operations? _(Tests understanding that tree structures benefit from recursion while linear structures rarely do.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_tail_finder)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.