# 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?

# 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 2^{N-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.