Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: 2, [[1,0]] 
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished   
             course 0. So the correct course order is [0,1] .

Example 2:

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both     
             courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. 
             So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .

Note:

1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
2. You may assume that there are no duplicate edges in the input prerequisites.

Solution:

class GraphNode {

    public:

    int val;

    vector<int> neighbors;

    GraphNode (int val) {

        val = val;

    }

};

class Solution {

private:

    

public:

    void topoSortDFS(int index, unordered_map<int, int>& visited,

                    vector<int>& ans, vector<GraphNode>& graph,

                    bool& cycle) {

        if (visited[index] == 2) {

            return;

        }

        

        if (visited[index] == 1) {

            cycle = true;

            return;

        }

        visited[index] = 1;

        for (int i = 0; i < graph[index].neighbors.size(); i++) {

            topoSortDFS(graph[index].neighbors[i], visited, ans, graph, cycle);

        }

        ans.push_back(index);

        visited[index] = 2;

        return;

    }

    

    void topoSort(vector<GraphNode>& graph,

                  unordered_map<int, int>& visited,

                  vector<int>& ans,

                bool& cycle) {

        for (int i = 0; i < graph.size(); i++) {

            topoSortDFS(i, visited, ans, graph, cycle);

        }

        return;

    }

    void prepareGraph(vector<GraphNode>& graph,

                      vector<vector<int>>& prerequisites) {

        for (int i = 0; i < prerequisites.size(); i++) {

            vector<int> neighbor = prerequisites[i];

            graph[neighbor[1]].neighbors.push_back(neighbor[0]);

        }

    }

    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {

        vector<int> ans;

        unordered_map<int, int> visited;

        bool cycle = false;

        for (int i = 0; i < numCourses; i++) {

            visited[i] = 0;

        }

        

        // Prepare graph.

        vector<GraphNode> graph;

        for (int i = 0; i < numCourses; i++) {

            GraphNode node = GraphNode(i);

            graph.push_back(node);

        }

        prepareGraph(graph, prerequisites);

        

        // ToPo Sort.

        topoSort(graph, visited, ans, cycle);

        if (cycle) {

            vector<int> empty;

            return empty;

        }

        reverse(ans.begin(), ans.end());

        return ans;

    }

};

=========== Another smaller one ========

class Solution { public: vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) { p_graph = vector<vector<int>>(numCourses); for (const auto& p : prerequisites) { p_graph[p[1]].push_back(p[0]); } vector<int> visit(numCourses, 0); for (int i = 0; i < numCourses; ++i) { if (dfs(i, visit)) return {}; } reverse(p_order.begin(), p_order.end()); return p_order; } private: vector<vector<int>> p_graph; vector<int> p_order; bool dfs(int cur, vector<int>& v) { if (v[cur] == 1) return true; if (v[cur] == 2) return false; v[cur] = 1; for (const auto& t: p_graph[cur]) { if (dfs(t, v)) return true; } v[cur] = 2; p_order.push_back(cur); return false; } };

Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Example: 

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:

If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n). 

class Solution {

public:

    int minSubArrayLen(int s, vector<int>& nums) {

        int ans = INT_MAX, sum = 0;

        int st = 0, end = 0;

        

        while (st < nums.size()) {

            if (sum >= s) {

                ans = min(ans, end - st);

                sum -= nums[st++];

            } else {

                if (end == nums.size()) {

                    break;

                }

                sum += nums[end++];

            }

        }

        return ans != INT_MAX ? ans : 0;

    }

};

======= Another Older one =======

class Solution {

public:

    int minSubArrayLen(int s, vector<int>& nums) {

        int sum = 0;

        int ans = INT_MAX;

        int beg = 0;

        if (nums.size() == 0) {

            return 0;

        }

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

            sum += nums[i];

            if (sum >= s) {

                ans = min(ans, i - beg + 1);

                while (beg <= i && sum - nums[beg] >= s) {

                    sum -= nums[beg];

                    beg++;

                    ans = min(ans, i - beg + 1);

                }

            }

        }

        return (ans == INT_MAX ? 0: ans);

    }

};

Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

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

