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

Evaluate Division

LeetCode ワーシャルフロイド グラフ理論 就活 Google

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

グラフ理論 TrieTree

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

First Common Ancestor

就活 binary tree グラフ理論

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)

文字列操作 LeetCode 就活 Amazon 動的計画法

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

Coins

就活 動的計画法

problem

Given a number of dollars, , and a list of dollar values for distinct coins, , find and print the number of different ways you can make change for dollars if each coin is available in an infinite quantity.

how to solve

I can solve this problem using dynamic programming

code

Remove all ads

LRU Cache (Leet Code, Amazon)

design hash cache LeetCode Google 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?

code

TopCoder srm 708c PalindromicSubseq2

TopCoder srm ハッシュ

problem

Problem Statement A palindrome is a string that reads the same forwards and backwards. For example, “abba” and “racecar” are palindromes.

An odd palindrome is a palindrome with an odd length. For example, “racecar” is an odd palindrome but “abba” is not. The middle letter of an odd palindrome is called its center.

Limak has a s consisting of N lowercase English letters.

For each valid i, let X[i] be the number of palidromic subsequences of s such that their center is s[i].

In other words: For a fixed i, there are exactly 2N-1 ways to erase some characters of s other than the character s[i]. X[i] is the number of ways of erasing for which the string that remains to the left of s[i] is the reverse of the string that remains to the right of s[i].

For each i, compute the value Y[i] = ((i+1) * X[i]) modulo 1,000,000,007. Then, compute and return the bitwise XOR of all the values Y[i].

how to solve

To solve this problem using two hash-table. I can solve this problem in O(n)

code