The Tail Finder

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L3
Asked in
Basis

Problem

lst holds a linked list's node values in order from head to tail, and what comes back is the value stored at the final node. The answer must be computed tail-recursively, so nothing is left to do once each recursive call returns.

Navigate to the end of a linked list using recursion.

Example 1

Input:

lst = [1,2,3,4,5]

Output:

5

Example 2

Input:

lst = []

Output:

null

Worked solution and explanation

What this really is

This is a base-case discipline test wearing a linked-list costume. Anyone can peel the head off with lst[1:] and recurse; the interviewer is watching how you decide the walk is over. The trap is asking the element instead of the list: lst[-1] or None, if not lst[0], if not result. Each reads naturally and each turns a final value of 0 or '' into None, so [3, 0] reports an empty tail when a real last node is sitting right there.

The empty example passes either way, which is exactly why the bug survives a quick check. Emptiness is a question about the list, never about a value.

Building it

Step 1: Guard the empty list by its size

if not lst is safe here because it asks whether the list has anything in it, not whether an element is falsy. Return None: there is no final node to report.

Step 2: Stop when one node is left

len(lst) == 1 means you are standing on the tail. Return lst[0] untouched, whatever it holds. Do not wrap it in or None; that is the trap in its smallest form.

Step 3: Hand the rest to the next call

Recurse on lst[1:] and return that result directly. Nothing happens after the call comes back, which is what makes it tail position: each frame has finished its work before delegating.

Tail-recursive last value
def find_tail(lst: list):
    if not lst:
        return None
    if len(lst) == 1:
        return lst[0]
    result = find_tail(lst[1:])
    return result
Asks the element
return lst[-1] or None or a stop condition like if not lst[0]. On [3, 0] the 0 is falsy, so the answer silently becomes None.
Asks the list
if not lst and len(lst) == 1 only look at how many nodes remain. [3, 0] returns 0, ['eu-west', ''] returns '', and [] returns None.
The shortcut that looks fine
def find_tail(lst: list):
    if not lst:
        return None
    return lst[-1] or None

Passes [1, 2, 3, 4, 5] and [], fails on any falsy tail.

Common follow-up questions