You are given a binary tree in which each node contains an integer value. Find 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). The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Given two strings s and t, write a function to determine if t is an anagram of s. For example, s = “anagram”, t = “nagaram”, return true. s = “rat”, t = “car”, return false. Note: You may assume the string contains only lowercase alphabets. Follow up: What if the inputs contain unicode characters? How would you adapt your solution to such case? Solution: public class Solution { public

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1. For example, 123 -> "One Hundred Twenty Three" 12345 -> "Twelve Thousand Three Hundred Forty Five" 1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven" Hint: Did you see a pattern in dividing the number into chunk of words? For example, 123 and 123000. Group the number by thousands (3 digits).

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. For example, given s = “catsanddog”, dict = [“cat”, “cats”, “and”, “sand”, “dog”]. A solution is [“cats and dog”, “cat sand dog”]. Solution 1: Time Limit Exceeded public class Solution { public List<String> wordBreak(String s, Set<String> wordDict) { Map<Integer, List<String>> dp = new HashMap<>(); int n = s.length(); List<String> tmp = new ArrayList<>(); tmp.add(""); dp.put(n, tmp); for(int i=n-1; i>=0; i--){ List<String> list = new ArrayList<>(); for(int j=i+1; j<=n; j++){ String str = s.substring(i, j); if(wordDict.contains(str)){ for(String suffix : dp.get(j)){ list.add(str + (suffix.isEmpty() ?

Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word. For example, Given words = [“oath”,“pea”,“eat”,“rain”] and board = [ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v'] ] Return [“eat”,“oath”]. Note: You may assume that all inputs are consist of lowercase letters a-z.

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters. For example, given: s: “barfoothefoobarman” words: [“foo”, “bar”] You should return the indices: [0,9]. (order does not matter). Solution: public class Solution { public List<Integer> findSubstring(String s,

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation. For example: Given “aacecaaa”, return “aaacecaaa”. Given “abcd”, return “dcbabcd”. Solution: public class Solution { public String shortestPalindrome(String s) { String str = s + "#" + new StringBuilder(s).reverse().toString(); int[] table = new int[str.length()]; for(int i=1; i<str.length(); i++){ int j = table[i-1]; while(j>0 && str.charAt(j)!=str.charAt(i)) j = table[j-1]; table[i] = j + (str.charAt(j)==str.charAt(i) ?

You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north, then x[1] metres to the west, x[2] metres to the south, x[3] metres to the east and so on. In other words, after each move your direction changes counter-clockwise. Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not. Example 1:

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. Examples: [2,3,4] , the median is 3 [2,3], the median is (2 + 3) / 2 = 2.5 Design a data structure that supports the following two operations: void addNum(int num) - Add a integer number from the data stream to the data structure.

Implement regular expression matching with support for ‘.’ and ‘*‘. '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples: isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false isMatch("aa", "a*") → true isMatch("aa", ".*") → true isMatch("ab", ".*") → true isMatch("aab",