Interview Prep #1 : Hashmaps

  Data Structure Prep #1: Hashmap 

by Ashur Baroutta

    With internship and job interviews heavily reliant on testing proficiency in data structure and algorithm knowledge, I thought it wise to pursue learning more about some key concepts and solving more challenging problems. Hashmaps can be thought of as data structures that store key-value pairs, for every key there is a corresponding value.  The reason they're important to know is due to their time and space complexity. 

    Let's take a look at what that means in practice.  Our problem, this is one of several potential problems commonly given in internship interviews for top tech companies, states "given an integer array "nums", return true if any value appears at least twice in the array, otherwise return false if every element is distinct. Simply put, we're to check if a given array has a duplicate. 

    Many students, raises hand, try to brute force this problem with a nested loop solution. My nested loop code is as follows. 


    This does work, but it has massive limitations in regards to its time complexity as its O(n^2). Meaning it has to potentially iterate through a given array twice to find the duplicate as we are using nested loops (two loops). This is where hashmaps shine because with a hash map we can iterate through an array once and store values in the hashmap as we traverse the length of the array. Since we store the values as we go, we can check if the map has a duplicate value at the current stage of the traversal before we add it to the map, since if our map already contains the value then we are finished! My code submission using a hashmap is as follows.

    
    The logic is similar though the burden of computation is significantly lighter the larger our given array is. Hashmap usage is very valuable the more complex and larger a data set gets and I look forward to continuing exploring adding it to my toolkit as I solve complex problems in preparation for my upcoming internship interviews at top tech companies.



    

Comments

  1. EricaMarch 3, 2022 at 12:00 PM

    Best of luck in your interviews. Keep pushing your capabilities and they'll undoubtedly see the value you will bring with you wherever you go.

    ReplyDelete
    Replies
    1. Ashur BarouttaMarch 4, 2022 at 6:16 PM

      Thank you so much!

      I will continue pushing myself and improving my skill.

      I feel like breaking out of my review cycle was a huge step in the right direction, I'm learning alot more being hands on.

      Delete

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