---
# System prepended metadata

title: Technical interview questions

---

# Technical interview questions

## Basic code understanding (stolen from Lorenzo)

```python
first_word = ["a", "d", "x", "y", "z"]
second_word = ["a", "b", "c", "d", "a"]


for first_letter in first_word:
    for second_letter in second_word:
        if first_letter == second_letter:
            print(first_letter) 
            break
```

```python
output = []
for second_letter in second_word:
    if second_letter not in output:
        output.append(second_letter)
for first_letter in first_word:
    if first_letter in output:
        print(first_letter)
```

## More open-ended (stolen from Sekhar)

You have a list of `N` floating point numbers.

Find the `k` smallest.

For example if the input is `[-10.3, 100.4, 200.0, 0, 5.0]` and `k=3` then the output should be `[-10.3, 0, 5.0]`.

### Simplest solution

Loop over the array k times and extract the smallest number in each pass. `O(Nk)` complexity.

### Semi-ideal solution 

1. Create a min-heap with `N` elements. `O(N)`
2. Pop the root `k` times. `O(klogN)` to get the `k` smallest values

Overall time complexity is `O(N+klogN)`

This is similar to sorting an array and removing the first or last `k` values. Sorting an array of size `N` has `NlogN` complexity.

### Ideal solution

1. Create a max-heap with first `k` elements of input. `O(k)`
2. Iterate over remaining `N-k` elements. `O(N-k)`
3. If any of the `N-k` elements are smaller than the root then replace the root with it and re-construct the heap `O(logk)`

Overall time complexity is `O(k + (N-k)logk)`
