Linked List, Easy

Question

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example 1:

1
2

Input: 1->1->2
Output: 1->2

Example 2:

1
2

Input: 1->1->2->3->3
Output: 1->2->3

Linked List, Easy

Question

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Linked List, Easy

Question

Sort a linked list in O(nlogn) time using constant space complexity.

Example 1:

1
2

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

1
2

Input: -1->5->3->4->0
Output: -1->0->3->4->5

Linked List, Easy

Question

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

Design paradigm

1. Divide the problem(instance) into subproblems
2. Conquer the subproblems by solving them recursively
3. Combine subproblem solutions

Example

1. Merge sort

$T(n) = 2T(n/2) + O(n)$

$T(n) = O(nlgn)$

2. Binary search

$T(n) = 1T(n/2) + O(1)$

3. Powering a number

given a number $x$, integer $n\leq 0$>=0, compute $x^n$

Naive algorithm: multiply, time complexity: $O(n)$

$T(n) = T(n/2) + O(1) $

$T(n) = O(lgn)$

4. Fibonacci number

$F_n = 0$ , when n = 1

$F_n = 1$ , when n = 2

$ F_n = F_{n-1} + F_{n-2} $ , else

naive recursive algorithm: $\phi ^n$, $\phi = \frac{1+\sqrt{5}}{2}$, golden ratio, exponential time

• Bottom-up algorithm

​ Compute $F_0, F_1, F_2..F_n$

​ Time complexity: $O(n)$

• Naive recursive squaring

  $F_n = \phi_n / \sqrt{5}$ rounded to the nearest integer

  Time complexity: $O(lgn)$

  This method is unreliable, since floating-point arithmetic is prone to round-off errors (四舍五入时会有误差)

  NOT allowed

5. Recursive Squaring(Fibonacci number)

Theorem:

$$
\begin{bmatrix}
F_{n+1} & F_n\\
F_n & F_{n-1}
\end{bmatrix}^n
=
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^n
$$
Time complexity: $O(lgn)$

proof: by induction on n

Base: (n=1)
$$
\begin{bmatrix}
F_2 & F_1\\
F_1 & F_0
\end{bmatrix}
=
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^1
$$
Inductive step: (n>=2)
$$
\begin{equation}
\begin{split}
\begin{bmatrix}
F_{n+1} & F_n\\
F_n & F_{n-1}
\end{bmatrix}
&=
\begin{bmatrix}
F_n & F_{n-1}\\
F_{n-1} & F_{n-2}
\end{bmatrix}
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix} \\\\
&=
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^{n-1}
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}\\\\
&=
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^n
\end{split}
\end{equation}
$$

6. Matrix multiplication

Input: $A = [a_{ij}], B = [b_{ij}]$

Output: $C= [c_{ij}] = A \cdot B$

$c_{ij} = \sum_{k=1}^na_{ij}\cdot b_{kj}$

1
2
3
4
5

for i = 1 to n
	for j = 1 to n
		c_ij = 0
			for k = 1 to n 
				c_ij = c_ij + a_ik * b_kj

Time complexity: $O(n^3)$

IDEA

$n \times n$ matrix = $2 \times 2$ matrix of $n/2 \times n/2$ submatrices
$$
\begin{bmatrix}
r & s\\
t & u
\end{bmatrix}
=
\begin{bmatrix}
a & b\\
c & d
\end{bmatrix}
\cdot
\begin{bmatrix}
e & f\\
g & h
\end{bmatrix}
$$
$C= A\cdot B$
$$
\begin{equation}
\begin{split}
r &= ae + bg \\
s &= af + bh \\
t &= ce + dg \\
u &=cf + dh
\end{split}
\end{equation}
$$
8 mults of $(n/2) \times (n/2) $submatrices – recursive mult

4 adds of $(n/2) \times (n/2) $submatrices – $O(n^2)$

explanation for $n^2$:

1
2
3
4
5
6
7
8
9

