Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 356
Good morning! Here's your coding interview problem for today.

This problem was asked by Netflix.

Implement a queue using a set of fixed-length arrays.

The queue should support `enqueue`, `dequeue`, and `get_size` operations.

Pull request:
Day356
Resolves #705.

Patch:
diff --git a/README.md b/README.md
index 450c65a..ad8a13b 100644
--- a/README.md
+++ b/README.md
@@ -340,6 +340,7 @@ problems from
 * [Day 350](https://github.com/vaskoz/dailycodingproblem-go/issues/695)
 * [Day 352](https://github.com/vaskoz/dailycodingproblem-go/issues/699)
 * [Day 353](https://github.com/vaskoz/dailycodingproblem-go/issues/701)
+* [Day 356](https://github.com/vaskoz/dailycodingproblem-go/issues/705)
 * [Day 359](https://github.com/vaskoz/dailycodingproblem-go/issues/708)
 * [Day 360](https://github.com/vaskoz/dailycodingproblem-go/issues/709)
 * [Day 361](https://github.com/vaskoz/dailycodingproblem-go/issues/712)
diff --git a/day356/problem.go b/day356/problem.go
new file mode 100644
index 0000000..bceab3b
--- /dev/null
+++ b/day356/problem.go
@@ -0,0 +1,102 @@
+package day356
+
+import "errors"
+
+const fixedArraySize = 10
+
+var errEmpty = errors.New("queue is empty")
+var errFull = errors.New("queue is full")
+
+// ErrEmpty is the error returned if queue is empty.
+func ErrEmpty() error {
+	return errEmpty
+}
+
+// ErrFull is the error returned if queue is full.
+func ErrFull() error {
+	return errFull
+}
+
+// NewQueueFLA returns a new instance of QueueFLA
+// with a given capacity.
+func NewQueueFLA(capacity int) QueueFLA {
+	slots := capacity / fixedArraySize
+	if capacity%fixedArraySize != 0 {
+		slots++
+	}
+	return &queueFLA{
+		set:       make([][fixedArraySize]interface{}, slots),
+		size:      0,
+		capacity:  capacity,
+		frontSlot: -1,
+		frontPos:  -1,
+		backSlot:  -1,
+		backPos:   -1,
+	}
+}
+
+// QueueFLA is a queue implemented using a set
+// of fixed-length arrays.
+// In this implementation, the fixed array size is 10.
+type QueueFLA interface {
+	Enqueue(interface{}) error
+	Dequeue() (interface{}, error)
+	Size() int
+}
+
+type queueFLA struct {
+	set                 [][fixedArraySize]interface{}
+	size, capacity      int
+	frontSlot, frontPos int
+	backSlot, backPos   int
+}
+
+// Enqueue attempts to add an item to the queue if there is room.
+func (q *queueFLA) Enqueue(item interface{}) error {
+	if q.size == q.capacity {
+		return errFull
+	}
+	q.size++
+	if q.frontSlot == -1 && q.frontPos == -1 {
+		q.frontSlot++
+		q.frontPos++
+		q.set[q.frontSlot][q.frontPos] = item
+		q.backSlot++
+		q.backPos++
+	} else {
+		q.backPos++
+		if q.backPos == fixedArraySize {
+			q.backPos = 0
+			q.backSlot++
+			if q.backSlot == len(q.set) {
+				q.backSlot = 0
+			}
+		}
+		q.set[q.backSlot][q.backPos] = item
+	}
+	return nil
+}
+
+// Dequeue attempts to remove an item from the queue if
+// the queue is not empty.
+func (q *queueFLA) Dequeue() (interface{}, error) {
+	if q.size == 0 {
+		return nil, errEmpty
+	}
+	q.size--
+	res := q.set[q.frontSlot][q.frontPos]
+	q.frontPos++
+	if q.frontPos == fixedArraySize {
+		q.frontPos = 0
+		q.frontSlot++
+		if q.frontSlot == len(q.set) {
+			q.frontSlot = 0
+		}
+	}
+	return res, nil
+}
+
+// Size returns the number of elements currently in the queue.
+func (q *queueFLA) Size() int {
+	return q.size
+}


Test patch:
diff --git a/day356/problem_test.go b/day356/problem_test.go
new file mode 100644
index 0000000..e8f73be
--- /dev/null
+++ b/day356/problem_test.go
@@ -0,0 +1,81 @@
+package day356
+
+import "testing"
+
+type action struct {
+	act  string
+	data interface{}
+	err  error
+}
+
+// nolint
+var testcases = []struct {
+	actions []action
+}{
+	{
+		[]action{
+			{"E", 100, nil}, {"S", 1, nil}, {"D", 100, nil},
+			{"D", nil, ErrEmpty()},
+		},
+	},
+	{
+		[]action{
+			{"E", 100, nil}, {"E", 200, nil}, {"E", 300, nil}, {"E", 400, nil}, {"E", 500, nil},
+			{"S", 5, nil}, {"E", 1000, ErrFull()},
+			{"D", 100, nil}, {"D", 200, nil},
+			{"S", 3, nil},
+			{"D", 300, nil}, {"D", 400, nil},
+			{"S", 1, nil},
+			{"E", 600, nil}, {"E", 700, nil}, {"E", 800, nil}, {"E", 900, nil},
+			{"E", 1000, ErrFull()},
+			{"D", 500, nil}, {"D", 600, nil}, {"D", 700, nil}, {"D", 800, nil},
+			{"S", 1, nil},
+			{"E", 1000, nil}, {"E", 1100, nil}, {"E", 1200, nil}, {"E", 1300, nil},
+			{"S", 5, nil},
+			{"D", 900, nil}, {"D", 1000, nil}, {"D", 1100, nil}, {"D", 1200, nil}, {"D", 1300, nil},
+			{"S", 0, nil},
+			{"D", nil, ErrEmpty()},
+		},
+	},
+}
+
+func TestQueueFLA(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		q := NewQueueFLA(5)
+		for _, action := range tc.actions {
+			switch action.act {
+			case "E":
+				if err := q.Enqueue(action.data); err != action.err {
+					t.Errorf("Expected %v, got %v", action.err, err)
+				}
+			case "D":
+				if item, err := q.Dequeue(); item != action.data || err != action.err {
+					t.Errorf("Expected (%v,%v), got (%v,%v)", action.data, action.err, item, err)
+				}
+			case "S":
+				if s := q.Size(); s != action.data {
+					t.Errorf("Expected a size of %d, got %d", action.data, s)
+				}
+			}
+		}
+	}
+}
+
+func BenchmarkQueueFLA(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			q := NewQueueFLA(5)
+			for _, action := range tc.actions {
+				switch action.act {
+				case "E":
+					q.Enqueue(action.data) // nolint
+				case "D":
+					q.Dequeue() // nolint
+				case "S":
+					q.Size()
+				}
+			}
+		}
+	}
+}