## Facebook Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 4 vote

LIS in the question should be 1 3 4 6

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

i think the question is talking about sequence not subsequence. Longest sequence can be calculated in O(n) time easily.

3 4 6 is the correct ouput.

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

Both 3,4,6 and 1,3,4,6 are sequences and subsequences of 1,5,3,4,6,4. :)

The question is about contiguous subsequences.

Otherwise we would have an online longest increasing subsequence problem. In this case imo there is no difference between the offline and an online algorithm

Not the length but the actual sequence is asked. So in the worst case we need to store the whole input. Plus we don't need to answer the question while the numbers come in; only at the end (and because we are reading from a file we know where the end is). Thus, again, there's no point having an online algorithm. We can simply store all numbers in a list and do the offline LIS algorithm after the last number.

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

``````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
of 0 vote

Online algorithm will probably have to remember ALL sequences so far... There should be no way to do better. Then you can keep them sorted by their last element and will have to manage O(n) sequences simultaneously in the worst-case. There is stuff you can do about optimizing memory though, but in principle this should be it.

So a more precise idea. Keep chunks of continous increases in a "Node" and has forward links (a list) which is empty. Further, keep all Nodes sorted by their highest element and you need to clone all Nodes, such that a sequence like "1 2 3" has three nodes, "1", "1 2" and "1 2 3". Now if you encounter a new Node, you scan in O(log(n)) time for the first Node that could continue in you new found sequence. You then add forward links to all folowing, already known Nodes. Then you clone and add these new Nodes... Also keep track of the maximum path found so far. I am not sure what you can do to improve if the future is totally unknown.

Wikipedia: Longest_increasing_subsequence

Offline:

``````L = 0
for i = 1, 2, ... n:
binary search for the largest positive j ≤ L
such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
P[i] = M[j]
if j == L or X[i] < X[M[j+1]]:
M[j+1] = i
L = max(L, j+1)``````

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

DP Algo

``````vector<int> LIS(int * A, int n)
{
vector<vector<int>> vv(1);
for(int i=0; i<n; i++)
{
int m = vv.size();
if (m == 1 || A[i] > vv[m-1].back())
{
vector<int> nv(vv[m-1]);
nv.push_back(A[i]);
vv.push_back(nv);
}

for(int j=m-1; j>=1; j--)
{
if ((vv[j-1].size() == 0 || A[i] > vv[j-1].back()))
{
if (A[i] < vv[j].back())
{
vector<int> nv(vv[j-1]);
nv.push_back(A[i]);
vv[j] = nv;
}
}
}
}
return vv[vv.size() -1];
}``````

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

DP Algo

``````vector<int> LIS(int * A, int n)
{
vector<vector<int>> vv(1);
for(int i=0; i<n; i++)
{
int m = vv.size();
if (m == 1 || A[i] > vv[m-1].back())
{
vector<int> nv(vv[m-1]);
nv.push_back(A[i]);
vv.push_back(nv);
}

for(int j=m-1; j>=1; j--)
{
if ((vv[j-1].size() == 0 || A[i] > vv[j-1].back()))
{
if (A[i] < vv[j].back())
{
vector<int> nv(vv[j-1]);
nv.push_back(A[i]);
vv[j] = nv;
}
}
}
}
return vv[vv.size() -1];
}``````

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

``````import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;

public class LongestSequence {

static Seq current = new Seq();
static Seq lastLongSequence = new Seq();

public static void main(String[] args) {

int a[] = { 1, 5, 3, 4, 6, 4 };
int[] expectedResult = { 3, 4, 6 };

// coming from an input
for (int i = 0; i < a.length; i++) {
}

Seq result = current.size() > lastLongSequence.size()?current:lastLongSequence;

if (Arrays.equals(expectedResult, result.getAsArray())) {
System.out.println("Goal");
} else {
System.out.println("fail");
}

}

private static void addSequence(int i) {

if (i > current.getLastElement()) {
} else {
if(lastLongSequence.size() < current.size()){
lastLongSequence = current;
}
current = new Seq();
}

}

static class Seq {

int last = 0;

// using a dynamic array
ArrayList<Integer> s = new ArrayList<Integer>();

public int[] getAsArray() {

return convert(s);
}

public int size() {

return s.size();
}

public void add(int i) {
last = i;

}

public int getLastElement() {
return last;
}

int[] convert(ArrayList<Integer> integers) {
int[] r = new int[integers.size()];
Iterator<Integer> iterator = integers.iterator();
for (int i = 0; i < r.length; i++) {
r[i] = iterator.next().intValue();
}
return r;
}

}

}``````

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

why seed-round startups shouldn't use Java. You run out of money before engineers finish typing their code.

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

``````int ARRAY, ARRAYLEN; // input
int subArrStartInex = 0, subArrLen = 0; // ouput
int tempStartIndex = 0; tempArrLen = 1;

