Ebay Interview Question
Software Engineer / DevelopersTeam: Traffic
Country: United States
Interview Type: In-Person
public static void main(String[] args) {
String seq = "123456789";
findSum(seq, 100,"");
}
private static void findSum(String seq,int currSum, String finalSeq) {
if(seq.length() == 0) {
if(currSum == 0) {
System.out.println("Found!"+finalSeq);
}
return;
}
for(int i = 1; i <= seq.length();i++) {
String subsequence = seq.substring(0, i);
int number = Integer.parseInt(subsequence);
findSum(seq.substring(i),currSum - number, subsequence +"+"+finalSeq );
findSum(seq.substring(i), number- currSum, subsequence +"-"+finalSeq );
}
}
Algorithm - Using backtracking
startIndex - current index/digit being processed
curSum - sum after startIndex elements have been processed
combo - String to store the combination so far
lastNumber - number that was added(or subtracted) in the last iteration
Input : - startIndex, curSum, reqSum,combo,lastNumber
1. If all numbers have been parsed and sum is reached, return the found combination.
2. If all number have been parsed and sum has not been reached, return null.
3. Let x = nextDigit
4. Case '+x' - >
4.1 update the sum so far; sum = sum + x
4.2 increment Index - startIndex++
4.3 Record next step; combo.append + "+" + x
4.4 Call recursively for nextIndex, with previousNum = +x (used in Step 6 and Step 7)
4.5 If previous call returned non-null, it means combo was found, return it
4.6 If previous call returned null, move to next case
5. Case '-x' -> Similar to case '+x', simply flip the sign
<Step 6 and 7 are applicable only if startIndex is not the first digit i:e lastNum exists>
6. Combine with previous digit and add(previous digit was +ve)
6.1 Increment index
6.2 decrement sum by previousNum
6.3 Combine previous Num with current digit - newNum = prevNum*10 + x
6.4 Update Sum; sum += newNum
6.5 Call recursively for nextIndex, with previousNum = newNum
6.6 If previous call returned non-null, it means combo was found, return it
6.7 If previous call returned null, move to next case
7. Nothing worked return null.
public class SumZero
{
public static void main(String args[])
{
int inp[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int sum = 100;
String combo = "";
combo = findCombo(inp, 1, inp[0], sum, "" + inp[0], inp[0]);
if (combo != null)
{
System.out.println("Required combo -> " + combo);
} else
{
System.out.println("No combo found");
}
}
private static String findCombo(int arr[], int startIndex, int curSum, int reqSum, String output, int lastNumber)
{
if (startIndex == 8)
{
//Uncomment this to print all the combination that are being explored
//System.out.println(output);
}
if (startIndex == arr.length - 1 && curSum == reqSum)
{
return output; // result found
}
if (startIndex == arr.length - 1 && curSum != reqSum)
{
return null;
}
//case 1 - single digit
// case 1.1 add
String result = findCombo(arr, startIndex + 1, curSum + arr[startIndex], reqSum, output + "+" + arr[startIndex], arr[startIndex]);
if (result != null)
{
return result;
}
//case 1.2 subtract Single
result = findCombo(arr, startIndex + 1, curSum - arr[startIndex], reqSum, output + "-" + arr[startIndex], -arr[startIndex]);
if (result != null)
{
return result;
}
// case2 combines digit with previous number, only valid if previous number exists
if (startIndex > 0)
{
// if the last added number was +ve
if (lastNumber > 0)
{
int newSum = curSum - lastNumber;
int newLastNumber = lastNumber * 10 + arr[startIndex];
newSum += newLastNumber;
result = findCombo(arr, startIndex + 1, newSum, reqSum, output + arr[startIndex], newLastNumber);
if (result != null)
{
return result;
}
}
// if the last added number was +ve
else if (lastNumber < 0)
{
int newLastNumber = Math.abs(lastNumber);
int newSum = curSum + newLastNumber;
newLastNumber = newLastNumber * 10 + arr[startIndex];
newSum -= newLastNumber;
result = findCombo(arr, startIndex + 1, newSum, reqSum, output + arr[startIndex], -newLastNumber);
if (result != null)
{
return result;
}
}
}
return null;
}
}
Javascript code follows. It is a straightforward recursive algo.
var findSequences = function(str, total) {
var recurse = function(string, remaining, result) {
if(string == '') {
if(remaining == 0) {
console.log(result);
}
return;
}
var i, tmp;
for(i = 1; i <= string.length; i++) {
tmp = parseInt(string.substr(0, i));
recurse(string.substr(i), remaining - tmp, result + '+' + tmp);
recurse(string.substr(i), remaining + tmp, result + '-' + tmp);
}
};
recurse(str, total, '');
};
findSequences('123456789', 100);
Hi. Your code contained a little mistake. The corrected code (in Java) is here:
package onpaper.tests01;
public class StringParser01 {
static void recurse (String string, Integer remaining, String result) {
//System.out.println("in recurse: " + string +" : " + remaining + " result so far: " + result );
if(remaining == 0) {
System.out.println(result);
}
if(string == "") {
return;
}
int i, tmp;
for(i = 1; i <= string.length(); i++) {
tmp = Integer.parseInt(string.substring(0, i));
recurse(string.substring(i), remaining - tmp, result + '+' + tmp);
recurse(string.substring(i), remaining + tmp, result + '-' + tmp);
}
}
static void findSequences (String str, Integer total) {
recurse(str, total, "");
}
public static void main(String[] args) {
findSequences("123456789", 100);
}
}
import java.util.ArrayList;
import java.util.List;
public class PlusMinus {
public static void main(String[] args) {
List<Integer> arr = getPlusMinus(100);
for(int i : arr)
System.out.print(i+" ");
}
static List<Integer> getPlusMinus(int sum) {
List<Integer> list = new ArrayList<Integer>();
int i=1 ;
int s = 0;
boolean flag = false;
while(s!=sum) {
if(s+i==sum) {
list.add(i);
break;
}
if(s+i>sum)
flag = true;
if(flag)
i*=-1;
list.add(i);
s+=i;
if(flag) {
if(i<1)
--i;
else
++i;
}
else
i++;
}
return list;
}
}
- greenwizard April 19, 2014