Atcoder Grand Contest : B Splatter Painting
problem
how to solve
The limitation of d is very small and it is key point to solve this problem. Consider that dp[v][i] which means “paint dp[v][i] among the range d distance from vertex v”. The time complexity is O(d(n+m) + q)
code
Evaluate Division
problem
Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.
Example: Given a / b = 2.0, b / c = 3.0. queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? . return [6.0, 0.5, -1.0, 1.0, -1.0 ].
The input is: vector<pair<string, string>> equations, vector
how to solve
I can solve this problem by using Warshall–Floyd algorithm. So I have to create the adjacent matrix. To do so, I create the hash table which the key is string and the value is integer for storing the index of string. This time complexity is O(n3).
code
Trie tree
What is Trie tree?
Trie tree is a data structure of handling string. - Looking up data in a trie is faster in the worst case O(m)(m is the length of a search string). - There are no collisions of different keys in a trie. - There is no need to provide a hash function or to change hash functions as more keys are added to a trie.
Implementation
First Common Ancestor
problem
Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.
how to solve
Starting from root node and check whether p or q is existed in subtree. If left subtree includes one node and right subtree includes the other node, we can decided that the current node is lowest common ancestor.
code
Word Break (LeetCode)
problem
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.
For example, given s = “leetcode”, dict = [“leet”, “code”].
Return true because “leetcode” can be segmented as “leet code”.
how to solve
https://leetcode.com/articles/word-break/
code
LRU Cache (Leet Code, Amazon)
problem
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
Follow up: Could you do both operations in O(1) time complexity?