Facebook Interview Question Software Engineer / Developers
Not correct.
input: 1 2 3 4 3 4 5 6 7 8 9 10
longest subsequesnce: 3 4 5 6 7 8 9 10
real anwser: 1 2 3 <<4 3>> 4 5 6 7 8 9 10
delete <<4 3>>
one possible solution using dynamic programming.
For every element i
{
maxcurr = 1; maxElemArr[i] = i; maxSumArr[i] = 0;
for every element j<i
{
if a[i]>a[j]{
if(maxcurr < maxSumArr[j]+1)){
maxcurr = maxSumArr[j]+1
maxElemArr[i] = j
}
}
}
maxSumArr[i] = maxcurr; //max sum
}
For sequence 1 2 3 8 10 5 6 7 12 9 4 0,
i=0; a[i]=1 maxSumArr = {1,0,0,....} maxElemArr = {0,0,0,0...}
i=1; a[i]=2 maxSumArr = {1,2,0,....} maxElemArr = {0,0,0,0...}
i=2; a[i]=3 maxSumArr = {1,2,3,....} maxElemArr = {0,0,1,0...}
i=3; a[i]=8 maxSumArr = {1,2,3,4...} maxElemArr = {0,0,1,2...}
i=4;a[i]=10 maxSumArr = {1,2,3,4,5..} maxElemArr = {0,0,1,2,3..}
i=5;a[i]=5 maxSumArr = {1,2,3,4,5,4,0,..} maxElemArr = {0,0,1,2,3,2,...}
i=6;a[i]=6 maxSumArr = {1,2,3,4,5,4,5,..} maxElemArr = {0,0,1,2,3,2,5.}
...and so on
#include <iostream>
#include <vector>
using namespace std;
template <typename T> vector<T> findLongestOrderedArray(const vector<T> &a);
int main(){
vector<int> a {1,2,3,8,10,5,6,7,12,9,4,0}; //{1,2,3,4,5,6,7,8,9,10};
vector<int> longestPath = findLongestOrderedArray(a);
cout<<"Longest Ordered Subsequence ::"<<endl;
for(int i=0;i<a.size();++i)
if(longestPath[i])
cout<<","<<a[i];
}
//!Find the longest ordered string in a sequence of numbers, returns a vector with bits set for longest path
template <typename T>
vector<T> findLongestOrderedArray(const vector<T> &a){
int finalIndx=0,finalMax=0,maxCurr=0,sz = a.size();
vector<T> maxElemArr(sz,0),maxSumArr(sz,0),longPath(sz,0);
int numComputs = 0;
for(int i=0;i<sz;++i){
maxCurr = 1; maxElemArr[i] = i; maxSumArr[i] = 0;
for(int j=i-1;j>=0;--j){ //go reverse. this improves the worst case
++numComputs;
if (a[i]>a[j]){
if(maxCurr < maxSumArr[j]+1){
maxCurr = maxSumArr[j]+1;
maxElemArr[i] = j;
}
}
if(maxCurr==j+2) break; //optimization
}if(finalMax<maxCurr){
finalMax = maxCurr;
finalIndx = i;
}maxSumArr[i] = maxCurr;
}
for(int indx=finalIndx;finalMax>0;--finalMax){
longPath[indx] = 1; //set
indx = maxElemArr[indx];
}
cout<<"numcomputes"<<numComputs<<endl;
return longPath;//longest path bits are set to 1
}
make a tree with each element as node and make the next element as next node if present element is less than the last element then go to a element in the tree which is just lest than this element and make a new branch there and continue
finally print the largest possible path of that tree
may be u can maintain the height while constructing
so the no of elements to remove is total no of elements - height of the tree
you algorithm doesn't work. demonstrate using this sequence 12,13,15,16,1,6,8,2,3,4,5,7,9,19,10,11,17
it will work fine. depends on how you visualize it.
Two data structures: 1) graph and 2) BST trees to lookup the node in the graph in logarithmic complexity. There will be a BST tree to look up in each branch of graph.
In graph, root node is the special node, keep on attaching new node to the previous node till the new node value > previous node. If not look up in all the BSTs for the new node value. Attach new node to all the previous node not null results from BSTs. Create a new BST with this new node and keep on adding to it till new branch forms.
The height of this graph will give us the largest subsequence.
start--->12--->13--->14--->15--->16--->null
|
--->1--->6--->8--->null
|
---->2--->3--->4--->5--->7--->9--->19--->null
|
---->10-->11-->17-->null
the height of this tree will give the right answer
My mistake correct graph is
start-->12-->13-->14-->15-->16-->19 (pointer to 19 node)
| |
| --->17 (pointer to 17 node)
|
--->1--->6--->8-------------------
| |
---->2--->3--->4--->5--->7--->9--->19--->null
|
---->10-->11-->17-->null
BSTs:
1) 12-->15------>17--> 19
| |
--->14-->15 -->16
|
-->13
2) 9--->11--->17--->19
| |
| --->10
|--->6--->8
|
--->1
3)BST of bottom of node 1
That was my solution. I extended TreeMap to map integers with the number of occurrences (to handle duplicates).
import java.util.List;
import java.util.ArrayList;
import java.lang.Integer;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;
public class Sequence {
public static class MyMap extends TreeMap<Integer,Integer> {
public MyMap() {
super();
}
public MyMap(SortedMap<Integer,Integer> m) {
super(m);
}
public void myPut(int i) {
Integer numIs = this.get(new Integer(i));
if(numIs == null) {
this.put(new Integer(i), new Integer(1));
} else {
this.put(new Integer(i), new Integer(numIs.intValue() + 1));
}
}
public String toString() {
String retval = "";
for(Integer i : keySet()) {
int numIs = get(i).intValue();
for(int j = 0; j < numIs; j++) {
retval += i + " ";
}
}
return retval;
}
}
public static MyMap longestSequence(int[] a) {
int numRemoved = 0;
List<MyMap> sequences = new ArrayList<MyMap>();
for(int i = 0; i < a.length; i ++) {
boolean added = false;
for(MyMap sequence : sequences) {
int top = sequence.lastKey().intValue();
if(a[i] >= top) {
sequence.myPut(a[i]);
added = true;
}
}
if(!added) {
List<MyMap> toAdd = new ArrayList<MyMap>();
for(MyMap sequence : sequences) {
SortedMap<Integer,Integer> beforeThis = sequence.headMap(new Integer(a[i] + 1));
if(!beforeThis.isEmpty()) {
MyMap copy = new MyMap(beforeThis);
copy.myPut(a[i]);
added = true;
}
}
sequences.addAll(toAdd);
}
if(!added) {
MyMap m = new MyMap();
m.myPut(a[i]);
sequences.add(m);
}
}
int max = 0;
MyMap largest = null;
for(MyMap sequence : sequences) {
if(sequence.size() > max) {
largest = sequence;
max = sequence.size();
}
}
return largest;
}
public static void main(String[] args) {
int [] a = new int[]{1,1,1,1,1,1,1,2,2,2,2,2,2,2,10,11,12,18,1,2,3,19,20,4,1,6};
System.out.println(longestSequence(a));
}
}
input array a[]
output array ord[]
N = 0;
M = 0;
for (i=1;i<n-1;i++){
if (a[i] >= a[i-1]){
if (M == 0){
tmp[0] = a[i-1];
tmp[1] = a[i];
M = 2;
}
else
tmp[M+1] = a[i];
}
else
if (M > N){
copy (tmp, ord);
N = M;
M = 0;
}
}
For this input, 8 9 1 2 3 4 5 10
your prog will output 8,9 while the right answer is 1 2 3 4 5
public static void main(String[] args){
int[] a={1,2,3,4,5,6,7,8,9,10,5,6,8,12,7,3,14,2,20};
int i=1,j=0;
int count=0;
while(i<a.length){
if(a[j]<a[i]){
System.out.print(a[j]);
j=i;
i=i+1;
}else if(a[j]>a[i]){
i++;
count++;
}
}
System.out.print(a[j]);
System.out.println("count "+count);
}
using dynamic programming
if a[i] >= max(a[0 ... i-1] then l(i) = l(i - 1) + 1, put a[i] into result array.
else l(i) = l(i-1);
public static int[] longestSubesequence(int[]a, int start, int end, int[] result, int max)throws IOException{
//Input: 1 2 3 8 10 5 6 7 12 9 4 0
//output: 1 2 3 5 6 7 12.
//1 2 3 8 10 5 6 7 12 9 4 0
int []prevArray = new int[0];
int []arr;
for(int i = start; i<a.length;i++){
if(max==0||result[max - 1] < a[i]){
result[max] = a[i];
arr = longestSubesequence(a, i + 1, end, result, max + 1);
if(arr.length > prevArray.length){
prevArray = arr;
}
}
}
if(prevArray.length < max){
prevArray = Arrays.copyOfRange(result, 0, max);
}
return prevArray;
}
public static void main(String[] args) throws IOException{
int [] numbers = { 1, 2, 3, 8, 10, 5, 6, 7, 12, 9, 4,0};
int [] result = new int[numbers.length];
PrintStream output = new PrintStream(new File("test.txt"));
int[] finals =longestSubesequence(numbers, 0, numbers.length, result, 0);
System.out.println(Arrays.toString(finals));
}
I think this can be done in O(n). (Similar to max sub array in given array but with twist)
maxCountTillNow = maxCount = 0;
maxValTillNow = maxVal = 0;
maxVal = maxValTillNow = curVal = arr[i];
maxCountTillNow = maxCount = 1;
List<int> indexes = new List<int>(), indexesTillNow = new List<>();
indexes.Add(0); //Add the first one.
for(int i=1; i< n; i++)
{
if(arr[i] > curVal)
{
maxVal = arr[i];
maxCount++;
indexes.Add(i);
//Check if the arr[i] is greater than maxValTillNow and if maxCount < maxCountTillNow.
//If so we can actually resume our previous sequence
if((maxCountTillNow > maxCount) && (arr[i] > maxValTillNow))
{
//we can start resuming our prev sequence. Just note which indexes to add to final array.
indexesTillNow.Add(i);
indexes.clear();
}
}
else
{
//Break in sequence
//Save maxCount if greater than maxCountTillNow
if(maxCountTillNow < maxCount)
{
maxCountTillNow = maxCount;
maxValTillNow = maxVal;
indexesTillNow = indexes;
}
maxVal = curVal;
maxCount = 1;
}
}
Review and let me know if you see issue.
One more initialization i forgot is:
//Check if the arr[i] is greater than maxValTillNow and if maxCount < maxCountTillNow.
//If so we can actually resume our previous sequence
if((maxCountTillNow > maxCount) && (arr[i] > maxValTillNow))
{
//we can start resuming our prev sequence. Just note which indexes to add to final array.
indexesTillNow.Add(i);
indexes.clear();
maxCountTillNow ++;
maxCount = maxCountTillNow;
maxValue = arr[i];
}
void longest_increasing_subseq(int *a, int n)
{
int seq_buffer[4096];
int next_buffer[4096];
int *seq_length = NULL;
int *next_index = NULL;
int max_len = 0;
int start_index;
int i, j;
if (n > 0) {
max_len = 1;
start_index = 0;
/* avoid malloc if request can be service through stack memory. */
if (sizeof(int)*n <= sizeof(seq_buffer)) {
seq_length = seq_buffer;
}else {
seq_length = (int *)malloc(sizeof(int)*n);
}
if (sizeof(int)*n <= sizeof(next_buffer)) {
next_index = next_buffer;
} else {
next_index = (int *)malloc(sizeof(int)*n);
}
}
for (i = 0; i < n; ++i) {
seq_length[i] = 1;
}
for (i = n - 1; i >= 0; --i) {
for (j = i + 1; j < n; ++j) {
if ((a[i] <= a[j]) && (seq_length[i] < seq_length[j] + 1)) {
seq_length[i] = seq_length[j] + 1;
next_index[i] = j;
if (seq_length[i] > max_len) {
max_len = seq_length[i];
start_index = i;
}
}
}
}
if (seq_length != seq_buffer) {
free(seq_length);
}
printf("Removal count: %d\n", n - max_len);
while (max_len--) {
printf("%d ", a[start_index]);
start_index = next_index[start_index];
}
printf("\n");
if (next_index != next_buffer) {
free(next_index);
}
return;
}
int main()
{
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int b[] = {1, 2, 3, 8, 10, 5, 6, 7, 12, 9, 4, 0};
longest_increasing_subseq(a, sizeof(a)/sizeof(a[0]));
longest_increasing_subseq(b, sizeof(b)/sizeof(b[0]));
return 0;
}
Longest increasing subsequence is the answer.
- nitin December 01, 2010And can be done in O(nlog(n)) in the worst case.