CareerCup

/* A naive solution is mark the time index and increment.
When we add a [start,end] we add and mark all time slices
between these -- but terrible usage of memory : call it version 1
*/
def mark_and_inc( history, log_slice ){
  for ( t = log_slice.start ; t <= log_slice.end ; t+= 1 ){
    if ( t !@ history ){
      history[t] = 0
    }
    history[t] +=1
  }
}
// create history by repeating mark and add 
def create_history( logs ){
  history = dict()
  for ( l : logs ){
    mark_and_inc( history, l)
  }
  history // return 
}
// create history 
history = create_history( logs )
// query is as straight forward as 
def process_count_at( t ){
  t @ history ? history[t] : 0
}

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.