Amazon Interview Question
Java DevelopersCountry: United States
Interval tree problem
package main
import "fmt"
type Interval struct {
Start int
End int
}
type IntervalTree struct {
Val Interval
Max int
Left *IntervalTree
Right *IntervalTree
}
func Insert(root *IntervalTree, val Interval) *IntervalTree {
if root == nil {
return &IntervalTree{
Val: val,
Max: val.End,
}
}
if val.Start < root.Val.Start {
root.Left = Insert(root.Left, val)
} else {
root.Right = Insert(root.Right, val)
}
if root.Max < val.End {
root.Max = val.End
}
return root
}
func CountIntervals(root *IntervalTree, search int) int {
if root == nil || root.Max < search {
return 0
}
res := 0
if root.Val.Start <= search && root.Val.End >= search {
res = 1
}
res += CountIntervals(root.Left, search)
res += CountIntervals(root.Right, search)
return res
}
func BuildTree(intervals []Interval) *IntervalTree {
var root *IntervalTree
for _, interval := range intervals {
root = Insert(root, interval)
}
return root
}
func main() {
root := BuildTree([]Interval{
Interval{1, 1234},
Interval{2, 1234},
})
fmt.Println(CountIntervals(root, 2))
fmt.Println(CountIntervals(root, 1))
fmt.Println(CountIntervals(root, 1235))
root = BuildTree([]Interval{
Interval{15, 20},
Interval{10, 30},
Interval{5, 20},
Interval{12, 15},
Interval{17, 19},
Interval{30, 40},
})
fmt.Println(CountIntervals(root, 18))
fmt.Println(CountIntervals(root, 30))
fmt.Println(CountIntervals(root, 14))
fmt.Println(CountIntervals(root, 4))
fmt.Println(CountIntervals(root, 44))
}
Separate out start and end lists. On every start increment the counter by 1 and every end decrement by 1.
While doing all of that, maintain a query index (one iteration may satisfy multiple query indices).
if q[index] >= prev && q[index] < curr (can be either start or end), store the value of counter.
- NoOne March 05, 2018