Epic Systems Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Written Test




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

public class PrintAllIncreasingSubsequence {

/**
* @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);

}
}

- Teddy October 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- sanjay.2812 November 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- tony.bruguier December 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)

- Anonymous December 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Tony,

In your example it's only one sequence...

the worst case is just your opposit I mean dec array... and I think there will be maximum of N sequence... not N^2

And also time complexity is not dependend on the output.. Its depends on the loop you are making to the array ..

- sanjay.2812 December 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- mystry November 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry. it should be i-- in the first for loop.

- mystry November 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous November 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Finding the RightMax is still O(n^2). IMHO, the way mystry post is even slower than a brutal force algorithm.

- amazon February 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can someone explain the DP code written above? Is there another way to do this problem?

- Anonymous November 29, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@mystry - please explain your solution!

- Anonymous November 29, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can it be solved by modifying LCS problem...
X = Y = input string
instead of comparing equality we should compare Cx > Cy

- Anonymous November 29, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// 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;
            }
        }
    }
}

- kartikaditya December 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous December 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Will we be asked to write code in the online test or will it be multiple choice questions

- Anonymous January 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This comment has been deleted.

- Administrator August 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Anonymous February 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

    } 
}

- disun March 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

- Anonymous March 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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() + " ");  
        }  
		
	}
}

- GKR March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
			}
					
		}
		
	}
}

- Anonymous March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Meraj Ahmed November 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- x November 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Djskra Algo April 13, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;
}

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

ooh man.. if you could just use indices instead of iterators and
declared some typedefs, your code would be so much easier to read..

- Anonymous November 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

----

- j December 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

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.

- hprem991 November 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Knuth–Morris–Pratt (KMP) is string searching algorithm!

- J January 15, 2013 | Flag


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