Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

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

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)

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

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

TopCoder srm 708b BuildingStrings

problem

The score of a string is its length multiplied by the number of different characters in the string. For example, the score of “abbcdxc” is 7 * 5 = 35. This is because the length of this string is 7 and there are five different characters: a, b, c, d, x.

Bear Limak wants to find a sequence of strings satisfying the following conditions:

There number of strings is between 1 and 50, inclusive. The length of each string is between 1 and 50, inclusive. The sum of scores of the strings is exactly K. Each character in each string is a lowercase English letter (‘a’ - ‘z’). You are given the K. Compute and return any sequence of strings with the above properties. If there are multiple solutions, you may return any one of them.

code

TopCoder srm 708a SafeBetting

problem

Limak is in a casino. He has b dollars. He wants to have at least c dollars (to be able to buy flowers for a girl he likes). In order to achieve that, he must win the money he’s missing.

The casino allows guests to risk some of their money on bets. Limak can make as many bets as he likes, but he has to make them one after another. Each time Limak makes a bet, he chooses the amount he wants to bet. The amount must be a positive integer. Each bet has two possible outcomes: either Limak loses the money, or he gets it back doubled.

For example, suppose Limak has 20 dollars. If he bets 5, he will be left with 20 - 5 = 15 dollars. If he loses the bet, that is his new total. If he wins the bet, he’ll get back 2*5 = 10 dollars, which will bring his total up to 15 + 10 = 25 dollars.

Limak doesn’t want to lose all his money. More precisely, he wants to make sure that at any moment he will have at least a dollars. He will not make a bet if losing the bet would mean that he will have less than a dollars.

For example, suppose Limak currently has 20 dollars. If a = 15, in the next round Limak can bet 1, 2, 3, 4, or 5 dollars. Note that a bet of 6 dollars is not allowed: if he lost it, he would have 20 - 6 = 14 dollars, which is less than a.

You are given the s a, b, and c. We will assume that Limak follows the rules described above when choosing the amounts to bet. Compute and return the smallest B such that Limak can reach his goal (i.e., have at least c dollars) after making B bets.

code