# Interview Cake's Greedy algorithms

Apple stocks, Highest product of three, Product of all other numbers, In-place shuffle

### 1. Given a list of stock prices (integer) in chronological order, return the max profit from buying at earlier time and selling at later time.

Example:

```
- Input: []int{10, 7, 5, 8, 11, 9}
Output: 6, because one can buy at 5 and sell at 11
```

Approach:

```
- Use a greedy approach to keep track of the minimum price and the maximum
profit for each value while iterating through the list.
```

Cost:

```
- O(n) time, O(1) space.
```

### 2. Given a list of integers, return the highest product of three numbers.

Example:

```
- Input: []int{-10, -10, 1, 3, 2}
Output: 300, because -10.-10.3 gives the highest product
```

Approach:

```
- Use a greedy approach to keep track of the current highest, current lowest,
highest of three, highest of two and lowest of two for every value as we
iterate through the list.
```

Cost:

```
- O(n) time, O(1) space.
```

### 3. Given a list of integers, return a corresponding list where every index holds the product of every other values except the value in that index. And, you can’t use division!

Example:

```
- Input: []int{1, 7, 3, 4}
Output: []int{84, 12, 28, 21}
```

Approach:

```
- Iterate through the list and at each step, calculate the product of all
the integers before each index and the product of all the integers after
each index.
```

Cost:

```
- O(n) time, O(n) space.
```

### 4. Given a list of integers, shuffle its location in-place.

Example:

```
- Input: []int{1, 2, 3, 4, 5}
Output: []int{2, 1, 4, 3, 5}
```

Approach:

```
- Iterate through the list, swap current value with a value in a randomized
index that is between the current and last index.
```

Cost:

```
- O(n) time, O(1) space.
```

For more coding problems, please visit https://github.com/hoanhan101/algo.

Tagged: #interviewcake, #algorithm