Apple Coding Interview Question - Product Of Array Except Self
HTML-код
- Опубликовано: 2 июл 2024
- The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/software-develo...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.dev/courses/nick
AlgoCademy - algocademy.com/?referral=nick...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/nickwhite
Follow My Twitter - / nicholaswwhite
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nickwwhite?locale.x...
Become A Member - / @nickwhite
#coding #programming #softwareengineering 
Наука
![ian - Fit Check (Feat. VonOff1700) [Official Music Video]](http://i.ytimg.com/vi/sDGWDBg45Dw/mqdefault.jpg)
Can’t divide?... a * Math.pow(b, -1); 😎
check mate
res[i] = (int)(p * Math.pow(nums[i],-1)); fails for 3 of the test cases O.o. I'm really curious about how you would solve it doing this
Just to know won't this be the same as divide ,so can we do it
That's literally dividing dude.
Modern problems require modern solutions 🤣🤣
I love how nick treats you like you know absolutely nothing; it helps so much; everyone else just speeds through the solution and I couldn't understand it; you're #1 for algo explanations, dude, gj
Hi, man I found your channel today and I love it so much! You are amazing man, you are helping a lot of beginners like me, thank you so much
The first time I did this I did it recursively. Basically pass in the current product * the current number to the recursive function. Then you can set the current answer to the current product (what was initially passed in) * whatever was returned from your recursive function. Then return the returned product * current number.
I woke up and i fell on this video .
It's my first time seeing and interview qiestion and i
just did the code in c it worked,but i guest there are more stronger and effective algorithms .
Thanks for posting such question.
Even if you do can not use division, it can still be done in O(n) with only one for loop going from 1 to n-2, computing left array and right array at the same time. For left array, the value at i-th position is a[i-1]*left[i-1], and for right array, the value is a[i+1]*right[i+1]. But the algo is very smart. Good job and nice video
Dude you're so chill. Watching these simple explanations is relaxing.
no homo.
Amazing solution! Thank you
Great vid! Another problem with the simple division solution is you gotta watch out for division by 0 error (if the input array contains 0).
The input doesn't contain anything less than 1
@@MohammadIshfaqueJahanRafee i think it was the length of array not the input of array
Use try n except blocks
If it throws zero division error
Then try to catch that error via exception block......store the result as zero
If it contained 0, easiest thing would be to write every other answer as 0 and then put the value of the product at the 0 value's index
You can easily come by that. In the first loop calculate the product of all non-zero numbers and set a boolean wheater or not you have seen a zero. If you run across a second zero, you can imedially return an all zero-array of the of the orginial length, otherwise replace the zero with the product and all other values with zero. Otherwise do the "division". Python Code:
def productExceptSelf(inputArray):
seenZero=False
product=1
for i in inputArray:
if i==0:
if seenZero: return [0]*len(inputArray)
seenZero=True
else:
product*=i
outputArray=[]
for i in inputArray:
if seenZero:
outputArray.append(0 if i!=0 else product)
else:
outputArray.append(product//i)
Thanks man, it is really helpful!
thank you so much for this amazing solution
Amazing stuff mate as usual
You Really Make Good Videos! It’s Just best whenever you explain those! Thank you for these and yeah, already subscribed 😁!
I noticed you had the same problem open at CodeSignal. However, if you tried to solve that one, you'd have probably seen that the challenge is a bit different. They do not guarantee that the product of all numbers in the input array fits any of the integer sizes in e.g. C++. It would be interesting to see a video on that one too
Also we can use division by subtraction method, since technically we are not allowed to use the division operator
Better explanation than Techlead
+
Humble and Funny and probably more talented
..
This dude is the whole package
This left of it and right of it like key to solving half the array questions I have tried ... It's kind of like recursion so I like it but it always ends up taking a lot of space
You are doing great work bro. Keep it up!!! 😀😀
this is how I did it in matlab:
a= [1,2,3,4];
out=[];
for i = 1:length(a)
b=a;
b(i)=[];
multi = prod(b);
out=[out,multi]
end
Great as usual ✊
Man, I came back here after 2 months and look you are a star now ! So happy for you buddy !
A way of making it O(n) instead of O(2n) which the problem asks for is to put them into the same for loop and put them both in at the same time, however, you do have to add an if statement to check whether the item is already in the list, and if so, times it by the item already in the list, if not, just add it in. However, you do have to have to keep track of the current multiplier which means an extra two variables, but these are only ints. This is it in PHP:
function productExceptSelf($nums){
$length = count($nums);
$output_arr = array();
$left_current=1;
$right_current = 1;
$j=$length-2;
$output_arr[0]=1;
for($i=1;$i
Division is also much more expensive operation than multiplication. So even if second algorithm looks more complex (O(3n) versus O(2n)) it will be much faster since there is no excessive usage of slow / operator. Time analysis gives us time complexity in regards to n. But it doesn't tell us how much time individual operations take. Something interesting to know... And btw, I got this question for internship interview in Microsoft Development Center in my country (Serbia)
I'll code both the variants. Let's see what's faster.
@@bhavyajain638 So??
@Nick White I noticed that in your previous video you initalized a hashSet and went ahead without looking at the complexity of it but I thought creating a null hash table required time O(m)
You can rotate the array every time abd gthan you can multiply everything that in the array to m-1 so every time you rotate it will be to the number you dont want to multiply in and than you can just to it but i dont thing its good for time complicity
Thanks for the wonderful explanation.
you make problems look simple
You're the coolest programmer I've ever seen on youtube.
well explained bro
we can get the product of every element in the array and then loop through the array one by one and divide that product with each element and store it in a new array of the same size
mine solution:
simplicity is a king :
def solution(arr):
out = []
mul = 1
for i in range(len(arr)):
mul *= arr[i]
for i in range(len(arr)):
out.append(int(mul/arr[i]))
return out
print(solution([1,3,7,5]))
if there is another way to get multiply of all members we can get ride off that first for loop 😊
Love how you explain this stuff 😅
you know, what tool he use to explain the solution?
hey im curious if i followed the rule , my step is to gather all number in inputarray and then remove one of the number depend on the i or how many time it loops (example if the second loop remove the number from index 1) and then multiply all the number within the array after that store it to outputrray
You can multiply in the second loop so it will be 2n
Number of operations would still be the same, still 3n. First loop: n. Second loop: 2n, so the total is still 3n :) Comes out to being a simple question of which solution is more legible or error-prone.
Yet again, thanks for this.
Just multiply i in a cycle unless i is equal to index of the numbee on output
Nice solution
Its just like the question of calculating area Between two towers.
Thank you for ur videos. It helps us alot. Much appreciated!!
nice explanation 🔥
great explanation
For i in range(n):
For j in range(n):
If i=!J:
s=s*arr[i]
m.append(s)
print(m)
To avoid division maybe we could use logarithmic approach
Using the first approach If we cannot divide then we can instead of dividing by 2 we can multiply by 1/2 so generalizing it instead of dividing by n we will multiply by 1/n just a trick to get around this problem using the first approach.
for x in array: array[x]=1, multiply, output[x]=result
That’s quadratic time
Initially, 😁 ,
I came up with this just after looking at the thumbnail (before watching) :
def pro(l):
p=1
for x in l:
p*=x
for i in range(len(l)):
k=l[i]
l[i]=p//k
return l
l=[1,2,3,4]
print(pro(l))
Can we also use recursion to the left, and right, then multiply them after ? Divide and conquer?
That was my first solution before watching his solution but I think it is O(n*log(n))
Yo Nick I just wanted to say something really surprising ...
You're awesome bud
Im an electrical engineer. I can code but Im not familiar with any of the computer science jargon you used. I solved it with a nested for loop. What is time complexity and space complexity?
I was asked this exact question in a recent interview by Goldmann Sachs. First I used division, then the interviewer asked to do it without division. I followed up with precalculating suffix products and calculating prefix products on the go.
how'd the interview go?
good logic !! 🤓
That chrome tab, "make bottom taskbar disappear" 😂😂
I assume you wouldn’t be allowed to multiply by i^-1 each time right?
Only video where I understood the solution/technique
I don’t think you need the 3rd loop. You could do the output array calculation in the 2nd loop after getting the right_products.
It's same time and space complexity
@@MegaPremios how is it same time complexity? Just Going through the loop, doing nothing will take some time. Won't it?
I'm a beginner.
@@bhavyajain638 You either do 2 operations N times, or you do 1 operation 2*N times. If you are looking at lines of code execution, it's the same
@@MegaPremios yes I get it. Thanks
Having not seen the solution in the video yet, my brute force approach would be to have two loops, the first loop goes through each element in the input array to keep track of the element we are skipping in the calculation. The next loop simply goes through the array again, this time we skip the element pointed to in the first loop, and simply get the product of every other element in the array, storing the result in a new array (we keep track of our location in this new array using the outer loop).
I believe this is O(N^2) complexity, so not sure if it would be an acceptable solution in an interview however, but this would be where I would start with this problem:
public static int[] productExcludingSelf(int[] input) {
int[] products = new int[input.length];
for(int i=0; i
Hey man! I also tried doing it this way but the output is way too different than what I expected it to be. I'm kind of new to programming so I didn't really go into complexity for this question and following the boilerplate code mentioned in the question. Can you pls tell me where I'm going wrong? Would be a great help. Here's my logic.
public static void prod(int[] arr)
{
for(int i=0; i
@@nayanyadav6919 hi man do not use this approach as you get it wrong when the particular element is repeated in the array. I will paste my sol in the below you can check it out you can do it by taking to loops and inputting the number of the second loop where both the loops run from 0 to the len(array)-1 and you can create two lists one outside the two loops and one inside the 1st loop and you will check that if the number in the 1st loop != number In the second loop in this way you can eliminate the element repetition and you will append
it with the 2nd list which is present inside and then at last you can append the second loop with the first loop in this way you can append only those numbers which are not same as the 1st loop number and at the end you can create another loop where it is in the form of a list inside the list and you can multiply the numbers in the end.
The solution in python:-
a=[2,2,3,4]
r=[]
for j in range(len(a)):
s=[]
for m in range(len(a)):
if j==m:
s=s
else:
s+=[m]
r+=[s]
for ch in r:
s=1
for m in ch:
s*=a[m]
print(s)
When it comes to job interview coding questions what are they mainly looking for? It is mostly or heavily Algorithms and understand how they perform???
I have read a lot about this, so tldr; you are expected to 'get the job done' but talking your way trough is very important, since they can't tell what you are thinking; so you've got to talk! You have to try make it more like a friendly technical-conversation, rater than technical question and answer test :)
At first I thought why u make video on such a simple question but at the end I realise why u did
same here bro xD
we can divide so we get to 2n (1. loop to multiple all elements to get product of all, 2. loop again to take elements and divide product)
but without division and with this solution it's 3n (left product , right product , result)
but why tho ... without division
...or use logarithm property: a/b = pow(x, logx(a) - logx(b)), where x is any base... and pay attention to zeros and signs :)
It would be computationally expensive compared to just looping 3 times. Imagine how that operation scales for an array of length 1000 or something.
@@freeshavaacadooo1095 1000? you've gotta be kidding me :D besides multiplication anyway will suffer for any large numbers due to overflow - from this point you'll find yourself solving quite another puzzle than pesky logarithm expensiveness :)
Can you please upload a video for a matrix travel in Python?
How about Divide and conquer like merge sort ?
To anyone who still says something like 'languages are all the same except different syntax' , this is litterally a one-liner in haskell (this legitimately took me 2 mins)
pes l = (product . (`delete`l)) l
Or in a less point-free style:
pes l = map (\x -> product (delete x l)) l
Nice... Great video
Index = int(input ("which Index you want?"))
C = 1
for I , j in enumerate(nums):
If I != index:
c*= j
Print(c)
I got a idea as take initial array contain 1s as same size of input and then multiple all items of output array expect the one for we are calculating
Thanks a lot Bro 👍
Logics do not click on mind what to do.
I am learning java by myself.
Even I do not able to understand the problem like code chef questions.
Me too and on which platform u r learning
@@harsimransidhu3961 First I studied from the Oracle book the complete reference upto inheritance. After that topic I am not getting from the book.
Then I studied on particular topics from random youtube search.
But problem is that I am not able solve the problems. Still struggling.
Master of codings :D
I used 2 for loops
Would we not want to use the length call and instead check to see if the end of the array was nil and do all of that if this was in C since it’s O(n). I mean it would increase runtime by only alittle, it would still be O(n) lol.
This is usually a phone screen interview question :) !!
What advantage does the leftproduct and rightproduct arrays provide as opposed to calculating and multiplying the elements in the list to the left and right of that index in the loop itself?
Raahel Baig time complexity. If you calculate the product of elements to the left and right of every single index (which would be necessary to be able to use your implementation), you have a time complexity of O(n^2) which is too long for the problem
Awsm bro, I always wait for your video.
Thats cheeting with reading from output array. it is allowd? Maybe I study too much of turing machine where you have output tape witch is write-only.
Wait what.
The division part is absolutely mental. There is no way that looping through all the elements n times will be faster than n divisions.
shouldn't the nums[i-1] in the final code for calculating left products be nums[i]????
Good work bro !! Nice explaination.
You make me better..
I solved it with a nested for loop. The first loop loops over the array, the second loop does the multiplying, and skips over the index of the current item. Less complicated and it allows you to make only 1 new array. Your indexes are tracked by the for loops and you only need to make 1 variable, the array.
Hey man! I also tried doing it this way but the output is way too different than what I expected it to be. I'm kind of new to programming so I didn't really go into complexity for this question and following the boilerplate code mentioned in the question. Can you pls tell me where I'm going wrong? Would be a great help. Here's my logic.
public static void prod(int[] arr)
{
for(int i=0; i
That's quadratic not linear
My go to solution was to have 2 for loops (1 is nested), *= a variable (initialized at 1). Only thing is that if the iteration variable of inner loop == interation variable of outer loop, continue through inner for loop. Store to temp, return temp, but I guess this is too long?
My code:
int[] allBut(int[] input){
int[] output = new int[input.length];
for(int i = 0; i < input.length; i++){
int product = 1;
for(int move = 0; move < input.length; move++){
if (move == i) continue;
product *= input[move];
}
output[i] = product;
}
return output;
}
My solution would be (JS):
function productExceptSelf(input) {
var output = [];
for (var i = 0; i < input.length; i++) {
var product = 1;
for (var j = 0; j < input.length; j++) {
if (j != i) {
product *= input[j];
}
}
output.push(product)
}
return output;
}
Seems the least complicated to me, because while multiplying with left and right is true, its easier to say it multiplies with everything except the own index (j != k)
I would have copied all the values from the input array into a new one in a loop and changed the index value to 1 and multiplied the elements in the array and added that to the output array
let tab = [1, 2, 3, 4]
let output=[]
tab.forEach(val1 =>output.push(tab.filter(val2=>val2!==val1).reduce((a,b)=>a*b,1)))
console.log(output); // [ 24, 12, 8, 6 ]
Cant we get the product of all elements, and then divide that product for each index element
Are these coding questions for Software roles? I have a CAD Engineer role interview with Apple. Can I expect similar questions?
Define a function
Int divide(Divident, divisor):
c=1
while (Divident>1):
Divident-=divisor
c-=-1
return c
I think this should also work...
if divisor is 0 or negative it's an infinite loop
Division here is O(n) so the entire solution would be O(n^2)
Great work man
A (surprisingly expressive) one-liner Haskell version of the first solution:
productExceptSelf :: [Int] -> [Int]
productExceptSelf nums = zipWith (*) (init $ scanl (*) 1 nums) (tail $ scanr (*) 1 nums)
We can also solve this by simply taking the except element to 0th index in single loop and splitting the list from 0th index and finding the product of elements of list from first index to end, so no notation of left and right required..🙌
In that case, you won't be able to solve it on O(n) complexity.
I knew what to do but I couldn't translate it into code :/
Before even watching the video, this is how I would do it (in C):
int input[4] = {1, 2, 3, 4}; // input array of the example
int output[4] = {1, 1, 1, 1}; // initialize output array to 1's (neutral element of multiplication)
for (int i = 0 ; i < 4 ; i++) {
// multiply the current position in the OUTPUT array with every value to the left of the current position in the INPUT array (except first one).
if (i != 0) {
for (int j = i-1 ; j > 0 ; j--) {
output[i] *= input[j];
}
}
// Do the same thing but to the right.
if (i != 3) {
for (int j = i+1 ; j < 4 ; j++) {
output[i] *= input[j];
}
}
}
Edit: I'll take it as a win
How about having a single for loop and each time making that particular index element as 1 and multiplying the whole array... Thus ending without division and O(n).
you'll multiply whole array n times (for each index) that leaves you with O(n^2).
This is N^2
First iterate a loop and multiply all elements of an array and store into result variable.
After that iterate same loop and divide result variable with ith element give ans for that position
It was asked not to use division
can't you just calculate the total multiplication and then divide by each element ?
Nice, excellent explanation
Nick - how is this explanation ? Its essentially the same as yours but condensed.
Take S = [2,3,4,5] as an example. The expected answer is P = [60, 40, 30, 24].
"DIAGRAM" :
"1"[3,4,5]. product = "1", 3,4,5.
[2][4,5]. product = 2,4,5.
[2,3][5]. product = 2,3,5.
[2,3,4]"1". product = 2,3,4, "1".
S = the given array, Ni = the i-th element of S,
Pi = product for Ni, Li = product of numbers on left of Ni, Ri = product of numbers on right of Ni.
Thus, Pi = Li * Ri, for each Ni. We also see it the above "diagram".
STEPS -
(1) First find only Li for each element in S ["1", {1 * 2}, {2 * 3} , {6 * 4}] == [1, 2, 6, 24]
(2) Next we find only Ri for each element in S [{20 * 3}, {5 * 4}, {5 * 1}, "1"] == [60, 20, 5, 1]
(3) Now, multiply the corresponding elements of Li & Ri to get Pi == [60, 40, 30,24].
Thus, step 3 gives us the answer we expected. Notice that we can combine steps 2,3 as discussed at 8:20 instead of doing them separately.
I was thinking a nested loop with outer loop varying from 0 to n-1,and inner loop with index j such that if i index equals j index increment j by 1 and continue iteration.For last edge case that is when i=n-1 j would have index error so reduce n by 1 in last iteration
Yes, why not, but the algorithm has a complexity of O(n^2), and the question specifies that we need to solve it in O(n)
@@GameSteals ok
Most popular coding interview question!
Hey bro it's an amazing video I loved it, I'm following your video from long back and had subscribed your channel 😉.
I'm stuck to a problem in code signal it is "Election Winner" could you please make a video on it so that people like me can easily refer your video and can clear there doubt. I'm waiting for the video 😊🙏.
Hi Nick
Can you please create a playlist of all hard problems in Leetcode? I love the way you explain... keep it up
He did created, check out his page
Can't you do something like this:
total = e^(sum(input))
for i in range 0,len(input):
output[i] = ln (total - e^input[i])
what about using log of exp