1. Storage and Data Management:
* Block Storage, Object Storage, File System Storage, Archive Storage
1. Compute:
* Capacity, Compute Engineering, Compute Product Management
1. Security Platform:
* Security Assurance, Security Products, Anti-Fraud, Compliance, Observability, Security Operations
1. Developer Services:
* Cloud Native Services, Console, Developer Life Cycle Services, Messaging, Strategic Engagements, Technical Content, UX
1. Enterprise Engineering, Developer Tools:
* Business Operations, Cloud Engineering and Apps, Collaborations Services, Corporate Apps, Endpoint and Security, Internal Builder Tools, Physical Infrastructure
1. Networking:
* Virtual Networking Core, Virtual Networking Edge, Load Balancers and WAF, DNS, Physical Network, Corporate Network, Product Management
1. AI/ML Data Services:
* Chief Data Scientist Applied Apps, Data Integration/Governance, AI Services, Big Data Services, AI/Data Science Platform

1. [a小於b大於c小於d大於e](#a小於b大於c小於d大於e)
2. [String to Integer](#StringToInteger)
3. [Snap shot array](#SnapShotArray)
4. [Largest BST in a binary tree](#Largest_BST_In_Binary_Tree)
5. [Meeting Room II](#Meeting_Room_II)
6. [Remove K digits](#Remove_K_digits)
7. [Reconstruct Itinerary](#Reconstruct_Itinerary)
8. [Exclusive Time of Functions](#Exclusive_Time_of_Functions)
9. [3 Sum](#3_Sum)
10. [Populating Next Right Pointers in Each Node](#Populating_Next_Right_Pointers_in_Each_Node)
11. [Basic Calculator II](#Basic_Calculator_II)
12. [Spiral Matrix](#Spiral_Matrix)

* [HashMap](#HashMap)
* [Process/Thread](#Process/Thread)
* [PUT/POST](#PUT/POST)
* [OracleDB](#OracleDB)
* [Software_Life_Cycle](#Software_Life_Cycle)
* [DDL_DML](#DDL_DML)
* [CAPS Theorem](#CAPS_Theorem)
* [VARCHAR_VARCHAR2](#VARCHAR_VARCHAR2)
## a小於b大於c小於d大於e
> 给一个int数组 让把这个数组arrange成[a < b > c < d > e < f]的格式

Sol: TC:O(n)
for (int i = 1; i < A.length; i+=2){
    // Find the biggest one among three numbers
    // If current odd element is smaller than previous
    if (A[i-1] > A[i] )
        swap(A, i, i-1);
    // If current odd element is smaller than next
    if (i + 1 < A.length && A[i] < A[i+1] )
        swap(A, i, i+1);
}

## StringToInteger
https://leetcode.com/problems/string-to-integer-atoi/

public int myAtoi(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }

    long res = 0;
    int index = 0;
    int sign = 1;

    while (index < s.length()) {
        while (index < s.length() && s.charAt(index) == ' ') {
            index++;
        }

        if (index < s.length() && (s.charAt(index) == '+' || s.charAt(index) == '-')) {
            sign = s.charAt(index) == '+' ? 1 : -1;
            index++;
        }

        while (index < s.length() && Character.isDigit(s.charAt(index))) {
            res = res * 10 + (s.charAt(index) - '0');
            if (res * sign >= Integer.MAX_VALUE) {
                return Integer.MAX_VALUE;
            }
            if (res * sign <= Integer.MIN_VALUE) {
                return Integer.MIN_VALUE;
            }
            index++;
        }

        return (int) (sign * res);
    }

    return 0;
}

## SnapShotArray
https://leetcode.com/problems/snapshot-array/

class SnapshotArray {
    // Time : Each call of get() cost O(snap_id), othersO(1);
    // Space: Total cost O(n), where n is number of calls of set().
    private List<Map<Integer, Integer>> shot;
    private Map<Integer, Integer> diff;
    
    public SnapshotArray(int length) {
        shot = new ArrayList<>();
        diff = new HashMap<>();
    }
    
    public void set(int index, int val) {
        diff.put(index, val);
    }
    
    public int snap() {
        shot.add(diff);
        diff = new HashMap<>();
        return shot.size() - 1;
    }
    
    // we only store the difference since previous snapshot; 
    // Therefore, if the value only changed on 1st snapshot, we would not get on current snap_id. 
    // Instead we have to go all way back to the search all previous snapshots. 
    // In case it fails to find any value, return default value of 0.
    
    public int get(int index, int snap_id) {
        for (int i = snap_id; i >= 0; i--) {
            if (shot.get(i).containsKey(index)) {
                return shot.get(i).get(index);
            }
        }
        
        return 0;
    }
}

## Largest_BST_In_Binary_Tree
https://www.techiedelight.com/find-size-largest-bst-in-binary-tree/

// A class to store information about a binary tree
class SubTreeInfo
{
	int min, max;
	int size;
	boolean isBST;
	Node root;
	SubTreeInfo(int min, int max, int size, boolean isBST, Node root)
	{
		this.min = min;
		this.max = max;
		this.size = size;
		this.isBST = isBST;
		this.root = root;
	}
}

public static SubTreeInfo findLargestBST(Node root)
{
    if (root == null) {
        return new SubTreeInfo(Integer.MAX_VALUE, Integer.MIN_VALUE, 0, true, null);
    }

    // Recur for the left and right subtrees
    SubTreeInfo left = findLargestBST(root.left);
    SubTreeInfo right = findLargestBST(root.right);

    SubTreeInfo info = null;

    // Check if a binary tree rooted under the current root is a BST

    // 1. Left and right subtree are also BST
    // 2. The value of the root node should be more than the largest value
    //	in the left subtree
    // 3. The value of the root node should be less than the smallest value
    //	in the right subtree
    if (left.isBST && right.isBST &&
        (root.data > left.max && root.data < right.min))
    {
        info = new SubTreeInfo(Math.min(root.data, Math.min(left.min, right.min)),
                               Math.max(root.data, Math.max(left.max, right.max)),
                               left.size + 1 + right.size,
                               true,
                               root);
    }
    else {
        // If a binary tree rooted under the current root is not a BST,
        // return the largest BST size in its left and right subtree
        if (left.size > right.size) {
            info = new SubTreeInfo(0, 0, left.size, false, left.root);
        } else {
            info = new SubTreeInfo(0, 0, right.size, false, right.root);
        }
    }

    return info;
}

## Meeting_Room_II
https://leetcode.com/problems/meeting-rooms-ii/
> Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Intuition: Track the change of room numbers in time order.

Explanation:

1. Save all time points and the change on current meeting rooms.
2. Sort all the changes on the key of time points.
3. Track the current number of using rooms cur and update result res.

public int minMeetingRooms(int[][] intervals) {
    Map<Integer, Integer> m = new TreeMap<>();
    for (int[] t : intervals) {
        m.put(t[0], m.getOrDefault(t[0], 0) + 1);
        m.put(t[1], m.getOrDefault(t[1], 0) - 1);
    }
    int res = 0, cur = 0;
    for (int v : m.values()) {
        res = Math.max(res, cur += v);
    }
    return res;
}

public int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);

    int rooms = 0;
    for (int[] interval : intervals) {
        int[] peek = pq.peek();
        if (pq.size() > 0 && interval[0] >= peek[1]) {
            pq.poll();
        }
        pq.add(interval);
        rooms = Math.max(rooms, pq.size());
    }

    return rooms;
}

public int minMeetingRooms2(int[][] intervals) {
    int[] starts = new int[intervals.length];
    int[] ends = new int[intervals.length];
    for (int i = 0; i < intervals.length; i++) {
        starts[i] = intervals[i][0];
        ends[i] = intervals[i][1];
    }

    Arrays.sort(starts);
    Arrays.sort(ends);

    int rooms = 0;
    int endsItr = 0;
    // whenever there's a end time precede start time, we need more rooms
    for (int i = 0; i < starts.length; i++) {
        if (starts[i] < ends[endsItr]) {
            rooms++;
        } else {
            endsItr++;
        }

    }
    return rooms;
}

## Remove_K_digits
https://leetcode.com/problems/remove-k-digits/
> 1. Let's think about the simplest case: how to remove 1 digit from the number so that the new number is the smallest possible？ Well, one can simply scan from left to right, and remove the first "peak" digit; the peak digit is larger than its right neighbor. One can repeat this procedure k times,

public String removeKdigits(String num, int k) {
    if (k == num.length()) {
        return "0";
    }

    Stack<Character> stack = new Stack<>();
    int i = 0;
    while (i < num.length()) {
        // whenever meet a digit which is less than the previous digit, discard the previous one
        while (k > 0 && !stack.isEmpty() && stack.peek() > num.charAt(i)) {
            // delete one digit
            stack.pop();
            k--;
        }
        stack.push(num.charAt(i));
        i++;
    }
    
    // 1. in case of 11111 (duplicate)
    // 2. in case of 12345 (ascending order number)
    while (k > 0) {
        stack.pop();
        k--;
    }

    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) {
        sb.append(stack.pop());
    }
    while (sb.length() > 1 && sb.charAt(sb.length() - 1) == '0') {
        sb.deleteCharAt(sb.length() - 1);
    }

    return sb.reverse().toString();
}

## Reconstruct_Itinerary
https://leetcode.com/problems/reconstruct-itinerary/
> 1. Build the graph from tickets
> 2. Sort the graph since it requires lexical order
> 3. DFS to traverse the path

public List<String> findItinerary(List<List<String>> tickets) {
    // build the graph
    Map<String, List<String>> map = new HashMap<>();
    for (List<String> ticket : tickets) {
        if (!map.containsKey(ticket.get(0))) {
            map.put(ticket.get(0), new ArrayList<>());
        }
        map.get(ticket.get(0)).add(ticket.get(1));
    }

    // sort the map by value
    for (Map.Entry<String, List<String>> entry : map.entrySet()) {
        Collections.sort(entry.getValue());
    }
    List<String> res = new ArrayList<>();
    findItineraryFrom("JFK", map, new ArrayList<>(), tickets.size(), res);
    res.add(0, "JFK");

    return res;
}

public void findItineraryFrom(String start, 
                              Map<String, List<String>> map, 
                              List<String> current, 
                              int numTickets,
                              List<String> res) {

    if (numTickets == current.size()) {
        res.addAll(current);
        return;
    }

    if (map.get(start) == null) {
        return;
    }

    for (int i = 0; i < map.get(start).size(); i++) {
        String dest = map.get(start).get(i);
        current.add(dest);
        map.get(start).remove(dest);
        findItineraryFrom(dest, map, current, numTickets, res);

        if (res.size() > 1) {
            return;
        }

        current.remove(current.size() - 1);
        map.get(start).add(i, dest);
    }
}

## Exclusive_Time_of_Functions
https://leetcode.com/problems/exclusive-time-of-functions/
> separate time to several intervals, add interval to their function

public int[] exclusiveTime(int n, List<String> logs) {
    int[] result = new int[n];
    Stack<Integer> st = new Stack<>();
    int pre = 0;
    // pre means the start of the interval
    for(String log: logs) {
        String[] arr = log.split(":");
        if(arr[1].equals("start")) {
            if (!st.isEmpty()) {
                result[st.peek()] += Integer.parseInt(arr[2]) - pre;
            }
            // arr[2] is the start of next interval, doesn't belong to current interval.
            st.push(Integer.parseInt(arr[0]));
            pre = Integer.parseInt(arr[2]);
        } else {
            result[st.pop()] += Integer.parseInt(arr[2]) - pre + 1;
            // arr[2] is end of current interval, belong to current interval. That's why we have +1 here
            pre = Integer.parseInt(arr[2]) + 1;
            // pre means the start of next interval, so we need to +1
        }
    }
    return result;
}

## 3_Sum
https://leetcode.com/problems/3sum/
> 1. Sort the array
> 2. Go through every num in the array, find the pair compensate for the num
> 3. Remember to remove duplicate cases

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(nums);

    for (int i = 0; i < nums.length; i++) {
        if (i == 0 || nums[i] != nums[i-1]) {
            int left = i + 1;
            int right = nums.length - 1;

            while (left < right) {
                if (nums[i] + nums[left] + nums[right] == 0) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                } else if (nums[i] + nums[left] + nums[right] > 0) {
                    right--;
                } else {
                    left++;
                }
            }
        }
    }

    return res;
}

## Populating_Next_Right_Pointers_in_Each_Node
https://leetcode.com/problems/populating-next-right-pointers-in-each-node/
> 1. Do level order traversal using queue
> 2. While traversing, add null to the end of every level

public Node connect(Node root) {
    if (root == null) {
        return null;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    // add null to end of every level
    queue.offer(null);
    while (queue.size() > 0) {
        if (queue.size() == 1 && queue.peek() == null) {
            break;
        }

        int size = queue.size();
        for (int i = 0; i < size; i++) {
            if (queue.peek() != null) {
                Node temp = queue.poll();
                temp.next = queue.peek();
                if (temp.left != null) {
                    queue.offer(temp.left);
                }
                if (temp.right != null) {
                    queue.offer(temp.right);
                }
            } else {
                queue.poll();
            }
        }
        // add null to end of every level
        queue.offer(null);
    }

    return root;
}

## Basic_Calculator_II
https://leetcode.com/problems/basic-calculator-ii/
> Example 1:
> Input: s = "3+2*2"
> Output: 7

> Example 2:
> Input: s = " 3/2 "
> Output: 1

public int calculate(String s) {
    char operation = '+';
    int curNum = 0;
    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i < s.length(); i++) {
        char ch = s.charAt(i);
        if (ch >= '0' && ch <= '9') {
            curNum = curNum * 10 + (int) ch - '0';
        } else if (ch != ' ') {
            stack.push(calculate(operation, curNum, stack));
            operation = ch;
            curNum = 0;
        }
    }

    stack.push(calculate(operation, curNum, stack));

    int res = 0;
    while (!stack.isEmpty()) {
        res += stack.pop();    
    }

    return res;
}

public int calculate(Character operation, int curNum, Stack<Integer> stack) {
    switch (operation) {
        case '+': return curNum;
        case '-': return -curNum;
        case '*': return stack.pop() * curNum;
        case '/': return stack.pop() / curNum;
        default : throw new RuntimeException();
    }
}

## Spiral_Matrix
https://leetcode.com/problems/spiral-matrix/

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> res = new LinkedList<>(); 
    if (matrix == null || matrix.length == 0) return res;
    int n = matrix.length, m = matrix[0].length;
    int up = 0,  down = n - 1;
    int left = 0, right = m - 1;
    while (res.size() < n * m) {
        for (int j = left; j <= right && res.size() < n * m; j++)
            res.add(matrix[up][j]);

        for (int i = up + 1; i <= down - 1 && res.size() < n * m; i++)
            res.add(matrix[i][right]);

        for (int j = right; j >= left && res.size() < n * m; j--)
            res.add(matrix[down][j]);

        for (int i = down - 1; i >= up + 1 && res.size() < n * m; i--) 
            res.add(matrix[i][left]);

        left++; right--; up++; down--; 
    }
    return res;
}

## HashMap
* HashMap is a part of java.util package.
* HashMap **extends an abstract class AbstractMap** which also provides an incomplete implementation of Map interface.
* It also implements **Cloneable** and **Serializable** interface. K and V in the above definition represent Key and Value respectively.
HashMap **allows null key also but only once** and multiple null values.
* This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time. It is roughly similar to HashTable but is unsynchronized.
* hash code of null key is 0.

> HashMap contains an array of Node and a node is represented as a class
> It can be seen that the node is containing a reference to its own object. So it’s a linked list.
> 
> 

1. Hashcode(): Get the hashcode of the object
2. equals(): Check that 2 objects are equal or not.
3. Buckets: A bucket is part of the map, used to store nodes
* capacity = number of buckets * load factor
4. Index:
> Hash code of key may be large enough to create an array. hash code generated may be in the range of integer and if we create arrays for such a range, then it will easily cause outOfMemoryException. So we generate index to minimize the size of array.
>
> index = hashCode(key) & (n-1

Put():
1. Calculate hash code of Key. 
2. Calculate index by hash code
3. Create a node object

Collision: Two objects has same hash code
If a collision happend, check via hashCode() and equals() method that if both the keys are same.
If keys are same, replace the value with current value.
Otherwise connect this node object to the previous node object via linked list

Get():
1. Calculate hash code of Key
2. Calculate index by hash code
3. Go to index of array and compare first element’s key with given key. 
   If both are equals then return the value, otherwise check for next element if it exists.
   

## Process/Thread

## PUT/POST
* Idempotent: If you request many times, the state won't change

> PUT is for full update
>PATCH is for customize update


## OracleDB

# Features_of_Oracle
* **Scalability and Performance**: Features like Real Application Clustering and Portability make an Oracle database scalable according to the usage. In a multiuser database, it is required to control data consistency and concurrency which are contemplated by Oracle.
* **Availability**: Real-time applications require high data availability. High performing computing environments are configured to provide all-time data availability. Data is available during the time of planned or unplanned downtimes and failures.
* **Backup and Recovery**: Its layout complete recovery features to recover data from almost all kinds of failures. In case of failure, the database needs to be recovered within no time for high availability. Unaffected parts of data are available while the affected ones are getting recovered.
* **Security**: Securing the data is always the top priority. Oracle provides mechanisms to control data access and usage. Implementing authorization and editing user actions can prevent unauthorized access and allow distinct access to the users.

# Benefits

1. Performance: It has methodologies and principles to achieve high performance. We can implement performance tuning in its database to retrieve and alter data faster, in order to improve query execution time and hence application operations.

2. Multiple Database: Its database supports managing multiple database instances on a single server. Instance Caging method is provided by Oracle to manage CPU allocations on a server running the database instances. Instance caging works with the database resource manager to manage services over multiple instances.

3. Editions: As we discussed above, about the different editions which are offered by Oracle, it gives benefit to the users to purchase edition as per their application requirements. They can seamlessly update the edition if their requirements change in the future. If you want to learn and do some hands-on Oracle, you can download and install the express edition database which is absolutely free.

4. Clusters: It uses Real Application Clusters to provide a high data availability system. The database with RAC has benefits over traditional database servers :

> Scaling the database over multiple instances.
> Load balancing
> Data redundancy and availability
> Flexible to increase processing capacity
5. Failure Recovery: RMAN (Recovery Manager) is the feature of an Oracle DB which recover or restore the database files during downtimes and outages. It supports online, archived backups and continuous archiving. Users can also SQL* PLUS for recovery, called as user-managed recovery, which is supported by it. There is an export utility available in the database to add user-managed backups.

6. PL/SQL: The database supports PL/SQL extension for procedural programming.

## Software_Life_Cycle

## DDL_DML

## CAPS_Theorem



## VARCHAR_VARCHAR2