Saturday, January 18, 2020

Leetcode solution 229: Major Element II


Problem Statement 

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Note: The algorithm should run in linear time and in O(1) space.
Example 1:
Input: [3,2,3]
Output: [3]
Example 2:
Input: [1,1,1,3,3,2,2,2]
Output: [1,2]
 Problem link

Video Tutorial

You can find the detailed video tutorial here

Thought Process

It's a follow up question on Majority Element, given the hint, there should only be at most 2 elements that can satisfy the requirement (You cannot have 3 elements that all appear more than n/3 times). We can perform the voting algorithm on two potential candidates and later do an actual sum to eliminate the false positive (e.g., [1, 2, 1] would have both 1 and 2 as potential candidate, but 2 should not be included)

You can refer to Majority Element for a detailed explanation on the voting algorithm.

An extension could be changing n/3 to n/k. We just need extra arrays to store votes and candidates. It will take O(Nk) time complexity

Solutions

Voting implementation

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

References

Saturday, January 11, 2020

Leetcode solution 169: Major Element


Problem Statement 

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
Example 1:
Input: [3,2,3]
Output: 3
Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2
 Problem link

Video Tutorial

You can find the detailed video tutorial here

Thought Process

Simple but great question that can be solved in many ways, the voting one approves to be the most time and space efficient solution.

You can refer to Leetcode official solution for a detailed explanation.

Solutions

Voting implementation

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

References

Saturday, January 4, 2020

Leetcode solution 6: ZigZag Conversion


Problem Statement 

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P   A   H   N
A P L S I I G
Y   I   R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I
 Problem link

Video Tutorial

You can find the detailed video tutorial here

Thought Process

It's a very good implementation problem, by simply simulating each character in the string to each row, it would take extra O(N) space to hold up the array where N is the string size. However, there is definitely a difference between a good and poor implementation.

There is also a math formula we can use, please see attached pdf for solutions.

Solutions

Simulation poor implementation

Time Complexity: O(N) where N is the string size
Space Complexity: O(N) since we used an extra array to store each character in the string

Simulation good implementation

Time Complexity: O(N) where N is the string size
Space Complexity: O(N) since we used an extra array to store each character in the string

References

Saturday, December 28, 2019

Leetcode solution 59: Sprial Matrix II


Problem Statement 


Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
Example:
Input: 3
Output:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]
 Problem link

Video Tutorial

You can find the detailed video tutorial here

Thought Process

Straight forward question, could use Spiral Matrix exact same recursion algorithm to solve this, you can also watch that video tutorial here

Still needs pay attribute to this guy, had another great solution:
https://leetcode.com/problems/spiral-matrix-ii/discuss/22282/4-9-lines-Python-solutions

Solutions

Simulation using Recursion

Time Complexity: O(M*N) where M, N is row and col of matrix
Space Complexity: O(M*N) since we used list to store the result, where M, N is row and col of matrix


References

Friday, December 27, 2019

System design interview: how to design a feeds system (e.g., Twitter, Instagram and Facebook news feed)

System design interview: how to design a chat system (e.g., Messenger, WeChat or WhatsApp)

Methodology: READ MF!

Please use this "READ MF!" framework for software engineer system interview purpose.

Key designs and terms 




  • So far the best detailed explanation on designing twitter is from Raffi (used to be VP of Twitter) on QCon. Presentation, Slides [All credits go to QCon). Raffi is very smart and articulate, really solid guy!
  • Read heavy system, not write heavy, optimized for user timeline. To be clear, there are two timelines, one is user's own tweets (easy to do), the other is the main timeline which is an aggregation of all the tweets from the people that user follows. 
  • Pre-calculate all the timelines. This is the interesting part of the design vs using a mysql and having index to query in realtime, which would not be scalable. When a tweet is posted, the tweets service would
    • Store this tweet in memory, and that later would be flushed to a main DB
    • Call the fanout deliver service to publish this tweet to all the users' timeline that followed this particular user. It could simply store a tweet ID (and later the content could be retrieved from the Tweets Cache) or hydrating the entire text content is also fine (note how we want to handle eidt or delete, twitter probably doesn't allow delete)
    • Call search service to index (Lucene). The search index is also hosted in memory on Redis. Note search here needs to fanout to all search clusters but due to the in memory hosting, it's acceptable.
  • Always remember disk access is at least 100k times slower than memory access, e.g, disk is 10ms vs 100ns on memory. https://gist.github.com/jboner/2841832
  • With the pre-caculate timeline design, there might be race conditions when celebrity (people with millions of followers) starts to talking to each other with replies. E.g., celebrity A tweets something, takes 30 sec to deliver to all the followers,  celebrity B replies before deliver finishes, some followers follow both A and B might see B's reply first before A's original post. One cheat workaround is to sort by timestamp or tweet IDs, but they are also experimenting with only pre-calculate non-celebrity tweets, and when generating timeline, realtime fetching the celebrity tweets. It depends which way is better and also the user experience. This is a good stop point to talk to your interviewers in real world about tradeoffs.
  • Since twitter is heavily relying on cache, you might want to checkout how they optimized the caching with twemproxy.

Baozi Youtube Video

Saturday, December 21, 2019

Leetcode solution 54: Sprial Matrix


Problem Statement 

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:
Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
 Problem link

Video Tutorial

You can find the detailed video tutorial here

Thought Process

It's a straight forward implementation question, we can simply just simulate the spiral order and print. You can choose to do it either iteratively (see reference to download the official Leetcode solution) or use recursion.

There is this awesome one line solution from this guy which is pretty insane.
def spiralOrder(self, matrix):
    return matrix and list(matrix.pop(0)) + self.spiralOrder(zip(*matrix)[::-1])
https://leetcode.com/problems/spiral-matrix/discuss/20571/1-liner-in-Python-%2B-Ruby

Solutions

Simulation using Recursion

Time Complexity: O(M*N) where M, N is row and col of matrix
Space Complexity: O(M*N) since we used list to store the result, where M, N is row and col of matrix


References

Saturday, December 14, 2019

Leetcode solution 322: Coin Change


Problem Statement 

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. Example 1:
Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3
Output: -1
 
Problem link

Video Tutorial

You can find the detailed video tutorial here

Thought Process

This is a classic problem and greedy might be the first thing comes into mind. For example, sort the coins on denomination and always use the largest amount coin. However, the optimal solution might not include the largest denomination.

for example , [1, 3, 4] and target value 6. The optimal is two 3s, not [4, 1, 1].

It seems we have to list out all the different combinations and find the min value, that leads to a brute fore solution as described here using recursion. It would be an exponential time complexity.

We can use a hash map as a lookup to remember for each amount, what would be the min cost. That would significantly reduce the time complexity from exponential to O(S*N) where S is the amount and N is the coins array size. It's not obvious why but once you see the DP solution, you can understand better, it's the same time complexity.

Another way is to use dynamic programming because the problem is asking for a single yes/no, extreme value(min, max), building up a lookup table using formula is the coding pattern. We have similar problems, Wild Card Matching, Regular Expression Matching

The idea is to build a lookup table for each amount, what's the minimal number of coins needed given current  denomination.
lookup[i] = min(lookup[i], lookup[i - coin value] + 1) given i - coin value >= 0

Solutions

Dynamic Programming

Time Complexity: O(S*N) where S is the amount and N is the coins array size
Space Complexity: O(N) since we used a lookup array


References