2017년 3월 8일 수요일

Hackerrank Array Left Rotation test case failing at test case 6, 8, 9

I'm learning GoLang and decided to do some algorithm quiz at Hackerrank with Go instead of reading and just follow up the tutorial code.

The one I tried yesterday was https://www.hackerrank.com/challenges/ctci-array-left-rotation

Following was my initial solution. It's kind of brute-force algorithm for shift things left, but anyway...

package main
import (
    "fmt"
    "strings"
    "bufio"
    "os"
    "bytes"
)

func main() {
    var len, nToRotate int
    var input string
    var buffer bytes.Buffer
    
    fmt.Scanln(&len, &nToRotate)
    
    scanner := bufio.NewScanner(os.Stdin)
    for scanner.Scan() {
        buffer.WriteString(scanner.Text())
    }
    input = buffer.String()
    var items []string
    items = strings.Fields(input)
    
    //fmt.Printf("%d", len(items))
    
    for i := 0; i < nToRotate; i++ {
        items = append(items[1:], items[0])
    }
    
    fmt.Println(strings.Join(items[:]," "))
}

My code passed the test when I clicked "Run Code", but it's failing unit test 6, 8, 9 when submitting the code. Those 6, 8, and 9 is pretty long one line input string and I was wondering if it's some kind of timeout or library error due to input string size.

After hours of investigation and asking questions to other GoLang experts ( than me ), I was able to pass all the tests and submitted the solution. Here is my answer. I changed algorithm a bit to be more time/space efficient as well. Check the highlighted line which was the solution of Runtime Error in Hackerrank page.

package main
import (
 "fmt"
)


func main() {
 var (
  length, nToRotate int
 )

 fmt.Scanln(&length, &nToRotate)

 items := make([]string, length)
 for i := 0; i < length; i++ {
  fmt.Scan(&items[i])
 }

 items = ShiftLeft(items, nToRotate)

 for i := 0; i < len(items); i++ {
  fmt.Printf("%s ", items[i])
 }
}

func ShiftLeft(items []string, nToRotate int) []string {
 var (
  i, j, k int
  temp string
 )
 size := len(items)
 for i = 0; i < gcd(nToRotate, size); i++ {
  temp = items[i];
  j = i
  for {
   k = j + nToRotate
   if k >= size {
    k = k - size
   }
   if k == i {
    break
   }
   items[j] = items[k]
   j = k
  }
  items[j] = temp
 }
 return items
}

func gcd(x, y int) int {
 for y != 0 {
  x, y = y, x % y
 }
 return x
}


And I just found that someone already had same issue (of course) with Go, and opened issue at GoLang's GitHub page. Check those conversation if you want to understand more about the issue.

https://github.com/golang/go/issues/17910


댓글 없음:

댓글 쓰기

가장 많이 본 글