KSoto

/*
         (A)
        ^ ^ \
     80/  |  \30
      /   |   v
     (D)  |40 (B)
      ^   |   /^
     70\  |50//70
        \ | v/

KSoto

/*

Leftmost column index of 1
Source: https://leetcode.com/discuss/interview-question/341247/Facebook-and-Google-or-Phone-screen-or-Leftmost-column-index-of-1

In a binary matrix (all elements are 0 and 1), every row is sorted in 
ascending order (0 to the left of 1). Find the leftmost column index with a 1 in it.

Example 1:

KSoto

/*

Approach:
- Use DSU
- For each cell, check if the one above, below, left or right is a 1. If they are, perform union.
- Remember to perform union on itself in case you have an orphan island.
- To create a unique identifier per cell, take the current row and multiply it by number of columns (3 for example), then add the current column. So the first row would be 0 * 3 (always 0), then add 0, 1, 2. Second row would be 1 * 3, then add 0, 1, 2… 

var x = current_row * num_columns + current_column

KSoto

/*
We are given a map of cities connected with each other via cable lines such that there is no cycle between any two cities. We need to find the maximum length of cable between any two cities for given city map.
Input : n = 6 
1 2 3  // Cable length from 1 to 2 (or 2 to 1) is 3
2 3 4
2 6 2
6 4 6
6 5 5
Output: maximum length of cable = 12
*/

KSoto

/*
Kruskal’s Minimum Spanning Tree Algorithm using DSU
1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. (Use union find / DSU to determine if a cycle has been formed)
3. Repeat step#2 until there are (V-1) edges in the spanning tree.

DSU explanation: https://gist.github.com/KSoto/3300322fc2fb9b270dce2bf1e3d80cf3
*/

class DSU {

KSoto

// https://www.youtube.com/watch?v=wU6udHRIkcc

/*
Disjoint Set Union (“DSU”)  is the Data Structure: disjoint-set data structure 
is a data structure that keeps track of a set of elements partitioned into a 
number of disjoint (non-overlapping) subsets.

Union Find is the Algorithm: A union-find algorithm is an algorithm that can 
be used to detect cycles in an undirected graph & performs two useful operations
 on such a data structure:

KSoto

# Katie Soto
# CPSC 473, CSUF, 2/2012
# Create a Ruby script that mimics the "Try Redis" tutorial on http://try.redis-db.com/

require 'sinatra'
require 'redis'

redis = Redis.new

redis.flushdb