Posts

Finding the Diameter of an N-Ary Tree: the "To-And-Thru" approach

Hello folks, this is a problem that exemplifies a technique that I like to call the To-And-Thru. We want to find the diameter of an N-ary tree (meaning a tree where each node has 0, 1 or more children). Take a look:  https://leetcode.com/problems/diameter-of-n-ary-tree/ What you want is a near-linear solution in the number of nodes. If you assume that the tree has N nodes, and that each node has an average of LogN children, then the To-And-Thru algorithm below will run in O(N * (LogN)^2) time. Not really linear, but something that seems to be closer to NLogN. The idea is the following: Post-Order DFS For each node, compute the following: The longest path TO the node The longest path THRU the node The above computation will take LogN*LogN since there are two nested loops ( I guess there might be a way to reduce this to LogN, meaning one loop ) As you compute 2.1 and 2.2, your diameter will be the Max See figure below. Works well enough. Code is down below, stay safe, stay motivated!...

Classic Dijkstra

Dijkstra invented one of the most classic algorithms to find the min/max path in a graph - we call it today simply  Dijkstra's Algorithm . This problem requires a classic use of Dijkstra's Algorithm:  https://leetcode.com/problems/path-with-maximum-probability/ 1514. Path with Maximum Probability Medium 194 4 Add to List Share You are given an undirected weighted graph of  n  nodes (0-indexed), represented by an edge list where  edges[i] = [a, b]  is an undirected edge connecting the nodes  a  and  b  with a probability of success of traversing that edge  succProb[i] . Given two nodes  start  and  end , find the path with the maximum probability of success to go from  start  to  end  and return its success probability. If there is no path from  start  to  end ,  return 0 . Your answer will be accepted if it differs from the correct answer by at most  1e-5 .  ...

Find root of a Tree in O(n)-time, O(1)-space

Here is the problem:  https://leetcode.com/problems/find-root-of-n-ary-tree/ In order to solve it in O(n)-time and O(1)-space, I did the following:  - The fact that the numbers are unique is certainly an important cue  - The root is the only val without a parent  - Sum up all the parents in a variable sumParents  - Sum up all the children in a variable sumChildren  - Given the uniqueness of the vals, the root index will be rootIndex = sumParents - sumChildren  - Do another O(n) pass to find the node whose val is rootIndex. Return that one Code is below, and me on vacation below. Stay safe!!! ACC public Node FindRoot(List<Node> tree) {     int sumParents = 0;     int sumChildren = 0;     foreach (Node node in tree)     {         sumParents += (node != null ? node.val : 0);         if (node != null)         {            ...

Is foreach around 9% slower than old-school for-loop?

Thanks to #covid19, I've been trying to find ways to kill the lock-down boredom. I decided to investigate the performance of the traditional "for" loop compared to the somewhat more modern (well, modern in the last 20 years, haha) "foreach" loop.  I remember back in the day when I was actually writing critical-path production code when a co-worker told me: don't use foreach, always use old-school for-loop because the former is much slower The hypothesis is that the foreach requires use of reflection by the compiler to determine the exact data type of the element in the foreach, and that extra computation results in a slightly less optimized iteration than the traditional loop. True? Well... I ran the code below for 100s of time. The result? Yeah, anywhere between 8.5% and 10% in favor of the old-school for-loop . Guess my co-worker was right... Cheers, stay safe, love, ACC. for each:       35720075 old-school for: 32380036 old-school is 9.35059346879871% fas...

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;     ...

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. https://leetcode.com/problems/clone-n-ary-tree/ public class Solution {     public Node CloneTree(Node root)     {         if ...

Deep Copy of Data Structure - A Classic Problem

This is actually a classic problem - how to make a deep copy of a data structure?  https://leetcode.com/problems/clone-binary-tree-with-random-pointer/ 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, ...