Skip to content

Instantly share code, notes, and snippets.

@P-A-R-U-S

P-A-R-U-S/Cracking_the_Coding_Interview_4-11_test.go

Created June 15, 2020 04:28
Show Gist options
  • Save P-A-R-U-S/29db9ea88cf189e4a69c0c0da57e10e1 to your computer and use it in GitHub Desktop.
Save P-A-R-U-S/29db9ea88cf189e4a69c0c0da57e10e1 to your computer and use it in GitHub Desktop.
Download ZIP
Cracking the Coding Interview - Task - 4.11 - Random Node, Insert Node, Delete Node
Raw
Cracking_the_Coding_Interview_4-11_test.go
package Part_4
import (
"fmt"
"math/rand"
"testing"
"time"
)
/*
Random Node: You are implementing a binary tree class from scratch which, in addition to insert, find, and delete,
has a method getRandomNode() which returns a random node from the tree. All nodes should be equally likely to be chosen.
Design and implement an algorithm for getRandomNode, and explain how you would implement the rest of the methods.
Hints: #42, #54, #62, #75, #89, #99, #7 72, #7 79
*/
/*
Вы пишете с нуля класс бинарного дерева поиска, который помимо методов вставки,
поиска и удаления содержит метод g e t R a n d o m N o d e ( ) для получения случайного узла дерева.
Вероятность выбора всех узлов должна быть одина­ ковой.
Разработайте и реализуйте алгоритм getRandomNode; объясните, как вы реализуете остальные методы.
*/
type value int
type Node struct {
id value
left *Node
right *Node
}
type DeleteDirection int
const (
MaxFromLeft DeleteDirection = iota
MinFromRight
)
func insertNode(root *Node, v value ) *Node {
n := &Node{id: v}
if root == nil {
return n
}
current_root := root
for {
if current_root.id < v {
if current_root.right == nil {
current_root.right = n
break
}
current_root = current_root.right
continue
}
if current_root.id > v {
if current_root.left == nil {
current_root.left = n
break
}
current_root = current_root.left
continue
}
}
return root
}
func deleteNode(root *Node, v value, deleteDirection DeleteDirection ) *Node {
if root == nil {
return nil
}
var parent_left, parent_right, node *Node
var s []*Node
visited := make(map[value]bool)
if root.id == v {
node = root
goto DELETENODE
}
s = append(s, root)
visited[root.id] = true
for len(s) > 0 {
n := s[len(s)-1]
s = s[:len(s)-1]
if n.left != nil {
if n.left.id == v {
node = n.left
parent_left = n
goto DELETENODE
}
if !visited[n.left.id] {
visited[n.left.id] = true
s = append(s, n.left)
}
}
if n.right != nil {
if n.right.id == v {
node = n.right
parent_right = n
goto DELETENODE
}
if !visited[n.right.id] {
visited[n.right.id] = true
s = append(s, n.right)
}
}
}
DELETENODE:
if node != nil {
// No child
if node.left == nil && node.right == nil {
// This is Root with no child
// just set root to nil
if parent_left == nil && parent_right == nil {
root = nil
goto END
}
if parent_right != nil {
parent_right.right = nil
}
if parent_left != node {
parent_left.left = nil
}
goto END
}
// One Child
// Node has Left child
if node.left != nil && node.right == nil {
if parent_left == nil && parent_right == nil {
root = nil
goto END
}
if parent_right != nil {
parent_right.right = node.left
node.left = nil
goto END
}
if parent_left != nil {
parent_left.left = node.left
node.left = nil
goto END
}
}
// Node has Right child
if node.left == nil && node.right != nil {
if parent_left == nil && parent_right == nil {
root = nil
goto END
}
if parent_right != nil {
parent_right.right = node.right
node.right = nil
goto END
}
if parent_left != nil {
parent_left.left = node.right
node.right = nil
goto END
}
}
//Two child
if node.left != nil && node.right != nil {
// Get Max from left
if deleteDirection == MaxFromLeft {
var prev_current_max *Node
current_max := node.left
for current_max.right != nil {
prev_current_max = current_max
current_max = current_max.right
}
//if current_max.left != nil {
if prev_current_max != nil {
prev_current_max.right = current_max.left
current_max.left = node.left
}
//}
if parent_left == nil && parent_right == nil {
root = current_max
}
if parent_left != nil && parent_right == nil {
parent_left.left = current_max
}
if parent_left == nil && parent_right != nil {
parent_right.right = current_max
}
current_max.right = node.right
node.right = nil
node.left = nil
goto END
}
//Get Min from right
if deleteDirection == MinFromRight {
var prev_current_min *Node
current_min := node.right
for current_min.left != nil {
prev_current_min = current_min
current_min = current_min.left
}
if prev_current_min != nil {
prev_current_min.left = current_min.right
current_min.right = node.right
}
if parent_left == nil && parent_right == nil {
root = current_min
}
if parent_left != nil && parent_right == nil {
parent_left.left = current_min
}
if parent_left == nil && parent_right != nil {
parent_right.right = current_min
}
current_min.left = node.left
node.right = nil
node.left = nil
goto END
}
}
}
END:
return root
}
func FindMin(root *Node) *Node {
//var prev_current_min *Node
current_min := root
for current_min.left != nil {
//prev_current_min = current_min
current_min = current_min.left
}
return current_min
}
func FindMax(root *Node) *Node {
//var prev_current_max *Node
current_max := root
for current_max.right != nil {
//prev_current_max = current_max
current_max = current_max.right
}
return current_max
}
func deleteNode_Recursion(root *Node, v value, deleteDirection DeleteDirection ) *Node {
if root != nil {
if root.id > v {
root.left = deleteNode_Recursion(root.left, v, deleteDirection)
goto END
}
if root.id < v {
root.left = deleteNode_Recursion(root.left, v, deleteDirection)
goto END
}
if root.id == v {
if root.left == nil && root.right == nil {
root = nil
goto END
}
if root.left == nil {
root = root.right
goto END
}
if root.right == nil {
root = root.left
goto END
}
//
if deleteDirection == MinFromRight {
min := FindMin(root.right)
root.id = min.id
root.right = deleteNode_Recursion(root.right, min.id, deleteDirection)
goto END
}
if deleteDirection == MaxFromLeft {
min := FindMax(root.left)
root.id = min.id
root.left = deleteNode_Recursion(root.left, min.id, deleteDirection)
goto END
}
}
}
END:
return root
}
func getRandomNode(root *Node) *Node {
var s, rn []*Node
v := map[value] bool{}
s = append(s, root)
v[root.id] = true
for len(s) > 0 {
n := s[len(s)-1]
s = s[:len(s)-1]
rn = append(rn, n)
if n.left != nil {
if !v[n.left.id] {
s = append(s, n.left)
v[n.left.id] = true
}
}
if n.right != nil {
if !v[n.right.id] {
s = append(s, n.right)
v[n.right.id] = true
}
}
}
rand.Seed(time.Now().UnixNano())
//fmt.Print("Total:", len(v), " Index:", )
//fmt.Println()
return rn[rand.Intn(len(v)-1)]
}
func InOrder(root *Node)[]value {
var result []value
if root != nil {
result = append(result, InOrder(root.left)...)
result = append(result, root.id)
result = append(result, InOrder(root.right)...)
}
return result
}
func PreOrder(root *Node) []value {
var result []value
if root != nil {
result = append(result, root.id)
result = append(result, PreOrder(root.left)...)
result = append(result, PreOrder(root.right)...)
}
return result
}
func PostOrder(root *Node) []value {
var result []value
if root != nil {
result = append(result, PostOrder(root.left)...)
result = append(result, PostOrder(root.right)...)
result = append(result, root.id)
}
return result
}
func CompareTree(expected *Node, actual * Node) bool {
IsIntArraysEquals := func (a []value, b []value) bool {
if len(a) != len(b) {
return false
}
for _, av := range a {
for _, bv := range b {
if av == bv {
goto Next
}
}
return false
Next:
}
return true
}
e_InOrder := InOrder(expected)
r_InOrder := InOrder(actual)
if !IsIntArraysEquals(e_InOrder,r_InOrder) {
fmt.Print("InOrder --> ")
fmt.Println()
fmt.Print("Expected:", e_InOrder)
fmt.Println()
fmt.Print("Actual: ", r_InOrder)
fmt.Println()
fmt.Println("--------------------------------------------------------------------------------")
fmt.Println()
return false
}
e_PreOrder := PreOrder(expected)
r_PreOrder := PreOrder(actual)
if !IsIntArraysEquals(e_PreOrder,r_PreOrder) {
fmt.Print("PreOrder --> ")
fmt.Println()
fmt.Print("Expected:", e_PreOrder)
fmt.Println()
fmt.Print("Actual: ", r_PreOrder)
fmt.Println()
fmt.Println("--------------------------------------------------------------------------------")
fmt.Println()
return false
}
e_PostOrder := PostOrder(expected)
r_PostOrder := PostOrder(actual)
if !IsIntArraysEquals(e_PostOrder,r_PostOrder) {
fmt.Print("PostOrder --> ")
fmt.Println()
fmt.Print("Expected:", e_PostOrder)
fmt.Println()
fmt.Print("Actual: ", r_PostOrder)
fmt.Println()
fmt.Println("--------------------------------------------------------------------------------")
fmt.Println()
return false
}
return true
}
func Test_DeleteNode(t *testing.T) {
testDatas := []struct{
root *Node
v value
derection DeleteDirection
result *Node
} {
//MaxFromLeft
{
&Node{
id: 12,
left: &Node{
id: 5,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
5,
MaxFromLeft,
&Node{
id: 12,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
},
{
&Node{
id: 12,
left: &Node{
id: 5,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
1,
MaxFromLeft,
&Node{
id: 12,
left: &Node{
id: 5,
left: &Node{
id: 3,
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
},
{
&Node{
id: 12,
left: &Node{
id: 5,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
3,
MaxFromLeft,
&Node{
id: 12,
left: &Node{
id: 5,
left: &Node{
id: 1,
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
},
{
&Node{
id: 12,
left: &Node{
id: 6,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
right: &Node{
id: 5,
left: &Node{
id: 4,
},
},
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
6,
MaxFromLeft,
&Node{
id: 12,
left: &Node{
id: 5,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
right: &Node{
id: 4,
},
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
},
{
&Node{
id: 12,
left: &Node{
id: 6,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
right: &Node{
id: 5,
left: &Node{
id: 4,
},
},
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
7,
MaxFromLeft,
&Node{
id: 12,
left: &Node{
id: 6,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
right: &Node{
id: 5,
left: &Node{
id: 4,
},
},
},
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
},
{
&Node{
id: 12,
left: &Node{
id: 6,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
right: &Node{
id: 5,
left: &Node{
id: 4,
},
},
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
9,
MaxFromLeft,
&Node{
id: 12,
left: &Node{
id: 6,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
right: &Node{
id: 5,
left: &Node{
id: 4,
},
},
},
right: &Node{
id: 7,
right: &Node{
id: 8,
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
},
{
&Node{
id: 12,
left: &Node{
id: 6,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
right: &Node{
id: 5,
left: &Node{
id: 4,
},
},
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
14,
MaxFromLeft,
&Node{
id: 12,
left: &Node{
id: 6,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
right: &Node{
id: 5,
left: &Node{
id: 4,
},
},
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 13,
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
},
{
&Node{
id: 12,
left: &Node{
id: 6,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
right: &Node{
id: 5,
left: &Node{
id: 4,
},
},
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
12,
MaxFromLeft,
&Node{
id: 11,
left: &Node{
id: 6,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
right: &Node{
id: 5,
left: &Node{
id: 4,
},
},
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
},
//MinFromRight
{
&Node{
id: 12,
left: &Node{
id: 6,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
right: &Node{
id: 5,
left: &Node{
id: 4,
},
},
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
6,
MinFromRight,
&Node{
id: 12,
left: &Node{
id: 7,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
right: &Node{
id: 5,
left: &Node{
id: 4,
},
},
},
right:&Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
},
{
&Node{
id: 12,
left: &Node{
id: 6,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
right: &Node{
id: 5,
left: &Node{
id: 4,
},
},
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
14,
MinFromRight,
&Node{
id: 12,
left: &Node{
id: 6,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
right: &Node{
id: 5,
left: &Node{
id: 4,
},
},
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 17,
left: &Node{
id: 13,
},
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
{
&Node{
id: 12,
left: &Node{
id: 6,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
right: &Node{
id: 5,
left: &Node{
id: 4,
},
},
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
18,
MinFromRight,
&Node{
id: 12,
left: &Node{
id: 6,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
right: &Node{
id: 5,
left: &Node{
id: 4,
},
},
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
},
},
},
},
},
{
&Node{
id: 12,
left: &Node{
id: 6,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
right: &Node{
id: 5,
left: &Node{
id: 4,
},
},
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
9,
MinFromRight,
&Node{
id: 12,
left: &Node{
id: 6,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
right: &Node{
id: 5,
left: &Node{
id: 4,
},
},
},
right: &Node{
id: 7,
right: &Node{
id: 11,
left: &Node{
id: 8,
},
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
},
{
&Node{
id: 12,
left: &Node{
id: 6,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
right: &Node{
id: 5,
left: &Node{
id: 4,
},
},
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 14,
left: &Node{
id: 13,
},
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
12,
MinFromRight,
&Node{
id: 13,
left: &Node{
id: 6,
left: &Node{
id: 3,
left: &Node{
id: 1,
},
right: &Node{
id: 5,
left: &Node{
id: 4,
},
},
},
right: &Node{
id: 7,
right: &Node{
id: 9,
left: &Node{
id: 8,
},
right: &Node{
id: 11,
},
},
},
},
right: &Node{
id: 14,
right: &Node{
id: 17,
right: &Node{
id: 20,
left: &Node{
id: 18,
},
},
},
},
},
},
}
for _, td := range testDatas {
r := deleteNode_Recursion(td.root, td.v, td.derection)
if !CompareTree(td.result, r) {
t.Errorf("Source: %v \n Expected: %v, Actual: %v",
td.root,
td.result,
r)
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment