Another Casual Coder

Another DP problem at LeetCode:  https://leetcode.com/problems/minimum-path-sum/ Given a  m  x  n  grid filled with non-negative numbers, find a path from top left to bottom right which  minimizes  the sum of all numbers along its path. Note:  You can only move either down or right at any point in time. Example: Input: [   [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum. The hints of DP are clear: problem is asking for a min solution, and the brute-force solution is highly exponential, and since the problem does not specify a boundary for the grid, it might be intractable to do it using brute-force. DP is a construction approach: instead of thinking like recursion where you think in terms of "base case and induction", think more around a "base case and construction", where you'll construct the solution for 0,1,2,....,n-1,n, and then your final solution is whatever you get for n...

1 comment

Here is today's problem:  https://leetcode.com/problems/repeated-dna-sequences/description/ : All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA. Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. Example: Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" Output: ["AAAAACCCCC", "CCCCCAAAAA"] My first solution just doing string manipulation timed out. A better solution (not the best though) is to use extra memory and do the following: Have two hashtables: one storing every dna of length 10, and one storing the solution As you add the dnas to be first hashtable, check if it has been there before If so, add to the solution It is still a slow solution, O(10*Len(s)), some optimization can be done to get it down to O(Len(s)) (r...

3 comments

Late night problem:  https://leetcode.com/problems/merge-two-binary-trees/description/ Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree. Example 1: Input: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 Output: Merged tree: 3 / \ 4 5 / \ \ 5 4 7 Note:  The merging process must start from the roo...

1 comment

This was one of the most interesting problems I've seen recently, comes from LeetCode, here it is its description:  https://leetcode.com/problems/check-completeness-of-a-binary-tree/description/ Given a binary tree, determine if it is a  complete binary tree . Definition of a complete binary tree from  Wikipedia : In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2 h  nodes inclusive at the last level h. Example 1: Input: [1,2,3,4,5,6] Output: true Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible. Example 2: Input: [1,2,3,4,5,null,7] Output: false Explanation: The node with value 7 isn't as far left as possible. Note: The tree will have between 1 and 100 nodes. I thought for a while and after goi...

2 comments

Here is today's problem from Daily Coding Problem: This problem was asked by Apple. Given a tree, find the largest tree/subtree that is a BST. Given a tree, return the size of the largest tree/subtree that is a BST. Take a look at the tree below. Every node by itself is a BST of course, but I have highlighted some other BSTs in this tree. The largest one has double lines covering it, and has 5 nodes: I first tried one approach de-serializing using in-order traversal so that I'd end up with a sorted list, and from there look at the BSTs, but it really doesn't quite work. An idea that worked was to do a post-order traversal using the following logic: The function returns the largest BST with the current node as the root Call for the left (a) Call for the right (b) The minimum number for the current node should be 1 But if the left node is smaller, add it (from (a)) But if the right node is larger, add it (from (b)) Check whether the current value is gre...

6 comments

Question on Leetcode:  https://leetcode.com/problems/design-hashmap/description/ Design a HashMap without using any built-in hash table libraries. To be specific, your design should include these functions: put(key, value)  : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value. get(key) : Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key. remove(key)  : Remove the mapping for the value key if this map contains the mapping for the key. Example: MyHashMap hashMap = new MyHashMap(); hashMap.put(1, 1);           hashMap.put(2, 2);         hashMap.get(1);            // returns 1 hashMap.get(3);            // returns -1 (not found) hashMap.put(2, 1);          // update the existing value hashMap.get(2);   ...

1 comment

Problem is by Leetcode: "Find First and Last Position of Element in Sorted Array", right here:  https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/ Given an array of integers  nums   sorted in ascending order, find the starting and ending position of a given   target   value. Your algorithm's runtime complexity must be in the order of  O (log  n ). If the target is not found in the array, return  [-1, -1] . Example 1: Input: nums = [ 5,7,7,8,8,10] , target = 8 Output: [3,4] Example 2: Input: nums = [ 5,7,7,8,8,10] , target = 6 Output: [-1,-1] The problem is looking for a Log(N) solution, but there are two values being asked for - the lower left, and the upper right. The way to find each one is to do a variation of binary search. And for each value, just run the algorithm twice for a O(2*Log(N)), which is the same as O(Log(N)). Code is below, cheers, Marcelo. public class Solu...

2 comments