Friedrich Ewald My Personal Website

Posts


  • 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:

    gas =  [1,1,2]
    cost = [2,1,1]
    # result: 2
    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.

    Continue reading

  • 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.

    class LRUCache:
      def __init__(self, capacity: int):
        pass
    
      def get(self, key: int) -> int:
        pass
    
      def put(self, key: int, value: int) -> None:
        pass
    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.

    Continue reading

  • 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.

    Continue reading

  • Leetcode: Word search

    Given a two-dimensional array with english upper- and lowercase letters, named board and a word, return True if the word appears on the board and false if not. We can go up, down, left, and right but not diagonal. Letters cannot be used twice. When looking at this problem, it helps to imagine the board as a tree. Every letter is a potential root of the tree, depending if it is equal to the start of the word that we are looking for. This allows us to apply a slightly modified version of the breadth-first-search algorightm (BFS).

    Continue reading

  • Leetcode: Unique paths

    Given an m * n grid, we start in the top left corner at position (1,1). We want to move to the bottom right corner with either right or down steps. How many different combinations of right and down are there for a given grid of size m * n? We need to find an algorithm that works on arbitrarily large grids. Given this example grid of (2,3):

    +---+---+---+
    | S |   |   |    S = Start
    +---+---+---+
    |   |   | F |    F = Finish
    +---+---+---+
    There are 3 different ways from start to finish:
    • Down, Right Right
    • Right, Down, Right
    • Right, Right, Down
    To simplify this problem, we can think of a down move as 1 and of a right move as 0. This shows us, that we can either do 100, 010, or 001. We observe that the one is in every position. Now, two different down moves are identical, hence there are less than 2^n solutions. If we think of this problem as a backtracking problem, we can come up with a recursive algorithm. At the first position we can go either down or right. Depending on which way we go, we have to shrink the field either on the x or y-axis. We then add the result of going right to the result of going down. This step is repeated until we can only go down or right in which case we can return 1.

    Continue reading

Page: 7 of 27