Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
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.
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.
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());
}
}
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)
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];
}
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];
}
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++) {
addSequence(a[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()) {
current.add(i);
} else {
if(lastLongSequence.size() < current.size()){
lastLongSequence = current;
}
current = new Seq();
current.add(i);
}
}
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;
s.add(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;
}
}
}
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).
Question -> "You should process it as soon as you are taking an input."
Probably the arraylen doesn't work..
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).
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!!
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.
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;
?>
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.
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];
}
}
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
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.
LIS in the question should be 1 3 4 6
- shailendraagarwal11 February 10, 2013