Are you gonna do more interview questions? Really love your videos, imo the best interview question channel on KZitem with clearest and best explanation. Please do more!!
@ByteByByte
7 жыл бұрын
Yep I definitely am. I really appreciate the support and I hate leaving you all hanging! Things have been very hectic at work so I haven't had a lot of time, but I'm going to try to post more regularly. Thanks for hanging in there :)
@baravi2005
7 жыл бұрын
Really awesome videos Sam...keep them coming!
@ByteByByte
7 жыл бұрын
thanks :)
@smirkedShoe
5 жыл бұрын
Using a HashSet doesn't make the size O(n) because it's a dynamic data storage and it will vary with the size of input array???
@QDem19
6 жыл бұрын
Great solution, but isn't introducing the hashset adding O(N) space complexity, it does not look like O(1) any more.
@ByteByByte
6 жыл бұрын
We're not counting that because it is just being used to store the final result/what is being returned
@QDem19
6 жыл бұрын
Okay, now if you were using the Hashset approach instead of the index approach then the hashset would have held the final result as well - so would you call that O(1) as well? I do not mean to start an argument, I would just like a discussion.
@ByteByByte
6 жыл бұрын
No it's a totally valid question. Basically we don't count the space that is explicitly used to store the input or the output, but every other space we use counts towards our space complexity
@aleksandarrusinov9974
5 жыл бұрын
Actually in the current solution you DO use additional space because you return a newly created ArrayList from the Set, until the next garbage collection you will have 2 * n additional space n of which is not needed!
@aleksandarrusinov9974
5 жыл бұрын
Actually you can refactor the function return type to Set instead of List - therefore the user will know that this function returns distinct elements every time.
@puneetdawer8657
4 жыл бұрын
What happen if input is [3,1,3] ? Answer should be [3] but with this solution it will give Array index out of bound. Input is satisfying criteria 1
@brent...
2 жыл бұрын
You have indices 0, 1, and 2. He checks or negates abs(val)-1. The maximum val is 3. abs(3)-1 = 2. 2 is in the set (0, 1, 2). What's the issue?
@PavelPalancica
6 жыл бұрын
Thanks for the video, Sam! This is my Swift implementation if anyone is interested: (Note that I created a copy of numbers from the beginning, cause I don't want to have any side effect. Plus, Swift won't even allow us to change numbers as is (it's a let constant, unless we add the inout after the colon, which will allow us to change it directly.) func duplicates(numbers: [Int]) -> [Int] { var resultSet = Set() var numbersCopy = numbers for i in 0..
@ByteByByte
6 жыл бұрын
Thanks for sharing. If you're interested in doing so, I'd love to have you create a PR and add your code on github! github.com/samgh/Byte-by-Byte-Solutions
@ROFEL
5 жыл бұрын
The encoding solution only works if the numbers in the array are within the size of the array.
@umapathybabu8397
5 жыл бұрын
can you use without modifying array?
@SmartProgramming
6 жыл бұрын
amazing explanation bro, thanks a lot for sharing this tutorial 👍👍🙂🙂
@ByteByByte
6 жыл бұрын
thanks!
@ashutoshbichare
4 жыл бұрын
a=[1,2,3,5,7,3,2] b=[] s=set(a) for i in s: b.append(i) print(b) #output: [2,3]
@samiahmadkhan2865
6 жыл бұрын
How is your Space Complexity O(1) ? Ain't you using HashSet? (Perhaps O(n) space complex??)
Your solution does made sense until u said u would use a set at last. Lol. All of the encoding logic got wasted making no much difference from the general O(N) solution.
@joydas1685
6 жыл бұрын
Simple and easy to understand explanation. Thank you sir. Sir can you post videos on how to use dynamic programming and greedy
@TheSrini007
6 жыл бұрын
I was thinking like counting sort, but the flipping of the sign to encode is even better!
@ujurak3899
4 жыл бұрын
It's pass by value, so isn't resetting the array unnecessary?
@allinoneuniverse9673
4 жыл бұрын
I had one list which contains n no.of numbers My list = [1,2,3,4,2,2,1,4,4,4,5,5,6,7,6,5] For this list I'm applying absolute techniques. It shows mess values. Do you clarify my question?
@soudiptadutta6886
6 жыл бұрын
Sam, this method is really good but we can use just HashMap to solve the question also. The solution is : int a [] = {1, 6, 5, 2, 3, 3, 2, -6}; Map map = new HashMap(); for(int i = 0 ; i < a.length;i++) { int r = a[i]; if (map.containsKey(r)) { System.out.println("duplicates => " + r ); }else { map.put(r, 1); } }//for
@SarveshDeshmukh
6 жыл бұрын
Keep up the good work!
@ArjunKalidas
4 жыл бұрын
Great explanation! Keep em coming. Thanks a lot. I liked the way you explained the problem solving approach and how you derived an optimized solution starting from brute force.
@vrushankdoshi7813
4 жыл бұрын
How can we approach the same problem with O(N) and O(1) space without modifying the array ?
@swagatochatterjee7104
4 жыл бұрын
Excellent approach. However the question is how did you come up with this? Is this a general strategy (like prefix sum) then what are some other examples where this strategy is useful? I mean I find array manipulation questions hard, over questions involving Trees and Linked Lists because it appears every Array-ish question involves a different strategy altogether, whereas the Trees and Linked List is about recursive subtree traversal and pointer manipulation respectively.
@nicolaswolyniec1354
6 жыл бұрын
wow! crazy idea! I love it. thanks a lot :D
@ByteByByte
6 жыл бұрын
thanks!
@cloudexpress9694
4 жыл бұрын
This is excellent. Thank you for sharing knowledge for free.
@santokhsingheng
4 жыл бұрын
Perhaps bitset can be used instead of hashset to check for duplicates and would it count as O(1) space? clever solution BTW
@daixtr
5 жыл бұрын
I'm curious if there is standard name in the CS literature about this self-referencing short circuit style algo. I saw this concept in other site. Is there a known inventor of this algo?
@vinithalampally1581
6 жыл бұрын
What if there are three duplicate elements it will print same element twice na?correct me if I am wrong..
@LudwigvanBeethoven2
5 жыл бұрын
So if we dont come up with this smart ass solution they decline us? I could guessed first 3 solution. But not the last one.
@selvaganesh138
5 жыл бұрын
For the input of [3, 3, 3], this logic return [3] or [3, 3]. i am pretty sure, this returns [3, 3]. But it supposed to be [3]. Am I right.?
@StarPlatinum3000
5 жыл бұрын
That's why he uses the HashSet data structure. A set can only have one entry even with multiple insertions at the same place. Finally the set is converted to an ArrayList, which turns the result into a standard List.
@batmansmk
7 жыл бұрын
Why did you not create an auxiliary structure (boolean array) for clarity and speed? The optimal space aspect of the presented algorithm assumes that we are storing the integer in a suboptimal structure knowing the constraints (aka signed integer instead of unsigned) :) good video anyhow
@ByteByByte
7 жыл бұрын
That's a valid point, although really that gets rid of the whole challenge of the problem. And there is also overhead of having multiple arrays, but there you go. Proves there are always tradeoffs
@amolgaikwad8937
6 жыл бұрын
Nice!! But how about the case arr[5,5,6]. Here the logic will fail.
@ByteByByte
6 жыл бұрын
That input is invalid
@seniorobjective7649
7 жыл бұрын
While being out of my depth, I'm enjoying these videos a lot. I'm at a point in college where we are focusing in on the high level concept of algorithms and data structures along with some basic implementations, what advice could you give to someone who wants to nail these foundations?
@ByteByByte
7 жыл бұрын
Here's an overview of how I suggest you approach studying, but feel free to comment or email me if you have any other questions :) www.byte-by-byte.com/optimize-studying/
@MrMikomi
6 жыл бұрын
I was about to say that I didn't get it. But I see now. He's just using the ability to flip the sign of an element's value as a simple boolean. Very clever. I wonder who first came up with this. For all we know it might have been some geezer in 1972.
@ByteByByte
6 жыл бұрын
"some geezer in 1972" describes most of the algorithms we use
@Loppy2345
6 жыл бұрын
Good explanation, much better than Geekforgeeks.
@ByteByByte
6 жыл бұрын
thanks!
@shreejitnair2174
6 жыл бұрын
wow Sam that was a great solution. How does one think through such solutions?? Looking at the approach it made great sense to me but at first glance I could have never been able to conjure up something like this. How does one build such intuition? Does it just come with solving a lot of problems? If we were able to come up with the hashset or sorting approaching and the interviewer expected us to do better would it be ok to ask them for some guidance?
@ByteByByte
6 жыл бұрын
Check out this post: www.byte-by-byte.com/stuck-on-coding-interview/
@mustapharaimilawal8053
5 жыл бұрын
Awesome video, please do more.
@GaneshShinde-qx2ey
5 жыл бұрын
what if my array contains negative duplicates?
@ByteByByte
5 жыл бұрын
Read the problem definition again
@jlecampana
5 жыл бұрын
One really quick Question Sam: During a Live phone Interview, are candidates allowed to type in their analysis of how to solve a problem like you do, prior to actually typing in the code that solves the problem? -Thanks!
@eile4219
4 жыл бұрын
I don't think phone interview will ask this question. You should always analysis and discuss with your interviewer. We are not looking for the answer. We are looking for the process. I fail people who just give the answer without saying anything
@michaelmast6725
6 жыл бұрын
No reason at all to use the unordered set to store results. You're already making a second pass to restore the input array, just build the result vector during that pass. Saves you a set->vector conversion as well.
@harshpatel105
5 жыл бұрын
You will have to worry about duplicates in vector for each element, add element only if it's not present. It will make it O(N^2) even we consider vector only
@gurmeetchawla8362
6 жыл бұрын
if the purpose is to just find the duplicates then if we keep spitting the element when you find arr[index] < 0 instead of storing it in the result set, that way you don't need to store and also you don't need to scan again.
@ByteByByte
6 жыл бұрын
What exactly are you suggesting?
@MrStevepm
6 жыл бұрын
Can't you just add every element to the HashSet, convert it, and you're done?
@ByteByByte
6 жыл бұрын
We're trying to find the duplicated items, though. Not deduplicate the array
@avinashpathak7563
5 жыл бұрын
what will happen when arr is [10,10,10,0,0,0]
@StarPlatinum3000
5 жыл бұрын
The question already has the constraint that the numbers will range from 1 to input-size. So this would be an illegal input, or rather, a different problem, where the best solution would probably become a direct "hash map/set for all input numbers" approach. The question is given at: www.byte-by-byte.com/findduplicates/ leetcode.com/problems/find-all-duplicates-in-an-array/
@sharmaanshulmca
6 жыл бұрын
For the case [1, 2, 2, 3, 3, 6] the solution is returning only 2, could you confirm me if I am missing something as all the values are 1
@ByteByByte
6 жыл бұрын
How did you test it? It should work for that case. If you download the code from the github repo (linked in the blog post) it works for the example you gave
@sharmaanshulmca
6 жыл бұрын
Thanks for your reply, I verified my code by comparing yours. Your solution is working correctly, I had error in my Swift code. Thanks a lot, Your posts are really helpful for me to prepare for interviews.
@srjsunny7941
5 жыл бұрын
Good logic.
@ankitajain4194
5 жыл бұрын
what if array element is negative?
@ByteByByte
5 жыл бұрын
Then it's not a valid input
@babumon5351
6 жыл бұрын
Awesome logic..Thanks
@ByteByByte
6 жыл бұрын
you're welcome!
@piyushsharma1638
6 жыл бұрын
it doesn't work for test case like [0,1,2,1], gives out of bound error.
@ByteByByte
6 жыл бұрын
1
@princeilu96
6 жыл бұрын
can't we modify this program for an arrray including 0 in it?
@TheZiZaZo
7 жыл бұрын
What if the set was [12 , 3, 2, 12]. That would set the index to 11. Making arr[index] Out of bounds. Or am I missing something?
@ByteByByte
7 жыл бұрын
That would be an invalid input. Don't forget the invariant: each value 1
@TheZiZaZo
7 жыл бұрын
Ahhh! Missed that part
@piyushsharma1638
6 жыл бұрын
it fails for test case like [0,1,2,1] too. REPLY
@PavelPalancica
6 жыл бұрын
That's invalid input too. An array of size 4 can only contain any item(s) from the set { 1, 2, 3, 4 }. None of the input array should contain 0. Pay attention to the details in the problem specification.
@dimpalbhatia5037
6 жыл бұрын
How to find common element in each row of 2D array Like we have array 23 96 74 10 85 11 12 96 2 22 96 11 85 52 10 96 Output should be :- 96 becoz 96 is common in all rows How to do this ??
@ByteByByte
6 жыл бұрын
You tell me. What would be the first step here?
@MrAkshay2711
6 жыл бұрын
you can apply BFS in matrix
@brucechen6052
5 жыл бұрын
What about [0,0,0]
@harshpatel105
5 жыл бұрын
You fuck read the question. Number ranges from 1 to N
Пікірлер: 94