Usability
Your addCombinations(String input, int index, List<String> output) is harder to use than necessary. The user must:
- create the storage for the result
- pass in a mysterious
0 value
It would be better to add a "helper" function, to do these tasks for the user:
public static void main(String[] args) {
List<String> output = combinations("0?1?");
System.out.println(output);
}
public static List<String> combinations(String input) {
List<String> output = new ArrayList<>();
addCombinations(input, 0, output);
return output;
}
Flexibility
Will '?' always be the replacement target? Will the replacements only be the characters '0' and '1'? It wasn't asked by the interviewer, but you could make the function more flexible. Or at least mention the possibility to the interviewer.
Code Style
This screams "hacky":
for (int i = index; i < input.length(); ++i) {
if (input.charAt(i) == '?') {
// Do work
return;
}
}
output.add(input);
You are looping ... but only execute the "real" body of the loop exactly once -- and return if you do -- and if you get to the end without doing work, you do some different work. As an interviewer, unless you've impressed me elsewhere, I'd be moving on to the next candidate.
What you are doing - what you intend to do - is find the first '?', replace that with '0' and '1', and recursing to find other occurrences for replacement. Make that clearer.
int position = input.indexOf('?', index);
if (position >= 0) {
addCombinations( ... );
addCombinations( ... );
} else {
output.add(input);
}
You've got two cases: found and not found. Recursive and leaf. No embedded return. Pretty clear.
Premature Optimization?
You've got an optimization which may be unnecessary. You pass in index to indicate where to start searching for the next '?'. But you've replaced the '?', so if you omitted this, and simply started searching from the start of the string, it would still work. Yes, you will be doing some unnecessary searching of the beginning of the string over and over again, but you've also removed passing the extra argument on the stack, which complicates the addCombinations(...) call.
To be fair, I've used String.indexOf() to do the searching, which is very fast, where as your code did the search itself, with a loop, a String.charAt() and a comparison, which would be significantly slower, so the optimization definitely makes sense in the original code.
The Better Way
As metioned by @greybeard, StringBuffer.setCharAt() would be much simpler to the string manipulation currently being done. But it is still the wrong choice. StringBuilder.setCharAt() is what you want. (StringBuilder is StringBuffer, but without the synchronization overhead).
Instead of creating and throwing away multiple StringBuilder objects, it would be possible to reuse one StringBuilder object for all recursive calls. Create the StringBuilder in the helper method I introduced, and pass it (instead of input) into the addCombinations() method. When a ? is found, replace it with a 0 and recurse, then a 1 and recurse, and then change it back to a ? before returning to ensure subsequent processing still works.
public static List<String> combinations(String input) {
StringBuilder workspace = new StringBuilder(input);
List<String> output = new ArrayList<>();
addCombinations(workspace, output);
return output;
}
private static void addCombination(StringBuilder workspace, List<String> output) {
int position = workspace.indexOf('?');
if (position >= 0) {
workspace.setCharAt(position, '0');
addCombination(workspace, output);
workspace.setCharAt(position, '1');
addCombination(workspace, output);
workspace.setCharAt(position, '?');
} else {
output.add(workspace.toString());
}
}
There is still a lot of repeated work going on. With 4 question marks, the first question mark is found once, the second is found twice, the third is found 4 times, and the fourth is found 8 times. You could count the number of question marks, create an int positions[] array, and locate all the question marks only once. You could also create an int state[] array, and use that to turn the recursion into a loop. Finally, once each execution of the loop generates one new combination, you could extract the body of the loop into its own Supplier<String>, and use Stream::generate(Supplier<? extends T>) to create a stream of combinations on demand, instead of filling in a list, but we've ran way beyond reasonable expectations for an interview question.
