doordash problem

main.go

package main

func max(x, y int) int {
	if x < y {
		return y
	}
	return x
}

type Node struct {
	Key      string
	Value    int
	Active   bool
	Children []*Node
}

func NewNode(key string, value int, active bool, children []*Node) *Node {
	return &Node{Key: key, Value: value, Active: active, Children: children}
}

// ChildAt return child node at index idx or nil if it does not exist
func (n Node) ChildAt(idx int) (out *Node) {
	if len(n.Children) > idx {
		out = n.Children[idx]
	}
	return
}

func (n Node) CountChildren() (count int) {
	for _, c := range n.Children {
		if c != nil {
			count += c.CountChildren()
		}
	}
	return count + 1
}

func Compare(a, b *Node) (count int) {
	if a == nil {
		return b.CountChildren()
	} else if b == nil {
		return a.CountChildren()
	}
	if a.Key != b.Key {
		count += 2
	} else if a.Value != b.Value || a.Active != b.Active {
		count++
	}
	m := max(len(a.Children), len(b.Children))
	for i := 0; i < m; i++ {
		count += Compare(a.ChildAt(i), b.ChildAt(i))
	}
	return
}

func main() {

}

main_test.go

package main

import (
	assert "github.com/stretchr/testify/assert"
	"testing"
)

func TestA(t *testing.T) {
	treeA :=
		NewNode("a", 1, true, []*Node{
			NewNode("b", 2, true, []*Node{
				NewNode("d", 4, true, nil),
				NewNode("e", 5, true, nil)}),
			NewNode("c", 3, true, []*Node{
				NewNode("f", 6, true, nil)})})

	treeB :=
		NewNode("a", 1, true, []*Node{
			nil,
			NewNode("c", 3, false, []*Node{
				NewNode("f", 66, true, nil)})})

	assert.Equal(t, 5, Compare(treeA, treeB))
}

func TestB(t *testing.T) {
	treeA :=
		NewNode("a", 1, true, []*Node{
			NewNode("b", 2, true, []*Node{
				NewNode("d", 4, true, nil),
				NewNode("e", 5, true, nil)}),
			NewNode("c", 3, true, []*Node{
				NewNode("f", 6, true, nil)})})

	treeB :=
		NewNode("a", 1, true, []*Node{
			nil,
			NewNode("c", 3, false, []*Node{
				NewNode("f", 66, true, nil)})})

	assert.Equal(t, 5, Compare(treeB, treeA))
}

func TestC(t *testing.T) {
	treeA :=
		NewNode("a", 1, true, []*Node{
			NewNode("b", 2, true, []*Node{
				NewNode("d", 4, true, nil),
				NewNode("e", 5, true, nil)}),
			NewNode("c", 3, true, []*Node{
				NewNode("g", 7, true, nil)})})

	treeB :=
		NewNode("a", 1, true, []*Node{
			NewNode("b", 2, true, []*Node{
				NewNode("d", 4, true, nil),
				NewNode("e", 5, true, nil),
				NewNode("f", 6, true, nil)}),
			NewNode("c", 3, true, []*Node{
				NewNode("g", 7, false, nil)})})

	assert.Equal(t, 2, Compare(treeA, treeB))
}

func TestD(t *testing.T) {
	treeA :=
		NewNode("a", 1, true, []*Node{
			NewNode("b", 2, true, []*Node{
				NewNode("d", 4, true, nil),
				NewNode("e", 5, true, nil),
				NewNode("f", 6, true, nil)}),
			NewNode("c", 3, true, []*Node{
				NewNode("g", 7, true, nil)})})

	treeB :=
		NewNode("a", 1, true, []*Node{
			NewNode("b", 2, true, []*Node{
				NewNode("d", 4, true, nil),
				NewNode("h", 5, true, nil)}),
			NewNode("c", 3, true, []*Node{
				NewNode("g", 7, true, nil)})})

	assert.Equal(t, 3, Compare(treeA, treeB))
}