Dijkstra’s algorithm

My version in python. The code is specific to how g, the graph matrix is defined.

Here is a good explanation to why we need to get the vertex with min edge in each iteration.

def graphDistances(g, s):
    INFINITY = 9999999999
    size = len(g)
    dist = [INFINITY] * size
    prev = [None] * size
    unvisited = set(range(size))

    dist[s] = 0

    while unvisited:
        u = findVertexWithMinDist(unvisited, dist)
        unvisited.remove(u)
        for v, edge_weight in enumerate(g[u]):
            if edge_weight == -1:
                continue
            my_dist = dist[u] + edge_weight
            if my_dist < dist[v]:
                dist[v] = my_dist
                prev[v] = u
        
    return dist

def findVertexWithMinDist(unvisited, dist):
    min_val = None
    min_idx = None
    for i in unvisited:
        v = dist[i]
        if min_val is None or v < min_val:
            min_val = v
            min_idx = i
    return min_idx

Ref:
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

The nightmare videos of children’s YouTube

Founder to CEO

A nice 99-page doc for anyone out there who may want to be a CEO someday.

https://docs.google.com/document/d/1ZJZbv4J6FZ8Dnb0JuMhJxTnwl-dwqx5xl0s65DE3wO8/preview#

Inorder Tree Traversal – Morris Traversal

# Python program to do inorder traversal without recursion and 
# without stack Morris inOrder Traversal
 
# A binary tree node
class Node:
     
    # Constructor to create a new node
    def __init__(self, data):
        self.data = data 
        self.left = None
        self.right = None
 
# Iterative function for inorder tree traversal
def MorrisTraversal(root):
     
    # Set current to root of binary tree
    current = root 
     
    while(current is not None):
         
        if current.left is None:
            print current.data ,
            current = current.right
        else:
            #Find the inorder predecessor of current
            pre = current.left
            while(pre.right is not None and pre.right != current):
                pre = pre.right
  
            # Make current as right child of its inorder predecessor
            if(pre.right is None):
                pre.right = current
                current = current.left
                 
            # Revert the changes made in if part to restore the 
            # original tree i.e., fix the right child of predecssor
            else:
                pre.right = None
                print current.data ,
                current = current.right
             
# Driver program to test above function
""" 
Constructed binary tree is
            1
          /   \
        2      3
      /  \
    4     5
"""
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
 
MorrisTraversal(root)
 
# This code is contributed by Naveen Aili

Ref: https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/

Data structures reference

https://www.interviewcake.com/data-structures-reference

Find the max possible sum from all contiguous subarrays of a given array

Given an array of integers, find the maximum possible sum you can get from one of its contiguous subarrays. The subarray from which this sum comes must contain at least 1 element.

For inputArray = [-2, 2, 5, -11, 6], the output should be
arrayMaxConsecutiveSum2(inputArray) = 7.

The contiguous subarray that gives the maximum possible sum is [2, 5], with a sum of 7.

Guaranteed constraints:
3 ≤ inputArray.length ≤ 105,
-1000 ≤ inputArray[i] ≤ 1000.

// ———————————–

Naively this can be solved with a brute-force O(N^2) solution.

Turns out there is an algorithm called Kadane’s Algorithm that can do O(N).

The idea is, imagine we keep dragging this sticky piece of jello along the array. Say it is now touching index 2 and 4, and sum of those 3 cells is -10. Now look at cell indexed 5, we want to decide if we should move the whole jello to cell 5 or we keep dragging it to cell 5. If cell 5 is 1, then keeping the old jello will give us -9, but starting fresh will give us 1. So why not starting fresh? So curr_max will become 1, move the whole jello to cell 5 and keep marching to cell 6. So on and so forth.

def arrayMaxConsecutiveSum2(inputArray):
    curr_max = inputArray[0]
    global_max = inputArray[0]
    for i in range(1, len(inputArray)):
        curr_max = max(curr_max + inputArray[i], inputArray[i])
        if curr_max > global_max:
            global_max = curr_max
    return global_max

List of unicorn startup companies

https://en.wikipedia.org/wiki/List_of_unicorn_startup_companies

I wasn’t aware of that many unicorn startups from china. Turns out there are quite a lot.