|Fabio Salvini a98226dc50||2 years ago|
|src||2 years ago|
|.gitignore||2 years ago|
|Dockerfile||2 years ago|
|README.md||2 years ago|
|pom.xml||2 years ago|
Technical challenge for an interview at Credimi S.p.A.
Suppose you're given a file with a single string of comma separated numbers like the following
$ cat input 123,456,789
Your program must print to STDOUT all possible permutations with repetitions, like follows (actual order is not relevant)
$ cat input | <your program> > output $ cat output 123,456,789 123,789,456 456,789,123 456,123,789 789,123,456 789,456,123
Your solution must print to STDOUT and any extraneous output will be considered an error (but you may print to STDERR at your convenience). Your program will be tested against inputs of growing size, the more they can take, the better!
The solution must contain documentation explaining time and space complexity of your implementation.
You should use only the standard library of your language of choice, any additional requirement should be documented and motivated.
Java, Python, Scala or Rust are preferred.
The challenge description contains an error.
It asks to print all possible permutations WITH repetitions, but the example shows the permutations without repetition.
If we consider permutations with repetitions, we would also need an additional parameter that is the desired length of the permutation. The typo is probably "with repetition" instead of "without repetition".
The most efficient algorithm to compute all permutations is
It minimizes elements swapping: every permutation is generated interchanging a single pair of elements from the previous one.
Heap algorithm cannot be parallelized, we could use a less efficient algorithm with better average time assuming thread
count > 1 (see for example
However, the bottleneck of our program is the writing to stdout, in some tests I saw that the multi-threaded version is actually slower, because threads need to synchronize to write to the output.
The challenge description does not specify the type of the input elements, they are just "numbers".
I decided to represent them with the Java primitive type
There is no noticeable performance improvement representing them with an
It's not specified what is the desired output if a number is repeated.
I've decided to not check for duplicate elements, since they affect the algorithm time and space complexity.
If one or more numbers is repeated, some permutations will be duplicated:
$ echo "1,1" | <my program> 1,1 1,1
I wrote the project in Java because it's the language where I have more experience.
It's a maven project that targets JDK11+.
Time and space complexity
Given n elements, there are n! permutations. Heap's algorithm compute a new permutation in
O(1) time. Each permutation
of n elements must also be printed to the stdout (
Time complexity is
The program uses two
n sized arrays and a fixed buffer. Space complexity is
I divided the program into three classes:
ElementsInputReader: to read the input elements.
PermutationsGenerator: to compute all the elements permutations.
PermutationsPrinter: to print permutations to the output.
I didn't use generics to compute permutations of an array
T because the program performance would be a lot worse
than using primitive types.
How to run the application
If you have JDK11+ and Maven installed, you can simply run
The jar file will be in
Otherwise, you can use the provided Dockerfile
docker build -t permutations .
(Maven compilation fails if you had built the project locally, be sure to delete
If you have built the project using Docker, you can simply run it
echo 1,2,3 | docker run --rm -i permutations
However running it with Docker has a big effect on performances.
To extract the jar file, run
docker create --name permutations permutations docker cp permutations:/app/permutations.jar .
Then run it with locally installed JRE (11+)
echo 1,2,3 | java -jar permutations.jar