Interview Prep #2 : HashSets and Intersection

 Interview Prep #2 : HashSets and Intersection

by Ashur Baroutta

    Continuing to explore different problems and tools to solve them, we follow up HashMaps with HashSets. A HashSet is simply a collection of unique objects, and because it only holds unique objects it allows us to add, remove, and check if an object is within the set in constant time. It differs from a HashMap in that it doesn't contain key-value pairs as by nature it cannot have more than 1 unique element, so an element essentially acts as its own key within a set. 

   HashSets allow us to use Intersection (set1.intersection(set2)) or (set1 & set2) (& being the intersect operator in python), allows us to pull shared elements from the sets.

    Our problem asks us "Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order." 

    We could use a loop and a HashMap (similar to finding duplicates but in reverse) to identify unique elements and then return a new list of those elements. However, we ought to work smarter not harder. Expanding the toolkit is essential for making problems like this simple! 

    So knowing sets can only have unique objects/elements within their collection, we can make the given arrays (num1 and num2) sets. This removes the duplicates immediately and after making the sets, we can use intersection and return the result as a list. What does this mean? 

    For example, if num1 = [1,2,2,1] when we make it a set the duplicates are removed and so its set would be {1,2}. Say our second array (num2) is [2,2], its set would be {2}. Great, how does this help? 
Well, our desired output is the point at which these 2 arrays intersect each other, in other words, what elements do they share? 

    Here is where the intersection makes a sentence out of a paragraph.  The code for our solution to the problem is as follows. 



    Understanding the data structure and its respective methods allowed me to beat out all but the top 5% of submissions ever submitted for the problem statement! I could have used loops and a HashMap or a variety of other ways to solve this problem, but I'm happy studying and applying my newfound knowledge led to a near-perfectly optimal runtime. 


    

Comments

  1. EricaMarch 12, 2022 at 10:17 AM

    Congratulations!! It almost never works so smoothly. Enjoy the victory! 🎉

    ReplyDelete

Post a Comment

Popular posts from this blog

IP #6 : Reversing an Integer

Image
 Reversing an Integer by Ashur Baroutta     The focus of this submission will be on reversing a given integer passed into our function. Our problem statement is as follows "Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 -1], then return 0." Seems simple, though was actually a little odd. My initial reaction is to convert the integer to a string and then just reverse each character. Though in a way that feels like cheating as I don't think that solution is in the spirit of the assignment,  and it takes more resources to complete.      Pivoting my attention to a mathematical solution made the problem a lot more fun. Say our first example for x is 123. The way we attack it is to setup variables to track the reversed total and to track the remainder of a given iteration, we also create a loop iterating through while x does not equal 0.  The ...
Read more

IP#5 : LinkedList Removing Duplicates II

Image
 Removing Duplicates II by Ashur Baroutta         In our last submissions, we worked on removing duplicates, this week we look at the more complicated problem of the same type. Our problem statement is " Given the  head  of a sorted linked list,  delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list . Return  the linked list  sorted  as well ."      So not only do we have to remove duplicates, but we cannot return values that are not distinct, for example, if our list originally contained three 1's, we need to delete all the 1's in our list as even if we delete all but one of them, the number 1 itself is not a distinct value.      This took me about 3 days to think through and complete, the following is our code submission.  We start by first creating a new ListNode called newlist. We set its .next reference pointing to head (the ListNode passed ini...
Read more