for (int i = 0; i < ARRAYLEN - 1; ++i) {
if (ARRAY[i] < ARRAY[i + 1]){
tempArrLen ++;
}
else {
// a descend detected
if (tempArrLen > subArrLen){
subArrStartIndex = tempStartIndex;
subArrLen = tempArrLen;
tempStartIndex = i + 1;
tempArrLen = 1;
}
}
}
if (tempArrLen > subArrLen){
subArrStartIndex = tempStartIndex;
subArrLen = tempArrLen;
}``````

It's O(n).

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

Question -> "You should process it as soon as you are taking an input."

Probably the arraylen doesn't work..

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

It's a fair comment. But the algorithm still applies because it doesn't use any future information. for loop can be replace with "while (next = file.getNextNumber())"
and the comparison (ARRAY[i] < ARRAY[i + 1])replaced by (cur < next). And late on update "cur" with (cur = next).

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

I have a question here. Why cant we just use the Longest Increasing subsequence solutions (Wiki)? Whenever an ith character is added, the list contains all the information to get the longest subsequence instantaneously!!

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

Is Longest Increasing sub-sequence different from this quesiton?

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

This does not work. Besides the fact that your algorithm can't return the subsequence in question, look at the following counterexample:

1 100 2 50 101 3 70 80 107 45

You temp and sub length are this:
t: 2 1 2 3 1 2 3 4 1
s: 0 2 2 2 3 3 3 3 4

So your result is 4, while the true answer is 6, that is:

1 2 50 70 80 107

> Is Longest Increasing sub-sequence different from this quesiton?

No but your algorithm does not fit the question. You need to keep track of all previous sequences, because they may all continue in the future and then turn out to be the longest with the very last element you read.

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

I think this should work

``````<?php
/**
* @Oct 15, 2012
* You are going to take some numbers as an input from a file.
* You need to witer a program to find longest increasing sequence.
* You should process it as soon as you are taking an input.
* After finishing the last input immediately you should be able to tell the sequence.
* Input: 1 5 3 4 6 4
* Output: 3 4 6
*/
\$fileHandle = fopen("data.txt", "r");

\$currentTotalMaximumSum = 0;
\$currentSeqMaximumSum   = 0;
\$previousNumber         = 0;
\$biggestStack           = array();
\$currentStack           = array();

while(!feof(\$fileHandle)) {
\$currentInputNumber = intval(fgets(\$fileHandle, 31)); //read from file
if(\$currentInputNumber) {
echo "\$currentInputNumber<br />";
if(\$currentInputNumber > \$previousNumber) {

//use the current number for the current sequence
\$currentSeqMaximumSum  += \$currentInputNumber;
\$currentStack[] = \$currentInputNumber;

if(\$currentSeqMaximumSum  > \$currentTotalMaximumSum) { //check against the current max
\$currentTotalMaximumSum = \$currentSeqMaximumSum ;
\$biggestStack    = \$currentStack;
}
} else { //reset the sequence and sum
\$currentSeqMaximumSum  = \$currentInputNumber;
\$currentStack  = array(\$currentInputNumber);
}
\$previousNumber = \$currentInputNumber;
}
}
echo "Biggest Sum Sequence is : " . implode(", ", \$biggestStack);
echo "<br />Biggest Sum is : " . \$currentTotalMaximumSum;

?>``````

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

This also can not work. You are forgetting older stacks. For instance imagine a sequence like:

1 2 3 50 51 52 80 61 62 63 64 65 4 5 6 7 8 9

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

This can be done using two linked lists. One denoting the longest increasing sequence "so far" (currentSeq). And another denoting the "next potential" increasing sequence (nextSeq). In the beginning, currentSeq = firstElementOnly and nextSeq = firstElementOnly. The moment nextSeq becomes longer than currentSeq, we do currentSeq = nextSeq. If an input element is encountered that is less than nextSeq.Tail, we do nextSeq = null. When the input ends, currentSeq will denote the longest sequence, and we just need to print it starting from currentSeq.Head.

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

No you have the same problem as everyone else... You are forgetting old sequences that later could become the largest.

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

int binarySearch(const vector<int>& leastNumber, int key) {
int l = 0, r = leastNumber.size();
while (l < r) {
int mid = (l+r) / 2;
if (key < leastNumber[mid]) {
r = mid;
} else
l = mid + 1;
}
return r;
}
int LongestCommonSequence(const vector<int>& data) {
vector<int> f, leastNumber;
f.resize(data.size());
for (int i = 0; i < data.size(); ++i) {
int j = binarySearch(leastNumber, data[i]);
if (j == leastNumber.size()) {
leastNumber.push_back(data[i]);
f[i] = leastNumber.size();
} else {
leastNumber[j] = data[i];
f[i] = j;
}
return f[data.size()-1];
}
}

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

this solution finds the length of maximum subsequence but not the sequence itself. An example input to show that is:
1, 5, 3, 4, 2

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

And this is no online algorithm as requested...

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

We can take use of a stack.

1. Keep reading numbers from the file.
2. Put the next number into stack if the top element on Stack is less than the current number.
3. If current number is less than the top element, pop all the elements and keep track of length of all the popped elements. This way you will keep track of longest number sequence.

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.