Sunday, September 18, 2022

Problem Statement

Design a food rating system that can do the following:

• Modify the rating of a food item listed in the system.
• Return the highest-rated food item for a type of cuisine in the system.

Implement the `FoodRatings` class:

• `FoodRatings(String[] foods, String[] cuisines, int[] ratings)` Initializes the system. The food items are described by `foods`, `cuisines` and `ratings`, all of which have a length of `n`.
• `foods[i]` is the name of the `ith` food,
• `cuisines[i]` is the type of cuisine of the `ith` food, and
• `ratings[i]` is the initial rating of the `ith` food.
• `void changeRating(String food, int newRating)` Changes the rating of the food item with the name `food`.
• `String highestRated(String cuisine)` Returns the name of the food item that has the highest rating for the given type of `cuisine`. If there is a tie, return the item with the lexicographically smaller name.

Note that a string `x` is lexicographically smaller than string `y` if `x` comes before `y` in dictionary order, that is, either `x` is a prefix of `y`, or if `i` is the first position such that `x[i] != y[i]`, then `x[i]` comes before `y[i]` in alphabetic order.

Example 1:

```Input
["FoodRatings", "highestRated", "highestRated", "changeRating", "highestRated", "changeRating", "highestRated"]
[[["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]], ["korean"], ["japanese"], ["sushi", 16], ["japanese"], ["ramen", 16], ["japanese"]]
Output
[null, "kimchi", "ramen", null, "sushi", null, "ramen"]

Explanation
FoodRatings foodRatings = new FoodRatings(["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]);
foodRatings.highestRated("korean"); // return "kimchi"
// "kimchi" is the highest rated korean food with a rating of 9.
foodRatings.highestRated("japanese"); // return "ramen"
// "ramen" is the highest rated japanese food with a rating of 14.
foodRatings.changeRating("sushi", 16); // "sushi" now has a rating of 16.
foodRatings.highestRated("japanese"); // return "sushi"
// "sushi" is the highest rated japanese food with a rating of 16.
foodRatings.changeRating("ramen", 16); // "ramen" now has a rating of 16.
foodRatings.highestRated("japanese"); // return "ramen"
// Both "sushi" and "ramen" have a rating of 16.
// However, "ramen" is lexicographically smaller than "sushi".
```

Constraints:

• `1 <= n <= 2 * 104`
• `n == foods.length == cuisines.length == ratings.length`
• `1 <= foods[i].length, cuisines[i].length <= 10`
• `foods[i]`, `cuisines[i]` consist of lowercase English letters.
• `1 <= ratings[i] <= 108`
• All the strings in `foods` are distinct.
• `food` will be the name of a food item in the system across all calls to `changeRating`.
• `cuisine` will be a type of cuisine of at least one food item in the system across all calls to `highestRated`.
• At most `2 * 104` calls in total will be made to `changeRating` and `highestRated`.

Video Tutorial

You can find the detailed video tutorial here

Thought Process

If we want to optimize highestRated API call (which we should), a max heap would help achieve it with O(1). Some details about implementation.

• Make each food into a class would make code clean, also maintain the order when insert/remove from the max heap through Comparable interface.
• Make sure we have O(1) access to each Food object by maintaining two HashMaps.
• foodIndex, Map<String, Food> -> Key: food name, Value: Food object
• CuisineIndex, Map<String, Queue<Food>>, Key: cuisine name, Value: Max heap on rating
• Follow up thought: if this is a system design question, how would you actually do it? Some read on how Youtube calculates total views.

Solutions

Time Complexity: highestRated: O(1), changeRating: O(N) because we have to remove the object, and in order to find the object in a max heap, it is O(N) scan (even though re-insert is O(lgN)).
Space Complexity: O(N) because we used extra maps linear to food names (which is larger than cuisine names)

Saturday, July 9, 2022

Problem Statement

There is a street with `n * 2` plots, where there are `n` plots on each side of the street. The plots on each side are numbered from `1` to `n`. On each plot, a house can be placed.

