7
\$\begingroup\$

I was asked this question in an interview:

Given a string s consisting of 0, 1 and ?. The question mark can be either 0 or 1. Find all possible combinations for the string.

I came up with below code but I wanted to know whether it is the best way to solve the problem?

  public static void main(String[] args) {
    List<String> output = new ArrayList<>();
    addCombinations("0?1?", 0, output);
    System.out.println(output);
  }

  private static void addCombinations(String input, int index, List<String> output) {
    for (int i = index; i < input.length(); ++i) {
      if (input.charAt(i) == '?') {
        addCombinations(input.substring(0, i) + "0" + input.substring(i + 1), i + 1, output);
        addCombinations(input.substring(0, i) + "1" + input.substring(i + 1), i + 1, output);
        return;
      }
    }
    output.add(input);
  }
\$\endgroup\$
  • \$\begingroup\$ Could you maybe add an example of the expected output? I'm pretty sure I understand it but I think it wouldn't hurt your post. \$\endgroup\$ – IEatBagels Jul 5 at 13:36
4
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

For an interview setting, I think the code presented to be a very decent initial solution but for the lack of comments:
it is easy to read (and consequently should be easy to maintain).

It invites a question if there is any (semi-obvious) way to reduce machine resources used.

(AJNeufeld is entirely right about StringBuilder vs StringBuffer - leaving it as is as a reminder not to present code in an answer without consulting an IDE.)
Only then I'd be inclined to suggest passing a StringBuffer as Java does almost all String manipulation using one using setCharAt(int, char) - this also removes most of the code replication (expression, really) I'd pick as a nit.

    if (pattern.charAt(i) == '?') {
        // collect solutions for same problem with one '?' less
        StringBuffer atEntry = new StringBuffer(pattern);
        pattern.setCharAt(i, '0');
        addCombinations(pattern, i + 1, output);
        atEntry.setCharAt(i, '1');
        addCombinations(atEntry, i + 1, output);
        return;
    }
}
output.add(pattern.toString());

But this not only calls addCombinations() for strings without wild cards, it instantiates as many StringBuffers needlessly as there are combinations. With a slightly modified interface:

    addCombinations(pattern, pattern.indexOf('?'), output);
…
/** Appends to <code>output</code> all combinations replacing the
 * character at <code>wildAt</code> and every <code>'?'</code>
 * to the end of <code>pattern</code> with <code>'0'</code> and
 * <code>'1'</code>. */
private static void
addCombinations(String pattern, int wildAt, List<String> output) {
    int next = pattern.indexOf('?', wildAt);
    StringBuffer modifyable = new StringBuffer(pattern);
    for (char digit = '0' ; digit <= '1' ; digit++) {
        modifyable.setCharAt(wildAt, digit);
        String modified = modifyable.toString();
        if (next < 0)
            output.add(modified);
        else
            addCombinations(modified, next, output);
    }
}
\$\endgroup\$
  • \$\begingroup\$ (As a further "improvement", one could try and identify runs of ? and replace them by zero-padded binary representations of a counter value from an appropriate range.) \$\endgroup\$ – greybeard Jul 4 at 7:13
  • \$\begingroup\$ (I knew there was something odd not cloning pattern. It has been plain wrong.) \$\endgroup\$ – greybeard Jul 4 at 9:06
2
\$\begingroup\$

Managing memory requirements

Did you get the method signature from the interviewer? If not, it could use some improvement. Consider Joop Eggen's answer and the worst case scenario, where there are 2^63 different combinations. While his approach is likely the most efficient computationally, the method signature limits the operation to calculating everything before the results can be examined. It requires storage of 5.81e+20 characters in memory (what's that... 581 exabytes?)

Instead of passing a collection to which the results are collected, pass a consumer so that the caller has a control over how the results are stored and processed. Taking AJNeufeld's solution, as it has already a bit improved method signatures:

public static void combinations(String input, Consumer<String> consumer) {
    StringBuilder workspace = new StringBuilder(input);
    addCombinations(workspace, consumer);
}

private static void addCombination(StringBuilder workspace,
    Consumer<String> consumer) {

    ...
    } else {
        consumer.accept(workspace.toString());
    }
}

This way, if the caller is only intersted in one specific result, it can, for example, throw an unchecked exception from the consumer as soon as the correct one has been found to make the algorithm stop.

\$\endgroup\$
  • 1
    \$\begingroup\$ This! Always check the requirements with the interviewer. What does 'Find all' mean? Print? A total list? Iterator? etc. Are the memory / cpu / execution contraints? etc. \$\endgroup\$ – RobAu Jul 5 at 11:49
1
\$\begingroup\$

Such a problem is also looking whether the interviewed has a nice logic filtering, simplifying things.

Now the problem actually only varies for the question marks. So:

