Facebook Interview Question for Software Engineer / Developers


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[0] = a[0];
s[1] = Max(a[0],a[1]);
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.

- DarkKnight October 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)
        return maxf(adj_max, arr[n]+inc_max);
    else
        return findMaxSeq (adj_max, a[n] + inc_max, n++);
}

- SimpleCoder October 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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]);

- yavasyavas78 November 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- LuanJunYi January 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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] }

- GS March 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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] }

- GS March 09, 2013 | Flag
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.

- Shyam October 14, 2012 | Flag Reply
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;
    }

- cvj October 14, 2012 | Flag Reply
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[0]+$a[1] > $a[2]){
      $cf=1;
    }
     $max = max($a[1]+$a[3], $a[2]);
  }
  return $max;
}

- ragnus October 15, 2012 | Flag Reply
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.

- ajit October 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ajit October 18, 2012 | Flag
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;
}

- penny October 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

def max_sub_sequence(subSeq, remaining):
	if len(remaining) == 0:
		return sum(subSeq)
	if len(remaining) == 1:
		return sum(subSeq) + remaining[0]
	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)

- Ravi November 01, 2012 | Flag
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

- Rohan November 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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();
			tempHolder.add(lsOfN);
			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);
		}
		tempHolder.add(lsofi);
		System.out.println("LsOf "+i+" = "+lsofi);
		pr.addAll(tempHolder);
	}
	
	public static void main(String[] args) {
		List<Integer> arrList = new ArrayList<Integer>();
		arrList.add(10);
		arrList.add(22);
		arrList.add(9);
		arrList.add(33);
		arrList.add(21);
		arrList.add(50);
		arrList.add(41);
		arrList.add(60);
		arrList.add(80);
		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());
	}

}

- Swati December 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous December 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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[1] include then a[1]
a[1] exclude then 0

a[2] include then a[2]
a[2] exclude then a[1]

a[3] include then a[3] + a[1]
a[3] exclude then max (a[1], a[2])

a[4] include then a[4] + max (a[1], [2])
a[4] exclude then max(max(a[1], a[2]), (a[3]+a[1]))

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))

- Swati December 01, 2012 | Flag
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[0];
$excl = 0;
$excl_new = 0;
$incla = array($arr[0]);
$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);
}
}

- Amit January 29, 2013 | Flag Reply
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=[0]*(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)

- light January 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

		var sum1 = array[0];
		var sum2 = array[1];

		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

- Ed February 13, 2013 | Flag Reply
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;
}

- FBNerd February 26, 2013 | Flag Reply
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;
	}

- BIN December 20, 2013 | Flag Reply
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;
}
int nonadjsum(int *arr,int size)
{
if(size==0)
return arr[0];
if(size==1)
return max(arr[1],arr[0]);
else
{
return max(nonadjsum(arr,size-2)+arr[size],nonadjsum(arr,size-1));

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

- Sam August 24, 2014 | Flag Reply
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;
}
int nonadjsum(int *arr,int size)
{
if(size==0)
 return arr[0];
if(size==1)
 return max(arr[1],arr[0]);
else
{
 return max(nonadjsum(arr,size-2)+arr[size],nonadjsum(arr,size-1));

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

- Anonymous August 24, 2014 | Flag Reply
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[0], 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);
}

- Raul Rivero March 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- pc May 02, 2015 | Flag Reply
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[0]+a[2]+...
s_odd=a[1]+a[3]+...

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

- iron_maiden87 September 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Safi December 05, 2014 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More