Epic Systems Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Written Test




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

public class substringsum {

	public static String checkifinsubstring(int [] arr, int sum)
	{
		for(int i=0;i<arr.length;i++)
		{
		int total = 0;	
			for(int j=i;j<arr.length;j++)
			{
				total = total+arr[j];
				if (total == sum)
				{
					return i+"-"+j;
				}
				else if(total>sum)
				{
					break;
				}
			}
		}
		return "Not found";
	}
	
	public static void main(String[] args)
	{
		// TODO Auto-generated method stub
		int [] arr = {1, 5, 9, 11, 2, 4};
		int sum = 27;
		System.out.println(checkifinsubstring(arr, sum));
		
	}

}

- Anonymous October 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You method is great, but you forget to search all possible combinations.

my code is the following:

package EPIC;

public class SubStringAddition {

	public static String checkifinsubstring(int [] arr, int sum)
	{
		String result = "";
		for(int i=0;i<arr.length;i++)
		{
		int total = 0;	
			for(int j=i;j<arr.length;j++)
			{
				total = total+arr[j];
				if (total == sum)
				{
					result += i+" - "+j + "\n";
				}
			}
		}
		
		if (result == "") {
			return "no such substring";
		}
		
		return result;
	}
	
	public static void main(String[] args)
	{
		int [] arr = {1, 5, 9, 11, 2, 4, 9};
		int sum = 150;
		System.out.println(checkifinsubstring(arr, sum));
		
	}

}

- albertchenyu March 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

3 + 5 + 8 is also 16.

- SixDegrees August 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Sliding window is a good start. Since we are trying to find a consecutive range, instead of calculating (from i to j) we can try to solve another problem. We find (0->i) and (0->j) such that those two segments will sum up to value1 and value1+target. To facilitate O(1) data access for each elements, map structure is used. The following code assumes array value can be any integer number, and will output all possible segments if multiple segments meet the criteria. Complexity O(n), O(n).
Playable version at

ideone.com/H7JJX2

vector<pair<int, int>> findRange(int A[], int n, int target) {
	unordered_multimap<int, int> um;
	vector<pair<int, int>> ret;
	for (int i(0), leftsum(0); i < n; ++i) {
		if (i == 0) leftsum = A[0];	// left sum is sum[0, i]
		else leftsum += A[i];
		um.insert(make_pair(leftsum, i));
	}
	for (int i(0), leftsum(0); i < n; ++i) {
		if (i == 0) leftsum = 0;	// now leftsum is sum[0, i-1]
		else leftsum += A[i - 1];
		int targetsum = leftsum + target;
		auto p = um.equal_range(targetsum);
		for (auto st = p.first; st != p.second; ++st) {
			if ((*st).second < i) continue;
			//ret.push_back(make_pair(i, (*st).second));
			ret.push_back(make_pair(i+1, (*st).second+1));
		}
	}
	return ret;
}

- XiaoPiGu December 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

We kinda share the same idea. Find the smallest substring[0, L] Sub that its sum is no less than the expected sum, then compute the diff = Sub - sum. Finally find substring of Sub whose sum = diff. I think linear time is much better than shifting window.

- NathanLRF January 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can this work if there exists 0 or duplicates?
Sorry, just found you were using multimap

- LuborLiu February 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

#include <stdio.h>
void substr_add(int *,int,int);
int main(int argc, char *argv[])
{
int arr[]={1,7,6,3,5,8,9};
int s=16;
substr_add(arr,7,s);
}
void substr_add(int *a,int size,int sum)
{
int i,total=0,j,flag=0;
for(i=0;i<size;i++)
{
total=0;
for(j=i;j<size;j++)
{
total+=a[j];
if(total==sum)
{
flag=1;
printf("the sum is from %d-%d\n",i+1,j+1);
break;
}
}
if(flag==1)
break;

}


}

- anvesh.patloori February 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

one has to get rid of last

