Given a list of votes of pairs. Return top k votes up to a certain timestamp. TreeSet When need this kind floor/ceiling type of operations, considering using tree set. lower()/higher()/headSet()/tailSet() Use priority queue to find top k. This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To […]
Given a string and a list of words (words have same length), find all start indices of substrings that are concatenation of all words from the list exactly once. Brute Force For each index in string we check whether the substring starts with this index contains all the words. We use a hashmap store words […]
Design a system that returns the top 3 (most searched) history that matches the sentence user typed. The results are ranked based on hot degree, and break even on alphabetical order. # sign terminates the a search. Use a hashmap store sentence to its search frequency. Also maintain state of current data user has entered […]
With Duplicate Numbers Note that amortize time complexity for operations in HashSet is O(1), because its underlying is a hash map. The idea is to have first store numbers in a LinkedList (supports removeLast() because ArrayList remove() can be confusing) and a map from number to their indices in the list. Insert: append to the […]
Convert Integer to Roman The key is to have base changes from 1000->100->10->1. Each time divide the number with the base to get the current digit. Then discuss the digit case by case. (Max is 3999). [0..3]: Repeat append x number of times char mapped to base. 4: append char mapped to based followed by […]
Given a list of strings, group anagrams together. HashMap Anagrams have properties such that after sorting, they are they same. Therefore, we can use a hash map to group anagrams where keys are sorted anagrams. Time: O(n) Space: O(n), hash map. This file contains bidirectional Unicode text that may be interpreted or compiled differently than […]
Given a list of distinct words, find all pairs of distinct indices such that the combination of the two words are palindrome. Naive Solution In the naive solution, we implement a helper function uses two pointers to determine whether the combination of two string is a palindrome. Then we call this helper method for each […]
Given an array and an integer k, find the number of continuous subarrays that equals to the given target. Prefix Sum Array First calculate the prefix sum array of the given array (prefix). Then loop through all subarrays and get sum prefix[r] – prefix[l – 1]. If equals to k, increment counter. Time: O(n^2) Space: […]
Strobogrammatic Number 1 A strobogrammatic number is defined as a number that is the same after rotate 180 degree. Hash Map Strobogrammatic number are only a few: 0, 1, 8, which are strobogrammatic number to themselves. And 6, 9 are strobogrammatic number to each other. We can put the mapping into a hash map. Then […]
Given a graph, return a deep clone of it. BFS Store a map from origin node to clone node in a hash map. Traverse the original graph using BFS. i.e. using a queue. Each time remove a node from queue to process, meaning create its clone in the map (if not exist), and clone all […]
bilbo3000.wordpress.com 