Ebay Interview Question for Software Engineer / Developers


Team: Traffic
Country: United States
Interview Type: In-Person




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

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

- greenwizard April 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

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

- ssd April 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- MD December 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- shukad333 September 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

123456789

- Anonymous December 09, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

123+4-5+67-89

- hmm January 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You need to come up with an algo here, so that when given a number like 100, you will return the possible combination

- juny January 08, 2014 | 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