Go: Fibonacci Sequence Rate Limiter
Date
Author
A fibonacci with modulo sequence is defined for a given modulo, mod, as follows:
- fib[x] = (fib[x – 1] + fib[x – 2]) % mod, x > 2
- fib[1] = 1, fib[2] = 2
[1, 2, 3, 5, 8, 13, 21 …] are the first few terms of the Fibonacci sequence. In this task, you are required to write a function that runs a server that generates a Fibonacci sequence.
It accepts boolean requests and returns the next number in the sequence. It should have rate limiter which should make the server send every response no earlier than 10 milliseconds after the previous one. The server should be created with two arguments – a boolean channel that accepts requests and a result int channel through which every result will be returned. The main function will also accept two arguments: the number of results that will be skipped from the beginning, and the number of results that will be printed to the console.
Note: Since the numbers can be large, the server must return the number modulo 109. For example, for the 50th Fibonacci number – 12586269025, the server should return 586269025.
For example, using the arguments 2 and 5 results in [3, 5, 8, 13, 21].
Function Description
Complete the function ModuloFibonacciSequence in the editor below. The function will return nothing as all its results will be returned through a channel.
ModuloFibonacciSequence has the following parameter(s):
requestChan: a channel of booleans (chan bool)
resultChan: a channel of integers (chan int)
Constraints
- 0 ≤ skip ≤ 100
- 1 ≤ total ≤ 200
SOLUTION:
package main
import (
"bufio"
"fmt"
"io"
"os"
"strconv"
"strings"
"time"
)
func ModuloFibonacciSequence(requestChan chan bool, resultChan chan int) {
a, b := 1, 2
for {
select {
case <-requestChan:
resultChan <- a
a, b = b, (a+b)%1000000000
time.Sleep(10 * time.Millisecond)
}
}
}
func main() {
reader := bufio.NewReaderSize(os.Stdin, 16 * 1024 * 1024)
skipTemp, err := strconv.ParseInt(strings.TrimSpace(readLine(reader)), 10, 64)
checkError(err)
skip := int32(skipTemp)
totalTemp, err := strconv.ParseInt(strings.TrimSpace(readLine(reader)), 10, 64)
checkError(err)
total := int32(totalTemp)
resultChan := make(chan int)
requestChan := make(chan bool)
go ModuloFibonacciSequence(requestChan, resultChan)
for i := int32(0); i < skip + total; i++ {
start := time.Now().UnixNano()
requestChan <- true
new := <-resultChan
if i < skip {
continue
}
end := time.Now().UnixNano()
timeDiff := (end - start)/1000000
if timeDiff < 10 {
time.Sleep(10*time.Millisecond - time.Duration(timeDiff)*time.Millisecond)
}
fmt.Println(new)
}
}
func readLine(reader *bufio.Reader) string {
str, _, err := reader.ReadLine()
if err == io.EOF {
return ""
}
return strings.TrimRight(string(str), "\r\n")
}
func checkError(err error) {
if err != nil {
panic(err)
}
}