Saturday, July 9, 2022

Leetcode solution 2320. Count Number of Ways to Place Houses

 

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
 Problem link

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.

References

Thursday, June 23, 2022

Leetcode solution 2304. Minimum Path Cost in a Grid


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
 Problem link

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

References

  • None

Monday, February 15, 2021

Leetcode solution 1752. Check if Array Is Sorted and Rotated

 

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


 Problem link

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

References

  • None

Sunday, August 2, 2020

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

直接上视频,建议1.5倍速收听😄




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



Saturday, July 25, 2020

Leetcode solution 1344. Angle Between Hands of a Clock

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.
 Problem link

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

References

Friday, July 17, 2020

Leetcode solution 1512. Number of Good Pairs

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
 Problem link

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

References

  • None

Saturday, July 4, 2020

System design interview: how to design a simple twitter search system


Methodology: READ MF!

[Originally from the Post: System design interview: how to design a chat system (e.g., Facebook Messenger, WeChat or WhatsApp)]

Remind ourselves with the "READ MF!" methodology.

Requirements

Simple text based search with "AND" or "OR" support. E.g., give me all the tweets that have words "Black" AND "Life" in it sorted by published time in descending order.

search(api_dev_key, search_terms, maximum_results_to_return, sort, page_token)


A follow up question would be sort those results in other orders, E.g., give me all the tweets that have words "Black" AND "Life" in it sorted by the most commented tweets in descending order.

Estimation

  • Storage: assuming twitter has 1B users, 50% of them post a tweet per day, each tweet is 140 char = 140 Byte. Each day, 1B * 0.5 * 280(roughly 300)Byte = 150GB data
  • Write QPS = 1B user * 0.5 post a tweet per day / 86400 = 5787 QPS = 6000 QPS
  • Query QPS = assuming 3x than write QPS = 18000 QPS
Write QPS in general we don't worry too much since it could be processed asynchronously. 18000 QPS for read is easy to handle as long as we have enough number of boxes and most of query would be returned via memory (not hitting disk). 

Key designs and terms


You can also divided the system as usual into three major layers, presentation, service and data layer.

A few key terminologies.

If the follow up question, we just need to build another index given the sort key or we could fetch the results on flight and sort (local optimal). Follow "Index -> Search -> Rank" steps.

  Baozi Youtube Video


References (Credits to original authors)

Saturday, June 27, 2020

Leetcode solution 213. House Robber II

Problem Statement 

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
             because they are adjacent houses.

Example 2:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.
 Problem link

Video Tutorial

You can find the detailed video tutorial here

Thought Process

This is very similar to House Robber I problem where the only difference is the houses now form a circle (French fancy way calls it cul-de-sac). It's same DP algorithm except now we need to consider two cases: whether we rob the first house or not. If we rob the first house, we should not rob the last house. If we do not rob the first house, we can rob the last house. We can even reuse the rob() function in House Robber I problem




Solutions

Use DP


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


References

Saturday, June 20, 2020

Leetcode solution 198. House Robber

Problem Statement 

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

 

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

 

Constraints:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 400
 Problem link

Video Tutorial

You can find the detailed video tutorial here

Thought Process

Easy problem and Dynamic Programming(DP) should jump into mind given it's only asking for max values (Just think about different combo we have to do without using DP, a little less than 2^N)

The mathematical induction formula is below, for any current max money at index i, you either choose to use the i-1 or i-2 + current house's money to not trigger police.
max[i] = max(max[i - 2] + a[i], max[i-1])

Solutions

DP

Time Complexity: O(N) N is the array size
Space Complexity: O(N) since we used an extra array

References