Return the number of ways houses can be placed such that no two houses are adjacent to each other on the same side of the street. Since the answer may be very large, return it modulo `109 + 7`.

Note that if a house is placed on the `ith` plot on one side of the street, a house can also be placed on the `ith` plot on the other side of the street.

Example 1:

```Input: n = 1
Output: 4
Explanation:
Possible arrangements:
1. All plots are empty.
2. A house is placed on one side of the street.
3. A house is placed on the other side of the street.
4. Two houses are placed, one on each side of the street.
```

Example 2:

```Input: n = 2
Output: 9
Explanation: The 9 possible arrangements are shown in the diagram above.
```

Constraints:

• `1 <= n <= 104`

Video Tutorial

You can find the detailed video tutorial here

Thought Process

A classic DP problem (Dynamic Programming) because it's either ask you a boolean yes or no questions, Or ask for extreme values, e.g., min, max, or just a number of solutions etc.
• Two sides are independent, each side is similar to Climb Stairs, House Robber  House Robber II
• Given each side is independent, the combo would be multiplied together.
• Implementation wise
• could use two variables to replace the array
• be careful about overflow (use long to cast back to int)

Solutions

Time Complexity: O(N) since going through each number till n
Space Complexity: O(1) if we use two variables to track, the above implementation is O(N) since an extra array is used.

Thursday, June 23, 2022

Problem Statement

You are given a 0-indexed `m x n` integer matrix `grid` consisting of distinct integers from `0` to `m * n - 1`. You can move in this matrix from a cell to any other cell in the next row. That is, if you are in cell `(x, y)` such that `x < m - 1`, you can move to any of the cells `(x + 1, 0)`, `(x + 1, 1)`, ..., `(x + 1, n - 1)`. Note that it is not possible to move from cells in the last row.

Each possible move has a cost given by a 0-indexed 2D array `moveCost` of size `(m * n) x n`, where `moveCost[i][j]` is the cost of moving from a cell with value `i` to a cell in column `j` of the next row. The cost of moving from cells in the last row of `grid` can be ignored.

The cost of a path in `grid` is the sum of all values of cells visited plus the sum of costs of all the moves made. Return the minimum cost of a path that starts from any cell in the first row and ends at any cell in the last row.

Example 1:

```Input: grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]
Output: 17
Explanation: The path with the minimum possible cost is the path 5 -> 0 -> 1.
- The sum of the values of cells visited is 5 + 0 + 1 = 6.
- The cost of moving from 5 to 0 is 3.
- The cost of moving from 0 to 1 is 8.
So the total cost of the path is 6 + 3 + 8 = 17.
```

Example 2:

```Input: grid = [[5,1,2],[4,0,3]], moveCost = [[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]]
Output: 6
Explanation: The path with the minimum possible cost is the path 2 -> 3.
- The sum of the values of cells visited is 2 + 3 = 5.
- The cost of moving from 2 to 3 is 1.
So the total cost of this path is 5 + 1 = 6.
```

Constraints:

• `m == grid.length`
• `n == grid[i].length`
• `2 <= m, n <= 50`
• `grid` consists of distinct integers from `0` to `m * n - 1`.
• `moveCost.length == m * n`
• `moveCost[i].length == n`
• `1 <= moveCost[i][j] <= 100`

Video Tutorial

You can find the detailed video tutorial here

Thought Process

A classic DP problem (Dynamic Programming) because it's either ask you a boolean yes or no questions, Or ask for extreme values, e.g., min, max
• Build up a minCost 2 day array, each array element denotes by far the min cost to reach to that element
• Make sure to initialize the values.

Solutions

Time Complexity: O(N^3) since going through the 2-d array and another nested loop
Space Complexity: O(N^2) used the 2-d minCost array

• None

Monday, February 15, 2021

Problem Statement

Given an array `nums`, return `true` if the array was originally sorted in non-decreasing order, then rotated some number of positions (including zero). Otherwise, return `false`.

There may be duplicates in the original array.

Note: An array `A` rotated by `x` positions results in an array `B` of the same length such that `A[i] == B[(i+x) % A.length]`, where `%` is the modulo operation.

