Stream

The heavy hitter problem

找出流中出现次数超过 (n/k)次的单词

vector<string> SearchFrequentItems(int k, istringstream* sin) {
  string buf;
  unordered_map<string, int> hash;
  int n = 0;  // Count the number of strings.

  while (*sin >> buf) {
    ++hash[buf], ++n;
    // Detecting k items in hash, at least one of them must have exactly
    // one in it. We will discard those k items by one for each.
    if (hash.size() == k) {
      auto it = hash.begin();
      while (it != hash.end()) {
        if (--(it->second) == 0) {
          hash.erase(it++);
        } else {
          ++it;
        }
      }
    }
  }

  // Resets hash for the following counting.
  for (auto& it : hash) {
    it.second = 0;
  }

  // Resets the stream and read it again.
  sin->clear();
  sin->seekg(0, ios::beg);
  // Counts the occurrence of each candidate word.
  while (*sin >> buf) {
    auto it = hash.find(buf);
    if (it != hash.end()) {
      ++it->second;
    }
  }

  // Selects the word which occurs > n / k times.
  vector<string> ret;
  for (const auto& it : hash) {
    if (it.second > static_cast<double>(n) / k) {
      ret.emplace_back(it.first);
    }
  }
  return ret;
}

295. Find Median from Data Stream

class MedianFinder {
public:

    // Adds a number into the data structure.
    void addNum(int num) {
        if (left_half.empty() || num > left_half.top()) {
            right_half.push(num);
            while (left_half.size() < right_half.size()) {
                left_half.push(right_half.top());
                right_half.pop();
            }
        } else {
            left_half.push(num);
            while (left_half.size() > right_half.size() + 1) {
                right_half.push(left_half.top());
                left_half.pop();
            }
        }
    }

    // Returns the median of current data stream
    double findMedian() {
        if ((left_half.size() + right_half.size())&0x1) {
            return left_half.top();
        } else {
            return (left_half.top() + right_half.top()) / 2.0;
        }
    }
private:
    priority_queue<int> left_half;
    priority_queue<int, vector<int>, greater<int>> right_half;
};

447 Search in a Big Sorted Array

Given a big sorted array with positive integers sorted by ascending order. The array is so big so that you can not get the length of the whole array directly, and you can only access the kth number by ArrayReader.get(k) (or ArrayReader->get(k) for C++). Find the first index of a target number. Your algorithm should be in O(log k), where k is the first index of the target number.

Return -1, if the number doesn't exist in the array.

class Solution {
public:
    /**
     * @param reader: An instance of ArrayReader.
     * @param target: An integer
     * @return: An integer which is the first index of target.
     */
    int searchBigSortedArray(ArrayReader *reader, int target) {
        // write your code here
        if (!reader) return -1;
        int p = 0;
        while (true) {
            int idx = (1 << p) - 1;
            int val = reader->get(idx);
            if (val == -1 || val > target) break;
            if (val == target) return idx;
            ++p;
        }

        int left = max(0, 1 << (p-1));
        int right = max(0, (1<<p) - 2);
        int res = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = reader->get(mid);
            if (val == target) {
                res = mid;
                right = mid - 1;
            }
            else if (val > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }

        }

        return res;
    }
};