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

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;

    }

        

    */

    }

};