Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 242
Good morning! Here's your coding interview problem for today.

This problem was asked by Twitter.

You are given an array of length 24, where each element represents the number of new subscribers during the corresponding hour. Implement a data structure that efficiently supports the following:

* `update(hour: int, value: int)`: Increment the element at index hour by value.
* `query(start: int, end: int)`: Retrieve the number of subscribers that have signed up between start and end (inclusive).

You can assume that all values get cleared at the end of the day, and that you will not be asked for start and end values that wrap around midnight.

Pull request:
Day242
Resolves #498.

Patch:
diff --git a/README.md b/README.md
index 9188c9f..d42c62a 100644
--- a/README.md
+++ b/README.md
@@ -251,3 +251,4 @@ problems from
 * [Day 238](https://github.com/vaskoz/dailycodingproblem-go/issues/489)
 * [Day 240](https://github.com/vaskoz/dailycodingproblem-go/issues/492)
 * [Day 241](https://github.com/vaskoz/dailycodingproblem-go/issues/493)
+* [Day 242](https://github.com/vaskoz/dailycodingproblem-go/issues/498)
diff --git a/day242/problem.go b/day242/problem.go
new file mode 100644
index 0000000..e8dab7c
--- /dev/null
+++ b/day242/problem.go
@@ -0,0 +1,88 @@
+package day242
+
+import "sync"
+
+// DailySubscriber is an interface that describes the two actions.
+type DailySubscriber interface {
+	Update(hour, value int)
+	Query(start, end int) int
+}
+
+type readOptimized struct {
+	sync.RWMutex
+	data [24]int
+}
+
+// NewReadOptimized returns a read-optimized version.
+func NewReadOptimized(data [24]int) DailySubscriber {
+	sum := data[0]
+	for i := 1; i < 24; i++ {
+		sum += data[i]
+		data[i] = sum
+	}
+	return &readOptimized{data: data}
+}
+
+func (r *readOptimized) Update(hour, value int) {
+	if hour < 0 || hour > 23 {
+		panic("invalid hour")
+	}
+	r.Lock()
+	for i := hour; i < 24; i++ {
+		r.data[i] += value
+	}
+	r.Unlock()
+}
+
+func (r *readOptimized) Query(start, end int) int {
+	if start < 0 || start > 23 || end < 0 || end > 23 {
+		panic("start and end must be between 0-23 inclusive")
+	}
+	if start > end {
+		panic("start must preceed or equal end")
+	}
+	r.RLock()
+	var sum int
+	if start == 0 {
+		sum = r.data[end]
+	} else {
+		sum = r.data[end] - r.data[start-1]
+	}
+	r.RUnlock()
+	return sum
+}
+
+type writeOptimized struct {
+	sync.RWMutex
+	data [24]int
+}
+
+// NewWriteOptimized returns a write-optimized version.
+func NewWriteOptimized(data [24]int) DailySubscriber {
+	return &writeOptimized{data: data}
+}
+
+func (w *writeOptimized) Update(hour, value int) {
+	if hour < 0 || hour > 23 {
+		panic("invalid hour")
+	}
+	w.Lock()
+	w.data[hour] += value
+	w.Unlock()
+}
+
+func (w *writeOptimized) Query(start, end int) int {
+	if start < 0 || start > 23 || end < 0 || end > 23 {
+		panic("start and end must be between 0-23 inclusive")
+	}
+	if start > end {
+		panic("start must preceed or equal end")
+	}
+	w.RLock()
+	var sum int
+	for i := start; i <= end; i++ {
+		sum += w.data[i]
+	}
+	w.RUnlock()
+	return sum
+}


Test patch:
diff --git a/day242/problem_test.go b/day242/problem_test.go
new file mode 100644
index 0000000..0ca59a4
--- /dev/null
+++ b/day242/problem_test.go
@@ -0,0 +1,196 @@
+package day242
+
+import (
+	"sync"
+	"testing"
+)
+
+// Read-optimized
+func TestReadOptimized(t *testing.T) {
+	t.Parallel()
+	input := [24]int{100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 1100, 1200, 1300, 1400,
+		1500, 1600, 1700, 1800, 1900, 2000, 2100, 2200, 2300, 2400}
+	ds := NewReadOptimized(input)
+	if sum := ds.Query(0, 23); sum != 30000 {
+		t.Errorf("Expected 30000, got %v", sum)
+	}
+	ds.Update(20, 100)
+	if sum := ds.Query(0, 23); sum != 30100 {
+		t.Errorf("Expected 30100, got %v", sum)
+	}
+	ds.Update(20, 1000)
+	if sum := ds.Query(20, 20); sum != 3200 {
+		t.Errorf("Expected 3200, got %v", sum)
+	}
+}
+
+func TestReadOptimizedConcurrently(t *testing.T) {
+	t.Parallel()
+	input := [24]int{100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 1100, 1200, 1300, 1400,
+		1500, 1600, 1700, 1800, 1900, 2000, 2100, 2200, 2300, 2400}
+	ds := NewReadOptimized(input)
+	var wg sync.WaitGroup
+	wg.Add(2)
+	go func() {
+		for i := 0; i < 24; i++ {
+			ds.Update(i, 100)
+		}
+		wg.Done()
+	}()
+	go func() {
+		for i := 0; i < 24; i++ {
+			ds.Update(i, -200)
+		}
+		wg.Done()
+	}()
+	wg.Wait()
+	if sum := ds.Query(0, 23); sum != 27600 {
+		t.Errorf("Expected 27600, got %v", sum)
+	}
+}
+
+func TestReadOptimizedInvalidInputUpdate(t *testing.T) {
+	t.Parallel()
+	defer func() {
+		if err := recover(); err == nil {
+			t.Errorf("expected an error for bad hour value")
+		}
+	}()
+	ds := NewReadOptimized([24]int{})
+	ds.Update(24, 100)
+}
+
+func TestReadOptimizedInvalidInputQuery(t *testing.T) {
+	t.Parallel()
+	defer func() {
+		if err := recover(); err == nil {
+			t.Errorf("expected an error for bad hour value")
+		}
+	}()
+	ds := NewReadOptimized([24]int{})
+	ds.Query(-1, 100)
+}
+
+func TestReadOptimizedQueryStartAfterEnd(t *testing.T) {
+	t.Parallel()
+	defer func() {
+		if err := recover(); err == nil {
+			t.Errorf("expected an error for bad hour value")
+		}
+	}()
+	ds := NewReadOptimized([24]int{})
+	ds.Query(21, 20)
+}
+
+func BenchmarkReadOptimizedReads(b *testing.B) {
+	input := [24]int{100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 1100, 1200, 1300, 1400,
+		1500, 1600, 1700, 1800, 1900, 2000, 2100, 2200, 2300, 2400}
+	ds := NewReadOptimized(input)
+	for i := 0; i < b.N; i++ {
+		ds.Query(0, 23)
+	}
+}
+
+func BenchmarkReadOptimizedWrites(b *testing.B) {
+	input := [24]int{100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 1100, 1200, 1300, 1400,
+		1500, 1600, 1700, 1800, 1900, 2000, 2100, 2200, 2300, 2400}
+	ds := NewReadOptimized(input)
+	for i := 0; i < b.N; i++ {
+		ds.Update(i%24, 1)
+	}
+}
+
+// Write-optimized
+func TestWriteOptimized(t *testing.T) {
+	t.Parallel()
+	input := [24]int{100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 1100, 1200, 1300, 1400,
+		1500, 1600, 1700, 1800, 1900, 2000, 2100, 2200, 2300, 2400}
+	ds := NewWriteOptimized(input)
+	if sum := ds.Query(0, 23); sum != 30000 {
+		t.Errorf("Expected 30000, got %v", sum)
+	}
+	ds.Update(20, 100)
+	if sum := ds.Query(0, 23); sum != 30100 {
+		t.Errorf("Expected 30100, got %v", sum)
+	}
+	ds.Update(20, 1000)
+	if sum := ds.Query(20, 20); sum != 3200 {
+		t.Errorf("Expected 3200, got %v", sum)
+	}
+}
+
+func TestWriteOptimizedConcurrently(t *testing.T) {
+	t.Parallel()
+	input := [24]int{100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 1100, 1200, 1300, 1400,
+		1500, 1600, 1700, 1800, 1900, 2000, 2100, 2200, 2300, 2400}
+	ds := NewWriteOptimized(input)
+	var wg sync.WaitGroup
+	wg.Add(2)
+	go func() {
+		for i := 0; i < 24; i++ {
+			ds.Update(i, 100)
+		}
+		wg.Done()
+	}()
+	go func() {
+		for i := 0; i < 24; i++ {
+			ds.Update(i, -200)
+		}
+		wg.Done()
+	}()
+	wg.Wait()
+	if sum := ds.Query(0, 23); sum != 27600 {
+		t.Errorf("Expected 27600, got %v", sum)
+	}
+}
+
+func TestWriteOptimizedInvalidInputUpdate(t *testing.T) {
+	t.Parallel()
+	defer func() {
+		if err := recover(); err == nil {
+			t.Errorf("expected an error for bad hour value")
+		}
+	}()
+	ds := NewWriteOptimized([24]int{})
+	ds.Update(24, 100)
+}
+
+func TestWriteOptimizedInvalidInputQuery(t *testing.T) {
+	t.Parallel()
+	defer func() {
+		if err := recover(); err == nil {
+			t.Errorf("expected an error for bad hour value")
+		}
+	}()
+	ds := NewWriteOptimized([24]int{})
+	ds.Query(-1, 100)
+}
+
+func TestWriteOptimizedQueryStartAfterEnd(t *testing.T) {
+	t.Parallel()
+	defer func() {
+		if err := recover(); err == nil {
+			t.Errorf("expected an error for bad hour value")
+		}
+	}()
+	ds := NewWriteOptimized([24]int{})
+	ds.Query(21, 20)
+}
+
+func BenchmarkWriteOptimizedReads(b *testing.B) {
+	input := [24]int{100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 1100, 1200, 1300, 1400,
+		1500, 1600, 1700, 1800, 1900, 2000, 2100, 2200, 2300, 2400}
+	ds := NewWriteOptimized(input)
+	for i := 0; i < b.N; i++ {
+		ds.Query(0, 23)
+	}
+}
+
+func BenchmarkWriteOptimizedWrites(b *testing.B) {
+	input := [24]int{100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 1100, 1200, 1300, 1400,
+		1500, 1600, 1700, 1800, 1900, 2000, 2100, 2200, 2300, 2400}
+	ds := NewWriteOptimized(input)
+	for i := 0; i < b.N; i++ {
+		ds.Update(i%24, 1)
+	}
+}