LeetCode: Evaluate Division – Prepare For Coder Interview

Evaluate Division

Similar Problems:

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution: dfs

// https://code.dennyzhang.com/evaluate-division
// Basic Ideas: union find + weighted graph
//
// Complexity: Time O(n+k), Space O(n)
//   n = node count; k = len(queries)
type MyNode struct {
    parent string
    ratio float64 // The ratio from parent to current node
}

var m map[string]MyNode

func union(str1 string, str2 string, ratio float64) {
    p1, w1 := find(str1)
    p2, w2 := find(str2)
    m[p2] = MyNode{parent:p1, ratio:(w1*ratio/w2)}
}

func find(str1 string) (p string, w float64) {
    w = m[str1].ratio
    for str1 != m[str1].parent {
        str1 = m[str1].parent
        w *= m[str1].ratio
    }
    p = str1
    return
}

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
    m = map[string]MyNode{}
    for _, eq := range equations {
        v1, v2 := eq[0], eq[1]
        m[v1] = MyNode{v1, 1}
        m[v2] = MyNode{v2, 1}
    }
    for i, eq := range equations {
        v1, v2 := eq[0], eq[1]
        union(v1, v2, 1/values[i])
    }
    res := make([]float64, len(queries))
    for i, query := range queries {
        v1, v2 := query[0], query[1]
        if _, ok := m[v1]; !ok {
            res[i] = -1
            continue
        }
        if _, ok := m[v2]; !ok {
            res[i] = -1
            continue
        }
        p1, w1 := find(v1) 
        p2, w2 := find(v2)
        if p1 != p2 {
            res[i] = -1
        } else {
            res[i] = w1/w2
        }
    }
    return res
}

Solution: union find

// https://code.dennyzhang.com/evaluate-division
// Basic Ideas: union find + weighted graph
//
// Complexity: Time O(n), Space O(n)
type MyNode struct {
    parent string
    weight float64 // from current node to its parent
}

var m map[string]MyNode

func union(str1 string, str2 string, weight float64) {
    p1, w1 := find(str1)
    p2, w2 := find(str2)
    m[p2] = MyNode{parent:p1, weight:(w1*weight/w2)}
}

func find(str1 string) (p string, w float64) {
    w = m[str1].weight
    for str1 != m[str1].parent {
        str1 = m[str1].parent
        w *= m[str1].weight
    }
    p = str1
    return
}

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
    m = map[string]MyNode{}
    for _, eq := range equations {
        v1, v2 := eq[0], eq[1]
        m[v1] = MyNode{v1, 1}
        m[v2] = MyNode{v2, 1}
    }
    for i, eq := range equations {
        v1, v2 := eq[0], eq[1]
        union(v1, v2, values[i])
    }
    res := make([]float64, len(queries))
    for i, query := range queries {
        v1, v2 := query[0], query[1]
        if _, ok := m[v1]; !ok {
            res[i] = -1
            continue
        }
        if _, ok := m[v2]; !ok {
            res[i] = -1
            continue
        }
        p1, w1 := find(v1) 
        p2, w2 := find(v2)
        if p1 != p2 {
            res[i] = -1
        } else {
            res[i] = w2/w1
        }
    }
    return res
}

Solution: union find

// https://code.dennyzhang.com/evaluate-division
// Basic Ideas: union find
//
// Complexity: Time O(n), Space O(n)
var weights map[int]float64 // ratio of current vs immediate parent

type DSU struct {
    parent []int
}

func constructor(size int) DSU {
    parent := make([]int, size)
    for i, _ := range parent {
        parent[i] = i
        weights[i] = float64(1)
    }
    return DSU{parent:parent}
}

func (dsu *DSU) union(x int, y int, w float64) {
    // connect parent of y to parent of x
    x1, w1 := dsu.find(x)
    y1, w2 := dsu.find(y)
    dsu.parent[y1] = x1
    weights[y1] = w1/(w*w2)
}

func (dsu *DSU) find(x int) (int, float64) {
    w := weights[x]
    for dsu.parent[x] != x {
        x = dsu.parent[x]
        w *= weights[x]
    }
    return x, w
}

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
    cnt := 0
    m := map[string]int{}
    weights = map[int]float64{}

    for _, eq := range equations {
        for _, b := range eq {
            if _, ok := m[b]; !ok {
                m[b] = cnt
                cnt++
            }
        }
    }

    dsu := constructor(cnt)
    for i, eq := range equations {
        b1, b2 := eq[0], eq[1]
        dsu.union(m[b1], m[b2], values[i])
    }
    res := make([]float64, len(queries))
    for i, q := range queries {
        b1, b2 := q[0], q[1]
        if _, ok := m[b1]; !ok {
            res[i] = -1
            continue
        }
        if _, ok := m[b2]; !ok {
            res[i] = -1
            continue
        }
        v1, w1 := dsu.find(m[b1])
        v2, w2 := dsu.find(m[b2])
        if v1 != v2 {
            // not connected
            res[i] = -1
        } else {
            // connect to the same ancestor
            res[i] = w1/w2
        }
    }
    return res
}

Post Views: 0