Facebook Interview Question for Software Engineer / Developers


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

- shailendraagarwal11 February 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- CnyrdSnyrd February 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Safi December 05, 2014 | Flag
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();
			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());
	}

}

- Anonymous December 01, 2012 | Flag Reply
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)

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

- BIN December 20, 2013 | Flag Reply
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];
	}

- BIN December 20, 2013 | Flag Reply
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++) {
			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;
		}

	}

}

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

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

- Ragnus October 15, 2012 | Flag
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).

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

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

Probably the arraylen doesn't work..

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

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

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

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

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

Is Longest Increasing sub-sequence different from this quesiton?

- peter tang October 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- FBNerd February 28, 2013 | Flag
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;

?>

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

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

- FBNerd February 28, 2013 | Flag
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.

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

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

- FBNerd February 28, 2013 | Flag
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];
}
}

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

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

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

And this is no online algorithm as requested...

- FBNerd February 28, 2013 | Flag
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.

- Mario October 14, 2012 | Flag Reply


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