Showing posts from September, 2017

Deleting leaves of a certain kind

Here is a problem: you're given a binary tree, say something like this: Now what we want to do is delete all the leaves from this tree whose value is equal to a certain target value. For this example's sake, the target value will be 5. That seems pretty straightforward: traverse down the tree, and the moment that you find a leave whose value equals to 5, chop it off: But hang on, what if the problem requires you to ensure that the remaining tree, after deleting any leaf whose value was 5, does not have any resulting leaf with value equals to five? Suppose for example that instead of "4", that node had the value "5": It would then trigger a cascading event where not only the "5" leaves would be deleted, but also their parent would be deleted too. This is because after deleting the "5"s, you'd end up with a new tree with new leaves whose values are also 5 :). Those should be deleted too. How to do that? A simple appr

200 problems solved on LeetCode

Howdy!!! I had solved 203 problems on Project Euler, until it got hacked. I had solved 200+ problems on Hacker-Rank, until I ran out of easy/medium problems to solve. Now I've crossed the 200 problems mark on LeetCode. I think I can get to the 300 there, assuming they keep on posting easy/medium problems, and that my interest for TV shows continue to be zero. The 200th problem was this one: : The set  S  originally contains numbers from 1 to  n . But unfortunately, due to the data error, one of the numbers in the set got duplicated to  another  number in the set, which results in repetition of one number and loss of another number. Given an array  nums  representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array. Example 1: Input: nums = [1,2,2,4] Output: [2,3] Note:

The type of problem that is asking for a Dynamic Programming solution

The problem is this one, new one from LeetCode: Given an unsorted array of integers, find the number of longest increasing subsequence. Example 1: Input: [1,3,5,4,7] Output: 2 Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7]. Example 2: Input: [2,2,2,2,2] Output: 5 Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5. Note:  Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int. The hints that tell me that we need a Dynamic Programming (DP) solution to this problem are twofold: 1) The problem is asking for the number  of sequences, but not the sequences themselves 2) Think about a brute-force approach: at each index you'd have to binary check every other previous index. That's an 2^n approach. n=2

Magic Dictionary

New problem by LeetCode: Implement a magic directory with  buildDict , and  search  methods. For the method  buildDict , you'll be given a list of non-repetitive words to build a dictionary. For the method  search , you'll be given a word, and judge whether if you modify  exactly  one character into  another  character in this word, the modified word is in the dictionary you just built. Example 1: Input: buildDict(["hello", "leetcode"]), Output: Null Input: search("hello"), Output: False Input: search("hhllo"), Output: True Input: search("hell"), Output: False Input: search("leetcoded"), Output: False Note: You may assume that all the inputs are consist of lowercase letters  a-z . For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest. Please remember to  RESET

String concatenation is BAD!!!!

So here was tonight’s problem, from our friend LeetCode: The set  [1,2,3,…, n ]  contains a total of  n ! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for  n  = 3): "123" "132" "213" "231" "312" "321" Given  n  and  k , return the  k th  permutation sequence. Note:  Given  n  will be between 1 and 9 inclusive. It is an interesting one because it asks precisely for the kth permutation sequence. I’m sure there must be a clever way to generate the kth one in O(1) but I decided to generate them all (given the small n) until we get to the kth one. Here was my first implementation: a recursive depth-first search without pruning until we get to the kth sequence:               public class Solution               {                            public string GetPermutation(int n,

Palindromic Substrings

Take a look at this problem, by LeetCode: Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters. Example 1: Input: "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c". Example 2: Input: "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa". Note: The input string length won't exceed 1000. The brute-force solution would be something like this: you get all the substrings of the original string, which would give you an O(n^2), and then for each one you check whether it is a palindrome or not, hence composing with another O(n) for a grand total of O(n^3). With an n=1000,