Epic Systems Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
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));
}
}
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;
}
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.
#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;
}
}
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);
}
}
}
}
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?
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";
}
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";
}
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";
}
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;
}
}
}
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.
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
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;
}
}
}
}
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()
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!");
}
}
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);
}
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");
}
}
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);
}
}
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);
}
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));
}
}
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));
}
}
}
}
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)";
}
}
}
- Anonymous October 29, 2013