Whiteboard Interview with Arrays and Hash Maps - Whiteboard Wednesday

Check out the detailed data structures and algorithms course at www.interviewa...
Welcome to Whiteboard Wednesday where I do programming (software engineering) interview problems on the whiteboard in a real interview setting.
Problem: You are given an array of repeating numbers. All numbers repeat in an even way, except for one. Find that odd occurring number.
As we want to mimic a real interview, I don't see the problems ahead of time. I see them for the first time when I solve them here. This way, you can see my problem solving methods and how I interact with the interviewer. You also see me struggle sometimes, it's all part of the package :)
New video every Wednesday. Please like, subscribe and share!

[@lakshmikantdeshpande2347]

You can XOR all the elements to get the element which occurs odd no. Of times

[@stewartzayat7526]

Can you explain what you mean by that please?

[@jayant3622]

Xor of a number with itself is 0. For example consider the numbers are [2,2,8]. In this case xor(2,2) = 0 and then xor(0, 8) = 8 so the xor is the answer.

[@stewartzayat7526]

Ah, I see! I wouldn't have come up with that in thousand years

[@souravmandal7527]

you don't need to be concerned with the intermediate values it will be some complex bulshit but in the end all of them will cancel each other except for the number occuring odd number of times.

[@sinharakshit]

@@Bdjdiwhbkdk If you XOR 2 with 1, you will get 3. Think about it this way - convert your decimal numbers 1 and 2 into binary. Now perform XOR on them. So XOR of 01 and 10 will give 11 in binary which is 3 in decimal. Now if you XOR 3 again with 1, you will get 2. Or if you XOR 3 with 2, you will get 1. Try it with the binary conversion and you'll see the proof yourself. That's the reason why we don't need to worry about the order in which the numbers are placed. If there are repeating numbers, they'll eventually "cancel" each other out in the end and you'll get the non-repeating number as the result.

[@yasminadir]

First I want to say thank you very much for this video! I really appreciate it! I just wanted to say that in the second optimized solution you described, you said it will result in better than O(n) space complexity. I think that this is not entirely correct since you can have for example the array [1,2,3,4,5,6,7,8,7,6,5,4,3,2,1] - by the time you traverse the array and reach number eight you will have ~n/2 elements in the hash map thus still resulting in overall O(n) space complexity.

[@dave161256]

Instead of using a hash table could you use a set. When you meet an element if it is not in the set, add it and if it is in the set remove it. At the end the set should contain one element which is the element that occurred an odd number of times

[@ramrai2642]

great! this would be clean data structure-wise

[@wtfishappeninghere]

In some programming languages, a set is implemented as a hash table.

[@wtfishappeninghere]

But I think using your method would save half the space in the worst case.

[@treyquattro]

this would be the simpler solution but a set is likely to be implemented as a tree and a hash table as an array or bucket list, so you have a difference in O(logN) vs O(1) (big omega really) in terms of asymptotic analysis

[@adityadubey5204]

this is true when there is one element that occurs odd number of times and this is better

[@Code-fr8qx]

Excellent video. The only improvement would be a mic for the interviewer. It is also important for us to hear what he or she has to say, that way it simulates a real interview scenario. Regardless great video. Subbed.

[@IrfanBaqui]

Thanks for the feedback! She'll be rocking a mic in the next one :)

[@matto483]

not hearing half the content kind of kills the point, but good work.

[@ErikaJadeLives]

So if all numbers in the input array are repeating and one of the numbers repeats an odd number of times.... then the number we are looking for has to have occurred at least 3 times.... In other words, there isn't a number that only occurs once. In his example for input... the number that occurs an odd number of times only occurs once, so this would be an invalid example. Then in the code you would need to account for this. The number of occurrences must be >= 3 for the number that occurs an odd amount of times. Did anyone else catch this? What do I know though.. Just a new developer still trying to get a job. LOL!

[@affanshaikh5353]

O(n) time complexity and O(1) space complexity Just xor all the elements remaining one will be the answer!

[@chaudharychaudhary6485]

This method is quite good, If we trying to find even one. While for finding odd ones we can go for XOR.

[@IssaqAl-Ahmed]

That was an excellent video! I am sure many people will find value in this. Keep it up!

[@naktaal]