if(flag==1) break;

to get all possible set of indexes.

- An Enthusiast November 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

This is the form of Subset Sum problem with DP giving the best value of O(n2)

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

since the problem is limited to the sum of the substrings we can do O(n^2) in any case, i.e.:

static void SubStringSum(int sum, int[] input)
{
	var suffixes = new int[input.Length];
	var curSum = 0;
	for(var i=input.Length - 1; i>=0;i--)
	{
		curSum += input[i];
		suffixes[i] = curSum;
	}
	for(var i=0;i<suffixes.Length;i++)
	{
		for(var j=i;j<suffixes.Length;j++)
		{
			if(suffixes[i] - suffixes[j] == sum)
			{
				Console.WriteLine("{0}-{1}",i,j-1);
			}
		}
	}
}

- S.Abakumoff February 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The subset sum problem is NP-complete, right? How can it be solved in polynomial time?

- Chih.Chiu.19 February 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

NP-complete is with negative numbers and this problem is for substring not subsequence

- papu March 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are adding numbers and storing them in a suffixes array? How do you handle Integer overflow cases?
All the number might be less than +Int.Max_Val but the sum might exceed max int value right?

- Coder December 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are adding numbers and storing them in a suffixes array? How do you handle Integer overflow cases?
All the number might be less than +Int.Max_Val but the sum might exceed max int value right?

- careercupuser December 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public string  SubsetSome()
    {
        int[] numbers = { 1, 2, 5, 7, 9, 11, 13 };
        int sum , totalsum = 20, from = 0, to = 0, i = 0, j = 0;


        for (i = 0; i < numbers.Length; i++)
        {
            sum = 0;
            for (j = 0; j < numbers.Length; j++)
            {
                sum += numbers[j+i];

                if (sum == totalsum)
                {
                    from = i;
                    to = j+i;
                    break;
                }
                if (sum > totalsum)
                    break;
            }
            if(from!=0 && to!= 0 )
            {
                break;
            }
        }

        return "From Index " + from + "  ----   " + to + "  Index";
    }

- Nishant Kumar February 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you should not consider the if (sum > totalsum) break;; as if the number in the list is negative then by adding negative number the sum will decrease and can be checked with the input.

- Coder February 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This code will take O(N^2)

public string  SubsetSome()
    {
        int[] numbers = { 1, 2, 5, 7, 9, 11, 13 };
        int sum , totalsum = 20, from = 0, to = 0, i = 0, j = 0;

        for (i = 0; i < numbers.Length; i++)
        {
            sum = 0;
            for (j = 0; j < numbers.Length; j++)
            {
                sum += numbers[j+i];

                if (sum == totalsum)
                {
                    from = i;
                    to = j+i;
                    break;
                }
                if (sum > totalsum)
                    break;
            }
            if(from!=0 && to!= 0 )
            {
                break;
            }
        }

        return "From Index " + from + "  ----   " + to + "  Index";
    }

- nihantanu February 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 votes

O(n) is enough. use a hashmap to store the sum of subsequences starting from 0 to 1,2,...n-1. Loop again for a sum a if a+16 exist in the map, got it.

- maillist.danielyin@gmail.com November 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public string SubsetSum()
{
    int[] numbers = { 1, 2, 5, 7, 9, 11, 13 };
    int sum , totalSum = 2222, from = 0, to = 0;

    for (var i = 0; i < numbers.Length; i++)
    {
        sum = 0;
        for (var j = i; j < numbers.Length; j++)
        {
            sum += numbers[j];
            if (sum == totalSum)
            {
                from = i;
                to = j;
                break;
            }
        }
        if (from != 0 && to != 0)
        {
            break;
        }
            
    }
    return "From Index " + from + "  ----   " + to + "  Index";
}

- nihantanu February 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

We can use sliding window to obtain better algorithm.
Time: O(N)
Space: O(1)

