Back to top

Hash Table

Overview

A hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. In the subsequent sections, we will be providing different patterns of programming questions commonly asked in coding interviews which can be solved using hash table. We don’t want to overwhelm our readers with a plethora of hash table questions. So, we have done the heavy lifting for you by going through almost all the questions on leetcode and categorizing the different patterns of questions commonly asked in the interviews.

Pattern -1 : Deep copy of objects

Prob 138 - Copy List With Random Pointers

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

       /**
         * We need to deep copy a list with random pointers
         * https://leetcode.com/problems/copy-list-with-random-pointer/
         *
         * Approach: We maintain a map to store the mapping between the
         * old and new node. We then just iterate through the original
         * list and use the new nodes for mapping.
         *
         * Time Complexity: O(n)
         * Space Complexity: O(n)
         *
         * @param head of the old list
         * @return head of the new list
         */
        public Node copyRandomList(Node head) {
            Map<Node, Node> map = new HashMap<>();

            Node run = head;
            while (run != null) {
                Node newNode = new Node(run.val);
                map.put(run, newNode);
                run = run.next;
            }

            run = head;
            while (run != null) {
                Node newNode = map.get(run);
                newNode.next = map.get(run.next);
                newNode.random = map.get(run.random);
                run = run.next;
            }

            return map.get(head);
        }

       class Node {
            int val;
            Node next;
            Node random;

            public Node(int val) {
                this.val = val;
                this.next = null;
                this.random = null;
            }
        }

Pattern -2 : String Manipulation

Prob 3 - Longest Substring Without Repeating Characters

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

       /**
         * We need to find the longest substring without repeating characters in a string.
         * https://leetcode.com/problems/longest-substring-without-repeating-characters/
         *
         * Approach: We will maintain a map to store mapping between characters of a string
         * and its index in the string. If a character has repeated, then remove the characters
         * before the index on which the character occured before.
         *
         * Time Complexity: O(n) as the character would be added and removed just once
         * Space Complexity: O(n)
         *
         * @param s - the input string
         * @return the length of longest sub string
         */
        public int lengthOfLongestSubstring(String s) {
            if (s.length() == 0) {
                return 0;
            }
            Map<Character, Integer> map = new HashMap<>();
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if(map.containsKey(c)) {
                    int lowerIndex = map.get(c);
                    List<Character> toRemove = new ArrayList<>();
                    for (Map.Entry<Character, Integer> entry : map.entrySet()) {
                        if (entry.getValue() < lowerIndex) {
                            toRemove.add(entry.getKey());
                        }
                    }
                    for (char ct : toRemove) {
                        map.remove(ct);
                    }
                }
                map.put(c, i);
                max = Math.max(max, map.size());
            }
            return max;
        }

Prob 438 - Find all Anagrams

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

       /**
         * We need to find start indexes of p's anagram in s
         * https://leetcode.com/problems/find-all-anagrams-in-a-string/
         *
         *
         * Approach: We use a map to maintain the frequency of characters
         * in p. We then use a separate map to maintain the frequency of
         * characters in s string. After that, we keep on removing the
         * old character and adding new characters in the map.
         *
         * Time Complexity : O(n)
         * Space Complexity: O(n)
         *
         *
         * @param s - the text string
         * @param p - the pattern string
         * @return - indexes of the p's anagrams
         */
        public List<Integer> findAnagrams(String s, String p) {

            if(s.length() < p.length()) {
                return new ArrayList<>();
            }

            List<Integer> res = new LinkedList<>();
            Map<Character, Integer> patternMap = new HashMap<>();
            for (char c : p.toCharArray()) {
                patternMap.put(c, patternMap.getOrDefault(c, 0) + 1);
            }

            Map<Character, Integer> textMap = new HashMap<>();
            for (int i = 0; i < p.length(); i++) {
                char c = s.charAt(i);
                textMap.put(c, textMap.getOrDefault(c, 0) + 1);
            }

            if (patternMap.equals(textMap)) {
                res.add(0);
            }

            for (int i = p.length(); i < s.length(); i++) {
                char newChar = s.charAt(i);
                char oldChar = s.charAt(i - p.length());
                if (textMap.get(oldChar) == 1) {
                    textMap.remove(oldChar);
                } else {
                    textMap.put(oldChar, textMap.get(oldChar) - 1);
                }
                textMap.put(newChar, textMap.getOrDefault(newChar, 0) + 1);

                if (patternMap.equals(textMap)) {
                    res.add(i - p.length() + 1);
                }
            }
            return res;
        }

