README.md 1.55 KB
Newer Older
Sondre.Bolland1's avatar
Sondre.Bolland1 committed
1
2
3
4
# Lab1 - Find Triplicate
Given a list of elements find an element that occurs (at least) three times.
For instance:
`[6, 81, 5, 2, 5, 10, 0, 23, 5]`
Sondre Bolland's avatar
Sondre Bolland committed
5
This list contains the triplicate: `5`.
Sondre.Bolland1's avatar
Sondre.Bolland1 committed
6
7

The code currently includes a benchmark algorithm for doing this:
Sondre Bolland's avatar
Sondre Bolland committed
8
**TriplicateBruteForce**
Sondre.Bolland1's avatar
Sondre.Bolland1 committed
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  * Simple solution: Triple for-loop (brute force)
  * Time Complexity: O(n<sup>3</sup>)

**TODO: Write a better/faster algorithm.**

## Task
Implement the ``ITriplicate`` interface. 
```java
public class MyTriplicate<T> implements ITriplicate<T> {

    @Override
    public T findTriplicate(List<T> list) {
        // Implement me :)
        return null;
    }
    
}
```
Write an algorithm which performs better than `TriplicateBruteForce`.
The algorithm must be functionally correct as well as faster than `TriplicateBruteForce`. Run `TriplicateTest` to check both requirements.

To see the empirical runtime of your solution add your algorithm/class to the list of algorithms/classes in `Main::main`. Run `Main` to see how fast (or slow) your solution is compared to `TriplicateBruteForce`. 

Sondre Bolland's avatar
Sondre Bolland committed
32
What time complexity does your algorithm have? Can you improve your time/write an even better algorithm?
Sondre.Bolland1's avatar
Sondre.Bolland1 committed
33
34
35
36
37
38
39
40
41
42
43
44


## Expected output
```
---Generating Integer Lists---
10 lists generated with 10 000 elements each.

---Processing Algorithms---
TriplicateBruteForce        | time elapsed: 2826194217 microseconds (2826,194217 seconds)
MyTriplicate                | time elapsed: ?????????? microseconds (??????????? seconds)
```

Sondre Bolland's avatar
Sondre Bolland committed
45
✅ The lab is passed when you have submited on Codegrade and all the tests there pass.