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.

Link to solution →

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.

Link to solution →

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.

Link to solution →

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.

Link to solution →

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



Tagged: #interviewcake, #algorithm