private void printSubstringSumWithSlidingWindow(int[] arr, int value){
		int left = 0; 
		int right = 0;
		
		int sum = arr[0];
		
		while( true ){
			
			if( sum > value ){
				
				sum -= arr[left]; 
				++left;
				
				if( left > right ){
					if( left == arr.length ){
						break;
					}
					right = left;
					sum = arr[left];
				}
			}
			else {
				if( sum == value ){
				System.out.println( "found: ("  + left + ", " + right + ")");					
				}
				
				if( right+1 == arr.length ){
					break;
				}
				
				sum += arr[right+1];
				++right;
			}
		}
		
	}

- m@}{ February 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

so wrong...what if the some arr[i]<0?

- jicheninsjtu July 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

To clarify: sliding window algorithm works only if all the values are positive or 0. For negative values we need to use DP approach.

- m@}{ February 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

0(n) solution.start from array index 0,keep on adding if u get the sum then print the element from 0 to that index or if u get the value > sum them start moving the start index and substract the value till u dont get the value <sum .repeat this unless u reach the end or get the sum.

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

time complexity for this solution is O(n^2).

- nagrath.divya February 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Well, this solution won't work. It work's only for sorted list. Since the list might not be sorted so the solution will not work.

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

public void SubAdd(int[] arr, int sum) {
		int j = 0;
		int k = 0;
		int sumarr = 0;
		for(int i=0; j < arr.length; i++ ) {
			if(i < arr.length) {
				sumarr += arr[i];
				k++;
			}
			if(sumarr > sum) {
				
				sumarr = sumarr - arr[j];
				j++;
			}
			if(sumarr == sum){
				System.out.println((j+1) +"-"+ k);
				break;
			}
			if(arr.length-1 == i) {
				System.out.println("Nothing found");
			}
		}
	}

O(n) Time complexity

- abhradeep.kundu March 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package Epic;

/**
 * 1.Substring Addition
 * 
 *  Write a program to add the substring  
 *  eg :say you have a list {1 7 6 3 5 8 9 } and user is entering 
 *  a sum 16.Output should display (2-4) that is {7 6 3} cause 
 *  7+6+3=16.
 * 
 * Logic: 
 * 	1. start with first index.
 *  2. Add the value of the array, till the sum if it equal with 
 *  	required Sum, you are done.
 *  3. Otherwise  move with the next index 
 * 
 * @author jhaxx030
 *
 */
public class SubstringAddition {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int []array = {1, 7, 6, 3, 5, 8, 9 };
		int desiredSum = 16;
		findSubstringForAddingNumber(array, desiredSum);
	}

	/**
	 * @param array
	 * @param desiredSum
	 */
	public static void findSubstringForAddingNumber(
			int []array, int desiredSum){
		int index = 0, sum = 0, startIndex = 0;
		for(int i = 0; i < array.length; i++){	
			sum += array[i];
			if(sum == desiredSum){
				index++;
				System.out.println((startIndex+1)+"----"
						+(index+1) + "\t "+ sum);
				//break;
			}else if(sum < desiredSum){
				index++;				
			}else{
				i = startIndex;
				startIndex++;
				index = i;
				sum = 0;
			}
		}
	}
}

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

My Code works for negative/positive values... However it has very high complexity of O(n2).

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

if you take the desired sum as 8 it gives an erroneous solution.
1----3 8
4----5 8
6----6 8

It should be 1---2

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

Python version, working code.
Printed all the possible continuely subsets. O(n^2)

@input 16
@output (2 - 4), (4 - 6)

"""

1.Substring Addition 
Write a program to add the substring 
eg :say you have a list {1 7 6 3 5 8 9 } and user is entering a sum 16.Output should display (2-4) that is {7 6 3} cause 7+6+3=16.
"""

