LeetCode 674 - Longest Continuous Increasing Subsequence

https://leetcode.com/problems/longest-continuous-increasing-subsequence/

Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray).

Example 1:

Input: [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3. 
Even though [1,3,5,7] is also an increasing subsequence, it's not a continuous one where 5 and 7 are separated by 4. 

Example 2:

Input: [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2], its length is 1. 

Note: Length of the array will not exceed 10,000

https://leetcode.com/articles/longest-continuous-increasing-subsequence/

  public int findLengthOfLCIS(int[] nums) {

    int ans = 0, anchor = 0;

    for (int i = 0; i < nums.length; ++i) {

      if (i > 0 && nums[i - 1] >= nums[i])

        anchor = i;

      ans = Math.max(ans, i - anchor + 1);

    }

    return ans;

  }

https://leetcode.com/problems/longest-continuous-increasing-subsequence/discuss/107352/Java-code-6-liner

public int findLengthOfLCIS(int[] nums) {
        if(nums.length==0) return 0;
        int length=1,temp=1;
        for(int i=0; i<nums.length-1;i++) {
            if(nums[i]<nums[i+1]) {temp++; length=Math.max(length,temp);}
            else temp=1; 
        }
        return length;
    }

follow up1 要求subsequence中前后两个元素最⼤大间隔为1
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/untag/LCIS%20Gap%20One/LCISGapOne.java

    public int findLengthOfLCIS(int[] nums) {
        if (nums.length < 2) return nums.length;
        int pp = 1;
        int p = nums[0] < nums[1] ? 2 : 1;
        int ans = p;
        
        for (int i = 2; i < nums.length; i ++) {
            int tmp = 1;
            if (nums[i - 2] < nums[i] && pp + 1 > tmp) tmp = pp + 1;
            if (nums[i - 1] < nums[i] && p  + 1 > tmp) tmp = p  + 1;
            ans = Math.max(ans, tmp);
            pp = p; p = tmp;
        }
        
        return ans;
    }

follow up2 要求subsequence中前后两个元素最⼤大间隔为k
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/untag/LCIS%20Gap%20One/LCISGapK.java

    public int findLengthOfLCIS(int[] nums, int k) {
        if (nums.length == 0) return 0;
        
        int[] f = new int[nums.length];
        Arrays.fill(f, 1);      // every number itself can be a shortest increasing subsequence
        
        int ans = 1;
        for (int i = 1; i < nums.length; i ++) {
            for (int j = Math.max(0, i - k - 1); j < i; j ++)   // the limit of gap k
                if (nums[i] > nums[j])                          // make sure subsequence is increasing
                    f[i] = Math.max(f[i], f[j] + 1);
            ans = Math.max(ans, f[i]);                  // update result
        }
        return ans;
    }

follow up3 允许⼀一个break Example:
Input: [7, 3, 2, 3, 5, 6, 4, 2, 1]
Output: 5 - [2, 3, 5, 6, 4], [6, 4] is the break OR [3, 2, 3, 5, 6], [3,2] is the break
要有⼀一个变量量判断当前状态是否break过, 还有breaking index是另⼀一个 subarray的开始

Implement Queue with Limited Size of Array - Airbnb

https://leetcode.com/discuss/interview-question/156969/Implement-Queue-using-fixed-size-array/

Assume in your programming language you only have a fixed size array of length 5. Implement a queue datastructure that can get unlimitted number of elements.

Assumption: The arrays hold 5 elements, each of which is the size of a pointer.
Our first level of abstraction is to use our stupid arrays to make a less stupid array, which has access in log(N) time.
Once we have an Array, with all of the capabilities of your typical array, implementing a queue, stack, deque, whatever, will be the normal way of doing so.

class Array {
    Array(int size) {
        this->size = size;
        
        depth = max(0, log5(size)-1); // Depth 0 is for size <= 5
        build_array(depth, head);
    }

    // Will hold 5^depth elements, which is likely greater than size, but you know
    // what they say about premature optimization
    void build_array(int depth, stupid_array arr) {
        if (depth == 0) return;
        for i = 0 to 4 {
            arr[i] = new stupid_array;
            build_array(depth-1, arr[i]);
        }
    }

    (stupid_array, int) find_index(int idx)
    {
        return find_index(0, idx, head);
    }

    (stupid_array, int) find_index(int d, int idx, stupid_array arr)
    {
        int net_depth = depth - d;
        int subarray_size = pow(5, net_depth-1);
        if (subarray_size == 1) {
            return (head, idx);
        }

        return find_index(d+1, idx % subarray_size, arr[idx / subarray_size]);
    }

    insert(void * value, int idx) {
        stupid_array subarr;
        int subidx;
        (subarr, subidx) =  find_index(idx);
        subarr[subidx] = value;
    } 

    void * get(int idx) {
        stupid_array subarr;
        int subidx;
        (subarr, subidx) =  find_index(idx);
        return subarr[subidx];
    }

    stupid_array head;
    int size, depth;
}

Now that we have an array that has a normal interface, and which has reasonably fast access of O(log(N)), we can easily create a queue

https://github.com/allaboutjst/airbnb

Implement a queue with a number of arrays, in which each array has fixed size.

2.Implement Queue with limited size of array: 使用double linkedlist

2. Implement Queue with limited size of array：方法二 ListNode with fixed size of array

https://github.com/allaboutjst/airbnb/blob/master/src/main/java/implement_queue_with_fixed_size_of_arrays/ImplementQueuewithFixedSizeofArrays.java

    public class QueueWithFixedArray {
        private int fixedSize;

        private int count;
        private int head;
        private int tail;
        private List<Object> headList;
        private List<Object> tailList;

        public QueueWithFixedArray(int fixedSize) {
            this.fixedSize = fixedSize;
            this.count = 0;
            this.head = 0;
            this.tail = 0;
            this.headList = new ArrayList<>();
            this.tailList = this.headList;
        }

        public void offer(int num) {
            if (tail == fixedSize - 1) {
                List<Object> newList = new ArrayList<>();
                newList.add(num);
                tailList.add(newList);
                tailList = (List<Object>) tailList.get(tail);
                tail = 0;
            } else {
                tailList.add(num);
            }
            count++;
            tail++;
        }

        public Integer poll() {
            if (count == 0) {
                return null;
            }

            int num = (int) headList.get(head);
            head++;
            count--;

            if (head == fixedSize - 1) {
                List<Object> newList = (List<Object>) headList.get(head);
                headList.clear();
                headList = newList;
                head = 0;
            }

            return num;
        }

        public int size() {
            return count;
        }
    }

TODO:
http://fabian-kostadinov.github.io/2014/11/25/implementing-a-fixed-length-fifo-queue-in-java/

Minimum Vertices to Traverse Directed Graph - Airbnb

https://leetcode.com/discuss/interview-question/124861/digraph-cover-all-vertices-with-the-least-number-of-vertices

Given a directed graph G (can contain sub graphs and cycles), find the minimum number of vertices from which all nodes are reachable.

For example:

Nodes:
    0, 1, 2, 3, 4, 5

Edges:
    1 <- 0
    0 <- 1 <- 2
    3 <- 1 <- 2
    2 <- 5
    4 <- 5

Representation:
    --> 4
  /
 5 --> 2 --> 1 <--> 0
              \
                --> 3
Matrix:
g = [[1, 1, 0, 0, 0, 0],
     [1, 1, 1, 0, 0, 0],
     [0, 0, 1, 0, 0, 1],
     [0, 1, 0, 1, 0, 0],
     [0, 0, 0, 0, 1, 1],
     [0, 0, 0, 0, 0, 1]]

Return 1 (node number 5). From node number 5 all other nodes are reachable.

If we remove edge 2 <- 5, the result is 2, because we need at least nodes number 5 and 2 to visit all nodes.

Representation of the graph if we remove the edge between nodes 2 and 5.

 5 --> 4

 2 --> 1 <--> 0
        \
          --> 3

I attempted to solve this problem by finding for every node j, and array of all nodes reachable from j. Basically, I did a DFS on every node, and the result looks like this:

{
    0: [True, True, False, True, False, False],
    1: [True, True, False, True, False, False],
    2: [True, True, True, True, False, False],
    3: [False, False, False, True, False, False],
    4: [False, False, False, False, True, False],
    5: [True, True, True, True, True, True]
}

This means that from node 0, I can reach nodes number 0, 1, 3. From node 1 I can reach nodes 0, 1 and 3. From node 5, I can reach all nodes.

Is this a good approach to solve the problem? Having this dictionary, how can I find the smallest group of nodes from which I can reach all nodes?

It's the number of strongly-connected components that aren't reachable from any outside vertex.

http://www.geeksforgeeks.org/strongly-connected-components/

What if you found all vertices with no incoming edges and started BFS from those vertices? If you run out of vertices with no incoming edges, then that means the rest of the vertices are either in a cycle or completely separated.

Each time you have to search from a new vertex, you would add 1 to your overall total vertices required.

Effectively you would run DFS on each "connected component", making the overall runtime O(E + V) to find the number of necessary vertices to explore all other vertices.

Is this a viable solution or am I mistaken?

https://github.com/allaboutjst/airbnb/blob/master/README.md

Given a directed grapjh, represented in a two dimension array, output a list of points that can be used to travese every points with the least number of visited vertices.

https://github.com/allaboutjst/airbnb/blob/master/src/main/java/minimum_vertices_to_traverse_directed_graph/MinimumVerticestoTraverseDirectedGraph.java

        private void search(Set<Integer> res, Map<Integer, Set<Integer>> nodes, int cur, int start,
                            Set<Integer> visited, Set<Integer> currVisited) {
            currVisited.add(cur);
            visited.add(cur);
            for (int next : nodes.get(cur)) {
                if (res.contains(next) && next != start) {
                    res.remove(next);
                }
                if (!currVisited.contains(next)) {
                    search(res, nodes, next, start, visited, currVisited);
                }
            }
        }

        public List<Integer> getMin(int[][] edges, int n) {
            Map<Integer, Set<Integer>> nodes = new HashMap<>();
            for (int i = 0; i < n; i++) {
                nodes.put(i, new HashSet<>());
            }
            for (int[] edge : edges) {
                nodes.get(edge[0]).add(edge[1]);
            }

            Set<Integer> visited = new HashSet<>();
            Set<Integer> res = new HashSet<>();
            for (int i = 0; i < n; i++) {
                if (!visited.contains(i)) {
                    res.add(i);
                    visited.add(i);
                    search(res, nodes, i, i, visited, new HashSet<>());
                }
            }

            return new ArrayList<>(res);
        }

https://rextester.com/discussion/NJE76317/Minimum-Vertices-to-Traverse-Directed-Graph