Epic Systems Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
the worst case scenario will be O(n^2). you can use a array of same size as of number. or use int *
put the first at the base.
read the next element if greater then write the seq in the 2-D array replace the element of the first index be new number. else put the number in the second index. loop the same way until the last number.
print the 2-D array according to the row.
Best Case is O(N)
The complexity cannot be n^2 because there are more subsequences than that. If the input is 1, 2, 3, ..., n
Then, there are 2^n subsequences.
Correct?
Tony Bruguier
nope, we do not take subsequences into account, i.e.,
always search for a longest sequence. If the nos are consecutive, there will be only 1 sequence.
the max no of sequences is O(n^2)
Can this be done using DP ?
Step1) Find RightMax for Each Element. If none then put -1.
input: 5 4 7 8 2 3 6 9 8 6 2 3 4 5
Rmax: 6 5 8 9 3 6 8 -1 -1 -1 3 4 5 -1
Step2)
for(i=n-1;i>=0;i++){
if(Rmax[i]==-1)
dp[i]=2;
else{
dp[i]=2*dp[j] // such that A[j]==Rmax[i] and i<j
}
}
output=0;
for (i =0;i<n;i++)
output+=dp[i];
//output will contains number of possible increasing subsequences.
// a small tweak in can print all the subsequences.
Correct me if am wrong.
but are you sure we can compute RightMax for each elt in time less than O(n^2) ? otherwise simple brute force method will work
// Keep number and length of max sub-seq ending in this number
// in every node of a balanced binary tree (RB tree) implementation
balanced_binary_tree<pair<int, int> > dp;
// O (n log n)
void findLongestIncreasingSubsequence (int a[], int n) {
// O(n log n)
for (int i = 0; i < n; ++i) {
// get node that has node.first <= a[i]
balanced_binary_tree::node node = dp.findLessThanEqNode (a[i]);
if (node == null) {
dp.insert (a[i], 1);
} else if (node.first == a[i]) {
++node.second;
} else {
dp.insert (a[i], node.second + 1);
}
}
// O (n)
// get node with max node.second
balanced_binary_tree::node node = dp.findMaxNode ();
int max = node.first;
int size = node.second;
print ("Max length :: " size);
// O (n log n)
// Printing reverse order of the increasing subsequence
int i;
// search for the max element first
for (i = n - 1; i >= 0; --i) {
if (a[i] == max) {
print (a[i]);
--size;
break;
}
}
// for every element less than current max, check if it
// tails the current max. In that case update max and size
for (;i >= 0; --i) {
if (a[i] <= max) {
balanced_binary_tree::node node = dp.findNode (a[i]);
if (node.second == size) {
print (a[i]);
max = a[i]
--size;
}
}
}
}
can you explain your soln please ?
note that here the task is to print *all* increasing subsequences,
not just the longest one.
Giving that, the number of them could be O(n) with length
O(n), I do not see how we can print all of them in O(nlog n) time.
For example, consider the original sequence to be:
[a, a-1, a-2, ..., a-n/2, a+1, a+2, ..., a+n/2]
then we have n/2 increasing sequences of length n/2, i.e.:
a, a+1,...,a+n/2
a-1, a+1,...,a+n/2
...
a-n/2, a+1,...a+n/2
static ArrayList<String> findSubString(String input){
ArrayList<String> result = new ArrayList<String> ();
ArrayList<String> tempresult = new ArrayList<String> ();
char[] inputChar= input.toCharArray();
for(int i=inputChar.length-1;i>=0;i--){
if(result.isEmpty()){
result.add(String.valueOf(inputChar[i]));
}
else{
for(String temp: result){
if(inputChar[i]<temp.charAt(0)){
tempresult.add(String.valueOf(inputChar[i]+temp));
}
else{
tempresult.add(String.valueOf(inputChar[i]));
}
}
for(String t: tempresult){
if(!result.contains(t))
result.add(t);
}
tempresult.clear();
}
}
return result;
}
import java.util.ArrayList;
public class increaseSubseq {
public static void printAll (int[] a) {
ArrayList<String> lst = new ArrayList<String>();
for (int i=0; i<a.length; i++) {
int max = 0;
max = a[i];
StringBuilder sb = new StringBuilder();
sb.append(max);
for (int j=i+1; j<a.length; j++) {
if (a[j] > max) {
max = a[j];
sb.append(max);
}
}
lst.add(sb.toString());
}
for (int i=0;i<lst.size(); i++){
System.out.println(lst.get(i));
}
}
public static void main(String[] args) {
int[] a = {5,4,7,8,2,3,6,9,8,6,2,3,4,5};
printAll(a);
}
}
import java.util.LinkedList;
import java.util.List;
public class IncrementFinder {
public static void main(String[] args) {
for (String string : find("61236578")) {
System.out.println(string);
}
}
private static List<String> find(String string) {
List<String> list = new LinkedList<String>();
char[] charArray = string.toCharArray();
for (int i = 0; i < charArray.length; i++) {
if (i == 0 || charArray[i] <= charArray[i - 1]) {
list.add(String.valueOf(charArray[i]));
} else {
int lastIndex = list.size() - 1;
list.set(lastIndex, list.get(lastIndex) + charArray[i]);
}
}
return list;
}
}
import java.util.LinkedList;
public class IncreasingSubsequence
{
public static int temp1, temp2 = 0;
public static int seq[]= {5,5,7,6,7,2,3,4,5,1,2,7,8,9,10,12};
public static LinkedList<Object> list = new LinkedList<Object>();
public static void main(String[] args)
{
for(int i=1;i<seq.length;i++)
{
temp1 = seq[i-1];
temp2 = seq[i];
if (temp1<= temp2)
{
list.add(String.valueOf(seq[i-1]));
if(i == seq.length-1) list.add(String.valueOf(seq[i]));
}
else
{
list.add(String.valueOf(seq[i-1]));
list.add(";");
if(i == seq.length-1) list.add(String.valueOf(seq[i]));
}
}
java.util.Iterator<Object> iterator = list.iterator();
while (iterator.hasNext())
{
System.out.print( iterator.next() + " ");
}
}
}
import java.util.LinkedList;
public class IncreasingSubsequence
{
public static int temp1, temp2 = 0;
public static int seq[]= {5,5,7,6,7,2,3,4,5,1,2,7,8,9,10,12};
public static void main(String[] args)
{
for(int i=1;i<seq.length;i++)
{
temp1 = seq[i-1];
temp2 = seq[i];
if (temp1<= temp2)
{
System.out.print(seq[i-1]+" ");
if(i == seq.length-1) System.out.print(seq[i]);
}
else
{
System.out.print(seq[i-1]+" ");
System.out.print("; ");
if(i == seq.length-1) System.out.print(seq[i]);
}
}
}
}
Here is a working code in C++:
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
long long int num, max, temp, arr[30], str[30], i, j;
cin>>num;
i=0;
while (num!=0)
{
arr[i]=num%10;
num=num/10;
str[i]=0;
i++;
}
i--;
if (i%2!=0)
{
for (j=0; j<=i/2; j++)
{
temp=arr[j];
arr[j]=arr[i-j];
arr[i-j]=temp;
}
}
else
{
for (j=0; j<i/2; j++)
{
temp=arr[j];
arr[j]=arr[i-j];
arr[i-j]=temp;
}
}
temp=i;
for (i=0; i<=temp; i++)
{
if (str[i]==1)
{
continue;
}
max=arr[i];
for (j=i; j<=temp; j++)
{
if (arr[j]>=max)
{
max=arr[j];
cout<<arr[j];
str[j]=1;
}
}
cout<<endl;
}
return 0;
}
public static void increaseNumber(String num){
int[] start = new int[num.length()];
char[] arr = num.toCharArray();
int index = 0;
while(index<num.length())
{
int i = index;
if(start[i]!=1)
{
int max = Integer.parseInt(arr[i]+"");
System.out.print(max);
i++;
while(i<num.length())
{
if(Integer.parseInt(arr[i]+"")>max)
{
max = Integer.parseInt(arr[i]+"");
start[i]=1;
System.out.print(max);
}
i++;
}
System.out.println();
}
index++;
}
}
public static void main(String[] args)
{
increaseNumber("54782369862345");
}
Brute force
Here is perfectly running c++ code
#include <iostream>
#include <vector>
using namespace std;
int base = 10;
void printAll(int A[], int n, vector<string> lst) {
for (int i = 0; i < n; i++) {
int max = 0;
max = A[i];
string sb;
char a[8];
for (int ii = 0; ii < 8; ii++)
a[ii] = '\0';
_itoa_s(max, a, base);
sb.append(a);
sb.append(" ");
for (int j = i + 1; j < n; j++) {
if (A[j] > max) {
max = A[j];
for (int ii = 0; ii < 8; ii++)
a[ii] = '\0';
_itoa_s(max, a, base);
sb.append(a);
sb.append(" ");
}
}
lst.push_back(sb);
}
for (int i = 0; i < lst.size(); i++)
cout << lst[i] << endl;
}
int main() {
const int n = 8;
vector<string> lst;
int A[n] = { 9, 1, 3, 7, 5, 9, 10, 4 };
printAll(A, n, lst);
return 0;
}
list<vector<int>> GetAllIncreaseSequences(const vector<int>& input)
{
list<vector<int> retSets;
for(vector<int>::const_iterator citer = input.begin; citer != input.end(); ++citer)
{
if(retSets.size() == 0)
{
retSets.push_back(vector<int>(*citer));
}
else
{
for(list<vector<int>::iterator iter = retSets.begin(); iter != input.end(); ++iter)
{
if(*citer > *(iter->end() - 1)
{
iter->push_back(*citer);
}
else
{
retSets.push_back(vector<int>(*citer));
}
}
}
}
return retSets;
}
If Time Complexity Matters the Most than , you can use the KMP Algo modification for integer accordingly.Its 0(n) , else if 0(n2) is okei than just need to use to loops one for picking each integer in a series and other for checking just the immediate next if its value is greater than itself and collection accordingly.
public class PrintAllIncreasingSubsequence {
- Teddy October 18, 2012/**
* @param args the command line arguments
*/
public static void printAll (int[] a, ArrayList<String> lst) {
for (int i=0; i<a.length; i++) {
int max = 0;
max = a[i];
StringBuilder sb = new StringBuilder();
sb.append(max + " ");
for (int j=i+1; j<a.length; j++) {
if (a[j] > max) {
max = a[j];
sb.append(max + " ");
}
}
lst.add(sb.toString());
}
for (int i=0;i<lst.size(); i++){
System.out.println(lst.get(i));
}
}
public static void main(String[] args) {
// TODO code application logic here
ArrayList<String> lst = new ArrayList<String>();
int[] a = {5,4,7,8,2,3,6,9,8,6,2,3,4,5};
printAll(a,lst);
}
}