Example 1:

```Input: nums = [3,4,5,1,2]
Output: true
Explanation: [1,2,3,4,5] is the original sorted array.
You can rotate the array by x = 3 positions to begin on the the element of value 3: [3,4,5,1,2].
```

Example 2:

```Input: nums = [2,1,3,4]
Output: false
Explanation: There is no sorted array once rotated that can make nums.
```

Example 3:

```Input: nums = [1,2,3]
Output: true
Explanation: [1,2,3] is the original sorted array.
You can rotate the array by x = 0 positions (i.e. no rotation) to make nums.
```

Example 4:

```Input: nums = [1,1,1]
Output: true
Explanation: [1,1,1] is the original sorted array.
You can rotate any number of positions to make nums.
```

Example 5:

```Input: nums = [2,1]
Output: true
Explanation: [1,2] is the original sorted array.
You can rotate the array by x = 5 positions to begin on the element of value 2: [2,1].
```

Constraints:

• `1 <= nums.length <= 100`
• `1 <= nums[i] <= 100`

Video Tutorial

You can find the detailed video tutorial here

Thought Process

Simple problem, just need to find a pattern
• If always non-decreasing, true
• If it has one decreasing pivot, the last element needs to be less or equal than the first element
• If it has more than one decreasing pivot, false

Solutions

Time Complexity: O(N) since going through the array once
Space Complexity: O(1) no extra space is used

• None

Sunday, August 2, 2020

包子聊天系列：中年大叔程序员疫情之后往哪里跳？

​【有没有觉得乔杉和习大大有那么一丢丢撞脸呀🤣】

Saturday, July 25, 2020

Problem Statement

Given two numbers, `hour` and `minutes`. Return the smaller angle (in degrees) formed between the `hour` and the `minute` hand.

Example 1:

```Input: hour = 12, minutes = 30
Output: 165
```

Example 2:

```Input: hour = 3, minutes = 30
Output: 75
```

Example 3:

```Input: hour = 3, minutes = 15
Output: 7.5
```

Example 4:

```Input: hour = 4, minutes = 50
Output: 155
```

Example 5:

```Input: hour = 12, minutes = 0
Output: 0
```

Constraints:

• `1 <= hour <= 12`
• `0 <= minutes <= 59`
• Answers within `10^-5` of the actual value will be accepted as correct.

Video Tutorial

You can find the detailed video tutorial here

Thought Process

Purely a math problem. Calculate the clock's hour hand and minute hand separately.
• There are 60 minutes in 360 angle, so each minute is 6 degree in angle.
• Angle should be the absolute value of (minute angel - hour angle)
• Final angle should be min(angle, 360 - angle)

Solutions

Time Complexity: O(1) since it's a math problem
Space Complexity: O(1) no extra space is used

Friday, July 17, 2020

Problem Statement

Given an array of integers `nums`.

A pair `(i,j)` is called good if `nums[i]` == `nums[j]` and `i` < `j`.

Return the number of good pairs.

Example 1:

```Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.
```

Example 2:

```Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array are good.
```

Example 3:

```Input: nums = [1,2,3]
Output: 0
```

Constraints:

• `1 <= nums.length <= 100`
• `1 <= nums[i] <= 100`

Video Tutorial

You can find the detailed video tutorial here

Thought Process

Array is the most basic data structures and common solutions inclue
• Nested for loops O(N^2)
• Sort O(NlgN)
• Use extra space O(N)
This applies to this problem perfectly. The O(N^2) brute force solution is naive. We can also use a Map data structure (key is the number, value is the occurrence count) thus O(N). We can also sort the array and use this simple formula (also leetcode's hint) to calculate the good number pair.
Good pairs = N * (N-1) / 2 where N is how many duplicate numbers, this is from combination C(n^2), from n elements pick two

Solutions

Use Map

Time Complexity: O(N), N is the array size
Space Complexity: O(N) since we use extra Map

Sort

Time Complexity: O(NlgN), N is the array size since we sort
Space Complexity: O(1) no extra space is used

• None