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.
   }
}

Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note: 
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

class Solution {

public:

    pair<int, int> findMax(vector<int>& nums, int st ,int end) {

        pair<int,int> ans = make_pair(INT_MIN, 0);

        // assuming k is always valid. i.e. less than nums.size().

        for (int i = st; i <= end; i++) {

            if (nums[i] > ans.first) {

                ans = make_pair(nums[i], i);

            }

        }

        return ans;

    }

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        vector<int> ans;

        

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

            return ans;

        }

        

        int st = 0, end = k - 1;

        pair<int,int> first_max = findMax(nums, st, end);

        ans.push_back(first_max.first);

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

            if (nums[i] > first_max.first) {

                first_max = make_pair(nums[i], i);

            } else if ((i - k) >= first_max.second) {

                first_max = findMax(nums, st + i - k + 1, end + i - k + 1);

            }

            ans.push_back(first_max.first);

        }

        return ans;

    }

};

Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int size = nums.size();
        vector<int> out(size, 1);
        int product = 1;
        for (int i = 1; i < size; i++) {
            product *= nums[i - 1];
            out[i] = product;
        }
        product = 1;
        for (int i = size - 2; i >= 0; i--) {
            product *= nums[i + 1];
            out[i] *= product;
        }
        return out;
    }
};

============= Another one ==========
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ans(nums.size(), 1);
        int i = 0, size = nums.size();
        int product = 1;
        while (i < size - 1) {
            product *= nums[i];
            ans[i + 1] = product;
            i++;
        }
        product = 1;
        while (i > 0) {
            product *= nums[i];
            ans[i - 1] *= product;
            i--;
        }
        return ans;
    }
};

================
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ans(nums.size(), 1);
        int prod = 1;
        for (int i = 0; i < nums.size() - 1; i++) {
            prod *= nums[i];
            ans[i + 1] = prod;
        }
       
        prod = 1;
        for (int i = nums.size() - 1; i > 0; i--) {
            prod *= nums[i];
            ans[i - 1] *= prod;
        }
        return ans;
    }
};

===========

class Solution {

public:

    vector<int> productExceptSelf(vector<int>& nums) {

        vector<int> output(nums.size(), 1);

        

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

            output[i] = nums[i - 1] * output[i - 1];

        }

        vector<int> output2(nums.size(), 1);

        for (int i = nums.size() - 2; i >= 0; i--) {

            output2[i] = nums[i + 1] * output2[i + 1];

        }

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

            output[i] *= output2[i];

        }

        return output;

        

        

        

    // space: efficient one

    /*

    vector<int> productExceptSelf(vector<int>& nums) {

        vector<int> ans(nums.size(), 1);

        int prod = 1;

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

            prod *= nums[i];

            ans[i + 1] = prod;

        }

        

        prod = 1;

        for (int i = nums.size() - 1; i > 0; i--) {

            prod *= nums[i];

            ans[i - 1] *= prod;

        }

        return ans;

    }

        

    */

    }

};