5
\$\begingroup\$

I saw this question on one of the socials, presented as an Apple interview question. I have had to paraphrase as it was not given in text format. (Credit: Instagram @greghogg5)

Given a string (S) which is guaranteed to contain only uppercase and lowercase alpha characters, return the number of times that the character changes, not considering case; i.e. "aAa" -> 0, "aBbA" -> 2

Here is my Go code:

strchange.go

package strchange

import (
    "bytes"
)

func CountStringChange(str string) int {
    var (
        count int
        cur   rune
    )

    arr := bytes.Runes([]byte(str))

    for i := 0; i < len(arr)-1; i++ {
        cur = arr[i]
        // Upper- and lowercase characters are 0x20 bits apart in ASCII
        if cur&^0x20 != arr[i+1]&^0x20 {
            count++
        }
    }

    return count
}

and my test cases:

strchange_test.go

package strchange

import (
    "fmt"
    "testing"
)

func TestStrChange(t *testing.T) {
    cases := []struct {
        str      string
        expected int
    }{
        {"aaa", 0},
        {"aAa", 0},
        {"aaAAbBbb", 1},
        {"abba", 2},
        {"abBa", 2},
        {"abbba", 2},
        {"abBba", 2},
        {"aBbBcCcA", 3},
        {"aAaBbBcCcAaA", 3},
    }
    for _, c := range cases {
        actual := CountStringChange(c.str)
        fmt.Printf("string: %s\t expected: %d actual: %d\n", c.str, c.expected, actual)
        if c.expected != actual {
            t.FailNow()
        }
    }
}
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Are the “alpha” characters guaranteed to be ASCII, or could they be any Unicode? The latter is more and more the case for real-world inputs. \$\endgroup\$
    – Davislor
    Commented Apr 28 at 4:22
  • \$\begingroup\$ @Davislor: str consists of only upper case and lower case English letters. \$\endgroup\$
    – peterSO
    Commented Apr 28 at 4:26
  • \$\begingroup\$ cur&^0x20 works fine in ascii, but you're explicitly using rune. That makes no sense. A rune is a UTF-8 character, byte is ASCII. Are you using multi-byte characters? If so, strings.ToLower exists, why make things harder? If performance is important, you may want to skip the ToLower call, but otherwise, I wouldn't worry about it too much, eliminate the variable of upper/lower case by normalising the input \$\endgroup\$ Commented Apr 29 at 14:06
  • 1
    \$\begingroup\$ @EliasVanOotegem: The original question says "str consists of only upper case and lower case English letters.". If you don't answer the question then you get an F and we won't hire you. \$\endgroup\$
    – peterSO
    Commented Apr 29 at 14:28
  • 1
    \$\begingroup\$ Missing test cases: always test with an empty string and a single-character string. Those are good edge cases to ensure the code is robust even for silly inputs (it does appear to be so; tests help keep it that way when you refactor). \$\endgroup\$ Commented Apr 30 at 14:26

1 Answer 1

4
\$\begingroup\$

A few comments.

Simple is good.

strchange.go:

package strchange

// s consists of only upper case and lower case English letters.
func CountChanges(s string) int {
    c := 0
    for i := 1; i < len(s); i++ {
        // to lowercase is not equal
        if s[i]&^0x20 != s[i-1]&^0x20 {
            c++
        }
    }
    return c
}

Conforming to standards is good.

Go Wiki: Go Code Review Comments: Useful Test Failures

Benchmarks are a good check on performance.

strchange_test.go:

package strchange

import "testing"

var changeTests = []struct {
    s    string
    want int
}{
    {"aaa", 0},
    {"aAa", 0},
    {"aaAAbBbb", 1},
    {"abba", 2},
    {"abBa", 2},
    {"abbba", 2},
    {"abBba", 2},
    {"aBbBcCcA", 3},
    {"aAaBbBcCcAaA", 3},
}

func TestChanges(t *testing.T) {
    for _, tt := range changeTests {
        got := CountChanges(tt.s)
        if got != tt.want {
            t.Errorf(
                "string: %q got: %d want: %d\n",
                tt.s, got, tt.want,
            )
        }
    }
}

func BenchmarkChanges(b *testing.B) {
    for range b.N {
        for _, tt := range changeTests {
            _ = CountChanges(tt.s)
        }
    }
}

$ go test strchange.go strchange_test.go -run=! -bench=. -benchmem
BenchmarkChanges-12    51221613   23.41 ns/op    0 B/op  0 allocs/op

Your code is less performant.

BenchmarkStrChange-12   3787999  323.8 ns/op   224 B/op  9 allocs/op
\$\endgroup\$
2
  • \$\begingroup\$ I removed the unnecessary allocations. Can you please elaborate on what you mean by "Conforming to standards is good."? Could you also rerun your benchmarks, as I believe you have modified your code, and I have certainly modified mine. I am running the benchmarks locally now, and writing a test generating function so that I can test with a string with orders of magnitude more changes. \$\endgroup\$
    – Romeo Lima
    Commented Apr 29 at 12:41
  • \$\begingroup\$ @RomeoLima: I'm no longer at the original computer. I have rerun the benchmarks on a different computer. \$\endgroup\$
    – peterSO
    Commented Apr 29 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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