Bonjour Malick
I failed my last 3 coding interviews. It's not that I was not able to pass them. I think I'm starting to forget the fundamentals. If I want to continue in this profession, I need to go over my lessons and maybe start Leetcode as a daily routine. Let's play some music shall we?
0.
I will try to write my chain of thoughts.
1. The statement:
Given an array nums, of n integers,
write a program to return an array product such that
product[i] is equal to the product of all the elements of nums
except nums[i].
The product of any prefix or suffix of nums
is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n),
without using the division operation...
Given an array nums of n of integers where n > 1,
return an array output such that output[i] is equal to
the product of all the elements of nums except nums[i].
Example:
Input: [1,2,3,4]
Output: [24,12,8,6]
Constraint: It's guaranteed that the product of the elements
of any prefix or suffix of the array (including the whole array)
fits in a 32 bit integer.
Note:
- Solve it without using the division operator
- Write a program that runs in O(n) time.
Follow up:
Could you solve it with constant space complexity?
The output array does not count as extra space
for the purpose of space complexity analysis.
2. First attempt, write something:
I decided to write a program without respecting the whole statement. I first tried to write something, I first tried to write anything that could give me the desired result.
- multiply all the items inside the array
- divide by the current item, unless this item equals zero
- store the result inside another array
- return the array
def d(nums: list[int]) -> list[int]:
product = []
# go through all the items
for i in nums:
m = 1
# if current item not equals zero
if i != 0:
# multiply all the items
for j in nums:
m *= j
# divide by current item
product.append(m // i)
# if current item equals zero
else:
# multiply all the items except the current one
for j in nums:
if j != i:
m *= j
# no need to divide, we can't divide by zero
# plus, the item was already excluded when multiplying
product.append(m)
return product
2. Second attempt, remove the division operator:
There are 2 problems with my solution: the program use the division operator and the program does runs in O(n²) time. Let's try to get rid of the division operator (it sounds like the easiest thing to do):
def e(nums: list[int]) -> list[int]:
product = []
# go through all the items
for i in nums:
m = 1
# if current item not equals zero
if i != 0:
# multiply all the items
for j in nums:
m *= j
# divide by current item but without using division
k = 0
m += i
while m > i:
m -= i
k += 1
product.append(k)
# if current item equals zero
else:
# multiply all the items except the current one
for j in nums:
if j != i:
m *= j
# no need to divide, we can't divide by zero
# plus, the item was already excluded when multiplying
product.append(m)
return product
3. Third attempt, remove the division operator, again:
I've managed to get rid of the division operator. But I have introduced another loop within the program. This will worsen the performance. If I try to compare execution time, this is what I have:
# let's try to measure execution time for our 2 functions
# by using the timeit function from the timeit module
t = timeit(lambda: d([1, 2, 3, 4]))
print(t) # ~0.7731416939059272
t = timeit(lambda: e([1, 2, 3, 4]))
print(t) # ~2.5302764819934964, slower
3.1. Let's try another idea:
- go through all the items in the array
- and for each item, again go through all the in items in the array (except the current one)
- multiply them
def f(nums: list[int]) -> list[int]:
# get length of the array
length = len(nums)
# create the array containing the products
product = [1] * length
for i in range(length):
for j in range(length):
# condition for skipping the current item
if j == i:
continue
product[i] = product[i] * nums[j]
return result
This program is not yet running in O(n) time, but, there is some progress:
- not using the division operator.
- already running faster than the previous function (~1.3750199479982257 on my machine)
3.2. Finally noticing a pattern:
What the previous function is doing can be broken down to:
- multiplying everything that is on the left of the current item: prefix
- multiplying everythint that is on the right of the current item: suffix
- multiplying prefix and suffix
[X, 2, 3, 4] # prefix items: none, suffix items: [2, 3, 4]
[1, X, 3, 4] # prefix items: [1] , suffix items: [3, 4]
[1, 2, X, 4] # prefix items: [1, 2], suffix items: [4]
[1, 2, 3, X] # prefix items: [1, 2, 3], suffix items: none
5. Fourth attempt, prefix and suffix:
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
The statement was really trying to give me a clue and I did not pay enough attention. The prefix of nums really meant: the product of all the numbers to the left of the current index. And the suffix of nums reall meant: the product of all the numbers to the right of the current index.
5.1. the product of all the numbers to the left of the current index:
def g(nums: list[int]) -> list[int]:
length = len(nums)
product = [1] * length
prefix = 1
for i in range(length):
product[i] = prefix
prefix *= nums[i]
return product
5.2. the product of all the numbers to the right of the current index:
def h(nums: list[int]) -> list[int]:
length = len(nums)
product = [1] * length
suffix = 1
for i in range(-1, -1 * (length + 1), -1):
product[i] *= suffix
suffix *= nums[i]
return product
9. More on this topic:
- How to improve myself?
- Maybe I should retire and start a farm
- How do I know when to harvest my potatoes?
10. While I still have your attention:
Join us as we make history with the first-ever DjangoCon Africa 2023 that will be held at the State University of Zanzibar Tanzania, from 6th - 11th November 2023.
