hle46

// Time complexity: n*log(k)
// Space complexity: O(n)
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> myMap;
        for (int num : nums) {
            ++myMap[num];
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

hle46

# Time Complexity: n*O(k)
#                  heapq.nlargest builds min heap of k elements 
#                  for each other elements, push new element and pop smallest element
# Space Complexity: O(n)
from collections import defaultdict
class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int

hle46

# Time Complexity: O(1) for move
# Space Complexity: O(n)
class TicTacToe(object):

    def __init__(self, n):
        """
        Initialize your data structure here.
        :type n: int
        """
        self.n = n

hle46

# Time Complexity: next: O(1)
from collections import deque
class MovingAverage(object):

    def __init__(self, size):
        """
        Initialize your data structure here.
        :type size: int
        """
        self._size = size

hle46

/* Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

 * For example,
 * MovingAverage m = new MovingAverage(3);
 * m.next(1) = 1
 * m.next(10) = (1 + 10) / 2
 * m.next(3) = (1 + 10 + 3) / 3
 * m.next(5) = (10 + 3 + 5) / 3
 * Company Tags: Google
 * Tags: Design, Queue

hle46

#include <cstdio>
#include <iostream>
#include <iterator>
#include <string>
#include <fstream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <future>

hle46

#include <iostream>
#include <numeric>
using namespace std;
int main() {
	istream_iterator<int> in(cin), eof;
	cout << accumulate(in, eof, 0) << endl;
}

hle46

/* Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

 * The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

 * Company Tags: Amazon, Bloomberg, Google
 * Tags: Stack, String
 * Similar Problems: (M) Generate Parentheses, (H) Longest Valid Parentheses, (H) Remove Invalid Parentheses
 */
class Solution {
public:

hle46

/* Given a linked list, remove the nth node from the end of list and return its head.

 * For example,

 *   Given linked list: 1->2->3->4->5, and n = 2.

 *   After removing the second node from the end, the linked list becomes 1->2->3->5.
 * Note:
 * Given n will always be valid.
 * Try to do this in one pass.

hle46

/* Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? 
 * Find all unique quadruplets in the array which gives the sum of target.

 * Note:
 * Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
 * The solution set must not contain duplicate quadruplets.
 *    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
 *
 *    A solution set is:
 *    (-1,  0, 0, 1)