Created
July 6, 2018 22:04
-
-
Save fredlahde/d3ff0e0676dd381d6d446023087129f1 to your computer and use it in GitHub Desktop.
Google Interview Questions - Aarray Multiplicator
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import "fmt" | |
/** | |
* There is an array A[N] of N numbers. | |
* You have to compose an array Output[N] such that Output[i] | |
* will be equal to multiplication of all the elements of A[N] except A[i]. | |
* For example Output[0] will be multiplication of A[1] to A[N-1] | |
* and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. | |
* Solve it without division operator and in O(n). | |
*/ | |
func Multiply(arr []int) []int { | |
output := make([]int, 0) | |
if len(arr) == 0 { | |
return output | |
} | |
output = append(output, 0) | |
for i := range arr { | |
if i == 0 { | |
continue | |
} | |
if i == 1 { | |
output = append(output, arr[0]) | |
continue | |
} | |
previousIndex := i - 1 | |
sum := arr[previousIndex] * output[previousIndex] | |
output = append(output, sum) | |
} | |
return output | |
} | |
func main() { | |
primes := []int{1, 2, 3, 4, 5, 6} | |
fmt.Printf("%v\n", primes) | |
fmt.Printf("%v\n", Multiply(primes)) | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import ( | |
"testing" | |
) | |
func TestMe(t *testing.T) { | |
input := []int{1, 2, 3, 4, 5, 6} | |
expected := []int{0, 1, 2, 6, 24, 120} | |
got := Multiply(input) | |
for i, n := range got { | |
if expected[i] != n { | |
t.Errorf("Wrong!\nwant: %v\ngot: %v\n", expected, got) | |
t.Fail() | |
} | |
} | |
} | |
func TestOneItem(t *testing.T) { | |
input := []int{1} | |
expected := []int{0} | |
got := Multiply(input) | |
for i, n := range got { | |
if expected[i] != n { | |
t.Errorf("Wrong!\nwant: %v\ngot: %v\n", expected, got) | |
t.Fail() | |
} | |
} | |
} | |
func TestEmpty(t *testing.T) { | |
input := []int{} | |
expected := []int{} | |
got := Multiply(input) | |
for i, n := range got { | |
if expected[i] != n { | |
t.Errorf("Wrong!\nwant: %v\ngot: %v\n", expected, got) | |
t.Fail() | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment