## Facebook Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: In-Person

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

This is a dynamic programming problem.
Let original array = a[0 to n-1]
Let solution array = s[0 to n-1] where
s[I] = max sum of non-adjacent numbers from a[0 to I];
So,
s = a;
s = Max(a,a);
Now recursively,
s[I] = Max(s[I-1],a[I]+s[I-2]); you either take the ith element or you dont

s[n-1] will be final solution.

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

``````int arr[] = {1, 3, 1, 4, 1, 3, 20}
int size = sizeof (arr)/sizeof (int);

int maxf (int a1, int a2)
{
return (a1 > a2) ? a1 : a2;
}

int findMaxSeq (int adj_max, int inc_max, int n)
{
if (n == size -1)
else
return findMaxSeq (adj_max, a[n] + inc_max, n++);
}``````

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

it doesn't work with following input:
1, 6, 2, 2, 3.
To fix the solution
change "s[I] = Max(s[I-1],a[I]+s[I-2]);"
to "s[I] = Max(s[I-1],a[I]+s[I-2], a[l] + s[l-3]);

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

Correct solution. Besides, I think the same algorithm can be extended easily for input with negative elements in it.

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

@yavasyavas78 : Ideally you solution is close but needs to be more generalized.

s[l] = Max { Max s(l-k) for all k in the range 2 to j + a[l] } , a[l] }

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

in the above it is 2 to l.
i.e.
s[l] = Max { Max s(l-k) for all k in the range 2 to l + a[l] } , a[l] }

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

I think this can be implemented with Kadane's algorithm with a small change in it.

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

Try this-Basically it goes by the logic that if you do not want adjacent values, then the third or fourth value becomes a potential candidate to add.

``````private static int func(int a[]) {
int current = 0, sum = 0;
int first = 0, second = 1, third = 2, fourth = 3;
int size = a.length;
if (fourth <= size - 1)
{
for (; fourth <= a.length - 1; first = current + 2, second = current + 3, third = current + 4, fourth = current + 5)
{
int firstSum = a[first] + a[third];
int secondSum = a[first] + a[fourth];
int thirdSum = a[second] + a[fourth];
current = firstSum > secondSum ? (firstSum > thirdSum ? first : second) : (secondSum > thirdSum ? first : second);
sum += a[current];
}
}
if (third <= size - 1)
{
int currentSum = ((a[first] + a[third]) > a[second]) ? (a[first] + a[third]): a[second];
sum += currentSum;
}
else if (second <= size - 1)
{
sum += (a[first] > a[second]) ? a[first]: a[second];
}
else if (first <= size - 1)
{
sum += a[first];
}
return sum;
}``````

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

``````function findMax(\$a){
\$l=count(\$a);
\$max=0;
\$cf=-1;
for(\$i=1; \$i<\$l-1; \$i++){
if(\$i-1==\$cf) continue;
if(\$a[\$i-1]+\$a[\$i+1] > \$a[i])
\$cf=\$i-1;
else
\$cf=\$cf[\$i];
\$max+=\$cf;
}
if(\$i==1){
if(\$a+\$a > \$a){
\$cf=1;
}
\$max = max(\$a+\$a, \$a);
}
return \$max;
}``````

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

assume A is original array and B is to point the indices of A starts from 0 to A.length then
FIND_MAXSUM_SUBARRAY(A,B)
{
for i=1 to A.length-1
for j=1 to B.length-1
if(a[j]>a[j+1])
swap(A[j],a[j+1])
swap(B[j],B[j+1])
for j=B.length to 1
if B[j]!=-1
C[i]=A[j]
i=i+1
for k=1 to j-1
if B[k]=B[j+1]+1
B[k]=-1
for k=1 to j-1
if B[k]=B[j]-1
B[k]=-1
B[j]=-1
}

This algorithm first sorts array A and changed positions of A will be stored in array B. starts from last value of A, as it is maximum put it under array C. Then make sure you won't consider a position immediate less or immediate above than that. You can do that by making indices values to -1. This algorithm takes Theta(n^2) at worst case. I traced it good and it works with different outputs. please let me know in case any improvements can be done.

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

I am sorry that I couldn't follow indentation since i am new to this site.

FIND_MAXSUM_SUBARRAY(A,B)

``````for i=1 to A.length-1
for j=1 to B.length-1
if(a[j]>a[j+1])
swap(A[j],a[j+1])
swap(B[j],B[j+1])
for j=B.length to 1
if B[j]!=-1
C[i]=A[j]
i=i+1
for k=1 to j-1
if B[k]=B[j+1]+1
B[k]=-1
for k=1 to j-1
if B[k]=B[j]-1
B[k]=-1
B[j]=-1``````

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

O(n) solution, non-recursion... the idea is similar as the first post above: the (i+1)th element is not included in the result if the sum till (i+1)th elem is less than the sum till ith element:

``````int maxSum(int* arr,int len)
{
int sum1=0;
int sum2=0;
for(int i=0;i<len-1;++i) {
int temp=sum2;
sum1+=arr[i];
sum2+=arr[i+1];
if(i!=len-2) {
sum2=sum1;
if(sum1>sum2) {
++i;
} else {
sum1=temp;
}
}
}
return (sum2>sum1)?sum2:sum1;
}``````

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

``````def max_sub_sequence(subSeq, remaining):
if len(remaining) == 0:
return sum(subSeq)
if len(remaining) == 1:
return sum(subSeq) + remaining
maxSum = 0
for i in range(0,len(remaining)-1):
value = max(max_sub_sequence(subSeq + [remaining[i]], remaining[i+2:]), max_sub_sequence(subSeq, remaining[i+1:]))
if value > maxSum:
maxSum = value
return maxSum

if __name__ == "__main__":
ls=[7,1,2,8,5]
print max_sub_sequence([],ls)``````

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

O(n): Use Dynamic Programming, Take two additional array Including[n], excluding[n]..
Including gives the max sum including current position, and excluding keeps track of max sum excluding current position.
For any position i, its including value = excluding[i-1] + Number at position i
and its excluding value = including[i-1]

Thats it, in the end, check the last value of excluding and last of including array, whichever is maximum, just return it..

Ex. -> Given Array 1 - 2 - 3 - 4 - 5 - 6
Including 1 2 4 6 9 12
Excluding 0 1 2 4 6 9

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

``````import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

class LSOfN {

private int arrIndex;
private int length;

LSOfN(int arrIndex, int length) {
this.arrIndex = arrIndex;
this.length = length;
}

public int getArrIndex() {
return arrIndex;
}
public int getLength() {
return length;
}

public String toString() {
return "LS("+arrIndex+") = "+length;
}
}

public class LongestIncrSubSeq {

/**
* @param args
*/
int size;
List<Integer> arrList;
PriorityQueue<LSOfN> pr;

LongestIncrSubSeq(List<Integer> arrList, int size) {
this.arrList = arrList;
this.size = size;
this.pr = new PriorityQueue<LSOfN>(size, maxSubSeqLengthComparator);
}

private Comparator<LSOfN> maxSubSeqLengthComparator = new Comparator<LSOfN>() {

@Override
public int compare(LSOfN o1, LSOfN o2) {
int maxLengthLeft = o1.getLength();
int maxLengthRight = o2.getLength();

if(maxLengthLeft > maxLengthRight) {
return -1;
} else if (maxLengthLeft < maxLengthRight) {
return 1;
}
return 0;
}
};

public void findLsOfi(int i) {
List<LSOfN> tempHolder = new ArrayList<LSOfN>();
LSOfN lsofi = null;
while(!pr.isEmpty()) {
LSOfN lsOfN = pr.poll();
if(lsOfN.getArrIndex() < i && arrList.get(i) > arrList.get(lsOfN.getArrIndex())) {
lsofi = new LSOfN(i, lsOfN.getLength() + 1);
break;
}
}
if(lsofi == null) {
lsofi = new LSOfN(i, 1);
}
System.out.println("LsOf "+i+" = "+lsofi);
}

public static void main(String[] args) {
List<Integer> arrList = new ArrayList<Integer>();
LongestIncrSubSeq ls = new LongestIncrSubSeq(arrList, arrList.size());
for(int index = 0; index < arrList.size(); index++) {
ls.findLsOfi(index);
}
System.out.println("Length of the longest subsequence is "+ls.pr.peek().getLength());
}

}``````

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

Sorry, posted to the wrong question - the above program finds the length of the max subsequence.

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

``````The solution lies in the following observation:

There can be 2 lists for including a[i] and for excluding a[i] for any given i.
This is because, the max sum can later increase or decrease by including a[i] or excluding a[i].

a include then a
a exclude then 0

a include then a
a exclude then a

a include then a + a
a exclude then max (a, a)

a include then a + max (a, )
a exclude then max(max(a, a), (a+a))

thus, we see that include_list for (a[i]) is a[i] + exclude_list[a[i-1]]
and exclude_list for a[i] is max(include_list(a[i-1]), exclude_list(a[i-1]))

Once the 2 lists are formed, the answer is given by max(include_list(a[n-1]), exclude_list(a[n-1))``````

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

<?php
\$array = array(2,1,4,3,5,9);
\$size = count(\$array);

function maxs(\$arr, \$size)
{
\$incl = \$arr;
\$excl = 0;
\$excl_new = 0;
\$incla = array(\$arr);
\$excla = array();
\$excl_newa = array();
for (\$i = 0; \$i<\$size;\$i++)
{
unset(\$excl_newa);
if (\$incl > \$excl)
{
\$excl_new = \$incl;
\$excl_newa = \$incla;
}
else
{
\$excl_new = \$excl;
\$excl_newa = \$excla;
}

\$incl = \$excl + \$arr[\$i];
\$excl = \$excl_new;
\$incla = \$excla;
\$incla[] = \$arr[\$i];
\$excla = \$excl_newa;
}
if (\$incl > \$excl)
{
echo ("total - " . \$incl);
print_r(\$incla);
}
else
{
echo ("total - " . \$excl);
print_r(\$iexcla);
}
}

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

we maintain an auxiliary array that holds the result upto a given value. rest is straight forward, very simple code

``````#!/usr/bin/python

def noncons(lst):
n=len(lst)
res=*(n+2)
for i in range(n):
l,r=res[i]+lst[i],res[i+1]
res[i+2]=max(l,r)
return res[n+1]

if __name__=='__main__':
lst=[1,2,3,4,5,6]
print noncons(lst)``````

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

``````function(array) {
if (array.length < 2) {
return -1;
}

var sum1 = array;
var sum2 = array;

var length = array.length;

for (var i = 0, j = 1; i < length && j < length; i += 2, j += 2) {
if (i + 2 < length) {
sum1 += array[i + 2];
}

if (j + 2 < length) {
sum2 += array[j + 2];
}
}

return Math.max(sum1, sum2);
}``````

For the above examples, it seems it returns the correct answers:
1, 6, 2, 2, 3 // 6, 2 -> 8

1, 2, 3, 4, 5, 6 // 2, 4, 6 -> 12

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

A loop is more efficient here than memorization but it doesn't impact the complexity, so heck.

``````#include <vector>
#include <iostream>
#include <unordered_map>

int findSubSeq_internal(
int offset,
const std::vector<int>& nums,
std::unordered_map<int, int>& space)
{
if(offset >= nums.size())
return 0;

auto it = space.find(offset);
if(it != space.end())
return it->second;

int a = findSubSeq_internal(offset + 3, nums, space);
int b = nums[offset] + std::max(a, findSubSeq_internal(offset + 2, nums, space));

space.insert(std::make_pair(offset, b));
return b;
}

int findSubSeq(std::vector<int> nums)
{
if(nums.empty())
return 0;

std::unordered_map<int, int> space;
int a = findSubSeq_internal(0, nums, space);
int b = findSubSeq_internal(1, nums, space);

return std::max(a, b);
}

int main(int argc, char** argv)
{
std::vector<int> nums = {2,6,3,4,5,17,9,12,3,89,3,6,7,3,4};
int sum = findSubSeq(nums);

return 0;
}``````

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

This is dp:

f(n) = max(f(n-2) + c(n), f(n-1)

``````int findMaxSeq (int* A, int n)
{
int m1 = 0;
int m0 = 0;
for(int i=0; i<n; i++)
{
int m = m1+A[i];
if (m < m0)
{
m = m0;
}
m1 = m0;
m0 = m;
}
return m0;
}``````

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

#include<iostream>
using namespace std;
int max(int x,int y)
{
if(x>y)
return x;
else
return y;
}
{
if(size==0)
return arr;
if(size==1)
return max(arr,arr);
else
{

}
}
int main()
{
int *arr,size,i,sum;
cin>>size;
arr = new int[size];
for(i = 0 ; i < size ; i++ )
{
cin>>arr[i];
}
cout<<sum;
}

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

``````#include<iostream>
using namespace std;
int max(int x,int y)
{
if(x>y)
return x;
else
return y;
}
{
if(size==0)
return arr;
if(size==1)
return max(arr,arr);
else
{

}
}
int main()
{
int *arr,size,i,sum;
cin>>size;
arr = new int[size];
for(i = 0 ; i < size ; i++ )
{
cin>>arr[i];
}
cout<<sum;
}``````

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

There's no need of DP approach, we can solve this in O(n) time and O(1) complexity!

``````public int MaxRobbingVal(int[] values)
{
int n = values.Length;
if (n == 0)
return 0;
int sum1 = values, sum2 = 0, sum_aux = 0;
for (int i = 1; i < n; i++)
{
sum_aux = Math.Max(sum1, sum2);
sum1 = sum2 + values[i];
sum2 = sum_aux;
}
return Math.Max(sum1, sum2);
}``````

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

here you go http : //ideone.com/U6YVpR

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

No need for any DP approach.

Since the array is all POSITIVE integers, the only two possible maximum sum subsequences with no adjacent elements are:
s_even=a+a+...
s_odd=a+a+...

You just need to do one linear pass to compute the two values s_even and s_odd, and one pass to output the elements corresponding to the larger of the two values, e.g:
1 2 3 4 5 6
s_even=1+3+5=9
s_odd=2+4+6=12
Output: 2, 4, 6

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

Not really. E.g. {6,2,3,6} s_even = 9, s_odd = 8 but s_actual = 12.

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.