Prob 76 - Minimum Window Substring

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

       /**
         * We need to find the minimum window in S which contains all
         * characters in string T
         * https://leetcode.com/problems/minimum-window-substring/
         *
         * Approach: We store the frequency of all character of T in
         * a map. We will then store the frequency of characters of S
         * in a separate map.
         *
         * After that, we remove the redundant characters by comparing
         * against the goalMap. We will then capture the minimum length
         * of the string.
         *
         * Time Complexity: O(n)
         * Space Complexity: O(n)
         *
         * @param s
         * @param t
         * @return
         */
        public String minWindow(String s, String t) {
            Map<Character, Integer> goalMap = new HashMap<>();
            for (char c: t.toCharArray()) {
                goalMap.put(c, goalMap.getOrDefault(c, 0) + 1);
            }
            int min = Integer.MAX_VALUE;
            int i = 0, totals = 0;
            Map<Character, Integer> elementMap = new HashMap<>();
            String result = "";
            for (int j = 0; j < s.length(); j++) {
                char c = s.charAt(j);
                if (!goalMap.containsKey(c)) {
                    continue;
                }

                int count = elementMap.getOrDefault(c, 0);
                if(count < goalMap.get(c)) {
                    totals++;
                }

                elementMap.put(c, count+1);

                if(totals == t.length()) {
                    while (!goalMap.containsKey(s.charAt(i)) || elementMap.get(s.charAt(i)) > goalMap.get(s.charAt(i))) {
                        char pc = s.charAt(i);
                        if(goalMap.containsKey(pc) && elementMap.get(pc) > goalMap.get(pc)) {
                            elementMap.put(pc, elementMap.get(pc) - 1);
                        }
                        i++;
                    }
                    if (min > j-i+1) {
                        min = j - i + 1;
                        result = s.substring(i, j +1);
                    }
                }

            }
            return result;
        }

Pattern -3 : Graph Traversal

Prob 743 - Network Delay Time

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

       /**
         * We want to know how long will it take for all nodes in the network
         * to receive the signal.
         * https://leetcode.com/problems/network-delay-time/
         *
         * Approach: We start by storing the network delays in an adjacency map.
         * We will store the delay times in an array for each of the nodes. After
         * that, we will keep on iterating through the adjacency map and update the
         * delayTimes array. The maximum value in the array will give the total time
         * to propogate the signal throughout the network.
         *
         * Time Complexity: O(M + N) where M is the size of times array
         * Space Complexity: O(M + N) where M is the size of times array
         *
         * @param times - the edges
         * @param N - number of nodes
         * @param K - source node
         * @return time to reach all the nodes
         */
        public int networkDelayTime(int[][] times, int N, int K) {
            Map<Integer, Map<Integer, Integer>> delays = new HashMap<>();
            for (int[] time: times) {
                if(!delays.containsKey(time[0])) {
                    delays.put(time[0], new HashMap<>());
                }
                delays.get(time[0]).put(time[1], time[2]);
            }

            int[] delayTimes = new int[N + 1];
            Arrays.fill(delayTimes, Integer.MAX_VALUE);
            Queue<Integer> queue = new LinkedList<>();
            queue.add(K);
            delayTimes[0] = 0;
            delayTimes[K] = 0;
            while (!queue.isEmpty()) {
                int n = queue.remove();
                Map<Integer, Integer> adj = delays.getOrDefault(n, new HashMap<>());
                for (int e : adj.keySet()) {
                    if(delayTimes[e] > delayTimes[n] + adj.get(e)) {
                        delayTimes[e] = delayTimes[n] + adj.get(e);
                        queue.add(e);
                    }
                }
            }

            int max = 0;
            for (int w : delayTimes) {
                max = Math.max(max, w);
            }

            return (max == Integer.MAX_VALUE)? -1 : max;
        }

References