Saturday, April 25, 2020

Google Kickstart 2020 Round A: Plates Solution

Problem Statement 


Dr. Patel has N stacks of plates. Each stack contains K plates. Each plate has a positive beauty value, describing how beautiful it looks.
Dr. Patel would like to take exactly P plates to use for dinner tonight. If he would like to take a plate in a stack, he must also take all of the plates above it in that stack as well.
Help Dr. Patel pick the P plates that would maximize the total sum of beauty values.


The first line of the input gives the number of test cases, TT test cases follow. Each test case begins with a line containing the three integers NK and P. Then, N lines follow. The i-th line contains K integers, describing the beauty values of each stack of plates from top to bottom.


For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum total sum of beauty values that Dr. Patel could pick.


Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ K ≤ 30.
1 ≤ P ≤ N * K.
The beauty values are between 1 and 100, inclusive.

Test set 1

1 ≤ N ≤ 3.

Test set 2

1 ≤ N ≤ 50.



2 4 5
10 10 100 30
80 50 10 50
3 2 3
80 80
15 50
20 10

Case #1: 250
Case #2: 180

In Sample Case #1, Dr. Patel needs to pick P = 5 plates:
  • He can pick the top 3 plates from the first stack (10 + 10 + 100 = 120).
  • He can pick the top 2 plates from the second stack (80 + 50 = 130) .
In total, the sum of beauty values is 250.
In Sample Case #2, Dr. Patel needs to pick P = 3 plates:
  • He can pick the top 2 plates from the first stack (80 + 80 = 160).
  • He can pick no plates from the second stack.
  • He can pick the top plate from the third stack (20).
In total, the sum of beauty values is 180.
Note: Unlike previous editions, in Kick Start 2020, all test sets are visible verdict test sets, meaning you receive instant feedback upon submission.

Problem link


Video Tutorial

You can find the detailed video tutorial here


 Thought Process

First thought is similar to merging multiple lists, this won't work since the lists are not sorted and we are not allowed to sort due to the order constraint.

Second thought is keep a max heap, and always merge the largest value from all the top elements in the lists. This is wrong since greedy won't work here. E.g., below if we want to pick 3 plates, using max heap will pick 2, 2, 2, instead of 1, 1, 100
2, 2, 2, 2, 2
1, 1, 100, 100, 100

Third thought seems we have to brute force, for all the combos of P, we check what's the maximum value. Quote from the analysis, it's exponential time complexity
For example, if N = 3 and for any given values of K and P, generate all possible triples (S1, S2, S3) such that S1+S2+S3 = P and 0 ≤ Si ≤ K. Note: Si is the number of plates picked from the i-th stack.
This can be done via recursion and the total time complexity is O(KN) which abides by the time limits.
Forth and final solution to optimize this is using dynamic programming. It's very common in those coding competitions.
Quote from the analysis

First, let's consider an intermediate state dp[i][j] which denotes the maximum sum that can be obtained using the first i stacks when we need to pick j plates in total.
Next, we iterate over the stacks and try to answer the question: What is the maximum sum if we had to pick j plates in total using the i stacks we've seen so far? This would give us dp[i][j]. However, we need to also decide, among those j plates, how many come from the i-th stack? i.e., Let's say we pick x plates from the i-th stack, then dp[i][j] = max(dp[i][j], sum[i][x]+dp[i-1][j-x]). Therefore, in order to pick j plates in total from i stacks, we can pick anywhere between [0, 1, ..., j] plates from the i-th stack and [j, j-1, ..., 0] plates from the previous i-1 stacks respectively. Also, we need to do this for all values of 1 ≤ j ≤ P.
The flow would look like:
for i [1, N]:
 for j [0, P]:
  dp[i][j] := 0
   for x [0, min(j, K)]:
    dp[i][j] = max(dp[i][j], sum[i][x]+dp[i-1][j-x])
If we observe closely, this is similar to the 0-1 Knapsack Problem with some added complexity. To conclude, the overall time complexity would be O(N*P*K).


DP solution

Time Complexity: O(N*P*K)
Space Complexity: O(N*max(P, K))


Saturday, April 18, 2020

Leetcode solution 75. Sort Colors

Problem Statement 

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note: You are not suppose to use the library's sort function for this problem.
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Follow up:
  • A rather straight forward solution is a two-pass algorithm using counting sort.
    First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
  • Could you come up with a one-pass algorithm using only constant space?
 Problem link

Video Tutorial

You can find the detailed video tutorial here

Thought Process

This is the classic Dutch National Flag Problem. 

Two pass with constant space is easy with count sort. (Reminds me of Radix Sort somehow) An extension would be what happens if there are K elements (K >=3)

If do it in one pass, then the idea must involve pointers and swap. Start from left to right, if 1, pass; if 0, move to the left; if 2, move to the right


Two pass

Time Complexity: O(N), where N is the array size, N + 3*N = 4N = O(N)
Space Complexity: O(1) since only need 3 elements in this case, still considered constant

One Pass

Time Complexity: O(N), where N is the array size
Space Complexity: O(1)


Saturday, April 4, 2020

System design interview: how to design a video platform (e.g, Youtube, Netflix)

System design interview: how to design a video platform (e.g., Youtube, Netflix)

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.

Key designs and terms 

Let's first admit this is a hard problem. Youtube has hundreds of smart engineers keep improving it and it's almost impossible to design a good one in 60 mins. This solution is a pretty decent one from Grokking the system design interviews where it covers the backbone about the system.
You can also divided the system as usual into three major layers, presentation, service and data layer.

A few key terminologies. If you are not familiar, brush up a bit
  • CDN: a distributed cache for videos
  • Codec: encoding and decoding, a video would be encoded to different resolutions and different formats, e.g, 16:9 mp4, 4: 3 avi
  • Video processing is slow, normally done asynchronously via queue and workflows 
  • Video de-duplication, hash content (SHA, MD5), phase correlation, block matching. If you forget about Fourier Transformation, watch 3Blue1Brown
  • Metadata sharding, pros vs con. If shard videos by user uuid (hot partition for popular users). If shard videos by video uuid (hot partition for popular videos)
  • To solve hot hot partition / hot key: Consistent Hashing (original paper 1997: Consistent Hashing and Random Trees:Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web)  + Load balancing + Replicate data (Need to automatically discover the hotkey first, redis has built-in support). Alibaba Cloud Read
  • Comment/Reply design, Likes and View counts (all sorts of counters) would be explained in a separate post.

 Baozi Youtube Video

References (Credits to original authors)