Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 134
Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

You have a large array with most of the elements as zero.

Use a more space-efficient data structure, SparseArray, that implements the same interface:
```
init(arr, size): initialize with the original large array and size.
set(i, val): updates index at i with val.
get(i): gets the value at index i.
```

Pull request:
Day134
Resolves #278.

Patch:
diff --git a/README.md b/README.md
index 44e6503..565b564 100644
--- a/README.md
+++ b/README.md
@@ -142,3 +142,4 @@ problems from
 * [Day 131](https://github.com/vaskoz/dailycodingproblem-go/issues/270)
 * [Day 132](https://github.com/vaskoz/dailycodingproblem-go/issues/272)
 * [Day 133](https://github.com/vaskoz/dailycodingproblem-go/issues/275)
+* [Day 134](https://github.com/vaskoz/dailycodingproblem-go/issues/278)
diff --git a/day134/problem.go b/day134/problem.go
new file mode 100644
index 0000000..c34abc0
--- /dev/null
+++ b/day134/problem.go
@@ -0,0 +1,56 @@
+package day134
+
+import "fmt"
+
+// SparseArray is a space-efficient array for one containing
+// mostly zeros.
+type SparseArray struct {
+	data map[int]int
+	size int
+}
+
+var errIndexOutOfRange = fmt.Errorf("Index is out of range")
+
+// ErrIndexOutOfRange returns the error that's associated with access beyond
+// the limits of the SparseArray.
+func ErrIndexOutOfRange() error {
+	return errIndexOutOfRange
+}
+
+// NewSparseArray initializes a SparseArray with an original array.
+func NewSparseArray(arr []int) *SparseArray {
+	sa := &SparseArray{make(map[int]int), len(arr)}
+	for i := range arr {
+		if arr[i] != 0 {
+			sa.data[i] = arr[i]
+		}
+	}
+	return sa
+}
+
+// Set mutates the value at position 'i' with value 'val'.
+func (sa *SparseArray) Set(i, val int) error {
+	if sa == nil {
+		return fmt.Errorf("Create with NewSparseArray")
+	}
+	if i >= sa.size || i < 0 {
+		return errIndexOutOfRange
+	}
+	if val == 0 {
+		delete(sa.data, i)
+	} else {
+		sa.data[i] = val
+	}
+	return nil
+}
+
+// Get returns the value at position 'i'.
+func (sa *SparseArray) Get(i int) (int, error) {
+	if sa == nil {
+		return 0, fmt.Errorf("Create with NewSparseArray")
+	}
+	if i >= sa.size || i < 0 {
+		return 0, errIndexOutOfRange
+	}
+	return sa.data[i], nil
+}


Test patch:
diff --git a/day134/problem_test.go b/day134/problem_test.go
new file mode 100644
index 0000000..63c10d0
--- /dev/null
+++ b/day134/problem_test.go
@@ -0,0 +1,59 @@
+package day134
+
+import (
+	"testing"
+)
+
+func TestSparseArray(t *testing.T) {
+	t.Parallel()
+	arr := []int{0, 0, 0, 0, 9, 8, 7, 6, 0, 0}
+	sa := NewSparseArray(arr)
+	for i, val := range arr {
+		if result, err := sa.Get(i); result != val || err != nil {
+			t.Errorf("Expected (%v,%v) got (%v,%v)", val, nil, result, err)
+		}
+	}
+	sa.Set(0, 10)
+	if result, err := sa.Get(0); result != 10 || err != nil {
+		t.Errorf("Set didn't work properly")
+	}
+	sa.Set(0, 0)
+	for i, val := range arr {
+		if result, err := sa.Get(i); result != val || err != nil {
+			t.Errorf("Expected (%v,%v) got (%v,%v)", val, nil, result, err)
+		}
+	}
+}
+
+func TestSparseArrayNoInit(t *testing.T) {
+	t.Parallel()
+	var sa *SparseArray
+	if err := sa.Set(0, 1); err == nil {
+		t.Errorf("Set returns an error if called before Init")
+	}
+	if _, err := sa.Get(0); err == nil {
+		t.Errorf("Get returns an error if called before Init")
+	}
+}
+
+func TestSparseArrayOutOfRange(t *testing.T) {
+	t.Parallel()
+	sa := NewSparseArray([]int{1})
+	if err := sa.Set(1, 1); err != ErrIndexOutOfRange() {
+		t.Errorf("Index 1 is out of range")
+	}
+	if _, err := sa.Get(-1); err != ErrIndexOutOfRange() {
+		t.Errorf("Index -1 is out of range")
+	}
+}
+
+func BenchmarkSparseArray(b *testing.B) {
+	arr := []int{0, 0, 0, 0, 9, 8, 7, 6, 0, 0}
+	sa := NewSparseArray(arr)
+	for i := 0; i < b.N; i++ {
+		sa.Set(0, 10)
+		sa.Get(0)
+		sa.Set(0, 0)
+
+	}
+}