# 学海无涯

### SQL/MySQL quick review

准备twitter OA的过程里多练习下SQL语句，顺便简单粗暴地学下MySQL。

when count(x) = 0, but need to print out 0. Use LEFT/RIGHT JOIN.

e.g. count (#students) = 0 group by dept_id —– dept_id’s table left join students table

ORDER BY – follow two orders, e.g. ORDER BY student_id desc, dept_id asc

LIMIT —

- The
`LIMIT`

clause can be used to constrain the number of rows returned by the`SELECT`

statement.`LIMIT`

takes one or two numeric arguments, which must both be nonnegative integer constants. - the first argument specifies the offset of the first row to return, and the second specifies the maximum number of rows to return. The offset of the initial row is 0 (not 1)
- SELECT * FROM tbl LIMIT 5,10; # Retrieve rows 6-15
- SELECT * FROM tbl LIMIT 5; # Retrieve first 5 rows

DISPLAY “NULL” — SELECT “anything-that-is-null” AS “title-as-needed”

GROUP BY and HAVING — use GROUP BY to organize the data and HAVING as a filter

### Valid Parentheses

Problem:

Given a string containing just the characters `'('`

, `')'`

, `'{'`

, `'}'`

, `'['`

and `']'`

, determine if the input string is valid.

The brackets must close in the correct order, `"()"`

and `"()[]{}"`

are all valid but `"(]"`

and `"([)]"`

are not.

Solution:

class Solution {

public boolean isValid(String s) {

Stack<Character> st = new Stack<Character>();

for (char c : s.toCharArray()) {

if (c == ‘(‘) {

st.push(‘)’);

} else if (c == ‘[‘) {

st.push(‘]’);

} else if (c == ‘{‘) {

st.push(‘}’);

} else if (st.empty() || st.pop() != c) {

return false;

}

}

return st.empty();

}

}

The stack idea is crucial to this problem. For each character, if it’s the first half of parentheses, then it matters whether the next char is the other half of parenthese. Therefore the adjacent element matters in this case and the push and pop from stack are useful.

Then the next step is to figure out several cases to decide true or false.

- no parentheses exist or only the other halves exist
- only the first halves exist
- parenthese don’t close
- parenthese all close but other chars exist

### Insersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3

begin to intersect at node c1.

**Notes:**

- If the two linked lists have no intersection at all, return
`null`

. - The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Your code should preferably run in O(n) time and use only O(1) memory.

public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {public static ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) {return null;}

int lenA = getLen(headA); int lenB = getLen(headB); while (headA != null && headB != null) { if (lenA > lenB) { headA = headA.next; lenA -= 1; } else if (lenA < lenB) { headB = headB.next; lenB -= 1; } else { if (headA == headB) { return headA; } headA = headA.next; headB = headB.next; lenA -= 1; lenB -= 1; } }

return null; } public static int getLen(ListNode head) { int len = 0; while (head != null) { len += 1; head = head.next; } return len; }

This problem is about traversing the linked list. Use the length of the list to mark the progress. My way of solution is a common one and the complexity is O(m+n).

### Semaphores in Java

References:

java-util-concurrency-semaphore

Semaphores have two usages:

- Guard the critical section and resources, to provide the mutual exclusion
- Send signals between two processes or threads

In the constructor, one can specify the fairness settings. Fairness is each time when a permit is released, the longest thread waiting in queue will acquire it. This can guarantee no thread needs to wait in the queue all the time. Therefore, starvation can be prevented in this way.

### Linked List Cycle

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

public class Solution {

public boolean hasCycle(ListNode head) {

if (head == null || head.next == null) {return false;}

ListNode slow = head;ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) {return true;} } return false;

}}

A nice trick about Linked List is the slow and fast pointers/runners. If both runners start at the same nodes, sooner or later they’ll meet at a specific node with the existence of the cycle. If there’s no cycle, then the fast runner will encounter null finally. Since fast.next also needs to visit its own next node, so the null check is also needed for fast.next. This case must be included in the condition of ending while-loop.

Be careful about the edge cases. The null list or single node list request the specific null check. Also, when there are only two nodes in the list, the slow and fast runners start at the same node. So the condition check of slow == fast is put after they both go forward their steps (I used “slow = head; fast = head”, if using “slow = head; fast = head.next”, will be different).

### BST to Greater Tree

/* Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST. Example: Input: The root of a Binary Search Tree like this: 5 / \ 2 13 Output: The root of a Greater Tree like this: 18 / \ 20 13 */ public class convertBST{ static int sum = 0; // trace the sum of previous nodes public static TreeNode convertBST(TreeNode root) { if (root == null) {return null;} convert(root); return root; } public static void convert(TreeNode node) { if (node == null) {return;} convert(node.right); sum += node.val; node.val = sum; convert(node.left); } public static void main(String[] args) { } } class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }

In a BST, every node only needs to add the values of nodes on the right. So use recursion to find the rightmost node first. Use a variable “sum” to store the accumulating values. Each time use “sum” to replace current value. Nothing to be accumulated to the left side.

### Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST. 1 2 3 4 5 6 7 8 4 2 6 1 3 5 7 8 1 2 3 4 5 6 7 8 9 10 11 12 6 3 9 1 4 7 11 2 5 8 10 12 */ public class sortedArrayToBST{ public static TreeNode sortedArrayToBST(int[] nums) { if (nums.length == 0) {return null;} int low = 0; int high = nums.length - 1; return helper(nums, low, high); } public static TreeNode helper(int[] nums, int l, int h) { if (l > h) {return null;} int m = (l + h) / 2; TreeNode root = new TreeNode (nums[m]); root.left = helper(nums, l, m - 1); root.right = helper(nums, m + 1, h); return root; } public static void main(String[] args) { int[] a = new int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}; TreeNode root = sortedArrayToBST(a); } } class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }