First off, thanks for making these videos, there aren't enough coding interview videos out there on CZcams. I'm considering making some of my own one day. Good job! Secondly, as a software engineer to another software engineer, I have a interview question I'd like you to solve in one of your videos. I think it would be a great one for the viewers. You are building a binary search tree from scratch. In your design, you are to implement a method to find a random node in that tree where each node has equal chance of being selected.
Thanks! :) That sounds like an interesting question. Do you know of a better solution than either generating the tree, then assigning numbers to each node and randomly picking one, or doing an online algorithm where you randomly select or reject each node as you go?
I think it is enough if we compute one xor i.e either left one or right one. Then we can simply subtract it from (totalSum-arrSum). I think it is a little more efficient that way(But not significantly).
@ByteByByte Won't the oneMissing solution break down? Because 1^2 = 3 (calculating totalXOR) and then when you try to go 3, it is 3^3 which is 0, so you get an incorrect sum? Also, I absolutely loved this playlist. It would be great if you could add more videos!!
XOR is not needed here at all. Take a look: void TwoMissing(int* arr, int size, int* first, int* second) { int total = 0; int arrTotal = 0; for (int i = 1; i
Using the quadratic equation class Test { public static void main(String[] args) { int n = 5; int[] a = {1, 3, 5}; int sumOfElements = (n * (n + 1) / 2) - getSumOrProduct(a, true); int productOfElements = getFactorial(n) / getSumOrProduct(a, false); double discriminant = (Math.pow(sumOfElements, 2) - 4 * productOfElements); int x = (sumOfElements + (int) Math.sqrt(discriminant)) / 2; int y = (sumOfElements - (int) Math.sqrt(discriminant)) / 2; System.out.println(x); System.out.println(y); } private static int getSumOrProduct(int[] a, boolean getSum) { int sum = 0; int product = 1; for (int element : a) { sum += element; product *= element; } if (getSum) { return sum; } return product; } private static int getFactorial(int n) { int factorial = 1; for (int i = 1; i
Excellent video, but a few points about the solution: 1. Here you incorrectly assume the array is already sorted. The problem statement doesn't specify that. 2. You don't have to calculate the second missing element, just subtract the (TotalSum - arrSum)-(firstMissingElement).
1. What makes you think the array needs to be sorted? This solution shouldn't require that. 2. In this case how are you calculating firstMissingSum to begin with?
Thanks for your response. To address your points: 1. The step when you get the pivot index, on the array, once you get the total sum. You look for the missing array element in index lower than the pivot index. This can only be true if the array is sorted. 2. You get the first missing number by following the step you mention (to get the first missing element in the lower half). But instead of doing the lookup for the upper half for the second missing element. Just take the difference between the first missing element and the totalSum of the missing elements. For Example: Lets say the totalSum missing is 8 and the first missing element is 3, then we can just do a 8 - 3 to get the second missing element.
1. So when you're pivoting, you're not actually paying any attention to the order, you're just saying for each element is it greater or less than the pivot. Therefore it's not actually reliant on the order. 2. Yes you could do that, but that doesn't really seem like any less effort to me
Someshwar Chatterjee your question is intuitive ... but if we closely look in the pivot calculation. let's say the given array is [4 1 5] size = size+2 so size =5 totalsum = (5*6)/2=15 arrsum=4+1+5=10 pivot =(15-10)/2=2 it means that the value one value will lie between (1,2) and other between (3,5). a clear understanding can be with this example given array is [3 1 2] now totalsum= 15 arrsum=6 pivot = 4 so one value will definitely lite between (1,4) and the other will lie between (5,5) (which is five itself ).. did I make sense?
Just want to get clarified, as I had the same question. The algorithm calculates xor on the based of comparing pivot value with array elements and not with array's pivot index.
I think one solution to this would be similar to your Find All Duplicated one. Only caveat being that either data is signed type or n < MAX/2 which would allow to add n to current value. Array size is not issue since due to required size is Source + Answer in length so can use answer part to make up. Just initialize them equal to first element of source array to avoid complications.
I was also thinking of this case... we are XORing of those numbers which are( less or equal to the pivot) or (greater than the pivot) ...so no matter where these numbers appear in array , only one element come from Left XOR and one from right XOR. ☺
totalSum formulla is wrong , it should be => totalSum = size * (size + 1) / 2. en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF UPDATE: he has corrected himself at the end of this video
Great job! Please, can you make a tutorial explaining problem 16.3 of Cracking the Coding Interview. You already made a tutorial explaining a similar problem, but I think it would be good to explain that one, too. The problem says: Given two straight line segments (represented as a start point and an end point), compute the point of intersection, if any. Thank you.
Hello Sam. Recently subscribed to your channel. It's really great work man. Thanks a lot. Can you suggest where I can find programming questions like these, please ??
It seems like you could use this technique for k missing numbers by calculating xor overlaps on k sections but at some point you would exceed O(n) time.
You can definitely generalize the algorithm, although it gets a bit more complicated. There is some discussion of that here if you're curious stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe
pretty much by definition, we need to start with 1, because otherwise you can't differentiate between an array missing 0 or missing a number at the end
This implementation will fail on this example: Range [0-5] i.e. A' = [0, 1, 2, 3, 4, 5] and input arr A = [5, 3, 0, 4]. As per implementation in this video pivot = (15 - 12)/2 = 1. TotalLeftXOR = 1 (As i starts from 1) arrLeftXOR = 5 TotalRightXOR = 2 ^ 3 ^ 4 ^ 5 = 0 arrRightXOR = 3 ^ 0 ^ 4 = 7 {1^5, 0^7} = {4, 7} Am I missing something?
!!! your solution does Not work when the two elements are at the beginning or at the end. sum = numberOfelements *( average) sum = numberOfelements* ((min+max)/2) [.... min, ..... max] when two elements are missing at the end, we have new max = max+2; sum = (numberOfelements+2) *( (min+max+2)/2) the average is min+max+2 (missing elements at the end) sum = (numberOfelements+2) *((min-2 + max)/2) the average is min-2+max (missing elts at the beginning) Thanks
Just FYI: I know it's written XOR but I've never heard it pronounced "X OR". Everywhere I've been, we always said "exclusive or". (But we used the abbreviation in writing!)
there is a more easy solution than this using set_difference method in c++ would find out the ans and that could also find n number of missing characters in the array !!!
defeats the purpose ! why ? i am a fresher and if in interview if this same question is asked and i answer it through set_difference will it be wrong ?
its like me asking you to sort an array and you using Arrays.sort. Yes it gives the same result but the only thing I learn about you is that you know that Arrays.sort exists.
I liked your smile when you go from one solution to a better solution
Amazing Solution. Without Memoization, I could not think of considering the half-of-sum idea. Brilliant!
thanks!
First off, thanks for making these videos, there aren't enough coding interview videos out there on CZcams. I'm considering making some of my own one day. Good job!
Secondly, as a software engineer to another software engineer, I have a interview question I'd like you to solve in one of your videos. I think it would be a great one for the viewers.
You are building a binary search tree from scratch. In your design, you are to implement a method to find a random node in that tree where each node has equal chance of being selected.
Thanks! :)
That sounds like an interesting question. Do you know of a better solution than either generating the tree, then assigning numbers to each node and randomly picking one, or doing an online algorithm where you randomly select or reject each node as you go?
I'll send you an email of the explanation, you'd have to be very careful with your concept to maintain that 'equal chance' probability for all nodes.
I think it is enough if we compute one xor i.e either left one or right one. Then we can simply subtract it from (totalSum-arrSum). I think it is a little more efficient that way(But not significantly).
@ByteByByte Won't the oneMissing solution break down?
Because 1^2 = 3 (calculating totalXOR) and then when you try to go 3, it is 3^3 which is 0, so you get an incorrect sum?
Also, I absolutely loved this playlist. It would be great if you could add more videos!!
XOR is not needed here at all.
Take a look:
void TwoMissing(int* arr, int size, int* first, int* second)
{
int total = 0;
int arrTotal = 0;
for (int i = 1; i
Dude, just wanted to say you're an awesome teacher! Thanks for taking out the time to make these videos!
Thanks!
Using the quadratic equation
class Test {
public static void main(String[] args) {
int n = 5;
int[] a = {1, 3, 5};
int sumOfElements = (n * (n + 1) / 2) - getSumOrProduct(a, true);
int productOfElements = getFactorial(n) / getSumOrProduct(a, false);
double discriminant = (Math.pow(sumOfElements, 2) - 4 * productOfElements);
int x = (sumOfElements + (int) Math.sqrt(discriminant)) / 2;
int y = (sumOfElements - (int) Math.sqrt(discriminant)) / 2;
System.out.println(x);
System.out.println(y);
}
private static int getSumOrProduct(int[] a, boolean getSum) {
int sum = 0;
int product = 1;
for (int element : a) {
sum += element;
product *= element;
}
if (getSum) {
return sum;
}
return product;
}
private static int getFactorial(int n) {
int factorial = 1;
for (int i = 1; i
more of a maths question than programming!! Good Explanation bro :D
Excellent video, but a few points about the solution:
1. Here you incorrectly assume the array is already sorted. The problem statement doesn't specify that.
2. You don't have to calculate the second missing element, just subtract the (TotalSum - arrSum)-(firstMissingElement).
1. What makes you think the array needs to be sorted? This solution shouldn't require that.
2. In this case how are you calculating firstMissingSum to begin with?
Thanks for your response. To address your points:
1. The step when you get the pivot index, on the array, once you get the total sum. You look for the missing array element in index lower than the pivot index. This can only be true if the array is sorted.
2. You get the first missing number by following the step you mention (to get the first missing element in the lower half). But instead of doing the lookup for the upper half for the second missing element. Just take the difference between the first missing element and the totalSum of the missing elements.
For Example: Lets say the totalSum missing is 8 and the first missing element is 3, then we can just do a 8 - 3 to get the second missing element.
1. So when you're pivoting, you're not actually paying any attention to the order, you're just saying for each element is it greater or less than the pivot. Therefore it's not actually reliant on the order.
2. Yes you could do that, but that doesn't really seem like any less effort to me
Someshwar Chatterjee your question is intuitive ... but if we closely look in the pivot calculation.
let's say the given array is
[4 1 5]
size = size+2
so size =5
totalsum = (5*6)/2=15
arrsum=4+1+5=10
pivot =(15-10)/2=2
it means that the value one value will lie between (1,2) and other between (3,5).
a clear understanding can be with this example
given array is [3 1 2]
now totalsum= 15
arrsum=6
pivot = 4
so one value will definitely lite between (1,4) and the other will lie between (5,5) (which is five itself ).. did I make sense?
Just want to get clarified, as I had the same question. The algorithm calculates xor on the based of comparing pivot value with array elements and not with array's pivot index.
I think one solution to this would be similar to your Find All Duplicated one. Only caveat being that either data is signed type or n < MAX/2 which would allow to add n to current value. Array size is not issue since due to required size is Source + Answer in length so can use answer part to make up. Just initialize them equal to first element of source array to avoid complications.
Interesting, hadn't though of doing it that way, but you're right that would work too. Thanks for sharing!
How to solve problem if given array is {3, 4, 5, 6} and missing numbers are 1, 2 ?
in this case, both missing nos are on left side of pivot.
totalSum - arrSum / 2 = 3/2 = 1. You still pivot in the same way and end up with 1 on one side and 2^3^4^5^6 on the other.
I was also thinking of this case... we are XORing of those numbers which are( less or equal to the pivot) or (greater than the pivot) ...so no matter where these numbers appear in array , only one element come from Left XOR and one from right XOR. ☺
Great illustration of problem towards complex form ,Thanks.
you're welcome!
Such a great idea to use XOR here wouldn't have thought about that one, thanks for the video.
totalSum formulla is wrong , it should be => totalSum = size * (size + 1) / 2. en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF
UPDATE: he has corrected himself at the end of this video
The solution is brilliant man
This solution in mind blowing!
i thought calculation for a sum of sequence of numbers is [(n)(n+1)/2 ] rather than [(n)(n-1)/2]]
yep you're right; its corrected in the blog post
n*(n-1)/2 if sequence starts with 0
Kimer Seen yes but sequence of n numbers is always considered as starting from 1 rather than 0.
Great job! Please, can you make a tutorial explaining problem 16.3 of Cracking the Coding Interview. You already made a tutorial explaining a similar problem, but I think it would be good to explain that one, too. The problem says: Given two straight line segments (represented as a start point and an end point), compute the point of intersection, if any. Thank you.
Hey thanks for the suggestion! I actually already did a solution to that problem, which you can see here :) www.byte-by-byte.com/lineintersection/
It's really inspiring! Thanks for the video!
Will this solution ends up in a overflow when n is sufficiently large.
Hello Sam. Recently subscribed to your channel. It's really great work man. Thanks a lot. Can you suggest where I can find programming questions like these, please ??
It seems like you could use this technique for k missing numbers by calculating xor overlaps on k sections but at some point you would exceed O(n) time.
You can definitely generalize the algorithm, although it gets a bit more complicated. There is some discussion of that here if you're curious stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe
Awesome explanation !!
thanks!
It's a nice video, curious, what happen if array starts with 0, such as {0}, or {0, 1, 3}?
pretty much by definition, we need to start with 1, because otherwise you can't differentiate between an array missing 0 or missing a number at the end
This implementation will fail on this example: Range [0-5] i.e. A' = [0, 1, 2, 3, 4, 5] and input arr A = [5, 3, 0, 4]. As per implementation in this video pivot = (15 - 12)/2 = 1.
TotalLeftXOR = 1 (As i starts from 1)
arrLeftXOR = 5
TotalRightXOR = 2 ^ 3 ^ 4 ^ 5 = 0
arrRightXOR = 3 ^ 0 ^ 4 = 7
{1^5, 0^7} = {4, 7}
Am I missing something?
Is given array is sorted?
You are awesome
hey can b done in o(n) . we know a+b we can find a2+b2 using summation of first n sq numbers then solve the 2 eq
this solution is already O(n). And sum of squares is a bit dangerous considering overflow
Byte By Byte Thanks for the reply I just thought that it was simpler .In fact using this it should tkae constant time ...keep up the gud work buddy..
Dude you are awesome , Keep up the good work (thumbsup)
thanks!
what if we take input form user
what is expected code change we have to made
Thank you man. 👌☝👍
Running time is incorrect unless it is given that input array is sorted.
How do we know that the missing numbers in [1, 2, 4] are 3 and 5? Couldn't it be 0 and 3? Will the pattern always start with 1?
Does it work for arrays that are not sorted?
Yes
must watch 🥰
Wouldn't it be much simpler to solve this problem with an occurence array?
!!! your solution does Not work when the two elements are at the beginning or at the end.
sum = numberOfelements *( average)
sum = numberOfelements* ((min+max)/2) [.... min, ..... max]
when two elements are missing at the end, we have new max = max+2;
sum = (numberOfelements+2) *( (min+max+2)/2) the average is min+max+2 (missing elements at the end)
sum = (numberOfelements+2) *((min-2 + max)/2) the average is min-2+max (missing elts at the beginning)
Thanks
How about if first 2 numbers missing, for example [3,4,5]
It will.still wirk fine
size * (size + 1) / 2 not (size - 1)
what about when we want find k missing number in range 1 to n
THat's a different problem
Just FYI: I know it's written XOR but I've never heard it pronounced "X OR". Everywhere I've been, we always said "exclusive or". (But we used the abbreviation in writing!)
there is a more easy solution than this
using set_difference method in c++ would find out the ans and that could also find n number of missing characters in the array !!!
yes you could use built in functions to do the work for you but that kind of defeats the purpose
defeats the purpose ! why ? i am a fresher and if in interview if this same question is asked and i answer it through set_difference will it be wrong ?
its like me asking you to sort an array and you using Arrays.sort. Yes it gives the same result but the only thing I learn about you is that you know that Arrays.sort exists.