# Every Trace

> It is in there somewhere. Where exactly?

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

Domain: Python · Difficulty: medium · Seniority: L3

## Problem

A monitoring feed records one reading per slot. You're auditing for a specific value: return the slots where that value appears, earliest first.

## Example 1

Input:

```
readings = [10,20,30,20,40,20], target = 20
```

Output:

```
[1,3,5]
```

## Example 2

Input:

```
readings = [1,2,3,4,5], target = 3
```

Output:

```
[2]
```

## Worked solution and explanation

### What this really is

Under the audit-log costume this is just 'give me every index where the value matches', and the tell is that people reach for `list.index` out of habit. It hands back the FIRST hit and nothing else, so the moment the target repeats you have silently dropped positions; call it in a loop to find the rest and you re-scan from the front each time, turning an O(n) walk into O(n^2). The skill being probed is walking position and value together and collecting as you go, plus not forgetting that 'nothing matched' is a real, empty answer.

---

### Break down the requirements

#### Step 1: Walk with the index in hand

Use `enumerate` (or `range(len(readings))`) so each step gives you both the position and the value at once.

#### Step 2: Keep every position that matches

Compare each reading to the target with `==` and append the index when they match. Because you scan left to right, the collected indices are already ascending.

---

### The solution

**Single-pass scan with equality check**

```python
def index_of_all(readings, target):
    result = []
    for i, value in enumerate(readings):
        if value == target:
            result.append(i)
    return result
```

> **Time and Space Complexity**
>
> **Time:** O(n) where n is the feed length. Every reading is checked once.
> 
> **Space:** O(k) where k is the number of matching positions.

> **Interviewers watch for**
>
> Comparing with `==`, not `is`. The `is` operator checks identity, so two equal-but-distinct objects would slip through and you'd miss real matches.

> **Common pitfall**
>
> Calling `list.index()` in a loop to find the next match. It restarts from the front every time, so a feed full of repeats becomes O(n^2). One left-to-right pass gives you all of them in order for free.

---

## Common follow-up questions

- What if the feed is sorted and you only need the range of matching positions? _(Tests binary search for first and last occurrence using bisect.)_
- How would you return the positions of every reading matching a predicate instead of a fixed value? _(Tests generalizing from equality to a callable filter function.)_
- What if the feed is enormous and you want to stream positions one at a time? _(Tests a generator-based approach that yields positions lazily.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/every_trace)
- [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). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.