Build Order
problem
You are given a list of projects and a list of dependencies ( which is a list of pairs of projects, where the second project is dependent on the first project). All of a project’s dependencies must be built before the project is. Find a build order that will allow the projects to be built. If there is no valid build order, return an error.
how to solve
This problem is topological sort. Topological sort algorithm is the following approach.
- Identify all nodes with no incoming edges and add those nodes to our topological sort.
- When we do the above, decline the number of incoming edges as the out coming from the added node.
- Repeat the above, When all the nodes have been added to the topological sort, then we done.
This algorithm is executed in time complexity O(V + E).
code
Paths with Sum
problem
You are given a binary tree in which each node contains an integer value(which might be positive or negative). Design an algorithm to count the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
how to use
If I can check the all path I can find the solution in O(n2). So I suggest the optimized one. In the optimized code, I use hash-table like two sum problem. This hash-table maps from a runningSum to the number of times we’ve seen that sum. In each node, I can find the count of root path to satisfy the condition in O(1) . So time complexity is O(n) and space complexity is O(n) to have a hash table.
code
Check Subtree
problem
T1 and T2 are two very large binary trees, with T1 much bigger than T2. Create an algorithm to determine if T2 is a subtree of T1. A tree T2 is a subtree of T1 if thre exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.
how to solve
I prepare two function. One is the function to determine if the 2 tree is same or not, and the other one is the function determine if the t1 is the subtree of t2. First function is implemented to check if all element is same or not recursively.
code
return k-th to last
problem
Implement an algorithm to find the kth to last element of a singly linked list
how to solve
We use two pointers slow-pointer and fast-pointer. Firstly we proceed the fast-pointer in k step. Secondly, we move them at the same pace and slow pointer will hit the end of the linked list after k length . This algorithm takes O(n) time and O(1) space.
code
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.
