Network Delay Time

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

辨别路由状态的合法性

路由协议的基本目标就是维护全局路由状态(global routing state)的合法性(valid)，可以通过死端和循环的存在来确定路由状态的合法性。路由状态合法的充分必要条件就是不存在死端与循环的链路。死端是对于一个路由，不存在出链路了，也就是无法继续转发这个包，死在互联网中。而循环在路由协议的制定中是一个比较受关注的问题，当前的不同的路由协议的差异就在于对循环的处理。

产生合法路由状态的方法

避免死端的做法比较简单，只需要将你知道的路由信息告诉你的邻居，如此递归进行下去，便不会出现死端的情况。而循环相对复杂，典型的解决方法有以下四种：

• 根据拓扑状态创建树：如果拓扑不包含循环，并且不将包转发回去，则可以确定不会产生循环转发情况。实际应用是L2的learning switch，应用场所是单栋大楼里面生成树加自学习，以太网。
• 获取全局视野(Global view)：如果我们知道整个网络的拓扑状态，就能根据很多图算法计算路由状态。实际应用是LS算法和SDN，应用场所是域内，企业或者校园网，OSPF全局视野，RIP最小跳度量
• 分布式路由计算：包含两种策略，第一种计算最小度量，第二种是路由器明确交换路径。实现方法一的策略是计算最短路径，终点先站起来，然后声明自己的距离为0，坐下之后邻居站起来，声明距离为1，以此类推，每个人都记得是谁叫的他们。直到起点站起来，并且知道是谁叫的他，往后追溯就可以寻找到一条路经。实际应用是DV算法。实现方法二同样是终点站起来，但是这次是声明路径，也就是自己本身，然后邻居站起来，将自己加到路径里面，实际应用是域间路由的BGP算法。

生成树协议

最简单的避免循环的方法是建立一个生成树，选择有最小identifier的结点作为root，然后计算出一个最小生成树。

距离矢量算法

• 迭代式：算法持续进行直至无信息需要在邻居间交换
• 分布式：每个节点收到邻居传送过来的路由信息，计算后再分发计算结果给邻居
• 异步：不需要所有的节点同时操作
• 自终止：算法不需要终止信号，知道什么时候应该终止

String in java

java中字符串的表示是不可变的定长char型数组，char型为16位无符号整数，采用Unicode编码，最多支持65536个字符。length以及charAt, substring方法为常数时间复杂度，substring只返回一个String的实例。而concat操作由于要创建新的char数组作为字符串返回，所以时间复杂度为concat的两个字符串的长度和。

基本算法

快排是一种基于分治的算法，将数组分成两部分，将两部分独立排序，当两个子数组都有序时，整个数组也就有序了。

1
2
3
4
5
6
7
8
9
10
11
12
13

public class Quick {
    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a); // 打乱数组
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        if(lo >= hi) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }
}

归并操作

归并排序算法的核心是归并操作，给定两个有序的数组，将其归并为一个更大的有序的数组。以下是归并操作的java实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public static void merge(Comparable[] a, int lo, int mid, int hi) {
    // 辅助数组
    Comparable[] aux = new Comparable[a.length];
    // 用两个指针标识位置
    int i = lo, j = mid + 1;
    // 将数组内容复制到aux数组
    for(int k = lo; k <= hi; k++)
        aux[k] = a[k];
    for(int k = lo; k <= hi; k++) {
        // 左半边遍历完成
        if(i > mid) a[k] = aux[j++];
        // 右半边遍历完成
        else if(j > hi) a[k] = aux[i++];
        // 右半边元素小于左半边，放置小的至原数组
        else if(aux[i] > aux[j]) a[k] = aux[j++];
        else a[k] = aux[i++];
    }
}

Redundant Connection

In this problem, a tree is an undirected graph that is connected and has no cycles.

The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, …, N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.

Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v.

Example 1:

1
2

Input: [[1,2], [1,3], [2,3]]
Output: [2,3]

Explanation: The given undirected graph will be like this:
1
/
2 - 3
Example 2:

1
2

Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output: [1,4]

Explanation: The given undirected graph will be like this:
5 - 1 - 2
| |
4 - 3
Note:
The size of the input 2D-array will be between 3 and 1000.
Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

题意分析

该题给定一个代表连接的二维数组，要寻找出一条冗余的边，去掉这条边可以将图变成树。最简单的考虑是利用union-find数据结构，当我们遇到一个连接时，首先检查是否这两个点已经连通，如果连通，那么说明这条边是一条冗余的边，由于题目要求多条冗余边出现时，返回最后一条，所以将这条边加入栈中。如果两点尚未连通，将其连通即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        if(edges == null) return null;
        if(edges.length == 0) return null;
        Stack<int[]> stack = new Stack<>();
        WeightedQuickUnionUF uf = new WeightedQuickUnionUF(edges.length + 1);
        for(int i = 0; i < edges.length; i++) {
            int v = edges[i][0];
            int w = edges[i][1];

            if(uf.connected(v, w)) {
                stack.push(edges[i]);
            } else uf.union(v, w);
        }
        if(!stack.isEmpty()) return stack.pop();
        return null;
    }

   private class WeightedQuickUnionUF {
        private int[] parent;
        private int[] size;
        private int count;

        public WeightedQuickUnionUF (int n) {
            count = n;
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        public int count() {return count;}

        public int find(int p) {
            while (p != parent[p])
                p = parent[p];
            return p;
        }

        public boolean connected (int p, int q) {
            return find(p) == find(q);
        }

        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) return;

            // make smaller root point to larger one
            if (size[rootP] < size[rootQ]) {
                parent[rootP] = rootQ;
                size[rootQ] += size[rootP];
            } else {
                parent[rootQ] = rootP;
                size[rootP] += size[rootQ];
            }
            count--;
        }
    }
}