class Solution { public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { vector<vector<int>> sol; if (nums.size() == 0) { return sol; } sort(nums.begin(), nums.end()); sol.push_back(vector<int>()); int beginning = 0, size; for (int i = 0; i < nums.size(); i++) { size = sol.size();
// Handle duplicate elements. if (i != 0 && nums[i] == nums[i - 1]) { // Start from the beginning of last insertion round. beginning = size - beginning; } else { // Start from beginning. beginning = 0; } for (int j = beginning; j < size; j++) { vector<int> tmp = sol[j]; tmp.push_back(nums[i]); sol.push_back(tmp); } // Adjust beginning for the next iteration. beginning = size - beginning; } return sol; } };

Peeking iterator

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation -- it essentially peek() at the element that will be returned by the next call to next().

---

Here is an example. Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].

Call next() gets you 1, the first element in the list.

Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.

You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.

Follow up: How would you extend your design to be generic and work with all types, not just integer?

// Below is the interface for Iterator, which is already defined for you.
// **DO NOT** modify the interface for Iterator.
class Iterator {
    struct Data;
Data* data;
public:
Iterator(const vector<int>& nums);
Iterator(const Iterator& iter);
virtual ~Iterator();
// Returns the next element in the iteration.
int next();
// Returns true if the iteration has more elements.
bool hasNext() const;
};


class PeekingIterator : public Iterator {
private:
    int pek;
    bool has_value;
public:
PeekingIterator(const vector<int>& nums) : Iterator(nums) {
    // Initialize any member here.
    // **DO NOT** save a copy of nums and manipulate it directly.
    // You should only use the Iterator interface methods.
        if (Iterator::hasNext()) {
            pek = Iterator::next();
            has_value = true;
        } else {
            has_value = false;
        }
}

    // Returns the next element in the iteration without advancing the iterator.
int peek() {
        if (has_value) {
            return pek;
        }
}

// hasNext() and next() should behave the same as in the Iterator interface.
// Override them if needed.
int next() {
        int old_peek = pek;
        if (Iterator::hasNext()) {
            has_value = true;
            pek = Iterator::next();
        } else {
            has_value = false;
        }
       
        return old_peek;
}

bool hasNext() const {
    return has_value;
}
};

Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

Example:

Given 1->2->3->4->5->NULL and k = 2,

return 4->5->1->2->3->NULL.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == NULL || k < 1) {
            return head;
        }
        ListNode *prev_head = head, *trav = head, *prev = NULL;
       
        int length = 0;
        while (trav != NULL) {
            length++;
            trav = trav -> next;
        }
        trav = head;
        k = length - (k % length);
       
        while (k > 0) {
            if (trav != NULL) {
                prev = trav;
                trav = trav -> next;
                k--;
            } else {
                trav = head;
            }
        }
        if (trav == NULL || prev == NULL) {
            return head;
        }
        head = trav;
        prev -> next = NULL;
       
        while (trav -> next != NULL) {
            trav = trav -> next;
        }
        trav -> next = prev_head;
        return head;
    }
};

Queue in c++

Class queue {
public:
   queue(int size): size(size), head(0), tail(0) {
   }
   bool is_full() {
      // or return ((tail + 1)%MAX_SIZE == head ? true : false);
      if(head == 0) {
         return tail == size - 1;
      } else {
         return tail == head - 1;
      }
   }

   bool empty() {
      return head == tail;
   }

   int front() {
       if (empty()) { //exception}
       return arr[head];
    }

   int back() {
       if (empty()) { //exception}
       return arr[tail];
    }

    void push(int val) {
        if (is_full())  {  //exception  }
        if (tail == size - 1) {
           tail = 0;
        } else {
           tail++;
        }
        arr[tail] = val;
    }

    void pop() {
       if (empty()) { //exception }
       if (head == size - 1) {
          head = 0;
       } else {
          head++;
       }
    }
   private:
      int size, head, tail;
      int arr[size];
};

===== Thread-Safe implementation using mutex and condition_variable.  ===
https://juanchopanzacpp.wordpress.com/2013/02/26/concurrent-queue-c11/

Topological Sort based on DFS

Class Node {
   int val;
   Node *child[];
   bool visited;
}

list<int> Toposort(list<Node *> graph) {   // list of node contains the graph head nodes.
   list<int> ans;
   for (int i = 0; i < graph.size(); i++) {
      dfs(graph[i], ans);
   }
   return ans;
}

void dfs(Node *head, list<int>& ans) {
   if (head == NULL || head -> visited) {
      return;
   }
   head -> visited = true;
   for (int i = 0; i < head->child.size(); i++) {
      if (!head->child[i] ->visited) {
         dfs(head->child[i], ans);
      }
       ans.front(head->val);   // Insert in front of list when node completes DFS traversal.
   }
}