|
15 | 15 | 11. binarySearch() |
16 | 16 | 12. bruteForceSearch() |
17 | 17 |
|
| 18 | +## Code Examples |
| 19 | +We are asked in exercise (1.1.19) to improve the fib method to use some sort of cache. This one is particularly interesting because it runs in O(1) time provided that the cache contains the previous two sequences. Generating the previous sequences is done using loops. |
| 20 | +```java |
| 21 | + // dynamic programming and memoization |
| 22 | + public static long FastFib(int N, HashMap<Integer, Long> cache) { |
| 23 | + if (N == 0) { |
| 24 | + cache.put(N, 0L); |
| 25 | + return 0; |
| 26 | + } |
| 27 | + |
| 28 | + if (N == 1) { |
| 29 | + cache.put(N, 1L); |
| 30 | + return 1; |
| 31 | + } |
| 32 | + |
| 33 | + cache.put(N, cache.get(N - 2) + cache.get(N - 1)); |
| 34 | + return cache.get(N); |
| 35 | + } |
| 36 | +``` |
| 37 | + |
18 | 38 | ## Python Implementation |
19 | 39 | I've implemented the same methods but in Python over [here](https://github.com/dev-xero/python-algorithms-exercise-practice), if you're interested. |
0 commit comments