about summary refs log tree commit diff
path: root/scratch/deepmind/part_two/todo.org
diff options
context:
space:
mode:
authorWilliam Carroll <wpcarro@gmail.com>2020-03-02T16·45+0000
committerWilliam Carroll <wpcarro@gmail.com>2020-03-02T16·45+0000
commit549e56186bcb152560e362d19c7ab291a95446ba (patch)
treebfcef26a530bdf7473d3e33d2975b9776a67470e /scratch/deepmind/part_two/todo.org
parent22d70b52c9780e7de7f9c58da33e94bae9119b89 (diff)
Solve InterviewCake's product-of-other-numbers
This problem challenged me: without using division, write a function that maps a
list of integers into a list of the product of every integer in the list except
for the integer at that index.

This was another greedy algorithm. The take-away is to first solve the problem
using brute force; this yields an algorithm with O(n*(n-1)) time
complexity. Instead of a quadratic time complexity, a linear time complexity can
be achieved my iterating over the list of integers twice:
1. Compute the products of every number to the left of the current number.
2. Compute the products of every number to the right of the current number.

Finally, iterate over each of these and compute lhs * rhs. Even though I've
solved this problem before, I used InterviewCake's hints because I was stuck
without them.

I should revisit this problem in a few weeks.
Diffstat (limited to 'scratch/deepmind/part_two/todo.org')
-rw-r--r--scratch/deepmind/part_two/todo.org2
1 files changed, 1 insertions, 1 deletions
diff --git a/scratch/deepmind/part_two/todo.org b/scratch/deepmind/part_two/todo.org
index ed3cc56277b9..078613611618 100644
--- a/scratch/deepmind/part_two/todo.org
+++ b/scratch/deepmind/part_two/todo.org
@@ -12,7 +12,7 @@
 * Greedy Algorithms
 ** DONE Apple Stocks
 ** DONE Highest Product of 3
-** TODO Product of All Other Numbers
+** DONE Product of All Other Numbers
 ** TODO Cafe Order Checker
 ** TODO In-Place Shuffle
 * Sorting, searching, and logarithms