Inefficient binary search? Hackerrank - Climbing the Leaderboard

Question

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
}

Answer 1

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.

reader := bufio.NewReaderSize(os.Stdin, 1024*1024*3)

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() {
    reader := bufio.NewReaderSize(os.Stdin, 1024 * 1024*3)

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

    defer stdout.Close()

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

    scoresCount, err := strconv.ParseInt(readLine(reader), 10, 64)
    checkError(err)

    scoresTemp := strings.Split(readLine(reader), " ")

    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)
    }

    aliceCount, err := strconv.ParseInt(readLine(reader), 10, 64)
    checkError(err)

    aliceTemp := strings.Split(readLine(reader), " ")

    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()
}

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 {
        // fmt.Println("Error: " + err.Error())
        panic(err)
    }
}