Given an unsorted array of n elements and a number k, write a function that determines whether k is present in the array.

What the interviewer wants to learn

  • Your ability to translate a simple problem statement into correct, readable code.
  • Whether you consider edge cases (empty array, null inputs, duplicate values).
  • Your sense of algorithmic efficiency and trade‑offs for a linear‑time solution.
  • How clearly you can explain your thought process and justify choices.

How to structure your answer

1. **Restate the problem** in your own words to confirm understanding.

2. **Identify constraints** (size of array, value range, expected time/space).

3. **Choose an algorithm** (here a linear scan is optimal).

4. **Explain the steps** of the algorithm, mentioning early exit when the element is found.

5. **State the complexity** (time O(n), space O(1)).

6. **Present clean code** and walk through a tiny example.

7. **Cover edge cases** and how the code handles them.

Example answer

“Sure, the task is to check if a given integer k appears anywhere in an unsorted array of length n. Since the array isn’t sorted, we can’t do better than looking at each element until we either find k or reach the end. That gives us a linear‑time solution, O(n), with constant extra space.

My approach is simple:

  • Loop through the array.
  • If the current element equals k, return true immediately.
  • If we finish the loop without a match, return false.

The code looks like this:

def contains(arr, k):
    if arr is None:          # guard against a null reference
        return False
    for x in arr:
        if x == k:
            return True
    return False

For example, with `arr = [4, 1, 7, 3]` and `k = 7`, the loop checks 4, then 1, then 7 and returns `True` right away. If `k` were 5, the loop would finish and return `False`. The algorithm runs in O(n) time and uses O(1) extra memory, which is optimal for an unsorted list.

Mistakes to avoid

  • **Assuming sorting is needed** – sorting would add O(n log n) time unnecessarily.
  • **Not handling null or empty arrays** – the function should return `False` gracefully.
  • **Returning the index instead of a boolean** when the question asks only whether the element exists.
  • **Missing early exit** – continue scanning even after finding `k` wastes time.
  • **Using extra data structures** (like a hash set) without justification; they increase space usage without improving complexity for a single‑lookup task.

More system design questions