Evaluate Division

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector<pair<string, string>> equations, vector& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector.

According to the example above:

1
2
3

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

题意分析

给定一些方程，试图去寻找一些query的解。如果query中出现未知的字母，就返回-1，否则根据已有的方程计算。本题可以抽象为图问题，即搜索路径。思路是首先还是建图，维护两个map，两个map都是字符串到ArrayList的映射，第一个map告诉我们哪两个点存在连接关系，而第二个map告诉我们相应的连接的值是多少。有一个需要注意的是，我们在建图的时候不仅要将a到b的值给出，还要将这个值的倒数计算出赋给b到a的值。建图之后就是对query遍历，对map进行dfs遍历，dfs需要检查几种特殊情况，第一种就是在我们维护的set中，这个是作函数栈的模拟，如果重复出现了start，说明这个图出现了环，为了避免死循环，需要终止递归，在这里就是返回0.0。还有就是若第一个map不存在start的key，那么说明没有路径，因为起点都不存在了。最后就是若start和end相等，这里要注意使用String.equal方法，这时就可以返回value了，说明找到了路径，并且可以返回相应的计算的值了。检查这三种情况后，就是常规的dfs，注意set在这里对栈的模拟，注意环的存在。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        Map<String, ArrayList<String>> pairs = new HashMap<>();
        Map<String, ArrayList<Double>> valuePairs = new HashMap<>();
        // 建图
        for(int i = 0; i < equations.length; i++) {
            String[] equation = equations[i];
            String x = equation[0];
            String y = equation[1];
            if(!pairs.containsKey(x)) {
                pairs.put(x, new ArrayList<>());
                valuePairs.put(x, new ArrayList<>());
            }
            if(!pairs.containsKey(y)) {
                pairs.put(y, new ArrayList<>());
                valuePairs.put(y, new ArrayList<>());
            }

            pairs.get(x).add(y);
            valuePairs.get(x).add(values[i]);

            pairs.get(y).add(x);
            valuePairs.get(y).add(1 / values[i]);
        }

        double[] result = new double[queries.length];
        for(int i = 0; i < queries.length; i++) {
            String[] query = queries[i];
            result[i] = dfs(query[0], query[1], pairs, valuePairs, new HashSet<String>(), 1.0);
            if(result[i] == 0.0) result[i] = -1.0;
        }
        return result;
    }

    private double dfs(String start, String end, Map<String, ArrayList<String>> pairs, Map<String, ArrayList<Double>> valuePairs, Set<String> set, double value) {
        if(set.contains(start)) return 0.0;
        if(!pairs.containsKey(start)) return 0.0;
        if(start.equals(end)) return value;

        set.add(start);
        ArrayList<String> pairList = pairs.get(start);
        ArrayList<Double> valueList = valuePairs.get(start);
        double tmp = 0.0;
        for(int i = 0; i < pairList.size(); i++) {
            tmp = dfs(pairList.get(i), end, pairs, valuePairs, set, value * valueList.get(i));
            if(tmp != 0.0) break;
        }
        set.remove(start);
        return tmp;
    }
}

Familiarizing yourself with Venus

Task: Paste the contents of lab3_ex1.s in Venus and Record your answers to the following questions. Some of the questions will require you to run the RISC-V code using Venus’ simulator tab.

What do the .data, .word, .text directives mean (i.e. what do you use them for)? Hint: think about the 4 sections of memory.
.data: subsequent items put in user data segment; .word: Store the n 32-bit quantities in successive memory words; .text: subsequent items put in user text segment(machine code)

Run the program to completion. What number did the program output? What does this number represent?

34, the number represents the 9th fibonacci number

At what address is n stored in memory? Hint: Look at the contents of the registers.

at address 0x10000010

Without using the “Edit” tab, have the program calculate the 13th fib number (0-indexed) by manually modifying the value of a register. You may find it helpful to first step through the code. If you prefer to look at decimal values, change the “Display Settings” option at the bottom.

We can achieve this by mannualy manipulate the value of counter register t3 to 13

Translating from C to RISC-V

Task: Find/explain the following components of this assembly file.

The register representing the variable k.
The registers acting as pointers to the source and dest arrays.
The assembly code for the loop found in the C code.
How the pointers are manipulated in the assembly code.

Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example 1:

1
2

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2

Example 2:

1
2

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

Note:

• Each element in the result should appear as many times as it shows in both arrays.

• The result can be in any order.
  Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?

• What if nums1’s size is small compared to nums2’s size? Which algorithm is better?

• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

题意分析

寻找两个数组的交集，并以尽可能多的次数出现。首先考虑遍历其中一个数组，将各数字出现的次数保存在map中，然后对另外一个数组做遍历，若map含有这个key就加入到结果list中，并且该key对应的value值要减小1，若减小至0，则删除这个key。最后将list转为数组即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        // Construct map, key is integer, value is count
        for(int num : nums1) map.put(num, map.getOrDefault(num, 0) + 1);
        List<Integer> aux_list = new ArrayList<>();
        for(int num : nums2) {
            if(map.containsKey(num)) {
                aux_list.add(num);
                map.put(num, map.get(num) - 1);
                map.remove(num, 0);
            }
        }
        // Convert aux_list to array
        int[] result = new int[aux_list.size()];
        for(int i = 0; i < aux_list.size(); i++) {
            result[i] = aux_list.get(i);
        }
        return result;
    }
}