Coding interview question from

In this video, I show how to find the two numbers missing from a sequence of integers

Do you have a big interview coming up with Google or Facebook? Do you want to ace your coding interviews once and for all? If so, Byte by Byte has everything that you need to go to get your dream job. We’ve helped thousands of students improve their interviewing and we can help you too.

Stuck on Dynamic Programming? Check out our free ebook: www.dynamicprogrammingbook.com

50 Practice Questions:

You can also find me on

Twitter:

Facebook:

Email: sam@byte-by-byte.com

Nguồn: https://wijstaanvooronzegrondrechten.org

Xem thêm bài viết khác: https://wijstaanvooronzegrondrechten.org/cong-nghe

Wouldn't it be much simpler to solve this problem with an occurence array?

Does it work for arrays that are not sorted?

what if we take input form user

what is expected code change we have to made

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 <= n; i++) {

factorial *= i;

}

return factorial;

}

}

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?

Running time is incorrect unless it is given that input array is sorted.

@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!!

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?

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 ??

Such a great idea to use XOR here wouldn't have thought about that one, thanks for the video.

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!)

How about if first 2 numbers missing, for example [3,4,5]

more of a maths question than programming!! Good Explanation bro 😀

!!! 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

Will this solution ends up in a overflow when n is sufficiently large.

Dude, just wanted to say you're an awesome teacher! Thanks for taking out the time to make these videos!

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

what about when we want find k missing number in range 1 to n

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).

Amazing Solution. Without Memoization, I could not think of considering the half-of-sum idea. Brilliant!

You can also calculate sum and product of the numbers and solve for the two equations.

Is that really what they ask in interviews !! B.S.

Dude you are awesome , Keep up the good work (thumbsup)

Awesome explanation !!

Great illustration of problem towards complex form ,Thanks.

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 !!!

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.

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.

It's a nice video, curious, what happen if array starts with 0, such as {0}, or {0, 1, 3}?

i thought calculation for a sum of sequence of numbers is [(n)(n+1)/2 ] rather than [(n)(n-1)/2]]

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).

Thanks a lot men it's so helpful I can do it now can you sub me please and thanks if you sub me then I will sub you oke thanks so much if you do ttttttt

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.

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.

First off, thanks for making these videos, there aren't enough coding interview videos out there on YouTube. 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.