public static int[][] AddMatrix(int[][] p,int[][] q,int n){
	int[][] result = new int[n][n];
	for(int i=0;i<n;i++){
      	for(int j=0;j<n;j++){
        	result[i][j] = p[i][j]+q[i][j];
      	}
    }
  	return result;
}

Time complexity: $T(n) = 8T(n/2) + O(n^2) = O(n^3)$

No better than the ordinary algorithm

Strassen’s algorithm

IDEA: reduce # mults to 7

multiply $2 \times 2$ matrices with only 7 recursive mults
$$
\begin{equation}
\begin{split}
P_1 &= a \cdot (f - h) \\
P_2 &= (a + b) \cdot h \\
P_3 &= (c + d) \cdot e \\
P_4 &= d \cdot (g - e) \\
P_5 &= (a + d) \cdot (e + h) \\
P_6 &= (b - d) \cdot (g + h) \\
P_7 &= (a - c) \cdot (e + f)
\end{split}
\end{equation}
$$

$$
\begin{equation}
\begin{split}
r &= P_5 + P_4 - P_2 + P_6 \\
s &= P_1 + P_2 \\
t &= P_3 + P_4 \\
u &= P_5 + P_1 - P_3 - P_7
\end{split}
\end{equation}
$$

Algorithm:

• Divide: Partition A and B into $n/2 \times n/2$ submatrices. Form terms to be multiplied using + and -

  $P_1, P_2 …$ – $O(n^2)$

• Conquer: Perform 7 multiplications of $n/2 \times n/2$ submatrices recursively

• Combine: Form C using + and - on $n/2 \times n/2$ matrices $O(n^2)$

Time complexity: $T(n) = 7T(n/2) + O(n^2) = O(n^{lg7}) = O(n^{2.81})$

The number 2.81 may not seem much smaller than 3, but because the difference is in the exponent, the impact on running time is significant. In fact, Strassen’s algorithm beats the ordinary algorithm on today’s machines for $n\geq 32$ or so.

Best to date (of theoretical interest only): $O(n^{2.376..})$

7. VLSI layout (超大规模集成电路)

Problem: Embed a complete binary tree with n leaves in a grid using minimal area

Naive:

$H(n) = H(n/2) + O(1) = O(lgn)$

$W(n) = 2W(n/2) + O(1) = O(n)$

$Area = O(nlgn)$

递归式

递归式刻画分治算法的运行时间

3种求解递归式的方法：

• 代入法
• 递归树法，将递归式转换成为一棵树
• 主方法：$T(n) = aT(n/b) + f(n)$, 生成 a 个子问题，每个子问题的规模是原问题规模的 1/b , 分解和合并步骤花费时间为 f(n)

Find maximum subarray, continuous

stock problem –> A[i] - A[i-1] –> find maximum subarray of A –> A[i..j]

Using divide and conquer, A[low..mid], A[mid+1..high]

Only three cases:

case 1: All in A[low..mid], so low<=i<=j<=mid

case 2: All in A[mid+1..high], so mid+1<=i<=j<=high

case 3: span over the mid, so low<=i<=mid<=j<=high

Question

输入一棵二叉树和一个整数， 打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

二叉树结点的定义：

1
2
3
4
5

public static class BinaryTreeNode {
    int value;
    BinaryTreeNode left;
    BinaryTreeNode right;
}

Dynamic Programming, Easy

Question

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

1
2
3
4
5

  3
 / \
2   3
 \   \ 
  3   1

Maximum amount of money the thief can rob = 3+3+1 = 7

Example 2:

1
2
3
4
5

    3
   / \
  4   5
 / \   \ 
1   3   1

Maximum amount of money the thief can rob = 4+5 = 9

Dynamic Programming， Easy

Question

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:

1
2
3
4

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.

Example 2:

1
2
3
4

Input: [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.

Sort, Easy

Question

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

1
2

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

1
2

Input: s = "rat", t = "car"
Output: false

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

LinkedList, Easy

Question

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

1
2

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4