Thanks for taking the time to make this! The community could definitely use more material like this. I'm looking forward to seeing your future videos. The only recommendation I have is to get a microphone for the interviewer. She could barely be heard.

[@IrfanBaqui]

Hi naktaal, I'm glad you liked it! Will make sure to get a mic for her too, thanks for the feedback!

[@PraneethPeiris]

Let me explain my answer using XOR. If we consider any two integers in binary form, XOR operation on itself is 0. i.e. 6 = 0110 0110 0110 ^ --------- 0000 ===== So, if there are even number of occurrences of a given integer, it will produce 0 when it's XORed. When you XOR an integer with 0 (resulted from the even number of integers), you will still get the same number. i.e. 5 ^ 0 0101 0000 ^ -------- 0101 ==== Which means when you keep on applying XOR on all the integers, the integer with an odd number of occurrences will remain, irrespective of the order of the integers. Example: 3, 1, 3, 2, 3, 1, 2 (XOR is done from left to right) 11 ^ 01 ^ 11 ^ 10 ^ 11 ^ 01 ^ 10 10 ^ 11 ^ 10 ^ 11 ^ 01 ^ 10 01 ^ 10 ^ 11 ^ 01 ^ 10 11 ^ 11 ^ 01 ^ 10 00 ^ 01 ^ 10 01 ^ 10 11 The answer is 11 in binary = 3 in decimal.

[@smontiu]

It´s not neened to loop the hashtable, instead use a sum, in case of repeated number sum it´s negative, at last you will have the return value

[@jamesmay1900]

SELECT a.val AS [oddly repeating value] , SUM(COUNT(a.val)) AS [count of repetition] FROM array as a GROUP BY a.val HAVING MOD(SUM(COUNT(a.val)),2) > 1

[@congdoan2006]

Thank you very much for your helpful video. In your code, the worse space complexity is O(# of distinct values in the input array). If values are integers then we can use XOR operator to have an elegant implementation, which is go through the array to perform XOR all the elements together. The end result is the odd recurring number. This is true because XORing any integer any even number of times yields zero whereas this will yield that integer itself for odd number of times.

[@iftak01]

Thanks 🙏 😊

[@georgepetrosyan4589]

I think use some additional functions like python funcs to check number is not correct. My first solution was use hashmap int int, Second same as first but hashmap int bool, Third use unordered set to add/remove number(solution 2 of this boy) One more. May be use first of all sort function, an then go throw the array ,get first number,set flag to true then go until next value will not be equal on each step change flag true to false and false to true. If in some step i, arr(i)!=arr(i+1) check flag if it true then value is odd and return, if it even then continue.

[@samanrajaei8129]

XOR would be the simplest as suggested by a few others. If I was doing your solution, I'd add the new 'unvisited' element to a stack, pop the element when I see it next and whichever elements stays in the stack at the end is your guy.

[@philbowden]

That was great thank you! Wish I could have heard the interviewer...but oh well:-)

[@thatbeastabdul]

Love the video, man! One suggestion I have is to just use a HashSet instead of a HashMap since a key only exists in the map with an associated value of 'true', so the mapping becomes redundant. Other than that, great video and I look forward to the rest of the videos in this series.

[@IrfanBaqui]

Thanks for the feedback, Abdul! That's definitely another way to do it.

[@HarshilLodhi]

Great explanation. Is the expectation of a O(1) space complexity valid for this question. I am thinking of a solution using XOR

[@IrfanBaqui]

Thanks! And yes, that's valid.

[@guitarockdude]

Space Complexity: O(n) Time Complexity: O(n)

[@youcan4913]

Write a code to.find a balance point in any array with time complexity of O(n) and a constant space complexity.

[@adrianharo6586]

Balance point?

[@TeeheeTummytums503]

Thanks for the video, friend.

[@vsigal]

Odd-way number is unique. Do not need to iterate huge array - break the loop. In Python3: for x in set(numList): if numList.count(x)%2 : print(x) break

[@crothert]

thank you so much for this free content you are king xD

[@jamezjaz]

Insightful! Thanks for sharing

[@farhad5287]

the space complexity of your solution is not O(1) if the question asks so. Example: [1,2,3,2,3]

[@tannerbarcelos6880]