void allCombinations(String pattern) {
    if (!pattern.matches("[01\\?]+") {
        throw new IllegalArgumentException("Invalid pattern: " + pattern);
    }
    int questionMarks = pattern.replaceAll("[^\\?]", "").length();
    if (questionMarks == 0) {
        System.out.println(pattern);
        return;
    }
    if (questionMarks > 63) {
        throw new IllegalArgumentException("Limited to 63 question marks: 2^63 combinations.");
    }
    long n = 1L << questionMarks; // Number of combinations.
    ...
    for (long i = 0; i < n; ++i) {
        // The bits of i[0 .. questionMarks-1] should fill in the pattern's qm's.
        ...
    }
}

The real work, its optimal programming I leave to your creativity.

The important thing is not to overcomplicate the combinating algorithm, a counter upto 2^questionMarks (java: 1 << questionMarks) suffices here.

Your solution loop + recursion is not that adequate, and seeing that this problem delivers O(2n) I would not be entirely satisfied.

Also one should consider how to deliver the result: a List<String> is immensive. An iterator like function would be better. Explained.


One implementation

As the work to do was still not entirely trivial:

    long n = 1L << questionMarks; // Number of combinations.
    ...
    char[] chars = pattern.toCharArray();
    int[] qmIndices = new int[questionMarks];
    int qmII = 0;
    for (int j = 0; qmII < questionMarks && j < chars.length; ++i) {
        if (chars[j] == '?') {
            qmIndices[qmII++] = j;
        }
    }
    for (long i = 0; i < n; ++i) {
        // The bits of i[0 .. questionMarks-1] should fill in the pattern's qm's.
        int bits = i;
        for (int j = 0; j < questionMarks; ++j) {
            chars[qmIndices[j]] = (char)('0' + (bits & 1));
            bits >>= 1;
        }
        System.out.println(new String(chars));
    }
\$\endgroup\$
  • \$\begingroup\$ Thanks for your suggestion. So basically we are getting total number of combinations we need to make and then in the for loop we need to execute it. I am now confuse how should I write things in the for loop so that we can get all the combinations. \$\endgroup\$ – user5447339 Jul 5 at 4:58
  • \$\begingroup\$ I'll write some simple (=not optimal) code. \$\endgroup\$ – Joop Eggen Jul 5 at 9:34
  • \$\begingroup\$ There is no requirement that limits the number of questionmarks, so why whould you build/implement this? Neither is this needed. You can either recursivly or dynamically fill all questionsmarks, without needing to limit input size. \$\endgroup\$ – RobAu Jul 5 at 11:06
  • \$\begingroup\$ @RobAu With N = number of question marks, you get 2^N combinations. Using a long for 63/64 bits seems sufficient (2^63 results), but one could do more bits. However the application would run very long, and one could no longer keep the data in memory: array lengths and List sizes are just ints. Just in this case an input validation would prevent probably unwanted/undeliverable behavior. \$\endgroup\$ – Joop Eggen Jul 5 at 12:03
  • \$\begingroup\$ There is also no requirement to keep it all in memory. Nor are there runtime-limitations. \$\endgroup\$ – RobAu Jul 5 at 12:05
1
\$\begingroup\$

Requirements

It all depends on what you think is 'best'. The code that can be implemented in as little time as possible? The most efficient code? In terms of memory? CPU?

The solution below doesn't do any input checking, but instead is an approach that would be rather fast and very memory efficient

Return type

I prefer a solution that has an Iterator or Stream and uses as less memory as needed.

State

The problem is that you have to keep state of all the ? you replace. This screams for a BitSet.

Basically, the solution keeps replacing all the ? with bits in the current BitSet. For each iteration, determine the next BitSet and create a new String with the 0 and 1 in the correct places.

Lets see:

input  n'th iteration   bitset   output
---------------------------------------
01?0?   0               00       01000
01?0?   1               01       01001
01?0?   2               10       01100
01?0?   3               11       01101

This is very memory efficient, as you only need 2 bits of state. Also efficient in terms of operations, as you build a String on the go, and never use slow String manipulation.

Reuse

Unfortunately, Java does not offer a FixedBitSet or a next() method on BitSet, so you'd have to implement it yourself

Solution

package org.robau;

import java.util.BitSet;
import java.util.Iterator;
import java.util.stream.IntStream;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

public class Strings {

    public static void main(String[] args) {

        Iterable<String> iterable = () -> getAllCominations("0??0?1");
        Stream<String> s = StreamSupport.stream(iterable.spliterator(), false);
        s.forEach(System.out::println);
    }

    // Given a string s consisting of 0, 1 and ?. The question mark can be either 0
    // or 1. Find all possible combinations for the string.
    static Iterator<String> getAllCominations(String s) {

        // Create a bitset the size of "the number of '?' in S" + 1 for         
        int nbits = (int) s.chars().filter(ch -> ch == '?').count() + 1; 

        FixedBitSet sbs = new FixedBitSet(nbits);
        char[] input = s.toCharArray();

        return new Iterator<String>() {

            @Override
            public boolean hasNext() {

                boolean isDone = sbs.get(sbs.getSize()-1); 
                //We don't have a next() if we have the overflowbit set
                return !isDone;
            }

            @Override
            public String next() {

                String s = mergeWithInput(sbs);
                sbs.next();
                return s;
            }

            private String mergeWithInput(FixedBitSet sbs) {
                int bitSetIndex =0;
                StringBuilder sb = new StringBuilder(input.length);
                for (int i = 0; i < s.length(); i++) {
                    if (s.charAt(i) == '?') {
                        sb.append(sbs.get(bitSetIndex)? '1': '0');
                        bitSetIndex++;
                    }
                    else
                    {
                        sb.append(s.charAt(i));
                    }
                }
                return sb.toString();
            }

        };
    }

    static class FixedBitSet extends BitSet {
        private int size;

        public FixedBitSet(int nbits) {
            super(nbits);
            this.size = nbits;
        }

        public int getSize() {
            return size;
        }

        public void next() {

            boolean carry = true;
            for (int i = 0; i < size; i++) {

                if (carry && !get(i)) {
                    flip(i);
                    return;
                } else if (carry && get(i)) {
                    flip(i); // keep carrying
                } else if (!carry && !get(i)) {
                    //done
                    return;
                } else {
                    //keep carry, take to next bit
                }
            }
        }

            @Override
        public String toString() {
            final StringBuilder buffer = new StringBuilder(size);
            IntStream.range(0, size).mapToObj(i -> get(i) ? '1' : '0').forEach(buffer::append);
            return buffer.toString();
        }

    }




}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.