Showing posts from June, 2020

Four Problems in 10min

Challenge was to solve 4 LC problems (2 easy, 2 medium) in <= 10min. I picked the ones below, new ones, from today. Solutions might not be the most elegant and/or efficient, but they all passed. Code is down below, cheers, ACC. Solution to Problem #1:     public class Solution     {         public int LongestSubarray(int[] nums)         {             Hashtable maxOnesAtPosition = new Hashtable();             bool insideOne = false;             int beginPos = 0;             for (int i = 0; i < nums.Length; i++)             {                 if (nums[i] == 1 && !insideOne)                 {                     beginPos = i;                     insideOne = true;                 }                 else if (nums[i] == 0 && insideOne)                 {                     maxOnesAtPosition.Add(beginPos, i - beginPos);                     if (i - 1 > beginPos)                     {                         maxOnesAtPosition.Add(i - 1, i - beginPos);                    

Clone a Tree

I've stumbled upon this problem multiple times, and solved it multiple times, but whenever I solve it, it always follows the same pattern in my mind: first I think it is easy-breezy. Then right before starting the code, I get confused with the exact recursion to be used. Takes me a minute or so to get my thoughts together and go back to the "easy-breezy" mindset. It is not a hard problem indeed. Take care of the base case ("null? Bail"), create the target tree and add the first element. At that point in the recursion, always add the children first, and only then do the induction. It works. You can also accomplish the same by making the private function "return" a pointer to the tree. As a personal preference, I like to keep it a void function. But, it is just a preference. Cheers friends, take good care of yourselves! ACC. public class Solution {     public Node CloneTree(Node root)     {         if (root

Deep Copy of Data Structure - A Classic Problem

This is actually a classic problem - how to make a deep copy of a data structure? The tree is represented in the same input/output way as normal binary trees where each node is represented as a pair of  [val, random_index]  where: val : an integer representing  Node.val random_index : the index of the node (in the input) where the random pointer points to, or  null  if it does not point to any node. You will be given the tree in class  Node  and you should return the cloned tree in class  NodeCopy .  NodeCopy  class is just a clone of  Node  class with the same attributes and constructors.   Example 1: Input: root = [[1,null],null,[4,3],[7,0]] Output: [[1,null],null,[4,3],[7,0]] Explanation: The original binary tree is [1,null,4,7]. The random pointer of node one is null, so it is represented as [1, null]. The random pointer of node 4 is node 7, so it is represented as [4, 3] where 3 is the index of node 7 in the

Design Browser History in O(1)-time

Here is a design problem, from LC: You have a  browser  of one tab where you start on the  homepage  and you can visit another  url , get back in the history number of  steps  or move forward in the history number of  steps . Implement the  BrowserHistory  class: BrowserHistory(string homepage)  Initializes the object with the  homepage  of the browser. void visit(string url)  visits  url  from the current page. It clears up all the forward history. string back(int steps)  Move  steps  back in history. If you can only return  x  steps in the history and  steps > x , you will return only  x  steps. Return the current  url  after moving back in history  at most   steps . string forward(int steps)  Move  steps  forward in history. If you can only forward  x  steps in the history and  steps > x , you will forward only  x  steps. Return the current  url  after forwarding in history  at most   steps .   Example: Input: ["Brow

ProjectEuler Problem 719 (some hints, but no spoilers)

Last time that I solved a ProjectEuler (PE) problem was in 2015... This is their latest problem as of today: Number Splitting        Problem 719 We define an  S S -number to be a natural number,  n n , that is a perfect square and its square root can be obtained by splitting the decimal representation of  n n  into 2 or more numbers then adding the numbers. For example, 81 is an  S S -number because  81 − − √ = 8 + 1 81 = 8 + 1 . 6724 is an  S S -number:  6724 − − − − √ = 6 + 72 + 4 6724 = 6 + 72 + 4 . 8281 is an  S S -number:  8281 − − − − √ = 8 + 2 + 81 = 82 + 8 + 1 8281 = 8 + 2 + 81 = 82 + 8 + 1 . 9801 is an  S S -number:  9801 − − − − √ = 98 + 0 + 1 9801 = 98 + 0 + 1 . Further we define  T ( N ) T ( N )  to be the sum of all  S S  numbers  n ≤ N n ≤ N . You are given  T ( 10 4 ) = 41333 T ( 10 4 ) = 41333 . Find  T ( 10 12 ) The rules of PE prevent me from disclosing the solution (they are very picky about it, rightfully so), but I can chat abo