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 |
README.md
Challenge
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.
Solution
Typo
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".
Algorithm
The most efficient algorithm to compute all permutations is
Heap's Algorithm.
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
Ouellet Indexed).
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.
Choices
Element types
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 long
.
There is no noticeable performance improvement representing them with an int
instead.
Repeated elements
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
Implementation
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 (O(n)
time).
Time complexity is O(n*n!)
.
The program uses two n
sized arrays and a fixed buffer. Space complexity is O(n)
.
Classes
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.
Generics
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
Compilation
If you have JDK11+ and Maven installed, you can simply run
mvn package
The jar file will be in target/permutations.jar
.
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 target
directory).
Run
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