# Problem Description:

https://leetcode.com/problems/4sum/

# Analysis:

This is another N-Sum problem. We may start by thinking “is the HashMap approach in 2Sum valid here”? The answer is yes if we use two loops to convert this problem into 2sum and use the hashmap approach solving it. Be aware that we need to sort the array to avoid duplication. In fact, this is no time complexity benefit in this case. The sorting takes O(N*log(N)), and the two loops take O(N^2 * N), so the entire time complexity takes O(N^3 + N * log(N)) which is O(N^3).

This is the hash map solution.

# Problem Description:

https://leetcode.com/problems/3sum-closest/

# Analysis:

I came up with a greedy approach at the first place: each time, find the closest to the target, and then subtract this value from the target value and remove it from the array, and then recursively compute. However, this approach did not work for all cases. For example, it will fail in the following case:

The reason of the failure of greedy approach is because there can be negative numbers. Selecting a large number at any step is possible because there may be a negative number which can be paired with this large number to get a closer sum to the target. For example,  [-100,1,100] target = 0 , a greedy approach will force us to select  1 at the first step, but actually this is not true.

The second though was to solve it as 3Sum or 2Sum using HashMap (this solution was described here), however, it is obvious that without a concrete target value (because their sum does not have to be equal to the target), it is impossible to use the HashMap solution, because HashMap can only tell if there is a value or not but we are going to compare their differences with the target.

# Problem Description:

https://leetcode.com/problems/palindrome-number/

# Analysis:

If this was a string, there are many ways to check if it is palindromic: we can use two pointers from start and end, we can also reverse the string and compare them. However, for an integer, if we convert it into a string and then check if it is palindromic, it will require more than constant space. If we can get the reverse integer using constant space and compare the new integer with the original one, that would be great. Recall that in this post: Reverse Integer, we have already had a linear solution with constant space to get a reverse of an integer. What we need to do is to just copy this solution and make a simple comparison. An exception is that if the integer is negative, it will never be a palindrome because of the negative sign.

# Problem Description:

https://leetcode.com/problems/string-to-integer-atoi/

# Analysis:

The main focus this problem is to come up with all corner cases. This requires a comprehensive communication with the interviewer before writing any code.

I won’t spend much time on this because there aren’t many algorithmic takeaways.

# Problem Description:

https://leetcode.com/problems/reverse-integer/

# Analysis:

It is a relatively simple problem, but it is also a hard problem.

It is simple because it seems that there are many ways to solve it: we can build a string and then convert it to number; we can convert the original string character array and then convert into an array of digits and calculate the result, convert into a character array and do in-place swaps, etc. Among all these methods, we don’t know which one should we started with, and what are the traps within each of these.

We still want to solve this problem in a beautiful way, so if we aim to solve it in a linear solution with constant space, we can tell that we may need to use a “digit by digit” solution.

# Problem Description:

https://leetcode.com/problems/zigzag-conversion/

# Analysis:

I won’t spend much time on this because there are not many generic approaches to take away.

You may wonder: is there any relationship between the index in the 2-d array and the index in the string? Then you may spend a lot of time to figure out the relationship and finally got nothing.

The right thing we need to do is: just write a program doing exactly like what you would do on a piece of paper. Then we can improve on the working version. The approach applies especially to the kind of problems like a game, maze, a word puzzle, etc., something seems to be not algorithm-heavy.

# Problem Description:

https://leetcode.com/problems/longest-palindromic-substring/

# Analysis:

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

REMINDER: read until the end, otherwise you will get it wrong.

The “longest”. As we have mentioned in previous posts, looking for “longest” substring usually relates to Dynamic Programming or Sliding Window algorithm. Let’s see which one fits the best here.

If we use Dynamic Programming approach, we need to memorize something like “the longest palindromic substring length so far” for each position, or something else; seems feasible.

If we use Sliding Window approach; we might need two pointers: a start and an end. Each time we expand the end pointer, check if the substring formed by start and end pointer is palindromic. When it reaches the end of the string, move start pointer forward a position and do the same thing. Feasible but is is clearly a Brute Force method: it basically tries all possible substrings and checks if each of them is palindromic. We do not want this, let’s take a deeper think of the Dynamic Programming approach then.

# Problem Description:

https://leetcode.com/problems/median-of-two-sorted-arrays/

# Analysis:

(Aside: Please note that this article mainly focuses on the thought process. An idea introduced in the beginning may be completely overturned in later paragraphs, so please be sure the read until the end. Also, this is intended to illustrate the process of deriving an initial solution -> figure out something wrong -> make a fix -> repeat until found a working solution.)

This is actually a very difficult problem. Let’s first gather some initial thoughts from the problem description:

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

# Problem Description:

https://leetcode.com/problems/longest-substring-without-repeating-characters/

# Analysis:

For questions asking about longest, largest, etc., we may try to think about Dynamic Programming and Sliding Window. In this case, we can try both on a piece of paper and will find out that sliding window should be the approach. If you are not familiar with sliding window algorithm, you can imagine a window formed by a starting point and ending point on an axis. They both can move freely but the starting point has to be on the left-hand side of (smaller than) the ending point. The sliding window algorithm is basically to move end point to a situation where it can no longer expand, then move starting point gradually towards to ending point. Depending on what you need, you may either want to try to move ending point further each time moving starting point or move starting point towards ending point to a situation the “window” can no longer shrink, then move ending point further again.

# Analysis:

The solution is obvious that just to go through the two linked lists at the same time, add the number and make the sum a new node into the result. However, this can be a very buggy program if not careful.

This time, we will try to find corner cases using test-driven development. So let’s create tests first.

When creating tests, we must come up all possible situations that may break the code. In industry production, we must also be careful of invalid or meaningless or harmful inputs (e.g. SQL injection), but we don’t have to worry about them here.

Before creating tests, let’s take another look at the input requirement: each input is a linked list of integers. During the interview, it is better to ask the interviewer if we can assume the input is valid, which in this case, yes, so we can assume that each linked list node is an integer from 0 to 9. When creating tests cases, we can hand calculate the expected outputs as well unless the algorithm is extremely complex.

Some tests and expected outputs can be:

# Problem Description:

https://leetcode.com/problems/two-sum/

# Analysis:

The brute force solution is so obvious and trivial; the main focus is to find out an elegant way.

Let’s start by analyzing the brute force approach: two nested loops; the outer loop iterates from index 0 to the end, and the inner loop iterates from the next index of outer loop to the end. We check if they can sum to the target then. An O(n^2) solution. At each inner loop step, we are actually looking for a number that can be summed up to the target with outer loop number. This is where we may try something to improve.

So, we need a way to find out whether there is a number in the array. This easily leads us to think about using a HashTable. If we can map the array into a hash table, using the array value as key, and the array index as value, then we can easily tell if a value exists in the array by checking if the hash table contains the key. The original inner loop is O(N), and the hash table approach reduces it to O(1) because we do not need an inner loop anymore. Implementing a hash table needs us to loop over the array; this is inevitable, thus the entire program is now O(N).

## Network Entropy & Information Gain Analyzing Tool (网络传输层熵的分析工具)

Final Project for CS740 Spring 2016

This program calculates entropy and information gain of network packets captured by Wireshark.

## Instruction:

### System Requirements:

Note on linux users: You may need use `sudo apt-get install python3-matplotlib` (Debian/Ubuntu) or `sudo yum install python3-matplotlib` (Fedora/Redhat) to install matplotlib for Python3 instead of Python2.