Another Casual Coder

As the title says, this will be a DP solution. Here is the Leetcode problem:  https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/description/ Given two strings  s1, s2 , find the lowest ASCII sum of deleted characters to make two strings equal. Example 1: Input: s1 = "sea", s2 = "eat" Output: 231 Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum. Deleting "t" from "eat" adds 116 to the sum. At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this. Example 2: Input: s1 = "delete", s2 = "leet" Output: 403 Explanation: Deleting "dee" from "delete" to turn the string into "let", adds 100[d]+101[e]+101[e] to the sum. Deleting "e" from "leet" adds 101[e] to the sum. At the end, both strings are equal to "let", and the answer is 100+1...

From Leetcode, problem #863:  https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/description/ We are given a binary tree (with root node  root ), a  target  node, and an integer value  K . Return a list of the values of all nodes that have a distance  K  from the  target  node.  The answer can be returned in any order. Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4] , target = 5 , K = 2 Output: [7,4,1] Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1. Note that the inputs "root" and "target" are actually TreeNodes. The descriptions of the inputs above are just serializations of these objects. Note: The given tree is non-empty. Each node in the tree has unique values  0 <= node.val <= 500 . The  target  node is a node in the tree. 0 <= K <= 1000 . Here is the idea (ignoring the special cases of zer...

Problem is here:  https://leetcode.com/problems/increasing-order-search-tree/description/ Given a tree, rearrange the tree in  in-order  so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child. Example 1: Input: [5,3,6,2,4,null,8,1,null,null,null,7,9] 5 / \ 3 6 / \ \ 2 4 8  / / \ 1 7 9 Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9] 1   \   2   \   3   \   4   \   5   \   6   \   7   \   8   \ 9 Note: The number of nodes in the given tree will be between 1 and 100. Each node will have a unique integer value from 0 to 1000. Even though the problem does not mention a BST, it "implies" a BST since in the signature of the fu...

Fun problem by Facebook, via Daily Coding Problem: This problem was asked by Facebook. Given a list of integers, return the largest product that can be made by multiplying any three integers. For example, if the list is  [-10, -10, 5, 2] , we should return  500 , since that's  -10 * -10 * 5 . You can assume the list has at least three integers. Clearly there is an O(n^3) solution, and with a little more analysis you can reduce that to O(nlogn) by sorting and analyzing the extremities. There is a better solution, though. It has to do with the " product of three numbers ". There are two cases to consider: a) Either the maximum product will be the product of the 3 largest numbers. I think that it is straightforward to see that, especially if the numbers are all positive. Even if they are all negative, the product of the 3 largest will give you the right answer. b) Or, the maximum product will be the product of the 2 smallest numbers and the largest number. T...

Problem:  https://leetcode.com/problems/long-pressed-name/description/ Your friend is typing his  name  into a keyboard.  Sometimes, when typing a character  c , the key might get  long pressed , and the character will be typed 1 or more times. You examine the  typed  characters of the keyboard.  Return  True  if it is possible that it was your friends name, with some characters (possibly none) being long pressed. Recursive solution, with simple base case, trimming based on the first chars equality (or inequality), optimization based on the typed string containing the name, and finally the recursion moving name once or keeping it as it is. Key optimization that made it pass was this . Cheers, Marcelo public class Solution { public bool IsLongPressedName(string name, string typed) { if (String.IsNullOrEmpty(name) && String.IsNullOrEmpty(typed)) return true; if (String.IsNullOrEmpty(name) || String.IsN...

So the problem comes from Daily Coding Problem: This problem was asked by Google. Implement integer exponentiation. That is, implement the  pow(x, y)  function, where  x  and  y  are integers and returns  x^y . Do this faster than the naive method of repeated multiplication. For example,  pow(2, 10)  should return 1024. So the secret here is to decompose the exponent (say 10) in its power of 2. So 10 = 8 + 2. Each of these parts can be computed in Log(N) time, which makes the overall execution time for exponentiation some constant * Log(y). Faster than the repeated multiplication. Code is down below, or on GitHub:  https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem11142018.cs Thanks, Marcelo using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace DailyCodingProblem { class DailyCodingProblem11142018 { public long Ex...

From LeetCode:  https://leetcode.com/problems/leaf-similar-trees/description/ Consider all the leaves of a binary tree.  From left to right order, the values of those leaves form a  leaf value sequence. For example, in the given tree above, the leaf value sequence is  (6, 7, 4, 9, 8) . Two binary trees are considered  leaf-similar  if their leaf value sequence is the same. Return  true  if and only if the two given trees with head nodes  root1  and  root2  are leaf-similar. Nothing really hard about this problem: do a pre-order DFS and add the leaves to a list of integer. Compare the two lists from both the roots. That's it. Code is below, cheers, Marcelo. public class Solution { public bool LeafSimilar(TreeNode root1, TreeNode root2) { LinkedList l1 = new LinkedList (); LinkedList l2 = new LinkedList (); GetLeafValues(root1, l1); GetLeafValues(root2, l2); return CheckSimilarList...

Today's Daily Coding Problem: This problem was asked by Apple. Implement a queue using two stacks. Recall that a queue is a FIFO (first-in, first-out) data structure with the following methods:  enqueue , which inserts an element into the queue, and  dequeue , which removes it. This is a very common technical interview question, including its variations, such as: Implement a stack using two queues Optimize for enqueue/push operation (O(1)-time) Optimize for dequeue/pop operation (O(1)-time) My implementation below optimizes it for the enqueue operation (in O(1)-time), while the dequeue will suffer a little bit on time (O(n)-time). The idea is as follows: On the enqueue operation, push to stack 1 On the dequeue, pop from stack 1 pushing to stack 2. Save the last element, which you'll return later. Then push all the elements back to stack 1 That's it! Code is here (GitHub):  https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodin...

Today's Daily Coding Problem: This problem was asked by Google. Implement an LRU (Least Recently Used) cache. It should be able to be initialized with a cache size  n , and contain the following methods: set(key, value) : sets  key  to  value . If there are already  n  items in the cache and we are adding a new item, then it should also remove the least recently used item. get(key) : gets the value at  key . If no such key exists, return null. Each operation should run in O(1) time. The O(1) means that both set and get operations must be performed in constant time, hence forget about using heaps or trees. The key here is to use extra space. There is no requirements on the space utilization. Here is the idea: Have a list to implement the cache. The list will be a list of <key, value> But also have a hash table point a key to each node in the list When setting, set an existing value or add a new one. Move it to the top of the l...

Daily Coding Problem: This problem was asked by Amazon. Given an array of numbers, find the maximum sum of any contiguous subarray of the array. For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take elements 42, 14, -5, and 86. Given the array [-5, -1, -8, -9], the maximum sum would be 0, since we would not take any elements. Do this in O(N) time. The solution is actually quite simple, but requires some thinking: you'll have two variables, one keeps track of the current sum, the other one the maximum sum. The logic for the maximum sum is actually pretty simple, so we'll start with that: max = Math.Max(current, max); Straightforward right? Basically max will be the max between max and current. Now for current, there are two options: if the current value plus current is positive, then sure, add it to current. Otherwise, set it to zero: current = Math.Max(current + numbers[i], 0); When you put it all togeth...