Facebook Interview Question Production Engineers
Country: United States
Interview Type: Phone Interview
space and time is O(n):
const testCases = [
[1,2,3,4,5,6,21],
[1,90, 50, 30, 5, 3, 2, 1 ],
[1, 50, 900, 1000 ],
];
const arraySums = arr => {
let sum1 = 0;
let sum2 = arr.reduce((sum, v) => sum + v, 0);
for (let i=0; i< arr.length; i++) {
sum2 -= arr[i];
sum1 += arr[i];
if (sum1 === sum2) {
return [
arr.slice(0, i + 1),
arr.slice(i),
];
}
}
return false;
}
testCases.map(arraySums)
function checkSplit(input) {
var startSum = 0;
var endSum = 0;
var index = 0;
var lastIndex = input.length - 1;
while (index <= lastIndex) {
if (startSum < endSum)
startSum += input[index++];
else
endSum += input[lastIndex--];
}
if (startSum == endSum) {
console.log(input.slice(0, index));
console.log(input.slice(lastIndex+1));
} else
console.log('Not possible');
}
Backtracking !
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static Boolean isSolution(List<Integer> solution, Integer sum) {
return (sum == 0);
}
public static List<Integer> construct_candidates(Integer []input, List<Integer> solution, Integer sum) {
List<Integer> candidates = new ArrayList<Integer>();
for (Integer i=0; i < input.length ; i++) {
if(!solution.contains(i) && sum >= i) {
candidates.add(i);
}
}
return candidates;
}
static void process_solution(Integer []input, List<Integer> solution) {
for (int i=0; i<input.length; i++) {
if (!solution.contains(i)) {
System.out.print(input[i] + " ");
}
}
System.out.println();
for (Integer i : solution) {
System.out.print(input[i] + " ");
}
}
static Boolean finished = false;
static void backtrack(Integer[] input, List<Integer> solution, Integer sum) {
if ( isSolution(solution, sum) ) {
finished = true;
process_solution(input,solution);
} else {
List<Integer> candidates = construct_candidates(input, solution, sum);
for (Integer candidate : candidates) {
if (!finished) {
sum -= input[candidate];
solution.add(candidate);
backtrack(input,solution,sum);
solution.remove(candidate);
sum += input[candidate];
}
}
}
}
public static void main (String[] args) throws java.lang.Exception
{
Integer[] input = { 5, 15, 10, 25, 35, 10, 15, 45};
Integer sum = 0;
for(Integer x : input) {
sum+=x;
}
if (sum%2 != 0) {
System.out.println("Not possible");
return;
} else
System.out.println("Sum is " + sum + " Trying for " + sum/2 );
List<Integer> solution = new ArrayList<Integer>();
backtrack(input,solution, sum/2);
}
}
public static int getPivot(int[] arr){
int l = 0, r = arr.length -1;
int piv = l+(r - l)/2;
int lSum = 0;
int rSum = 0;
for(int i= 0; i<piv;i++){
lSum += arr[i];
}
for(int j=piv; j<arr.length; j++){
rSum += arr[j];
}
while(piv > 0 && piv < r){
if(lSum == rSum){
return piv;
}
else if(lSum > rSum){
rSum+=arr[piv -1];
lSum-=arr[piv-1];
piv -= 1;
}
else{
rSum-=arr[piv+1];
lSum+=arr[piv+1];
piv += 1;
}
}
return -1;
}
The Above (rager) code seems to have an off by one error
Minor fix
const testCases = [
[1,2,3,4,5,6,21],
[1,90, 50, 30, 5, 3, 2, 1 ],
[1, 50, 900, 1000 ],
];
const arraySums = arr => {
let sum1 = 0;
let sum2 = arr.reduce((sum, v) => sum + v, 0);
for (let i=0; i< arr.length; i++) {
sum2 -= arr[i];
sum1 += arr[i];
if (sum1 === sum2) {
return [
arr.slice(0, i+1),
arr.slice(i+1),
];
}
}
return false;
}
console.log(testCases.map(arraySums))
public static boolean splitInEqualSum(final int[] arr) {
int totalSum = 0;
for (int value : arr) {
totalSum += value;
}
if (totalSum % 2 != 0) {
return false;
}
int halfSum = totalSum / 2;
for (int anArr : arr) {
totalSum -= anArr;
if (totalSum == halfSum) {
return true;
}
}
return false;
}
def checkSum(arr):
wR=0
wL=0
total = arr[0]
while(wR<len(arr)):
if total<sum(arr[wR+1:]):
wR +=1
total += arr[wR]
if total==sum(arr[wR+1:]):
print arr[:wR+1],arr[wR+1:]
break
if total>sum(arr[wR+1:]):
return False
return False
arr=[[1,2,3,3,2,1],[1,2,3,4,5,6,21],[1,90, 50, 30, 5, 3, 2, 1 ],[50, 50, 900, 1000 ]]
for test in arr:
print checkSum(test)
def checkSum(arr):
wR=0
total = arr[0]
while(wR<len(arr)):
if total<sum(arr[wR+1:]):
wR +=1
total += arr[wR]
if total==sum(arr[wR+1:]):
return arr[:wR+1],arr[wR+1:]
if total>sum(arr[wR+1:]):
return False
return False
arr=[[1,2,3,3,2,1],[1,2,3,4,5,6,21],[1,90, 50, 30, 5, 3, 2, 1 ],[1, 50, 900, 1000 ]]
for test in arr:
print checkSum(test)
'''
([1, 2, 3], [3, 2, 1])
([1, 2, 3, 4, 5, 6], [21])
([1, 90], [50, 30, 5, 3, 2, 1])
False
'''
Backtracking
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static Boolean isSolution(List<Integer> solution, Integer sum) {
return (sum == 0);
}
public static List<Integer> construct_candidates(Integer []input, List<Integer> solution, Integer sum) {
List<Integer> candidates = new ArrayList<Integer>();
for (Integer i=0; i < input.length ; i++) {
if(!solution.contains(i) && sum >= i) {
candidates.add(i);
}
}
return candidates;
}
static void process_solution(Integer []input, List<Integer> solution) {
for (int i=0; i<input.length; i++) {
if (!solution.contains(i)) {
System.out.print(input[i] + " ");
}
}
System.out.println();
for (Integer i : solution) {
System.out.print(input[i] + " ");
}
}
static Boolean finished = false;
static void backtrack(Integer[] input, List<Integer> solution, Integer sum) {
if ( isSolution(solution, sum) ) {
finished = true;
process_solution(input,solution);
} else {
List<Integer> candidates = construct_candidates(input, solution, sum);
for (Integer candidate : candidates) {
if (!finished) {
sum -= input[candidate];
solution.add(candidate);
backtrack(input,solution,sum);
solution.remove(candidate);
sum += input[candidate];
}
}
}
}
public static void main (String[] args) throws java.lang.Exception
{
Integer[] input = { 5, 15, 10, 25, 35, 10, 15, 45};
Integer sum = 0;
for(Integer x : input) {
sum+=x;
}
if (sum%2 != 0) {
System.out.println("Not possible");
return;
} else
System.out.println("Sum is " + sum + " Trying for " + sum/2 );
List<Integer> solution = new ArrayList<Integer>();
backtrack(input,solution, sum/2);
}
}
int[] ThreeByThreeArray2 = new int[9];
Random intRand = new Random();
for (int i = 0; i < 9; i++)
{
ThreeByThreeArray2[i] = intRand.Next(1, 9);
Console.WriteLine("position for[" + i + "] is:" + ThreeByThreeArray2[i]);
}
IfTwoArrayWouldHaveSameResults(ThreeByThreeArray2);
void IfTwoArrayWouldHaveSameResults(int[] inputArray)
{
int sumOfArray1 = 0;
int sumOfArray2 = 0;
bool results = false;
int j = inputArray.Length - 1;
for (int i = 0; i <= inputArray.Length/2; i++)
{
sumOfArray1 = sumOfArray1 + inputArray[i];
sumOfArray2 = sumOfArray2 + inputArray[j];
j--;
Console.WriteLine("sum of array 1: " + sumOfArray1);
Console.WriteLine("sum of array 2: " + sumOfArray2);
if (sumOfArray1.Equals(sumOfArray2))
{
results = true;
Console.WriteLine("results can be split with same results: " + results);
}
}
}
bool checkEqualSplit(vector<int>& dataArray)
{
vector<int> sumLeft(dataArray.size());
vector<int> sumRight(dataArray.size());
int count = 0;
size_t totalCount = dataArray.size();
for (size_t i = 0; i < totalCount; i++) {
count += dataArray[i];
if (i == 0) {
sumLeft[i] = dataArray[i];
sumRight[totalCount - 1] = dataArray[totalCount - 1];
} else {
sumLeft[i] = sumLeft[i - 1] + dataArray[i];
sumRight[totalCount - (i + 1)] = sumRight[totalCount - i] + dataArray[totalCount - (i + 1)];
}
}
if ((count % 2) == 0) {
for (size_t i = 0; i < totalCount -1 && sumLeft[i] < sumRight[i]; i++) {
if (sumLeft[i] == sumRight[i + 1]) {
printArray(dataArray, 0, totalCount - 1, sumRight[0]);
printArray(dataArray, 0, i, sumLeft[i]);
printArray(dataArray, i + 1, totalCount - 1, sumRight[i + 1]);
cout << endl << endl;
return true;
}
}
}
cout << "cannot equally split" << endl;
printArray(dataArray, 0, totalCount - 1, sumRight[0]);
cout << endl << endl;
return false;
}
#include<stdio.h>
int findsum(int *a,int n){
int i,j=0;
for(i=0 ;i<n;i++){
j=j+a[i];
}
return j;
}
int main (void){
int a[6]={2,4,2,5,3,1};
int sum=findsum(a,6);
int sumh=sum/2;
int i,j=0;
for(i=0;i<6;i++){
if(j==sumh) break;
else
j=j+a[i];
}
int c,b=0;
for(c=i;c<6;c++){
b=b+a[c];
}
if(b==sumh)
printf("satisfies");
else printf("doesnt");
}
#include<stdio.h>
int findsum(int *a,int n){
int i,j=0;
for(i=0 ;i<n;i++){
j=j+a[i];
}
return j;
}
int main (void){
int a[6]={2,4,2,5,3,1};
int sum=findsum(a,6);
int sumh=sum/2;
int i,j=0;
for(i=0;i<6;i++){
if(j==sumh) break;
else
j=j+a[i];
}
int c,b=0;
for(c=i;c<6;c++){
b=b+a[c];
}
if(b==sumh)
printf("satisfies");
else printf("doesnt");
}
#include<stdio.h>
int findsum(int *a,int n){
int i,j=0;
for(i=0 ;i<n;i++){
j=j+a[i];
}
return j;
}
int main (void){
int a[6]={2,4,2,5,3,1};
int sum=findsum(a,6);
int sumh=sum/2;
int i,j=0;
for(i=0;i<6;i++){
if(j==sumh) break;
else
j=j+a[i];
}
int c,b=0;
for(c=i;c<6;c++){
b=b+a[c];
}
if(b==sumh)
printf("satisfies");
else printf("doesnt");
}
Simple Python solution.
a) Get the sum of the input array. If its odd, there can never be two equal parts.
b) If its even, iterate the array and see if the expected sum can be attained or not.
def checkSum(arr):
if sum(arr)%2 != 0: return False
expected = sum(arr)/2
i = curr = 0
while curr < expected:
curr += arr[i]
i += 1
return (arr[:i], arr[i:]) if curr == expected else False
the question is about getting the minimum number of hours required not about how/who they are assigned to.
Get the TotalSum.
targetSum = TotalSum/2
iterate and sum from the beginning until the sum is equal to targetSum.
return array[0 to index] & array[index to len]
you could think about when the totalSum is odd/even and handle it accordingly.
def split_array(array_):
if len(array_) == 1:
return [], []
back_index = len(array_) - 1
x = 1
count_left = array_[:1][0]
count_right = array_[-1:][0]
while back_index - x != 0:
if count_left < count_right:
count_left += array_[x]
x += 1
else:
count_right += array_[back_index]
back_index -= 1
return array_[:x], array_[back_index:]
import random
A = [random.randint(0,100) for x in xrange(10)]
sum_map = dict()
num_comb = 2 ** len(A)
v = list()
x = range(num_comb)
#
# Perform sum of all combinations
#
for elem in x:
nsum = 0
for i in range(1,len(A)):
if (elem & (1<<i)) == (1<<i):
nsum += A[i]
sum_map[elem] = nsum
faelem = 0
fbelem = 0
for aelem in x:
for belem in x:
if aelem ^ belem == (2 ** len(A)) -1:
if sum_map[aelem] == sum_map[belem]:
faelem = aelem
fbelem = belem
break
#
# Find combinations with the same sum
# Print the two vector with the same sum
#
favec = []
fbvec = []
if faelem != 0 and fbelem != 0:
for i in range(1,len(A)):
if (faelem & (1<<i)) == (1<<i):
favec.append(A[i])
if (fbelem & (1<<i)) == (1<<i):
fbvec.append(A[i])
print favec
print fbvec
else:
print "impossible to split"
#
# Test
#
if faelem != 0 and fbelem != 0:
if sum(favec) == sum(fbvec):
print "Test passed"
else:
print "Test failed"
import itertools
array=[83, 77, 31, 41, 33, 23, 65, 15, 87]
array_one = []
print "Original array: %s" % array
for x in range(0, len(array)+1):
for subset in itertools.combinations(array, x):
if sum(subset) == sum(array)/2:
result = subset
for i in result:
array_one.append(i)
array.remove(i)
print "Array one: %s" % array_one
print "Array two: %s" % array
print "Sum of first array: %s" % sum(array_one)
print "Sum of second array: %s" % sum(array)
import itertools
array=[70, 84, 62, 82, 50, 36, 14, 12, 34]
array_one = []
print "Original array: %s" % array
for x in range(0, len(array)+1):
for subset in itertools.combinations(array, x):
if sum(subset) == sum(array)/2:
result = subset
for i in result:
array_one.append(i)
array.remove(i)
print "Array one: %s" % array_one
print "Array two: %s" % array
print "Sum of first array: %s" % sum(array_one)
print "Sum of second array: %s" % sum(array)
"""
Split Array Sum of two resulting should be same
Given an array of integers greater than zero, find if it is possible to split it in two
(without reordering the elements), such that the sum of the two resulting arrays is the same.
Print the resulting arrays.
"""
def split(array):
arrays = []
for i in range(len(array)):
for j in range(i+1,len(array)):
if sum(array[i:j])==sum(array[j:]):
arrays.append([array[i:j],array[j:]+array[0:i]])
return arrays
"""
Split Array Sum of two resulting should be same
Given an array of integers greater than zero, find if it is possible to split it in two
(without reordering the elements), such that the sum of the two resulting arrays is the same.
Print the resulting arrays.
"""
def split(array):
arrays = []
for i in range(len(array)):
for j in range(i+1,len(array)):
if sum(array[i:j])==sum(array[j:]):
arrays.append([array[i:j],array[j:]+array[0:i]])
return arrays
#!/usr/bin/env ruby
def equal_sum_partition ary
idx_left = -1
idx_right = ary.size
sum_left = 0
sum_right = 0
while true
if sum_left < sum_right
idx_left += 1
sum_left += ary[idx_left]
else
idx_right -= 1
sum_right += ary[idx_right]
end
if idx_left == idx_right - 1
if sum_left == sum_right
return idx_right
else
return
end
end
end
end
ary = Array.new(100) {rand 20}
if part_idx = equal_sum_partition(ary)
puts part_idx
puts "left #{ary[0...part_idx].inject(:+)} #{ary[0...part_idx]}"
puts "right #{ary[part_idx..-1].inject(:+)} #{ary[part_idx..-1]}"
end
#!/usr/bin/env ruby
def equal_sum_partition ary
idx_left = -1
idx_right = ary.size
sum_left = 0
sum_right = 0
while true
if sum_left < sum_right
idx_left += 1
sum_left += ary[idx_left]
else
idx_right -= 1
sum_right += ary[idx_right]
end
if idx_left == idx_right - 1
if sum_left == sum_right
return idx_right
else
return
end
end
end
end
ary = Array.new(100) {rand 20}
if part_idx = equal_sum_partition(ary)
puts part_idx
puts "left #{ary[0...part_idx].inject(:+)} #{ary[0...part_idx]}"
puts "right #{ary[part_idx..-1].inject(:+)} #{ary[part_idx..-1]}"
end
#!/usr/bin/env ruby
def equal_sum_partition ary
idx_left = -1
idx_right = ary.size
sum_left = 0
sum_right = 0
while true
if sum_left < sum_right
idx_left += 1
sum_left += ary[idx_left]
else
idx_right -= 1
sum_right += ary[idx_right]
end
if idx_left == idx_right - 1
if sum_left == sum_right
return idx_right
else
return
end
end
end
end
ary = Array.new(100) {rand 20}
if part_idx = equal_sum_partition(ary)
puts part_idx
puts "left #{ary[0...part_idx].inject(:+)} #{ary[0...part_idx]}"
puts "right #{ary[part_idx..-1].inject(:+)} #{ary[part_idx..-1]}"
end
public static void main(String[] args) {
int arr[]={1,90, 50, 30, 5, 3, 2, 1};
int n =arr.length;
int Lsum=arr[0];
int Rsum=arr[n-1];
int i=0;
int j=n-1;
while( i != j-1 ){
if (Lsum == Rsum && i != j-1){
i++;
Lsum += arr[i];
j--;
Rsum +=arr[j];
}
if (Lsum < Rsum){
i++;
Lsum += arr[i];
}else{
j--;
Rsum += arr[j];
}
}
if (Lsum == Rsum){
System.out.println("i= "+i+" Left Sum = "+Lsum+" j= "+j+" right Sum = "+Rsum);
}else{ System.out.println("not possible to split it in two ");
}
}
public class SeparateToTwoArrays {
public void makeTwoList(int[] nums) {
if (nums == null || nums.length <= 1) {
System.out.println("not possible");
return;
}
int origSum = getSum(nums, 0, nums.length - 1);
if (origSum % 2 != 0) {
System.out.println("not possible");
return;
}
int target = origSum / 2;
int firstSum = nums[0];
for (int i = 1; i < nums.length - 1; i++) {
firstSum += nums[i];
if (firstSum == target) {
System.out.println(arrToStr(nums, 0, i));
System.out.println(arrToStr(nums, i + 1, nums.length - 1));
return;
}
if (firstSum > target) {
System.out.println("not possible");
return;
}
}
System.out.println("not possible");
}
private String arrToStr(int[] nums, int first, int last) {
String str = "[ ";
for (int i = first; i <= last; i++)
str += nums[i] + ", ";
if (str.endsWith(", ")) str = str.substring(0, str.length() - 2);
return str + " ]";
}
private int getSum(int[] list, int first, int last) {
int sum = 0;
for (int i = first; i <= last; i++)
sum += list[i];
return sum;
}
public static void main(String[] args) {
SeparateToTwoArrays st = new SeparateToTwoArrays();
int[] test1 = {1,2,3,4,5,6,21};
int[] test2 = {1,90, 50, 30, 5, 3, 2, 1};
int[] test3 = {2, 50, 900, 1000};
System.out.println("test1");
st.makeTwoList(test1);
System.out.println("test2");
st.makeTwoList(test2);
System.out.println("test3");
st.makeTwoList(test3);
}
}
public class SeparateToTwoArrays {
public void makeTwoList(int[] nums) {
if (nums == null || nums.length <= 1) {
System.out.println("not possible");
return;
}
int origSum = getSum(nums, 0, nums.length - 1);
if (origSum % 2 != 0) {
System.out.println("not possible");
return;
}
int target = origSum / 2;
int firstSum = nums[0];
for (int i = 1; i < nums.length - 1; i++) {
firstSum += nums[i];
if (firstSum == target) {
System.out.println(arrToStr(nums, 0, i));
System.out.println(arrToStr(nums, i + 1, nums.length - 1));
return;
}
if (firstSum > target) {
System.out.println("not possible");
return;
}
}
System.out.println("not possible");
}
private String arrToStr(int[] nums, int first, int last) {
String str = "[ ";
for (int i = first; i <= last; i++)
str += nums[i] + ", ";
if (str.endsWith(", ")) str = str.substring(0, str.length() - 2);
return str + " ]";
}
private int getSum(int[] list, int first, int last) {
int sum = 0;
for (int i = first; i <= last; i++)
sum += list[i];
return sum;
}
public static void main(String[] args) {
SeparateToTwoArrays st = new SeparateToTwoArrays();
int[] test1 = {1,2,3,4,5,6,21};
int[] test2 = {1,90, 50, 30, 5, 3, 2, 1};
int[] test3 = {2, 50, 900, 1000};
System.out.println("test1");
st.makeTwoList(test1);
System.out.println("test2");
st.makeTwoList(test2);
System.out.println("test3");
st.makeTwoList(test3);
}
}
#include <stdio.h>
int main()
{
int arr[] = {9,6,10,20,5,7,7,1,3,10,7,5};
size_t n = sizeof(arr)/sizeof(arr[0]);
int i=0;
int j=n-1;
int lowSum = arr[i];
int highSum = arr[j];
while ( 1 )
{
printf("i=%d, j=%d, lowSum=%d, highSum=%d\n", i,j,lowSum, highSum);
if (lowSum > highSum)
{
j--;
highSum += arr[j];
} else {
i++;
lowSum += arr[i];
}
if ( (j==i+1))
break;
}
printf("i=%d, j=%d, lowSum=%d, highSum=%d\n", i,j,lowSum, highSum);
if (lowSum == highSum)
{
printf("Array can be split at arr[%d]-arr[%d] %\n",i,j);
}
return 0;
}
I am in no way a coder and this code probably can be simplified and/or optimised and maybe I misunderstood the requirement but I gave it a go in python.
a = [1,1,1,8,8,9]
b = []
while len(a) > 0:
b.append(a[0])
a.pop(0)
if sum(a) == sum (b):
flag = True
break
else:
flag = False
if flag == True:
print "Winner winner, chicken dinner", a, b
else:
print 'This array can''t be split in 2 equal sum arrays'
Not sure if I interpreted the requirements correctly and in no way am I a coder and this code can be simplified/optimized but I gave it a go in python.
a = [1,1,1,8,8,9]
b = []
while len(a) > 0:
b.append(a[0])
a.pop(0)
if sum(a) == sum (b):
flag = True
break
else:
flag = False
if flag == True:
print "Winner winner, chicken dinner", a, b
else:
print 'This array can''t be split in 2 equal sum arrays'
O(N) runtime and memory (map, which save an iteration on expense of memory)
def split_sum(numbers):
if not numbers:
return [], []
s = 0
sum_to_index = {}
for i,n in enumerate(numbers):
s = s + n
sum_to_index[s] = i
if s % 2 == 0 and (s / 2) in sum_to_index:
i = sum_to_index[s / 2]
return numbers[:i+1], numbers[i+1:]
else:
return [], []
A Python 2 solution
O(N) runtime
O(N) memory Uses map for saving additional lookup loop, can be O(1) memory with additional loop
def split_sum(numbers):
if not numbers:
print [], []
s = 0
sum_to_index = {}
for i,n in enumerate(numbers):
s = s + n
sum_to_index[s] = i
if s % 2 == 0 and (s / 2) in sum_to_index:
i = sum_to_index[s / 2]
print numbers[:i+1], numbers[i+1:]
else:
print [], []
public static int splitArray(int[] inp) {
int begin = 0;
int end = inp.length - 1;
int sumOne = inp[begin];
int sumTwo = inp[end];
while (begin < end) {
if (sumOne > sumTwo) {
sumTwo += inp[--end];
} else if (sumOne < sumTwo) {
sumOne += inp[++begin];
} else {
if (end - begin == 1) {
return begin;
} else {
sumOne += inp[++begin];
sumTwo += inp[--end];
}
}
}
return -1;
}
public static void main(String[] args) {
int[] inp = { 1, 2, 3, 4, 5, 3, 2, 6, 4 };
int breakPoint = splitArray(inp);
if (breakPoint != -1) {
for (int i = 0; i <= breakPoint; i++) {
System.out.print(inp[i] + " ");
}
System.out.println();
for (int i = breakPoint + 1; i < inp.length; i++) {
System.out.print(inp[i] + " ");
}
System.out.println();
} else {
System.out.println("No");
}
}
public class Solution {
private int getIndexDividingEqualSum(int[] array) {
if(array == null || array.length <= 0) {
return -1;
}
int index = 0, lastIndex = array.length - 1, indexSum = Integer.MAX_VALUE, lastIndexSum = Integer.MAX_VALUE;
while(index < lastIndex) {
indexSum = (indexSum == Integer.MAX_VALUE ? 0 : indexSum) + array[index];
lastIndexSum = (lastIndexSum == Integer.MAX_VALUE ? 0 : lastIndexSum) + array[lastIndex];
if(indexSum <= lastIndexSum) {
index++;
}
else {
lastIndex--;
}
}
return indexSum == lastIndexSum ? index - 1 : -1;
}
}
space: O(n) (only bc of the slice)
time: O(n)
- yaboyyyy March 21, 2017const testCases = [ [1,2,3,4,5,6,21], [1,90, 50, 30, 5, 3, 2, 1 ], [1, 50, 900, 1000 ], ]; const arraySums = arr => { let sum1 = 0; let sum2 = arr.reduce((sum, v) => sum + v, 0); for (let i=0; i< arr.length; i++) { sum2 -= arr[i]; sum1 += arr[i]; if (sum1 === sum2) { return [ arr.slice(0, i + 1), arr.slice(i), ]; } } return false; } testCases.map(arraySums)