Showing posts from April, 2020

Adding one row to a Binary Tree

Love tree problems, once you get it right, there are usually very few corner cases (other than the d=1, which was mentioned in the problem description anyways). Here it is, and code is down below. Song that goes along well with this problem: Cheers, ACC. 623. Add One Row to Tree Medium 378 119 Add to List Share Given the root of a binary tree, then value  v  and depth  d , you need to add a row of nodes with value  v  at the given depth  d . The root node is at depth 1. The adding rule is: given a positive integer depth  d , for each NOT null tree nodes  N  in depth  d-1 , create two tree nodes with value  v  as  N's  left subtree root and right subtree root. And  N's   original left subtree  should be the left subtree of the new left subtree root, its  original right subtree  should be the right subtree o

Covid and Fibonacci Source Code

public class CovidAndFibonacci {     public static void CovidAndFibonacciApproximation()     {         DateTime ed = new DateTime(2020, 4, 18);         double target = 2330793;         double best = 0;         double bestActualVal = 0;         double bestx = 0;         double besty = 0;         for (double x = 0.1; x < 1; x += 0.1)         {             for (double y = 0.1; y < 1; y += 0.1)             {                 //Fibo                 double f1 = 0;                 double f2 = 1;                 DateTime dt = new DateTime(2020, 1, 1);                 while (DateTime.Compare(dt, ed) <= 0)                 {                     double temp = f2;                     f2 = f1 * x + f2 * y;                     f1 = temp;                     dt = dt.AddDays(1);                 }                 if (best == 0 || Math.Abs(target - f2) < best)                 {                     bestActualVal = f2;                     best = Math.Abs(target - f2)

Minimum Number of Fibonacci Numbers

Interesting problem, fresh out of the oven: 1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K Medium 26 5 Add to List Share Given the number  k ,  return the minimum number of Fibonacci numbers whose sum is equal to  k , whether a Fibonacci number could be used multiple times. The Fibonacci numbers are defined as: F 1  = 1 F 2  = 1 F n  = F n-1  + F n-2  , for n > 2. It is guaranteed that for the given constraints we can always find such fibonacci numbers that sum  k . Example 1: Input: k = 7 Output: 2 Explanation: The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, ... For k = 7 we can use 2 + 5 = 7. Example 2: Input: k = 10 Output: 2 Explanation: For k = 10 we can use 2 + 8 = 10. Example 3: Input: k = 19 Output: 3 Explanation: For k = 19 we can use 1 + 5 + 13 = 19. Constraints: 1 <= k <= 10^9 Accepted 4,104 S

The Power of C# List Class

The solution to this problem demonstrates the power of the C# List Class . Here it is: 1409. Queries on a Permutation With Key Medium 20 40 Add to List Share Given the array  queries  of positive integers between  1  and  m , you have to process all  queries[i]  (from  i=0  to  i=queries.length-1 ) according to the following rules: In the beginning, you have the permutation  P=[1,2,3,...,m] . For the current  i , find the position of  queries[i]  in the permutation  P  ( indexing from 0 ) and then move this at the beginning of the permutation  P.  Notice that the position of  queries[i]  in  P  is the result for  queries[i] . Return an array containing the result for the given  queries . Example 1: Input: queries = [3,1,2,1], m = 5 Output: [2,1,2,1] Explanation: The queries are processed as follow: For i=0: queries[i]=3, P=[1,2,3,4,5], position of 3 in P is 2 , then we move 3 to the beginning

Logger, by Google

First, #StayHomeStaySafe !!! Hopefully all this craziness will be over soon. Here is the problem: 359. Logger Rate Limiter Easy 400 95 Add to List Share Design a logger system that receive stream of messages along with its timestamps, each message should be printed if and only if it is  not printed in the last 10 seconds . Given a message and a timestamp (in seconds granularity), return true if the message should be printed in the given timestamp, otherwise returns false. It is possible that several messages arrive roughly at the same time. Example: Logger logger = new Logger(); // logging string "foo" at timestamp 1 logger.shouldPrintMessage(1, "foo"); returns true; // logging string "bar" at timestamp 2 logger.shouldPrintMessage(2,"bar"); returns true; // logging string "foo" at timestamp 3 logger.shouldPrintMessage(3,"foo"); returns false; // log

Geometric Algorithms

Arguably, Geometric Algorithms (GA) stand side by side with Dynamic Programming (DP) as the hardest-to-grasp out of all the undergrad-level algorithms (clearly I'm not referring to advanced algorithms, for which GA and DP don't even scratch the surface in terms of difficulties). The complexities manifest in different ways, though: DP seems to challenge you to think from a completely different perspective on how to solve the problem, whereas GA is not necessarily hard to come up with a solution, however it requires few things: a) Brush up your high school geometry knowledge again b) Pencil and paper c) A formidable attention to details when coding Seems like GA is more "mechanically laborious" whereas DP is more "intellectually challenging". Example of GA: 1401. Circle and Rectangle Overlapping Medium 40 20 Add to List Share Given a circle represented as ( radius ,  x_cent

Dynamic Programming in O(N^3)

Problem is this one: Easy 687 71 Add to List Share There are a row of  n  houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. The cost of painting each house with a certain color is represented by a  n  x  3  cost matrix. For example,  costs[0][0]  is the cost of painting house 0 with color red;  costs[1][2]  is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses. Note: All costs are positive integers. Example: Input: [[17,2,17],[16,16,5],[14,3,19]] Output: 10 Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.   Minimum cost: 2 + 5 + 3 = 10. Accepted 78,373 Submissions 152,619 It smells like a DP, so it must be DP. What ca