## Facebook Interview Question for Software Engineers

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python solution :

``````import numpy as np
a = [-1,3,5,2,-2,-2,-4,4,-1,-199,10,-2131]
b = np.zeros(len(a)-1)
for i in xrange(len(a)-1):
b[i] = a[i]+a[i+1]
currmax = 0
totalmax = 0

for i in a:
currmax += i
if currmax < 0:
currmax = 0
flag = 0
else:
flag += 1
if currmax > totalmax and flag >=2:
totalmax = currmax

if totalmax==0:
print max(b)
else:
print totalmax``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

int maxSubArraySum (const vector<int> &v)
{
const int n = v.size ();
int i = 0;
int j = 0;
int sum = 0;
int maxSum = INT_MIN;

sum = v[0] + v [1];
maxSum = sum;

for (i = 2; i < n; i++)
{
sum += v[i];

maxSum = max (maxSum, sum);

while (j + 1 < i)
{
if (v[j] < 0)
{
sum -= v[j];
maxSum = max (maxSum, sum);

j++;
}
else
{
break;
}
}
}

while (j < n - 1)
{
sum -= v[j];

maxSum = max (maxSum, sum);

j++;
}

return (maxSum);
}

int main ()
{
int n;
vector<int> v;

cin >> n;

for (int i = 0; i < n; i++)
{
int x;

cin >> x;

v.push_back (x);
}

cout << maxSubArraySum (v) << endl;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

int maxSubArraySum (const vector<int> &v)
{
const int n = v.size ();
int i = 0;
int j = 0;
int sum = 0;
int maxSum = INT_MIN;

sum = v[0] + v [1];
maxSum = sum;

for (i = 2; i < n; i++)
{
sum += v[i];

maxSum = max (maxSum, sum);

while (j + 1 < i)
{
if (v[j] < 0)
{
sum -= v[j];
maxSum = max (maxSum, sum);

j++;
}
else
{
break;
}
}
}

while (j < n - 1)
{
sum -= v[j];

maxSum = max (maxSum, sum);

j++;
}

return (maxSum);
}

int main ()
{
int n;
vector<int> v;

cin >> n;

for (int i = 0; i < n; i++)
{
int x;

cin >> x;

v.push_back (x);
}

cout << maxSubArraySum (v) << endl;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python Terminal recursive solution:

``````ar = [-2, -1, -3, -4, -1]
ar2 = [-1,3,5,2,-2,-2,-4,4,-1,-199,10,-2131]

def fsbrecsum2(tab, rest, rmax, res):
a = tab[0] + tab[1]
if (res == None or a > rmax):
rmax = a
res = tab
try:
return (fsbrecsum2(rest[:2], rest[2:], rmax, res))
except:
return res

def fsbrecsum(tab):
try:
return fsbrecsum2(tab[:2] ,tab[2:], None, None)
except:
raise("not enough element in tab")

print(fsbrecsum(ar))
print(fsbrecsum(ar2))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python Terminal Recursive solution :

``````ar = [-2, -1, -3, -4, -1]
ar2 = [-1,3,5,2,-2,-2,-4,4,-1,-199,10,-2131]

def fsbrecsum2(tab, rest, rmax, res):
a = tab[0] + tab[1]
if (res == None or a > rmax):
rmax = a
res = tab
try:
return (fsbrecsum2(rest[:2], rest[2:], rmax, res))
except:
return res

def fsbrecsum(tab):
try:
return fsbrecsum2(tab[:2] ,tab[2:], None, None)
except:
raise("not enough element in tab")

print(fsbrecsum(ar))
print(fsbrecsum(ar2))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python Terminal Recursive Solution:

``````ar = [-2, -1, -3, -4, -1]
ar2 = [-1,3,5,2,-2,-2,-4,4,-1,-199,10,-2131]

def recSumProxy(tab, rest, rmax, res):
tmp = tab[0] + tab[1]
if (res == None or tmp > rmax):
rmax = tmp
res = tab
try:
return (recSumProxy(rest[:2], rest[2:], rmax, res))
except:
return res

def recSum(tab):
try:
return recSumProxy(tab[:2] ,tab[2:], None, None)
except:
raise("not enough element in tab")

print(recSum(ar))
print(recSum(ar2))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python solution to print the maxSum subarray.

``````def getMaxSum(array):
if not array or len(array) == 1:
return None

maxSum = seriesSum = None

for i in xrange(1, len(array)):
if seriesSum is not None:
seriesSum = max(seriesSum + array[i], array[i]+array[i-1])
maxSum = max(seriesSum, maxSum)
else:
seriesSum = maxSum = array[i] + array[i-1]
return maxSum``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class FindSubArray {

public static void main(String[] args) {

int[] a= {-2, -1, -3,4,-1};
int[] result= findLargestSubArray(a);

System.out.print("[");
for (int i = 0; i < result.length; i++) {
if (i== result.length-1)
System.out.print(result[i]);
else
System.out.print(result[i] + ",");
}
System.out.println("]");
}

static int[] findLargestSubArray(int [] a){
int[] result= new int [2];
int largest=0;
for (int i = 0; i < a.length-1; i++) {
int sum=a[i] + a[i+1];
if(sum>largest || largest==0){
result[0]=a[i];
result[1]=a[i+1];
largest=sum;
}
}
return result;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

int maxSubArraySum (const vector<int> &v)
{
const int n      = v.size ();
int i      = 0;
int sum    = 0;
int maxSum = INT_MIN;

sum    = v[0] + v [1];
maxSum = sum;

for (i = 2; i < n; i++)
{
int nextUseValue = max (sum, v[i - 1]);

sum    = nextUseValue + v[i];
maxSum = max (maxSum, sum);
}

return (maxSum);
}

int main ()
{
int         n;
vector<int> v;

cin >> n;

if (n < 2)
{
cerr << "Array size must be >= 2." << endl;
return (-1);
}

for (int i = 0; i < n; i++)
{
int x;

cin >> x;

v.push_back (x);
}

cout << maxSubArraySum (v) << endl;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

import numpy as np
import time as tm
import math as mh

num_list=[]
mx=0

for i in range(10):
num_list.append(np.random.randint(-100,0))

for rec in range(len(num_list)-1):
if mx < num_list[rec]+num_list[rec+1] or rec == 0:
mx = num_list[rec]+num_list[rec+1]
rem=rec

print('Maximum NUmber -',mx)
print('Numbers are (%d, %d)'%(num_list[rem],num_list[rem+1]))
print(num_list)

Comment hidden because of low score. Click to expand.
0
of 0 vote

import numpy as np
import time as tm
import math as mh

num_list=[]
mx=0

for i in range(10):
num_list.append(np.random.randint(-100,0))

for rec in range(len(num_list)-1):
if mx < num_list[rec]+num_list[rec+1] or rec == 0:
mx = num_list[rec]+num_list[rec+1]
rem=rec

print('Maximum NUmber -',mx)
print('Numbers are (%d, %d)'%(num_list[rem],num_list[rem+1]))
print(num_list)

Comment hidden because of low score. Click to expand.
0
of 0 vote

{
import numpy as np
import time as tm
import math as mh

num_list=[]
mx=0

for i in range(10):
num_list.append(np.random.randint(-100,0))

for rec in range(len(num_list)-1):
if mx < num_list[rec]+num_list[rec+1] or rec == 0:
mx = num_list[rec]+num_list[rec+1]
rem=rec

print('Maximum NUmber -',mx)
print('Numbers are (%d, %d)'%(num_list[rem],num_list[rem+1]))
print(num_list)
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#dynamic programming
def max_sub_array(nums):

end_element = len(nums) - 2
#base case - make sum of last thwo elements, and we need at least two element so additional_minus for this case we will store sum of last thwo elements
for i in range(end_element-1,-1,-1):

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#dynamic programming
def max_sub_array(nums):

end_element = len(nums) - 2
#base case - make sum of last thwo elements, and we need at least two element so additional_minus for this case we will store sum of last thwo elements
for i in range(end_element-1,-1,-1):

Comment hidden because of low score. Click to expand.
0
of 0 vote

In Elixir:

``````defmodule Lists do
def maxSubArraysSum([i, j | tail]),
do: do_maxSubArraysSum([j | tail], i + j)

def do_maxSubArraysSum([_], max), do: max
def do_maxSubArraysSum([i, j | tail], max) do
sum = i + j
do_maxSubArraysSum([j | tail], if(sum > max, do: sum, else: max))
end
end``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def findmax (aray):
if not aray or len(aray)==1:
return None
else:
y={(aray[i],aray[j]):aray[i]+aray[j] for i in range(len(aray)) for j in range(i,len(aray)-1) if i!=j}
z=[c for c in y if y[c]==max(y.values())]
return y,z``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````func findMaxSubArray(_ arr: [Int]) -> [Int] {
var maxVal = arr[0] + arr[1]
var maxArr = [arr[0], arr[1]]
var currArr = maxArr
var currSum = maxVal

for i in 2..<arr.count {
let val = arr[i]
let prev = arr[i - 1]
let valPlusPrev = val + prev
currSum += val

if valPlusPrev > currSum {
currSum = val + prev
currArr = [prev, val]
} else {
currArr.append(val)
}

if currSum > maxVal {
maxArr = currArr
maxVal = currSum
}
}

return maxArr
}

print(findMaxSubArray([-1,3,5,2,-2,-2,-4,4,-1,-199,10,-2131]))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int MaxSubarray(vector<int> const &a)
{
int max_sum = numeric_limits<int>::min();
if (a.size() >= 2) {
int sum = a[0];
for (int i = 1; i < a.size(); ++i) {
sum += a[i];
max_sum = max(max_sum, sum);
if (a[i] >= sum) {
sum = a[i];
}
}
}
return max_sum;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

keep an index to the start of the segment, when the segment size get above k, remove start element from sum and add new element, this way the segment will stay of size k and and new elements can be check for maximum sum.

``````int maxsum = -infinity;
int sum = 0;
int start = 0;
int end = 0;
for(int end=0; end<array.length; end++)
{
if(end - start > k)
{
sum = sum - array[start];
start++;
}

sum += array[end];

if(sum > maxsum)
{
maxsum = sum;
}

if(sum < 0)
{
sum  = 0;
start = end + 1;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void main(String[] args) {
int[] k = {-3, -1, -20, -5, 1, -8, 2, -3, 0};

int maxStartIndex = 0, maxEndIndex = 0, maxSum = Integer.MIN_VALUE;
int start = 0;
int sum = 0;

for (int end = 0; end < k.length; end++) {
sum += k[end];

if (end - start > 0) {
if (sum > maxSum) {
maxSum = sum;
maxStartIndex = start;
maxEndIndex = end;
}
}

if (sum < 0) {
sum = k[end];
start = end;
}
}

for (int i = maxStartIndex; i <= maxEndIndex; i++) {
System.out.print(k[i] + ", ");
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static int LargestSum(int[] n) throws Exception {
if (n == null || n.length < 2) throw new Exception("Array must have at least 2 elements");
int s = n[0] + n[1];
for (int i = 2; i < n.length; i++) {
int candidate1 = s + n[i];
int candidate2 = n[i-1] + n[i];
s = Math.max(s, Math.max(candidate1, candidate2));
}
return s;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/*
* Question: find largest aub-array (at least 2 elements) with maximum sum
*
* Analysis
* its obvious that as long as we see positive values, we prefer to add them to the sub-array, bcz the sum only increases.
* the hard question is what do we do when we have some negative values & then positive.
*  	should we add the negative in order to then add the ositives?
*  	obiously adding some of the negatives is never done bcz it only reduces the sum. so either we add the whole sub-array of negatives or not.
* so we can reduce the input array to a shorter array of interleaved positive/negative elements. each such element is the sum of all adjacent positive/negative, respectively.
* e.g.:
* Input: 1,2,3,-5,-6,4,-7,8,-9,-10,-1
* reduced array is: 1+2+3,-5-6,4,-7,8,-9-10-1 = 6,-11,4,-7,8,-20
*
* from here on we refer to the reduced array in which adjacent elements are always of opposite sign
*
* lemma
* --------
* for 2 positive elements separated by a negative elements:
*  	1) we prefer the set of all 3 if-and-only-if the negative is smaller than both positives.
*  			bcz otherwise, we'll simply pick the largest positive & it will be bigger than all 3
*  			obiously picking one positive & one negative is nonsense.
*  			e.g.: A > 0, B < 0, C > 0
*  			so if if A>-B && C>-B ===>>> A+B > 0 && C+B>0 ===>>> A+B+C > A && A+B+C > C
*  	2) if we picked all 3, then the decision to add the next adjacent pair (of negative & positive) will have the same answer, regardless of whether merged or not.
*  			bcz if we merged A,B,C and we have D<0,E>0 on the right then:
*  					we would add D+E to C id -D < E && -D < C
*  					but since A+B+C > C then A+B+C > C > -D.
*  					so the truth remains.
*
* lemma
* ------
* the order in which we merge triplet doesnt matter. so we can merge by iterating the reduced array
* if we have A,B,C,D,E from earlier than merging A,B,c or C,D,E first doesnt matter - its symmetric
*
* what do we do with 0
* we can add it or drop it, it doesnt matter - so just drop it while we reduce the array
*
* Algorithm
* -------------
* reduce array with a single scan (can be implemented lazily as we merge positive/negative sub-arrays)
* 		drop any negative at ends, in case positive exist
* scan reduced array & merge as long as possible. once we decide not to merge, a new sub-array begins.
* whenever we start a new sub-array, we save aside the maximum sub-array we found so far.
*
* followup: input is a stream
* ---------------------------
* in this case, we need to provide the sub-array whose sum is maximize, over the part we already read from the stream.
* so a lazy summation of adjacent negative/positive solves the issue & requires a single scan.
*/

#include <stdbool.h>
#include <limits.h>
#include <assert.h>

bool is_same_sign(int X, int Y)
{
if (((X > 0) && (Y > 0)) ||
((X < 0) && (Y < 0)))
return true;
return false;
}

int maxSubArray_v1(const int	*_nums,
const int	_N)
{
int		nums[_N];
int		N = 0;
int		max_elem = INT_MAX;	// element of maximum value
// max sub-array found so far
int		sum, max_sum = INT_MIN;

if (_N < 2)
return 0;
// reduce array to interchanging positive/negative
nums[0] = _nums[0];
for (int i=1; i < _N; i++) {
if (_nums[i] > max_elem)
max_elem = _nums[i];
if (_nums[i] == 0)
continue;	// skip it as it adds/changes nothing.
if (is_same_sign(nums[N], _nums[i])) {
// both have same sign - accumulate into reduced array element
nums[N] += _nums[i];
} else {
if (!((N == 0) && (nums[0] < 0))) {
// first element in reduced array is negative. since there is a second element (which must be positive), drop first element
N++;
}
nums[N] = _nums[i];
}
}
N++;
assert(N >= 1);
assert(nums[0] > 0);

// check for special cases
if (N == 1) {
// we have either all negative or all positive.
if (nums[0] > 0) {
// all positive - pick all array.
return nums[0];
} else {
// all negatives. picks single element which is largest
return max_elem;
}
}
// drop last element in case its negative
if (nums[N-1] < 0)
N--;
assert(N >= 1);
// from here on, grow sub-arrays of reduced array.
max_sum = nums[0];	assert(max_sum > 0);
sum = nums[0];
for (int i=2; i < N; i+=2) {
assert(nums[i] > 0);
assert(nums[i-1] < 0);
assert(nums[i-2] > 0);
if ((-nums[i-1] < nums[i  ]) &&
(-nums[i-1] < nums[i-2])) {
// merge all 3, check if we have a new top
sum += nums[i-1] + nums[i];
} else {
// start a new sub-array from nums[i]
sum = nums[i];
}
if (sum > max_sum)
max_sum = sum;
}
return max_sum;
}

/*
* implement for stream input, were we need to maintain sub-array of max sum that weve found up till any element,
* single pass element
*/
int maxSubArray_v2(const int	*nums,
const int	N)
{
int		max_elem = INT_MAX;	// element of maximum value
int		max_sum = INT_MIN;
int		curr;
int		sum;	// sum of currerntly merged elements
int		sum_0;	// sum of [i  ] in v1 impl
int		sum_1;	// sum of [i-1] in v1 impl
int		sum_2;	// sum of [i-2] in v1 impl

// consume elements that are zero/negative, drop all & save aside the max one.
for (curr = 0; (curr < N) && (nums[curr] <= 0); curr++) {
if (nums[curr] > max_elem)
max_elem = nums[curr];
}

if (curr == N) {
// consumed all of the stream.
// all elements are non positive - result is single element of max value
assert(max_elem <= 0);
return max_elem;
}

// sum positives
assert(nums[curr] >= 0);
for (sum=0; (curr < N) && (nums[curr] >= 0); curr++) {
sum += nums[curr];
}
assert(sum > 0);
max_sum = sum;
sum_2 = sum;

// 'curr' now points at first positive element
while (curr < N) {
// sum negatives
for (sum_1 = 0 ; (curr < N) && (nums[curr] <= 0); curr++) {
sum_1 += nums[curr];
}

// BEWARE: from here on, stream might be fully consumed !!!

// sum positives
for (sum_0 = 0; (curr < N) && (nums[curr] >= 0); curr++) {
sum_0 += nums[curr];
}
if (sum_0 > 0) {
// we consumed elements to create sum_1 & sum_0 (i.e.: stream didnt just got to its end in the middle, in which case, end has only negatives so no improvement over the sum_2 alone
assert(sum_1 < 0);
if ((-sum_1 < sum_2) &&
(-sum_1 < sum_0)) {
// merge all 3
sum += sum_1 + sum_0;
} else {
// start a new sub-array from nums[i]
sum = sum_0;
}
if (sum > max_sum)
max_sum = sum;
} else {
assert(curr == N);
}
}

return max_sum;
}

int main ()
{
const int in_0[] = {-3,-4,1,2,3,-5,-6,4,-7,8,-9,-10,-1};
const int in_1[] = {1,2,3,-5,-6,4,-7,8,-9,-10,-1};
int		max_sum_v0, max_sum_v1;

max_sum_v0 = maxSubArray_v1(in_0, 13);
assert(max_sum_v0 == 8);
max_sum_v1 = maxSubArray_v2(in_0, 13);
assert(max_sum_v1 == 8);

max_sum_v0 = maxSubArray_v1(in_1, 11);
assert(max_sum_v0 == 8);
max_sum_v1 = maxSubArray_v1(in_1, 11);
assert(max_sum_v1 == 8);

return 0;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````import java.io.*;
import java.util.*;

public class MaxSubArray
{

private static class SubArray
{
int startIndex;
int endIndex;
int sum;

SubArray(int s, int e, int max)
{
startIndex = s;
endIndex = e;
sum = max;
}

}
public static void main(String[] args)
{
int [] arr = {-1, -1, -4, -1, -2, -1, 5, -3};//{-2, -3, 4, -1, -2, 1, 5, -3};
SubArray subArray = maxSubArray(arr);
if(subArray == null)
{
System.out.print("Either sub-array contains one element or "
+ "max sum > 0 does not exist for the given array");
return;
}

System.out.print("Max SubArray is : { ");
for(int i = subArray.startIndex; i<=subArray.endIndex; i++)
System.out.print(arr[i]+ ", ");

System.out.print(" } -- Max Sum is : "+subArray.sum);

}

static SubArray maxSubArray(int[] a)
{
int startIndex = -1;
int endIndex = -1;
int length = a.length;
int maxTillNow = 0;
int maxOverAll = 0;//Integer.MIN_VALUE;

for(int i = 0; i<length; i++)
{
maxTillNow += a[i];
if(maxTillNow < 0)
maxTillNow = 0;
if(maxOverAll < maxTillNow)
{
if(startIndex == -1)
startIndex = i;
endIndex = i;
maxOverAll = maxTillNow;
}
}
if(startIndex == -1 || startIndex == endIndex)
return null;

return new SubArray(startIndex, endIndex, maxOverAll);
}

}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

package daily.practice.impl.misc;

public class HighestSum {
private static int solution(int arr[]){
int length = arr.length;
int highestSum = -100;
for(int i=0;i<length-1;i++){
int tempSum = arr[i] + arr[i+1];
if(tempSum>highestSum){
highestSum = tempSum;
}
}
System.out.println("[solution] Highest sum of two consecutive numer is: "+highestSum);
return highestSum;
}

public static void main(String args[]){
int arr[] = {-4,-1,-3,-2,-1};
System.out.println("[main] Highest sum is: " +solution(arr));
}
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.