3/08/2017

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


댓글 없음:

댓글 쓰기

UIUC MCS-DS 2018 가을학기 끝, 그리고 2019 봄학기 등록 과목

이 포스팅은 제 미디엄(https://medium.com/@wjung/) 에 작성된 것의 중복포스팅입니다. 2018년 가을학기의 과목이었던 CS410 Text Information System을 드디어 끝냈다. 기말고사는 거의 2주 쯤 전인 12...