Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
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++);
}
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]);
Correct solution. Besides, I think the same algorithm can be extended easily for input with negative elements in it.
@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] }
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;
}
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.
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
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;
}
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)
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
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());
}
}
Sorry, posted to the wrong question - the above program finds the length of the max subsequence.
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))
<?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);
}
}
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)
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
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;
}
#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;
}
#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;
}
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);
}
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
This is a dynamic programming problem.
- DarkKnight October 14, 2012Let 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.