The initial thought was use a hashmap, and return the key who’s value is odd. Which is fine. However that two separate loops. It all truncates to O(n), but it could be optimized further such that we only need one loop. And I think a good way of doing it would be to use a set that stores an element you have seen, and if you encounter it again in your traversal, remove it from the set and you would know that that’s been at least two times you’ve seen it and unless you see it again, that occurred evenly so we continue. At the end of the loop, you are guaranteed to have seen a value that never leaves the set, thus yielding your final answer which is just the first element in the set. You sacrifice some space, sure, but the time is better, and the space really wouldn’t be insanely hindered. Great optimization!

[@safiyapathan7510]

Thanks for creating this video! It really gives me a good idea on how to structure a problem on the whiteboard. What do you think about covering other data structures and some advanced material?

[@IrfanBaqui]

Glad you liked it! The first video is fairly easy because I want you to focus on the process rather than the problem itself. I'll cover moderate to hard problems in the next videos, so stay tuned!

[@debdutsaha4316]

at first we can sort the array in O(logn) and then we can iterate through the sorted array and count the occurence of the numbers and then whenever we find number of occurence is odd then we can break the loop in case of hashmap it is taking space complexity as well. So overall in worst case senario it is O(n) not as mensioned 2O(n).

[@mereum9669]

Why do we need to decrease the number of keys in hashmap? Space complexity is defined by the largest amount of memory that is used at certain time during the program, so the last modification to shorten a hashmap is not doing anything in this case, is it?

[@bensmith9253]

Great video

[@rrsqrd4932]

Excellent video. I am preparing for this exact scenario. You explained your thoughts and solution to this problem very clearly. I definitely learned something new! thank you

[@rafaelcupello2549]

Nice!!!!!!!!!!!!!!!!!!!

[@TeCHnoMonkeys]

Great vid

[@francisaiello6197]

Great idea Irfan - my only comment would be that in the future - I would repeat the question (difficult to hear interviewer)

[@Patrickedoherty]

Brilliant videos and its excellent to see your raw thought processes. Thanks dude, I'm loving this channel.

[@ThePolaris87]

Excellent example! Will definitely subscribe to this series of videos.

[@Jubanjan]

with python dictionary this becomes dead easy! Is that allowed in interview?

[@shafidayatar4249]

Why not use HashSet instead. Logic is very good!

[@samarthtandon2163]

Code this on python is bit easy...

[@fmango]

hmmm how would you code this in java tho?

[@rizzwanofficial6373]

if no of any of digits would be 3 like [ 1, 4, 1, 4, 1, 6, ] then what will be the result

[@charulsaxena4242]

I would also be interested in the reply. There can be a scenario where even 2 of the numbers in the array are occurring odd time. What is the result then. Where are we checking that.

[@rolandgavrilescu3099]

Very helpful, thanks!

[@neerajkungwani6295]

Awesome !! Keep doing the good work

[@KevinFash]

Very Helpful. Hope you continue making these.

[@IrfanBaqui]

I'm glad you found it helpful, Kevin. There's more to come, so make sure you subscribe :)

[@parvezrafisparta]

Great irfan!!!

[@arjuns.3752]

Sort the array using inbuilt function and count frequency of each number in 1 for loop.if ..... Count%2!=0 Print number and then break loop

[@alexsky88749]

Excellent interview training video! I learned a lot on how to behave and explain.The logic is fluid and good too.

[@devyashsanghai585]

Another solution, If I am not wrong would be to take and xor sum of all the number in the array. It will return the number that is repeated odd number of times.

[@ramrai2642]

Sounds like this is most optimal so far: i.e XOR of all elements together is the answer

[@jonjrodriguez]

Thanks for the video. I subscribed but do have some feedback. 1. The code you wrote isn't valid javascript. I know you said it was pseudocode at the end, but from my experience the code should be valid (or at least close). 2. Final solution wasn't the optimal solution (can be done in O(n) time and O(1) space). I know it's the first time you're seeing the question and we don't all get the optimal solution, but it would be good to quickly talk about the optimal solution in the end review. Thanks again and looking forward to more.

[@IrfanBaqui]

Jonathan Rodriguez Thanks for the feedback!

[@MylesGmail]

Ty. I tweeted this.