Hash Table (Part 2)

Target May 20th to finish

Frequency Count

299	Bulls and Cows

If two chars  matches, add aCnt, otherwise, increase their frequency in hashMap and process bCnt in second pass (add the minimum of the two same digits frequency to B count)

554	Brick Wall

Count the frequency of each breakpoint length. And find the max frequency breakpoint length maxVal, then the wall.size() - maxVal will be the minimum number of bricks got cut.

447	Number of Boomerangs

Idea: Use each point as the first point of the tuple, calculate the distance from all the other points to this point. Any two points that have the same distance with the current point can construct a tuple that is boomerangs (n * (n - 1) / 2). And we have two answers for the two points (say b, c) that has same distance with a (i.e: a,b,c and a,c,b). We use hash map to calculate the distance from all the other points to the current point (the same distance are counted in the second of map entry).  Accumulate all the combination.

Tree

94 Binary Tree Inorder Traversal
      (a)  Recursive:  DFS(root->left, res), res.push_back(root->val), DFS(root->right, res);
      (b) Iterative:  (b.1) Use a stack st to do this. Define p and initialize it to root. While p is not NULL and the stack st is not empty(), do the following.  (b.2) while p is not NULL, keep push p into the stack and let p = p->left. (b.3) after b.2, check if the stack is not empty. If so, visit the top element and pop it and let p = p->right.

Priority Queue

347 Top K Frequent Elements   

Hash table + priority queue
(1) Use hash table to save the frequency of each number
(2) Make pairs from each pair in the frequency map ( {f.second, f.first}  or make_pair<f.second, f.first>) and push into the priority queue
(3) Pop the first k elements from the queue and push into the result array and return it.

A slightly better way is only push (N - k) elements  on to the priority queue, after that pop the top and then push the next pair made from the map element. repeat this k times.

692

Top K Frequent Words

 Similar to 347 above.
Only different is we have to define a customized compare function for priority_queue to  make sure that words of the same length are outputted in the ascending order of alphabet. 
We can define as follows:
typedef priority_queue< pair<int, string>, vector<pair<int, string> >, decltype(comp) > PQT;
PQT pq(comp); // Don't forget pass comp to pq definition.

        
 Here we are sort the queue using descending order of frequency of words.
 and ascending order of alphabet order for words with the same length, that's

 why we use '<' for first and '>' for second. :-). Please remember that the default heap in C++ STL is max heap, which using smaller<int>(), we can pass in greater<int>() for the third parameter to make a min heap. So we can consider that max heap is made from ascending order while min heap is made from descending order. We know ascending using '<' while descending using '>' for other containers like vector. 

        auto comp = [&] (const pair<int, string>& a, const pair<int, string>& b) {
            return (a.first < b.first) || (a.first == b.first && a.second > b.second);
        };   

O(KlgN) time, O(N) space if no optimization (O(N - K)) space with opt.
Since insert into the heap is O(1) delete top from heap is O(lgN), we do K times of the deleting from the heap.

 

Sort 

451.  Sort Characters By Frequency  
Solution 1: Bucket sort
(1) Count the char frequency in the input string s (n = s.size()) using map
(2) Initialize a bucket using vector of string which has size n + 1
(3) For loop each map element  m and append  m.second number of m.first to the bucket at position m.second.
(4) Backward for loop the bucket and append each bucket string to the result string and return the result string after.

Solution 2: using STL sort with customized compare function
(1) Count the char frequency in the input string s (n = s.size()) using map
(2) call sort(s.begin(), s.end(),  [&](char a, char b) { return mp[a] > mp[b] || (mp[a] == mp[b] && a < b); });

  
 676 Implement Magic Dictionary  
 

Idea:

Fuzzy match

Time Complexity:

buildDict: O(n*m)

n: numbers of words

m: length of word

search: O(m)

m: length of word

Space Complexity:

O(n*m)

Stack

739. Daily Temperatures  

Define a stack, and initialize the N value of result array to all zero
(1) Loop the temperature array backward.  Use the stack to save the temperature index looped.
(2) While the stack is not empty and the current temperature is greater than the temperature at stack top index, pop the stack.
(3) set result array value at the current temperature index j to 0 if the stack is empty. Otherwise to stack top value minus j.
(4) push j to the stack
(5) return the result array.

811	Subdomain Visit Count

- first split your cpdomain into int n and string s
- then parse s backwards looking for '.' and do a += n to a hashmap with the substring for domain
- make sure to add the whole domain to hasmap when you hit beginning of line
- create vector of strings at the end from hashmap and return

599	Minimum Index Sum of Two Lists

Using HashMap (linear)

We make use of a HashMap to solve the given problem in a different way in this approach. Firstly, we traverse over the whole $list1$ and create an entry for each element of $list1$ in a HashMap $map$, of the form $\left(list\right[i],i)$. Here, $i$refers to the index of the $i^{th}$ element, and $list\left[i\right]$ is the $i^{th}$ element itself. Thus, we create a mapping from the elements of $list1$ to their indices.

Now, we traverse over $list2$. For every element ,$list2\left[j\right]$, of $list2$ encountered, we check if the same element already exists as a key in the $map$. If so, it means that the element exists in both $list1$ and $list2$. Thus, we find out the sum of indices corresponding to this element in the two lists, given by $sum=map\mathrm{.}get\left(list\right[j\left]\right)+j$. If this $sum$ is lesser than the minimum sum obtained till now, we update the resultant list to be returned, $res$, with the element $list2\left[j\right]$ as the only entry in it. 

If the $sum$ is equal to the minimum sum obtained till now, we put an extra entry corresponding to the element $list2\left[j\right]$ in the $res$ list.

609	Find Duplicate File in System

Idea is simple: Use a hashmap with names vectors to store all files contents, and then prints the duplicates

the time complexity is O(n^2 * k) since in worse case we might need to compare every file to all others. k is the file size, n is the number of input files.

However, In a real life solution we will not hash the entire file content, since it’s not practical ( a file system would have GB even TB size). Instead we will first map all the files according to size. Files with different sizes are guaranteed to be different. We will than hash a small part of the files with equal sizes (using MD5 for example). Only if the md5 is the same, we will compare the files byte by byte

748	Shortest Completing Word

(1) Make the pattern by appending only alpha letters to the pattern (ignore space and other chars)
(2) For loop each word and check whether the current word contains the pattern and has a smaller length using a find function.  If so update both the length and result word string.
(3) the find function using hash map to count both the frequency of chars in the pattern and word. Make sure all the chars frequencies in pattern less than or equal to the char frequencies in the word, only so return true. else return false.

525	Contiguous Array

In this approach, we make use of a $count$ variable, which is used to store the relative number of ones and zeros encountered so far while traversing the array. The $count$ variable is incremented by one for every $$ encountered and the same is decremented by one for every $$ encountered.

We start traversing the array from the beginning. If at any moment, the $count$ becomes zero, it implies that we've encountered equal number of zeros and ones from the beginning till the current index of the array($i$). Not only this, another point to be noted is that if we encounter the same $count$ twice while traversing the array, it means that the number of zeros and ones are equal between the indices corresponding to the equal $count$ values. 

System Design

355	Design Twitter

Complexity: O(1) post/follow/unfollow, O(n + k log n) newsfeed for getting k tweets from n followed users, with the O(n) part coming from constructing the heap of followed users (see below), as correctly noted by @poligun.

Use std::vector to store tweets, std::unordered_set to store followed users, std::unordered_map to associate each user with their tweets and followed users.

Use a heap to merge most recent k tweets from followed users. std::make/push/pop_heap provide finer control than std::priority_queue.