This is study note when I’m learning machine learning course online. This course is taught by Andrew Ng.
For the first two weeks, it mainly talks about linear regression. Here are some important formulas: week-1-2
This is study note when I’m learning machine learning course online. This course is taught by Andrew Ng.
For the first two weeks, it mainly talks about linear regression. Here are some important formulas: week-1-2
Recently I’m researching on Database design. So I will write some knowledge when I’m learning. Today I will talk about the differences between ByteBuffer and DirectByteBuffer. We all know they can use to read and write data. And their differences are not hard to understand, here I draw a picture to explain everything.
Here we record some basic data structures which are easily involved in coding.
Map<Integer, Integer> tweets = new HashMap(); PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>(){ @Override public int compare(Integer a, Integer b) { return tweets.get(b) - tweets.get(a); // tweets.get(a)-tweets.get(b) is increasing/ascending // tweets.get(b)-tweets.get(a) is downing trend } }); pq.add(key); pq.poll(); //return head and delete head pq.peek(); // return head
Set set = new HashSet(); set.add("a"); set.remove("a"); Iterator iterator = set.iterator(); while(iterator.hasNext()) { String elem = iterator.next(); }
TreeMap tm = new TreeMap(); tm.put("a", 2); tm.put("b", 1); tm.get("a"); // return 2 tm.lastKey(); // return "b" tm.firstKey(); // return "a" tm.remove("a"); TreeMap<Integer, HashSet> t = new TreeMap(); // if HashSet's size is zero, we need to use t.remove(key) to remove this element in TreeMap. Because its null value will influence TreeMap's firstKey and lastKey result.
Arrays.asList("a", "b");// initialize List with values
// List to Array
lists.toArray(new String[lists.size()]);
For recursion method, we might need to copy the last result to current result. For example, for f(i-1), its result is left (List<Integer>) and for f(i), its result is to merge left with current value.
Wrong version:
List<List<Integer>> rec = new ArrayList<List<Integer>>(): rec.addAll(left); for(List<Integer> left: lefts) { left.add(nums[index]); rec.add(elem); }
Right version:
List<List<Integer>> rec = new ArrayList<List<Integer>>():
rec.addAll(left);
for(List<Integer> left: lefts) {
ArrayList<Integer> elem = new ArrayList<Integer>(left);
elem.add(nums[index]);
rec.add(elem);
}
The problem of the wrong version is that it will change left’s content. For example, if left=[[], [1]] and nums[1]=2, the wrong version’s output is [[2],[1,2],[2],[1,2]]. For the right version, it creates a new ArrayList to physically build a new list, so later add method won’t change original content. So the right output is [[], [1], [2], [1,2]].
Stack<String> s = new Stack(); s.push("zara"); s.peek(); s.pop();
int integer = 1;
String t = String.valueOf(integer);
The string is very common, so the only special point is to convert to char[] when needed.
char[] arr = str.toCharArray(); Arrays.sort(arr); String t = String.valueOf(arr); String t1 = new String(arr);
The more LeetCode questions we practice, the more rules we find. We can split all questions to serval categories, such as Stack, Map/HashMap, Dynamic Programming, etc. It looks good to use these existing data structure to improve the solution, but sometimes, we still need to build our own suitable data structure to fit some questions’ special scenario.
Today I take “Binary Tree Maximum Path Sum” as an example. (Later, I will enhance this post by adding more examples.)
Given a binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
For any node, it has two cases, one is single side(not circle), the other is go-through-circle. We need to record the two cases for each node and then to be provided to parent’s node to evaluate. So it is quite clear to solve the problem. Now you can use int[] which contains 2 elements to code it, but we all know it is not the good one and hard to read. The better solution is to build our own data structure to describe the two cases clearly.
private class ResultType { int singlePath, maxPath; ResultType(int singlePath, int maxPath) { this.singlePath = singlePath; this.maxPath = maxPath; } }
Here we conclude above two cases to two parameters: singlePath is to record the maximum path for single side(not circle) and maxPath to record the maximum value for the current node, including circle case and non-circle case. So the whole codes are here:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { private class ResultType { int singlePath, maxPath; ResultType(int singlePath, int maxPath) { this.singlePath = singlePath; this.maxPath = maxPath; } } public int maxPathSum(TreeNode root) { ResultType res = helper(root); return res.maxPath; } public ResultType helper(TreeNode root) { if (root == null) return new ResultType(Integer.MIN_VALUE, Integer.MIN_VALUE); ResultType left = helper(root.left); ResultType right = helper(root.right); int singlePath = Math.max(0, Math.max(left.singlePath, right.singlePath)) + root.val; int maxPath = Math.max(left.maxPath, right.maxPath); maxPath = Math.max(maxPath, Math.max(left.singlePath, 0)+ Math.max(right.singlePath, 0)+root.val); return new ResultType(singlePath, maxPath); } }
We see parent’s singlePath = Max(their children’s singlePath + root value) and parent’s maxPath = Max( children’s maxPath, children’s singlePath + root value).
Meanwhile, we comparing singlePath with zero, to determine whether to involve it or not.
Another clever point is to return Integer.MIN_VALUE, not zero for the empty node. This is very clever to solve the case, like only one node with a negative value. Because in this case, this negative value is still the maximum value for this node.
Today we talk about overflow. This is a very shy problem when interviewing. And it is also a very good way to distinguish whether you are a good programmer or just so-so programmer.
When I interviewed in a big company (I forgot its name, maybe eBay), the interviewer asked me to write a sum function. So easy?! In fact, No. You have to consider overflow for your solution.
First, let’s understand what’s overflow and what’s underflow. Overflow and underflow are related to a data type. Every data type has its own range. For example, int, in Java, you can use Integer.MIN_VALUE and Integer.MAX_VALUE to know its range. In Java arithmetic operators, it doesn’t report overflow and underflow problem and never throws an error exception. It just simply swallows it.
Second, there are several ways to avoid it.
Finally, I list my solution for LeetCode-576 (Out of Boundary Paths) (Here I don’t list the content of the question, you can read it from LeetCode’s website. ) to help you understand how to avoid overflow issue. Meanwhile, it is a good way to see how to use three dimensions array to fix the problem with dynamic programming method.
public class Solution { public int findPaths(int m, int n, int N, int i, int j) { final int MOD = 1000000007; if (N == 0) return 0; long[][][] dp = new long[m][n][N+1]; //k:1-N for(int ii=0; ii<m;ii++) { for(int jj=0; jj<n;jj++) { int count = 0; if (ii-1<0) count++; if (ii+1>=m) count++; if (jj-1<0) count++; if (jj+1>=n) count++; dp[ii][jj][1] = count; } } for(int k=2; k<=N;k++) { for(int ii=0; ii<m; ii++) { for(int jj=0; jj<n; jj++) { long count = 0; if (ii-1>=0) count += dp[ii-1][jj][k-1]; if (jj-1>=0) count += dp[ii][jj-1][k-1]; if (ii+1<m) count += dp[ii+1][jj][k-1]; if (jj+1<n) count += dp[ii][jj+1][k-1]; dp[ii][jj][k] = count%MOD; } } } long rec = 0; for(int k=1; k<=N; k++) { rec += dp[i][j][k]; } return (int)(rec%MOD); } }
Another simple LeetCode question also requires us to consider overflow issue: Valid Binary Search Tree. Here is the solution which considers using Long to replace Integer to avoid overflow.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isValidBST(TreeNode root) { return isValidBSTCheck(root, Long.MIN_VALUE, Long.MAX_VALUE); } public boolean isValidBSTCheck(TreeNode root, long min, long max) { if (root == null) return true; if (root.val > min && root.val < max) { return isValidBSTCheck(root.left, min, root.val) && isValidBSTCheck(root.right, root.val, max); } else return false; } }
For next following posts, I will write down some tips when coding. These are all summaries while I practice on LeetCode. I know there are so many LeetCode answers of questions online, but that is a just question-to-answer model. If we just read the question and then answer it, we never grow up fast. We need to know why others’ algorithm is faster than mine and what’s the differences between them; in future, how can we apply others’ good places into our own. So, let’s start!
We all know Map (key-value pair) is a good data structure to optimize algorithm speed sometimes. Because Map’s get speed is O(1) with well-designed hash function. But if we don’t write it well, it still might lose its advantage.
Map<Integer, List<Integer>> map = new HashMap();
// nums is a int[] array.
for(int i=0; i< nums.length; i++) {
List<Integer> value = new ArrayList();
value.add(nums[i]);
if (map.containsKey(i)) {
value.addAll(map.get(i));
}
map.put(i, value);
}
Map<Integer, List<Integer>> map = new HashMap();
for(int i=0; i<nums.length; i++) {
if (!map.containsKey(i)) {
map.put(i, new ArrayList<>());
}
map.get(i).add(nums[i]);
}
For small volume of data, this kind of advantage might be not too obvious, but for big data, the second version is much better than the first one.
It is quite easy to understand its improvement. For the first version, it has “addAll” to insert the whole list to another one. From physical side, we know it needs to handle a lot of things, such as allocating space. In fact, ArrayList.addAll already did some optimization, like allocating enough space to add every single element in one step, rather than having to reallocate multiple times if adding large numbers of elements. To avoid these things, the second version uses an empty data (” new ArrayList<>()” ) to well get rid of space allocation issue.
The Question requests to design a set data structure that supports all operations in average O(1) time.
List<Integer> data; public boolean insert(int val) { if (data.contains(val)) return false; else { data.add(val); return true; } } public boolean remove(int val) { if (data.contains(val)) { int index = data.indexOf(val); data.remove(index); return true; } else return false; }
List<Integer> data; Map<Integer, Integer> map; // to store val->index public boolean insert(int val) { if (map.containsKey(val)) return false; else { data.add(val); map.put(val, data.size()-1); return true; } } public boolean remove(int val) { if (!map.containsKey(val)) return false; else { int index = map.get(val); if (index != data.size()-1) { int lastValue = data.get(data.size()-1); data.set(index, lastValue); map.put(lastValue, index); } data.remove(data.size()-1); map.remove(val); return true; } }
We see the great difference between the two version is that we introduce a Map to store each value’s index; for remove function, we swap the target with the last element of the list and then finally delete the last one.
The reason we improve like this is to reach O(1) purpose. ArrayList’s indexOf and remove method are opposite with this target.
Each SSL Certification has its own valid date. When your server’s certification is expired, your website will be not visitable. In this case, you need to renew your expired certification. It is quite simple and easy. But Here I just write it down to record its steps.
openssl x509 -in domain.crt -noout -enddate
This step depends on your service, I mean which SSL service you get. For me, I get this service from Godaddy. I need to go to Godaddy to get new crt files. There are two crt files which you need to download.
And then you need to use SCP command to copy these files to your server. If you forget the target location, you just need to go to your Nginx’s conf file to check this parameter: ssl_certificate and you will know where to copy to.
Here is an example of SSL part in Nginx.
ssl on; ssl_certificate /etc/ssl/domain.crt; ssl_certificate_key /etc/ssl/domain.key;
Here ssl_certificate is your primary certificate; ssl_certificate_key should be the key file generated when you created the CSR.
Please note, this part is just to update expired SSL certificate so you don’t need to do anything on the key file.
In fact, you need to backup or remove the existing expired domain.crt first and the do concatenate. Just for safe.
cat 29393****.crt gd_bundle-g2-g1.crt >> domain.crt
sudo nginx -s reload