Subscribed unsubscribe Subscribe Subscribe

Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

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

Remove all ads

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

Remove all ads

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

Remove all ads

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

gist.github.com

Atcoder Grand Contest : B Splatter Painting

problem

agc012.contest.atcoder.jp

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& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return 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

Remove all ads