interview.md

Merkle Tree

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

A Merkle tree is a binary tree where each node's value is calculated by hashing both of it's child leaves: sha256(left_child + right_child). Uninitialized leafs should have the value of a hash of an empty string: sha256('').

Task

Create a data structure representing a fixed-height Merkle tree in-memory with the following API:

func NewMerkleTree(height uint) *MerkleTree

func (m *MerkleTree) GetHeight() uint

func (m *MerkleTree) GetRoot() Hash

func (m *MerkleTree) SetLeaf(index uint, data Hash)

Write unit-tests to cover those API methods.

Tips

For hashing you can use the go-ethereum packages:

import (
	"github.com/ethereum/go-ethereum/common"
	"github.com/ethereum/go-ethereum/crypto"
)

func HashTwo(a, b common.Hash) common.Hash {
	buf := make([]byte, 64)
	copy(buf[0:32], a.Bytes())
	copy(buf[32:64], b.Bytes())
	return crypto.Keccak256Hash(buf)
}