4
\$\begingroup\$

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
}
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – hoffmale Jul 6 '18 at 14:42
  • \$\begingroup\$ @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? \$\endgroup\$ – Blackstone4 Jul 7 '18 at 10:22
  • \$\begingroup\$ 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). \$\endgroup\$ – hoffmale Jul 7 '18 at 10:28
  • \$\begingroup\$ @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) \$\endgroup\$ – Blackstone4 Jul 7 '18 at 11:04
  • \$\begingroup\$ @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 \$\endgroup\$ – Blackstone4 Jul 7 '18 at 12:01
1
\$\begingroup\$

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)
    }
}
\$\endgroup\$
  • \$\begingroup\$ By the way, no need to rewrite binary search when sort.Search is available. \$\endgroup\$ – Dave C Sep 3 '18 at 19:16
  • 1
    \$\begingroup\$ True - I was doing it as a learning exercise. \$\endgroup\$ – Blackstone4 Sep 4 '18 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.