class SubStringAdd(object):
  def __init__(self, string, sum):
    if string is None or sum is None:
      print 'Invalid paras!'
      raise SystemExit
      
    self._string = string
    self._sum = sum
    
  def findSub(self):
    output = []
    for i in range(len(self._string)):
      tmpSum = self._string[i]
      if tmpSum == self._sum:
          output.append('(' + str(i+1) + ' - ' + str(i+1) + ')')
      for j in range(i+1, len(self._string)):
        tmpSum += self._string[j]
        # print tmpSum
        if tmpSum > self._sum:
          break
        if tmpSum == self._sum:
          output.append('(' + str(i+1) + ' - ' + str(j+1) + ')')
        
    if output == []:
      return 'Not FOUND!'
    else:
      return ', '.join(output)
        
if __name__ == '__main__':
  sub = SubStringAdd([1, 7, 6, 3, 5, 8, 9], 16)
  print sub.findSub()

- tosay.net March 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;
 using System.Collections;
 
 class subStrSum
 {
 	static void subStrSumFun(int count, int sum, int[] inputArr)
 	{
 		int tempCount = 0;
 		for(int i = 0; i < inputArr.Length; i++)
 		{
 			int tempSum = 0;
 			for(int j = i; (j < i + count)&&(i+count < inputArr.Length); j++)
 			{
 			   if(tempSum < sum)
 				   tempSum += inputArr[j];;
 			}
 			if(tempSum == sum)
 			{
 				tempCount ++;
 				Console.Write(tempCount + " : The sub-string is ");
 				for(int k = i; k < i+count; k++ )
 					Console.Write(inputArr[k] + " ");
 				Console.WriteLine();
 			}	
 		}
 		if(tempCount == 0)
 			Console.WriteLine("Sorry, there is no such sub-string with the length of " + count + " and the subtotal of " + sum + ".");
 		
 	}
 	static void Main()
 	{
 		Console.WriteLine("Please input a sequence of integers with a blanket to seperate each other.");
 		string input = Console.ReadLine();
 		string [] seperated = input.Split(' ');
 		int[] numSeq = new int[seperated.Length];
 		int totalsum = 0;
 		for(int i =0; i< numSeq.Length;i++)
 		{
 			numSeq[i] = Int32.Parse(seperated[i]);
 			totalsum +=numSeq[i];
 		}
 		Console.WriteLine("The length of a sub-int-string: (must less than or equal to the whole length.)");
 		int lenth = Int32.Parse(Console.ReadLine());
 		Console.WriteLine("The sum of the sub-int-string: (must less than the total sum.)");
 		int sum = Int32.Parse(Console.ReadLine());
 		while(lenth <= numSeq.Length && sum <totalsum)
 		   subStrSumFun(lenth,sum,numSeq);
 		
 	   Console.WriteLine("Sorry, no such sub-int-string exits!");
 		
 	}
 }

- SubString implemented with C# April 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void subStrAdd(int[] arr, int value) {
		int s = 0;
		int e = 0;
		int sum = 0;
		boolean found = false;
		for (int i = 0; i < arr.length; i++) {
			sum += arr[i];
			e = i;
			if (sum > value) {
				sum -= arr[s];
				s += 1;
			}
			if (sum == value) {
				found = true;
				break;
			}
		}
		if (found) {
			System.out.println(value + " is [" + String.valueOf(s + 1) + "-"
					+ String.valueOf(e + 1) + "]");
		} else {
			System.out.println("value is not found in list.");
		}

	}

	public static void main(String[] args) {
		int[] arr = { 1, 7, 6, 3, 5, 8, 9 };
		subStrAdd(arr, 16);
	}

- sm July 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class SubstringAddtion {
           	
	public static void main(String[] args) throws Exception
	{ 
	  int [] arr = {1,7,6,3,5,8,9};
	  int n=16;
	  for(int i=0,j=0;i<arr.length-1;j++,i++)
	  {  
		  String s="";
		  int chk=arr[i];
		  s=s+arr[i];
		  while(i<arr.length-1 && chk < n)
		  {
		  chk =chk+arr[i+1];
		  s= s+arr[i+1];
		   i++;
		  }
		  i=j;
		  if(chk == n)
		  {
			System.out.println(s);
		    break;
		  }
	  }
    System.out.println("Substring not found");	       
	     
	}
}

