Created
July 8, 2016 17:40
-
-
Save ninnemana/bffab2aad8e53a8661c8ed44529c581c to your computer and use it in GitHub Desktop.
Facebook Initial code challenge
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
// Problem: Given a sequence of nonnegative integers A and an integer T, return whether there is a *continuous sequence* of A that sums up to exactly T | |
// Example: | |
// [23, 5, 4, 7, 2, 11], 20. Return True because 7 + 2 + 11 = 20 | |
// [1, 3, 5, 23, 2], 8. Return True because 3 + 5 = 8 | |
// [1, 3, 5, 23, 2], 7 Return False because no sequence in this array adds up to 7 | |
// Note: We are looking for an O(N) solution. There is an obvious O(N^2) solution which is a good starting point but is not the final solution we are looking for. It’s important for the code to be as efficient as possible | |
package main | |
import ( | |
"fmt" | |
"unsafe" | |
) | |
func on2(data []int, sum, iter int) bool { | |
var current int | |
for i := 0; i < iter; i++ { | |
current = data[i]; | |
for j := i+1; j <= iter; j++ { | |
if current == sum { | |
return true | |
} | |
if current > sum || j == iter { | |
break | |
} | |
current = current + data[j] | |
} | |
} | |
return false | |
} | |
var ( | |
sequences = map[int][]int{ | |
20: []int{23, 5, 4, 7, 2, 11}, | |
8: []int{1, 3, 5, 23, 2}, | |
7: []int{1, 3, 5, 23, 2}, | |
} | |
) | |
func oNSeq(data []int, sum, iter int) bool { | |
current := data[0] | |
start := 0 | |
for i := 1; i <= iter; i++ { | |
for current > sum && start < (i-1) { | |
current = current - data[start] | |
start = start + 1 | |
} | |
fmt.Println(current, sum) | |
if current == sum { | |
return true | |
} | |
if i < iter { | |
current = current + data[i] | |
} | |
} | |
return false | |
} | |
func main() { | |
for sum, ints := range sequences { | |
subs := unsafe.Sizeof(ints)/unsafe.Sizeof(ints[0]) | |
if oNSeq(ints, sum, int(subs)) { | |
fmt.Printf( | |
"Sum %d was %s in %+v\n", | |
sum, | |
"found", | |
ints, | |
) | |
} else { | |
fmt.Printf( | |
"Sum %d was %s in %+v\n", | |
sum, | |
"not found", | |
ints, | |
) | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment