Another Casual Coder

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

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

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)         {            ...

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