- Kanha August 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class SubStringAddition {
	
	public static void findSubStringAddition(int[] arr, int value){
		for(int i=0;i<arr.length;i++){
			int sum=0;
			for(int j=i;j<arr.length;j++){
				sum+=arr[j];
				if(sum==value){
					print(arr, i, j);
				}
			}
		}
	}
	
	public static void print(int[] arr, int st, int end){
		for(int i=st;i<=end;i++){
			System.out.print(arr[i]+" ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		int [] arr =  {1, 7 ,6 ,3, 5, 8, 9 };
		findSubStringAddition(arr, 16);
	}
}

- supermonk247 September 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void add(int[] nums, int sum) {
		int begin = 0, next = 0, currSum = 0;
		List<Integer> res = new LinkedList<Integer>();
		System.out.println(nums.toString());
		do {
			currSum += nums[next];
			res.add(nums[next]);

			if (currSum > sum) {
				begin++;
				next = begin;
				currSum = 0;
				res.clear();
			} else if (currSum < sum) {
				next++;
			} else {
				if (begin == next)
					System.out.println(begin);
				else
					System.out.println("(" + begin + "-" + next + ")");
			}
		} while (begin < nums.length - 1 && next < nums.length);
	}

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

public class SumSubSequence
{
	public static String getSumSubSequence(int[] list, int sum)
	{
		for (int i = 0; i < list.length; i++)
		{
			int currentSum = 0;
			int j = i;
			for (; j < list.length; j++)
			{
				currentSum += list[j];

				if (currentSum == sum)
					return "(" + i + "," + j + ")";
				else if (currentSum > sum)
					break;
			}
			if (j == list.length)
				return "Not Found";
		}
		return "Not Found";
	}

	public static void main(String[] args)
	{
		int[] seq = { 1, 7, 6, 3, 5, 8, 9 };
		System.out.println(getSumSubSequence(seq, 9));
	}
}

- Mahmoud El-Maghraby June 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class subStringAddition {

public static void main(String args[])
{
int[] array = {1, 7, 6, 3, 5, 8, 9 };
int expectedSum = 8;
int dig = 0;
int sum = 0;

for (int i = dig; i < array.length; i++) {

sum = sum + array[i];
if(sum > expectedSum){
i=dig++;
sum = 0;
continue;
}

if(sum == expectedSum){
System.out.println("Set found at : " + (dig+1) + "--" + (i+1));
}
}
}
}

- Anonymous October 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Test
{
    internal class SubstringAddition
    {
        public static void Main(string[] args) {
            string[] numbers = Console.ReadLine().Trim().Split(" ");
            int sum = Convert.ToInt32(Console.ReadLine().Trim());

            string result = Total(numbers, sum);

            Console.WriteLine(result);
        }

        public static string Total(string[] numbers, int sum) {

            int total = 0;
            int lowerBoundIdx = 0;
            for (int i = 0; i < numbers.Length - 1; i++) {
                total += Convert.ToInt32(numbers[i]);
                if (total == sum)
                {
                    return "(" + Convert.ToString(lowerBoundIdx + 1) + "-" + Convert.ToString(i + 1) + ")";
                }

                if (total > sum) {
                    total = total - Convert.ToInt32(numbers[lowerBoundIdx]);
                    lowerBoundIdx ++;
                    if (total == sum)
                    {
                        return "(" + Convert.ToString(lowerBoundIdx + 1) + "-" + Convert.ToString(i + 1) + ")";
                    }
                }
            }
            return "(not found)";
        }
    }
}

- monika.leslivania January 03, 2023 | 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