Software Engineering Mock Interview: Find the Duplicate Number (with Google SWE)
Vložit
- čas přidán 22. 07. 2024
- Don't leave your software engineering career path to chance. Make sure you're interview-ready with Exponent's software developer interview prep course: bit.ly/3wFcUtn
Ahmed Khaled explains how to find the duplicate number in an array without modifying the array and only using constant extra space.
Chapters -
00:00 - Introduction
00:40 - Question
01:19 - Answer
07:39 - Test cases
09:30 - Tips
Watch more videos here:
- Amazon SWE answers system design interview question: • Amazon System Design I...
- Google SWE answers algorithms interview question: • Google Software Engine...
- Google TPM answers Tiktok system design interview question: • System Design Mock Int...
- Microsoft SWE answers algorithms interview question: • Microsoft Software Eng...
👉 Subscribe to our channel: bit.ly/exponentyt
🕊️ Follow us on Twitter: bit.ly/exptweet
💙 Like us on Facebook for special discounts: bit.ly/exponentfb
📷 Check us out on Instagram: bit.ly/exponentig
📹 Watch us on TikTok: bit.ly/exponenttikttok
ABOUT US:
Did you enjoy this interview question and answer? Want to land your dream career? Exponent is an online community, course, and coaching platform to help you ace your upcoming interview. Exponent has helped people land their dream careers at companies like Google, Microsoft, Amazon, and high-growth startups. Exponent is currently licensed by Stanford, Yale, UW, and others.
Our courses include interview lessons, questions, and complete answers with video walkthroughs. Access hours of real interview videos, where we analyze what went right or wrong, and our 1000+ community of expert coaches and industry professionals, to help you get your dream job and more!
#softwareengineering #amazon #coding #leetcode #equalsum #subarray #google #tech #entrepreneurship #exponent
Don't leave your software engineering career path to chance. Make sure you're interview-ready with Exponent's software developer interview prep course: bit.ly/3wFcUtn
Best comment ever, start with any solution, and dont try to give the best solution at first. Better to have something then nothing
It was asked not to modify the array but this answer modifies it. We need to use Floyd's cycle finding algorithm to meet the requirements of using constant space and O(n) time.
Exactly! so he actually failed.
Wouldnt using XOR better??
@@nameless2850 Will it be considered as an extra space?(To store the XOR's in a variable)
It wouldn’t be hard for him to fix it. Since he max some numbers negative, just loop thru them to make them positive once again. Then return the duplicate.
for those who are l;ooking for the correct solution:
int findDuplicateCal(int* arr, int size) {
int n = size - 1;
// Calculating the expected sum of the first n natural numbers using the formula: n(n+1)/2
int expected_sum = n * (n + 1) / 2;
// Calculating the actual sum of the array elements
int actual_sum = 0;
for (int i = 0; i < size; i++) {
actual_sum += arr[i];
}
// The duplicate number is the difference between the actual and the expected sum
return actual_sum - expected_sum;
}
For modifying the array, it could be simply returned back with an extra loop and we would still have it O(2N) = O(N), so I think he has the best solution.
That exercise is mind blowing for me, even with him providing a resolution proposal
Marking a[i]-1 value as negative at each index and while doing this, if you already find a negative value, you can simply return i, because that's your duplicate value.
Take sum and subtract from sum(1 to n) to get the duplicate value.
My first thought lol!
sum(all) - n*(n+1)/2
No it won't work... If arr=1, 2,2,4 sum Of array=9, sum(1-4) =10... Subtract and you get 1 but the duplicate value is 2
@@S__ArslaanIt works. And, In the problem statement it's given that the array contains n+1 elements ranging from 1 to n. Therefore the example array you provided doesn't match the problem statement.
@@S__Arslaanthe array would be 1,2,2,3
Would it using a bitarray with the int go against the rule of using constant space? He is using now set, that's not constant space
Question asked not to modify the array
I was thinking the same.
We can again able to restore back the original elements .
for(int i=0;i
@@HariKrishnan-ff4hf without modifying the array means you can’t change its values in the first place. You should assume it’s a read-only array
The previous one I watched (product array except own number) they forgot to mention that the question states no division. That completely changes the question, I thought there's a way faster solution using division and she will probably explain it at the end, not taking the current solution serious (since I had an O(N) solution in mind using the division). Please add the full question then in an overlay so people who watch can properly code along. @Exponent. Thanks for making the content available.
Sure but in a real interview the interviewer will just point that out and even if he can't figure out the answer (tortoise and hare cycle detection), he'll be praised by the interviewer for being able to come up with this answer
good job friend!!
Summing all the elements won't work in the case you have an element duplicated more than once ,, the same for xor(xor(arr),xor(1-n)) would work only for even nuber of duplications , so i think he gave the best general solution, great job
Excellent explanation, thanks
question says only one extra duplicate and not more than once . n+1 terms and numbers ranging from 1 to n with one duplicate . 0:05
First of all he was not supposed to modify the array, if we can then we can do simple cyclic sort, its done
@@darkhunter882we can simply run extra for loop and make all values positive. And we got our input back as it is.
I have run this code, it's fails on test cases like [2,2,4,3,1].
subtract sum of 1 to n from sum of all elements present in array, simple 🙂
Iterate once finding the array sum, then subtract the sum of n numbers : Ans = ArrSum - (n*(n+1)/2)
I don't get why all these mock Interviews are skipping over the simplest/obvious solutions. It's like the candidates don't even take a minute to think about the problem and just jump straight into solutions.
The number can be repeated more than twice too. That's why it won't work.
@@sharatchandra1586 Hmmmm. Feel like someone should clarify that. Am I the only one would infer 2 times by the word duplicate?
@@sharatchandra1586, as per my understanding, duplicate means 2 unless stated otherwise.
@@sharatchandra1586 also, there are only n+1 numbers in the array, that stresses more on just one number repeated twice.
Pretty easy question
My solution:
create a Hash Set, for each number in list, add them to the hash, if it's already in it, return it (duplicated)
O(n) (1 loop)
set_nums = set()
for n in range(len(nums)):
if nums[n] in set_nums:
return nums[n]
set_nums.add(nums[n])
return -1
How would we solve if the input is [1, 100, 0, -1, 100, 50, 60]?
Duplicate Value = Sum(array) - (N * (N+1))/2. For example, Array = [5, 2, 4, 3, 1, 4], and N=5. Sum(Array) = 19, (5*(5+1))/2 = 15. Difference is the duplicate value = 19 - 15 = 4. Just iterate over array if Index is needed for duplicate value.
🤯🤯
how does it work for [2,2,2,2,2]
@@wasifnehvi7705 the diff should be within 1 and n, for your case is 4. But it turns out that the diff is 0, therefore, the input is invalid!
read the question first@@wasifnehvi7705
@@chowcao1753if you check all constraints again then you will realise that [3,3,3,3,3] is also a valid input case.
Here also all elements are ranging from 1 to 4 if size is 5.
And she is not saying element is repeated only once.
what if there is a greater element than length of array? then it will throw arrayindexoutofbound exception
yes
For me the solution is
Sum(array) - ( sum((index +1) for n indexes) - array.length)
Ultimately the idea is the sum of an array element (which has n+1 elements ) - ( sum of 1 to n elements)
Cool trick with the 2nd solution - deriving a hash from index. However, The time complexity of his 1st solution is not O(n2) but better as his inner loop has j=i+1 so the time complexity is the combinations formula i.e (n*(n-1)/2)
Correct me if iam wrong but approx that's O n^2 only.
perhaps i worded it badly (and fixed it now).. i wanted to say that the diff between the quads is big.. and that the combinations one takes far less time.. i.e O(n^2) is approx double that of O(n*n-1/2)..
Chapters (Powered by ChapterMe) -
00:00 - Introduction
00:40 - Question
01:19 - Answer
07:39 - Test cases
09:30 - Tips
you were not supposed to modify the array right
size_t FindDuplicateNumber(size_t* arr, size_t len)
{
size_t sum = 0;
for(size_t i = 0; i < len; i++)
sum += arr[i];
return sum - len * (len - 1) / 2;
}
what is this algorithm called?
@@iampavel865 I don't exactly know what you mean, but the key to this problem is, that the array consists of the first n natural numbers plus one duplicate. For the sum of the first n natural numbers you can use the Gaussian Sum Formula. Henceforth, since the array consists of exactly this sum and one duplicate number, we can retrieve the duplicate by subtracting the sum of the Gaussian Sum Formula.
@@sky_beast5129 Thank you, i did not know about this formula.
No problem. If you're wondering why my function uses len * (len - 1) / 2 for the Gaussian Sum Formula, that is because the Gaussian Sum Formula is for the first n natural numbers and the array in this problem has a size of n+1 numbers. So my variable "len" is actually equal to n+1, that's why I needed to replace each n in the formula with (n-1).
So the Formula is n * (n+1) / 2
and then becomes
(n-1) * ((n-1)+1) / 2 = (n-1) * n / 2
Or just len * (len-1) / 2 with my variable.
Using a dictionary(hashmap), adding any non existing number to it and returning the number if it exist in it with one for loop, would be O(n) too.
She asked him to keep the space complexity O(1)
yeah, but need Time Complexity to be O(N). This would be easy and just like two sum in leetcode which would use hash map
he is modifying the array which we can't do , right?
Yep.
as per the constraint yes. he modified and thus did not meet the requirements.
Here's a JS solution, using memoization, O(n) time complexity and not modifying the original array:
function findDuplicate(arr) {
const memo = {}
for (let i = 0; i < arr.length; ++i) {
if (arr[i] in memo) {
memo[arr[i]] = memo[arr[i]] + 1
} else {
memo[arr[i]] = 1
}
}
return Object.keys(memo).filter((k) => memo[k] !== 1)
}
// time complexity: O(n)
i also came up with this solution..But that's not constant extra space.. it's O(n) extra space..
def find_rep(lst):
for i in range(len(lst)):
rep = 0
if i>0:
rep= lst[i-1]
if lst[i] == rep:
return rep
return "Nothing's repeating"
lst = list(map(int,input().split()))
print(find_rep(lst))
# This will do?
You are using extra space so it failed. The correct solution is:
public static int findDup(int arr[]) {
for(int i = 0; i < arr.length-1; i++)
{
if(arr[i] == arr[i+1])
return arr[i];
}
return -1;
}
@@MoMoGammerOfficial could you explain what's wrong
Sort array and loop array compare ith and i-1 element if both are same, break loop return value
sorting the array is modifying it
@@MrHenryG123 Exactly!
@@MrHenryG123 not if it's passed in by value, she never mentioned it had to be passed in by L value reference.
Can we do sum(1 to n+1) elements - (n*(n+1)/2)=Ans
No it will fail for cases which have same number duplicated more than one time
@@sidvyas Exactly.
This solution will work for {1,44,2,44}? I think no
Nums are only in range 1 - n. So if length of arr is 4, you can only have nums from 1-3 and one duplicated number
@@itsdadannyboy ohh i see i was looking for extended solution and didnt took close look on array constraints 😅😅
They should have asked this to a math not CS student. Just sum the array and subtract the triangle formula n*(n+1)/2 to get the answer. Google rejected me twice; too bad I didn't get this problem.
Yeah too bad, you would have been rejected again. Doesn’t work for [1,1,1,2]
@@aup720 It does not work for the input [1,1,1,2] because the input is invalid. The question states, that only one number is repeated in the array.
@@sky_beast5129 The input ils perfectly valid, "repeated" doesn't mean it appears only twice. The interviewee in the video took care of checking his solution covers this case.
@@sky_beast5129input is perfectly valid
Why not just use a hashmap and store the count of each item in the array and then return the number with count 2 in the hashmap.
She said, without modifying the array but the solution provided modifies the array.
Use xor
is this correct
#include
int missing_element(const int *a,int &size){
int total_array=0;
int sum_of_n=0;
for(int i=0;i
Hey teluguanimetoon2811, thanks for solving it along with us!
Unfortunately, your solution finds the missing element and not the repeated element so it won't work for this case.
I think you might be able to tweak the logic in your code to solve this problem though. You've got this! 💪
leetcode 268 just xor all elements and 1 to n
We can count the numbers in a loop (=n), and then check if there is a number greater than one in the new array.
Am I wrong?
this would work but will not be a constant space solution.
XOR(XOR(array), XOR(1 to n))
This approach will help you to find the missing number in the array (1 to n) not to get the duplicated one
@@MahmoudAhmed-sc7jg yeah actually I need to do few more steps. After doing xor of all numbers and 1 to n, whatever the result xor will be there, i need to get the right most set bit of that xor result. Then I will xor all numbers which are having that bit set in one variable and the numbers which are not having that bit set in another variable. Now one of the variable contains the duplicate number, we can easily check that with a for loop.
Since the array was constructed with n+1 order. then following script will suffice:
int findDup(int arr[]) {
for(int i = 0; i < arr.length-1; i++)
{
if(arr[i] == arr[i+1])
return arr[i];
}
return -1;
}
But this would only work if the array is sorted.. it's not given in the question..
It works only for positive integers
Which is fine, since the problem specifies numbers in range 1 to N
(1) sum of first n numbers : n*(n+1)/2
(2) sum of elements in array : sum of first n numbers + duplicate number
ans = (2) - (1)
time = O n
space = O 1
The requirement says you cant use extra space, and you cant modify the array input as well so summing to find dup is not a solution.
Bro all these comments just use Copilot
Did he modify the array?
Yes he did, it was not what was asked at all
just sum them all?
what is the point of summing them?
you can find sum of all numbers 1 to n in constant time then you can subtract that from the sum of the array to find the number that is repeated
@@alanwang8733 have you tried this approach with some inputs?
(1,2,2)
sum of 1 and 2 is 3 sum of array is 5 duplicate number is 2 no?
int main() {
int n = 10;
int arrSum = 0;
int arr[n+1] = {1,2,3,4,5,5,6,7,8,9,10};
for(int i = 0; i
This is an incorrect answer lol should mention this solution is wrong and why in the video. This is kind of the opposite of providing good interview prep material. I would've rejected this candidate.
let tab=[1,2,3,5,4,1,6,7,8]
let repeated;
tab.forEach(val=>tab.filter(vall=>vall===val).length > 1 ? repeated=val :null )
console.log(repeated) // 1 & foreach loop doesn't change the original array