Leetcode 18. 4Sum

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.

Read More

Leetcode 16. 3Sum Closest

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.

Read More

Leetcode 9. Palindrome Number

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.

Read More

Leetcode 7. Reverse Integer

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.

Read More

Leetcode 6. ZigZag Conversion

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.

Read More

Leetcode 5. Longest Palindromic Substring

Problem Description:

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

Analysis:

The problem asks for

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.

Read More

Leetcode 4. Median of Two Sorted Arrays

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

Read More

Leetcode 3. Longest Substring Without Repeating Characters

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.

Read More

Leetcode 2. Add Two Numbers

Problem Description:

https://leetcode.com/problems/add-two-numbers/

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:

Read More

Leetcode 1. Two Sum

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).

Read More

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

这个是我在CS740 Advanced Network (UW-Madison, taught by Paul Barford, Spring 2016) 课上做的研究课题,最后写的论文就不放在这里了,水平有限。

把我写的代码分享一下吧:https://github.com/xiqi/network-entropy-infogain

这个工具可以通过分析传输层(TCP、UDP)的IP地址对(Source/Destination)的熵,来判断应用层的网络活动。

 

以下是GitHub上的README,具体代码请见上面的GitHub链接:

 

University of Wisconsin-Madison

Final Project for CS740 Spring 2016

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

You can get Wireshark here for free.

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.

Read More

Heartbleed Detector and Exploiter (Java)

OpenSSL的Heartbleed漏洞已经过去有一段时间了,当时正好在上一门信息安全(UW-Madison CS642: Information Security)的课,于是Heartbleed这个素材也就完美的成为了作业题目。作业要求写一个简单的程序能够探测服务器是否存在Heartbleed漏洞,并且如果存在漏洞的话能够dump出内存。不过由于作业题目的版权原因,我没有办法把作业题目公布。

当时我写了一个简单的Java程序放在了GitHub上,不过由于是作业所以一直设为保密。现在学期已经结束了,不如公开和大家分享。网上也有很多类似的攻击脚本,不过很多都是Python的。

GitHub地址:https://github.com/xiqi/CS642-EC-Heartbleed

这个程序使用很简单,编译后直接执行

Read More

针对WordPress采用了Google Fonts而导致国内访问缓慢的解决方法

WordPress的后台默认引用了Google Fonts,同时一些商业主题也采用了Google Fonts,而这些让中国大陆的用户在访问和使用WordPress时都遭遇了十分缓慢的速度。

除了从源码中直接删除相关语句,我另外推荐两种方法解决这个问题:

  • 利用插件禁用Google Fonts

Disable Google Fonts:这个插件启用之后可以移除前台和后台所有引用了Google Fonts的功能,安装后直接启用即可不需设置。

 

  • 采用奇虎(360网站卫士)提供的Google Fonts国内CDN镜像

详情请见“360网站卫士常用前端公共库CDN服务”,即把 fonts.googleapis.com 替换为 fonts.useso.com 即可。另外除了直接修改源码,有网友写出了一个WordPress插件可以做到同样的功能,请见博文源地址:http://www.soulteary.com/2014/06/08/replace-google-fonts.html 为了方便,也可以点击这里直接下载:Replace-Google-Fonts,安装启用即可不需设置,测试效果表明速度效果十分理想。