146 lines
4.4 KiB
Markdown
146 lines
4.4 KiB
Markdown
# Challenge
|
|
|
|
Technical challenge for an interview at [Credimi S.p.A.](https://www.credimi.com/)
|
|
|
|
Suppose you're given a file with a single string of comma separated numbers like the following
|
|
|
|
```shell
|
|
$ cat input
|
|
123,456,789
|
|
```
|
|
|
|
Your program must print to STDOUT all possible permutations with repetitions, like follows (actual order is not
|
|
relevant)
|
|
|
|
```shell
|
|
$ 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](https://en.wikipedia.org/wiki/Heap%27s_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](https://www.codeproject.com/Articles/1250925/Permutations-Fast-implementations-and-a-new-indexi)).
|
|
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:
|
|
|
|
```shell
|
|
$ 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
|
|
|
|
```shell
|
|
mvn package
|
|
```
|
|
|
|
The jar file will be in `target/permutations.jar`.
|
|
|
|
Otherwise, you can use the provided Dockerfile
|
|
|
|
```shell
|
|
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
|
|
|
|
```shell
|
|
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
|
|
|
|
```shell
|
|
docker create --name permutations permutations
|
|
docker cp permutations:/app/permutations.jar .
|
|
```
|
|
|
|
Then run it with locally installed JRE (11+)
|
|
|
|
```shell
|
|
echo 1,2,3 | java -jar permutations.jar
|
|
```
|