# Posts

• ## Leetcode: Maximum product subarray

Given an array `nums` with integer values `-10 <= x <= 10`, calculate the maximum consecutive product. For example, the array `[2,3,-1,4]` produces the maximum product `6` because `2*3=6`. The first obsveration that we can make is that whenever a `0` is encountered, it sets the whole product to `0`. This means, if a `0` is somewhere in the middle of the array, we need to look at the left and right part individually because they cannot be connected. Secondly, an odd amount of negative numbers makes the whole product negative. Having `2`, `4,`, `6`, … negative numbers will keep the product at the same amount (if all of them are `-1`) or increase it. Finally, since those numbers are all integers, the longer the chain of multiplied numbers, the higher to outcome.

• ## Leetcode: Sort list

Given a single linked list, sort the values in ascending order.

• ## Leetcode: Gas station

Given two arrays, `gas` and `cost` and an infinite tank, it costs `costs[i]` to go from one index to the other. The most a car can get gas is `gas[i]`. The task is to determine whether a car can go a full round for any possible starting point. The program should return the starting index if it is possible and `-1` if it is not possible to do so. Example:

The result is `2`, because we can start from index `2`, get `2` units of gas, and it costs us `1` unit to go to `1`, leaving us with `1` unit. Then we can get another unit which is exactly the required `2` units it takes us to get to `1` and from there we get `1` leaving us with `0` at `2` and completing the cycle.

• ## Leetcode: LRU cache

Given the following code skeleton, implement an LRU cache with a variable capacity. The time complexity for `get` and `put` should be `O(1)` respectively.

In general, a cache is just a map which assigns keys to values. What makes a cache special is that values get evicted. This can be either after a certain time or when values are not used. In the case of an LRU cache, the least recently used element should be deleted once a cache reaches its predefined capacity.

• ## Leetcode: Merge sorted array

Given two lists or arrays, `nums1` and `nums2` as well as two integers `m` and `n` which give the length of the arrays `nums1` and `nums2` respectively. `nums1` should be modified in place. The first idea that came to my mind was a merge-sort. Given that those initial arrays are already sorted, I could have two pointers and iterate over both arrays simulatenously, copying the values into a third one. The problem here is that the array should be modified in place. The way to achieve this in `O(2(n+m)) => O(n+m)` is to iterate over the temporary array and write it back to the initial array.

Page: 8 of 28