Inefficient binary search? Hackerrank - Climbing the Leaderboard

I'm learning Golang and have been trying to get 100% on the following Hackerrank practice challenge: Climbing the Leaderboard

The code passes ~8 of 11 tests. The Hackerrank tests are time-bound and my code is not efficient enough to past the most intensive tests.

I'm removing duplicates from the scores using a map. Then work through each of Alice's scores to find the index of each one by doing a binary search. Given that Alice's scored are sorted, I re-use the index for the next search.

Any ideas?

package main

import (
"fmt"
)

func main() {

// example 1
scores := []int32{100, 100, 50, 40, 40, 20, 10}
alice := []int32{5, 25, 50, 120}
r := climbingLeaderboard(scores, alice)
for a, v := range r {
fmt.Printf("Position: %d alice[a]: %d\n", v, alice[a])
}
fmt.Printf("\n")
}

func removeDuplicates(a []int32) []int32 {
r := []int32{}
seen := map[int32]int32{}
for _, val := range a {
if _, ok := seen[val]; !ok {
r = append(r, val)
seen[val] = val
}
}
return r
}

func getMidPoint(start, end int) int {
i := end - start
if i%2 == 0 {
return i/2 + start
}
return (i+1)/2 + start
}

// 100 100 50 40 40 20 10
// 100 50 40 20 10
// 0   1  2  3  4
func binarySearch(scores []int32, v int32, i int) int {
var mid int
start := 0
end := i

for true {
if end-start == 1 {
//fmt.Printf("1 - v: %d start: %d end %d\n", v, start, end)
if v < scores[end] {
return end + 2
} else if v < scores[start] {
return start + 2
}
return 1
}
if end == 0 {
return 1
}

mid = getMidPoint(start, end)

if v > scores[mid] {
end = mid
} else if v < scores[mid] {
start = mid
} else {
// v == scores[mid]
//fmt.Printf("2 - v: %d start: %d end %d\n", v, start, end)
return mid + 1
}
}
return end
}

// attempt 3 - binary search
func climbingLeaderboard(originalScores []int32, alice []int32) []int32 {

r := make([]int32, len(alice))

//create scores and remove dups
scores := removeDuplicates(originalScores)
i := len(scores)

for a, v := range alice {
// fmt.Printf("1 - i: %d a: %d alice[a]: %d\n", i, a, alice[a])
i = binarySearch(scores, v, i-1)
r[a] = int32(i)
}

return r
}
• Do you get "Runtime Error :(" or "Time limit exceeded" as feedback on hackerrank? It seems like the provided parsing code is broken, which fires a panic on test cases 6, 8 and/or 9. – hoffmale Jul 6 '18 at 14:42
• @hoffmale good point. I got a "Runtime Error :(" response (I had initially assumed it was due to a timeout). How come the parsing code breaks for tests 6,8 and 9 but works for the other tests? – Blackstone4 Jul 7 '18 at 10:22
• I tracked it down to the first loop (where it reads the original scores). My best guess would be that there's an unexpected whitespace somewhere in the input file, so strconv.ParseInt fails on an empty string. Most other languages (that I looked at) were far more tolerant for this case. The parsing code can be adapted to use fmt.Fscan to get the same behavior.as the other languages (it even simplyfies the parsing code a bit). – hoffmale Jul 7 '18 at 10:28
• @hoffmale you're right. I downloaded the input data and ran it locally with some debugging comments. I'm getting an "panic: runtime error: index out of range" on the following code scoresItemTemp, err := strconv.ParseInt(scoresTemp[i], 10, 64) – Blackstone4 Jul 7 '18 at 11:04
• @hoffmale making progress... I increased the size of the Reader's memory and tests 6 and 9 now work. reader := bufio.NewReaderSize(os.Stdin, 1024*1024*3). Previously it couldn't read in all of the input so I was seeing this: int(scoresCount): 200000 len(scoresTemp): 104858. It's still failing test 8 with an  index out of range error when int(scoresCount): 200000 len(scoresTemp): 200000 – Blackstone4 Jul 7 '18 at 12:01

As @hoffmale correctly pointed out, the Hackerrank code to read in the input files on the larger tests was causing a problem. More specifically it didn't have enough memory to read in the array. So I increased the size of the reader and the writer (just in case). I also made a change to my binary search to ensure end would not be out of bounds on scores.

package main

import (
"bufio"
"fmt"
"io"
"os"
"strconv"
"strings"
)

func removeDuplicates(a []int) []int {
r := []int{}
seen := map[int]int{}
for _, val := range a {
if _, ok := seen[val]; !ok {
r = append(r, val)
seen[val] = val
}
}
return r
}

func getMidPoint(start, end int) int {
i := end - start
if i%2 == 0 {
return i/2 + start
}
return (i+1)/2 + start
}

func binarySearch(scores []int, v int, i int) int {
var mid int
var end int

start := 0
if i >= len(scores) {
end = len(scores) - 1
} else {
end = i
}

for true {
if end-start == 1 {
// fmt.Printf("1 - v: %d start: %d end %d\n", v, start, end)
if v < scores[end] {
return end + 2
} else if v < scores[start] {
return start + 2
}
return 1
}
if end == 0 {
return 1
}

mid = getMidPoint(start, end)

if v > scores[mid] {
end = mid
} else if v < scores[mid] {
start = mid
} else {
// v == scores[mid]
// fmt.Printf("2 - v: %d start: %d end %d\n", v, start, end)
return mid + 1
}
}
return end
}

// attempt 3 - binary search
func climbingLeaderboard(originalScores []int, alice []int) []int {

r := make([]int, len(alice))

//create scores and remove dups
scores := removeDuplicates(originalScores)
i := len(scores)

for a, v := range alice {
// fmt.Printf("1 - i: %d a: %d alice[a]: %d\n", i, a, alice[a])
i = binarySearch(scores, v, i-1)
r[a] = i
}

return r
}

func main() {

stdout, err := os.Create(os.Getenv("OUTPUT_PATH"))
checkError(err)

defer stdout.Close()

writer := bufio.NewWriterSize(stdout, 1024 * 1024*3)

checkError(err)

var scores []int

for i := 0; i < int(scoresCount); i++ {
scoresItemTemp, err := strconv.ParseInt(scoresTemp[i], 10, 64)
checkError(err)
scoresItem := int(scoresItemTemp)
scores = append(scores, scoresItem)
}

checkError(err)

var alice []int

for i := 0; i < int(aliceCount); i++ {
aliceItemTemp, err := strconv.ParseInt(aliceTemp[i], 10, 64)
checkError(err)
aliceItem := int(aliceItemTemp)
alice = append(alice, aliceItem)
}

result := climbingLeaderboard(scores, alice)

for i, resultItem := range result {
fmt.Fprintf(writer, "%d", resultItem)

if i != len(result) - 1 {
fmt.Fprintf(writer, "\n")
}
}

fmt.Fprintf(writer, "\n")

writer.Flush()
}

if err == io.EOF {
return ""
}

return strings.TrimRight(string(str), "\r\n")
}

func checkError(err error) {
if err != nil {
// fmt.Println("Error: " + err.Error())
panic(err)
}
}
• By the way, no need to rewrite binary search when sort.Search is available. – Dave C Sep 3 '18 at 19:16
• True - I was doing it as a learning exercise. – Blackstone4 Sep 4 '18 at 19:15