#include <stdio.h>
#include <stdlib.h>
// To execute C, please define "int main()"
static char buffer[256];
struct LinkNode {
int start;
int end;
struct LinkNode *next;
};
static struct LinkNode *free_header = NULL;
void initFreeMemory();
void *allocate(int size);
int main() {
initFreeMemory();
printf("%p\n", buffer);
void *addr1 = allocate(3);
printf("%p\n", addr1);
void *addr2 = allocate(128);
printf("%p\n", addr2);
printf("%p\n", buffer+free_header->start);
return 0;
}
void initFreeMemory() {
free_header = (struct LinkNode *)malloc(sizeof(struct LinkNode));
free_header->start = 0;
free_header->end = 256;
free_header->next = NULL;
}
void *allocate(int size) {
struct LinkNode *p = free_header;
while (p) {
if (p->end - p->start >= size) break;
p = p->next;
}
if (p == NULL) return NULL;
void *ret = buffer+p->start;
p->start += size;
return ret;
}
/*void free(void *object) {
int size = sizeof(object);
struct LinkNode *node = malloc(sizeof(struct LinkNode));
node->start = object;
node->end = node->start + size;
free_header->next = node;
}*/
Showing posts with label design. Show all posts
Showing posts with label design. Show all posts
Wednesday, August 10, 2016
Memory Allocator
This question is asked in one of my phone interview. The question is "To implement a memory allocator that allows multiple clients to allocate and free memory from a buffer". My initial thought is the maintain a front and rear pointer and make the buffer as a ring. However, such design doesn't satisfy the requirement because there are multiple users for example, user1 has requested buffer[0-3], user2 has requested buffer[4-6] and user3 has requested buffer[7]. When user2 releases his buffer before user3, you'll get a problem because of memory fragmentation. You can't simply move the front pointer back to 4 because it'll release user3's buffer which is being used currently. So I thought of the way how Linux kernel maintains the memory. I'll need a pointer that maintains a list of free memory chunk. Yes, it is a linked list because of the memory fragmentation. When you request a piece of memory, you'll check the list to see if there is any memory fragment that has enough space for the request. If so, update the offset pointer for that node. Otherwise, return NULL pointer.
Monday, August 8, 2016
379. Design Phone Directory
I was thinking to build up a hash table for every number in the construction function. However, it turns out too costly. Actually, I only needs to have two arrays, with one storing numbers and another storing used tag. The idea behind is that we really don't have to care about the order of number that we dispensed and even who got the number. So don't think over too much. It's a very simple design.
1: class PhoneDirectory {
2: private:
3: vector<int> numbers;
4: vector<bool> used;
5: int front;
6: int maxNumbers;
7: public:
8: /** Initialize your data structure here
9: @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
10: PhoneDirectory(int maxNumbers) {
11: this->maxNumbers = maxNumbers;
12: numbers = vector<int>(maxNumbers, 0);
13: used = vector<bool>(maxNumbers, false);
14: front = 0;
15: for (int i = 0; i < maxNumbers; i++) {
16: numbers[i] = i;
17: }
18: }
19: /** Provide a number which is not assigned to anyone.
20: @return - Return an available number. Return -1 if none is available. */
21: int get() {
22: if (front == maxNumbers) return -1;
23: int ret = numbers[front++];
24: used[ret] = true;
25: return ret;
26: }
27: /** Check if a number is available or not. */
28: bool check(int number) {
29: if (number < 0 || number > maxNumbers-1) return false;
30: return !used[number];
31: }
32: /** Recycle or release a number. */
33: void release(int number) {
34: if (number >= 0 && number < maxNumbers && used[number]) {
35: numbers[--front] = number;
36: used[number] = false;
37: }
38: }
39: };
40: /**
41: * Your PhoneDirectory object will be instantiated and called as such:
42: * PhoneDirectory obj = new PhoneDirectory(maxNumbers);
43: * int param_1 = obj.get();
44: * bool param_2 = obj.check(number);
45: * obj.release(number);
46: */
Thursday, July 21, 2016
173. Binary Search Tree Iterator
This is actually a iterative traversal of BST by the help of stack.
1: /**
2: * Definition for binary tree
3: * struct TreeNode {
4: * int val;
5: * TreeNode *left;
6: * TreeNode *right;
7: * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8: * };
9: */
10: class BSTIterator {
11: private:
12: stack<TreeNode *> stk;
13: public:
14: BSTIterator(TreeNode *root) {
15: while (root) {
16: stk.push(root);
17: root = root->left;
18: }
19: }
20: /** @return whether we have a next smallest number */
21: bool hasNext() {
22: return !stk.empty();
23: }
24: /** @return the next smallest number */
25: int next() {
26: TreeNode *t = stk.top();
27: stk.pop();
28: if (t->right) {
29: TreeNode *p = t->right;
30: while (p) {
31: stk.push(p);
32: p = p->left;
33: }
34: }
35: return t->val;
36: }
37: };
38: /**
39: * Your BSTIterator will be called like this:
40: * BSTIterator i = BSTIterator(root);
41: * while (i.hasNext()) cout << i.next();
42: */
Tuesday, July 19, 2016
288. Unique Word Abbreviation
The key idea has bee explained in the code. When I revisited this problem, I made a mistake in line 26. I returned "mp[abbr].size() == 1 && mp[abbr].count(word) == 1". This is wrong because it should be true if the new word does not exist in the hashed set.
1: class ValidWordAbbr { 2: private: 3: unordered_map<string, unordered_set<string>> dict; 4: bool flag; 5: string abbreviation(string word) { 6: if (word.size() <= 2) return word; 7: return word[0] + to_string(word.size()-2) + word[word.size()-1]; 8: } 9: public: 10: ValidWordAbbr(vector<string> &dictionary) { 11: for (string s : dictionary) { 12: string abbr = abbreviation(s); 13: dict[abbr].insert(s); 14: } 15: } 16: bool isUnique(string word) { 17: string abbr = abbreviation(word); 18: // The idea is set up a hash table whose key is the abbreviation and value is the corresponding word set. 19: // We only get true when the word set only contains the input word. 20: // Case 1: FALSE, the word set donesn't contain the input word. 21: // e.g. ["dog"]; isUnique("dig"). dict["d1g"].size() = 1 while dict["d1g"].count("dig") = 0. 22: // Case 2: TRUE, the word set only contains the input word. 23: // e.g. ["dog"]; isUnique("dog"). dict["d1g"].size() = 1 while dict["d1g"].count("dog") = 1. 24: // Case 3: FALSE, the word set contains more than one word. 25: // e.g. ["dog", "dig"]; isUnique("dog"). dict["d1g"].size() = 2 while dict["d1g"].count("dog") = 1. 26:return dict[abbr].size() == dict[abbr].count(word);27: } 28: }; 29: // Your ValidWordAbbr object will be instantiated and called as such: 30: // ValidWordAbbr vwa(dictionary); 31: // vwa.isUnique("hello"); 32: // vwa.isUnique("anotherWord");
Monday, July 18, 2016
155. Min Stack
Maintain two stacks. One is the normal stack and the other stores the minimum number so far. These two stacks should always have the same size. When I revisit this problem, I made a mistake in line 11.
1: class MinStack { 2: private: 3: stack<int> stk; 4: stack<int> minStk; 5: public: 6: /** initialize your data structure here. */ 7: MinStack() { 8: } 9: void push(int x) { 10: stk.push(x); 11:if (!minStk.empty()){ 12: minStk.push(x < minStk.top() ? x : minStk.top()); 13: } else { 14: minStk.push(x); 15: } 16: } 17: void pop() { 18: if (!stk.empty()) { 19: stk.pop(); 20: minStk.pop(); 21: } 22: } 23: int top() { 24: if (!stk.empty()) { 25: return stk.top(); 26: } else { 27: return -1; 28: } 29: } 30: int getMin() { 31: if (!minStk.empty()) { 32: return minStk.top(); 33: } else { 34: return -1; 35: } 36: } 37: }; 38: /** 39: * Your MinStack object will be instantiated and called as such: 40: * MinStack obj = new MinStack(); 41: * obj.push(x); 42: * obj.pop(); 43: * int param_3 = obj.top(); 44: * int param_4 = obj.getMin(); 45: */
Sunday, July 17, 2016
359. Logger Rate Limiter
I was trying to solve it as the same way as "362. Design Hit Counter" did. However, after reading the top rated solutions, I realized this problem is much easier. We can have a hash table whose key is the message and value is the expiration time. Once a new message comes in, we check if the timestamp falls in the expiration time which means the existing message is still valid, i.e. it has been printed in last 10 seconds. In this case, we print false. Otherwise, we update the expiration time.
1: class Logger {
2: unordered_map<string, int> mp;
3: public:
4: /** Initialize your data structure here. */
5: Logger() {
6: }
7: /** Returns true if the message should be printed in the given timestamp, otherwise returns false.
8: If this method returns false, the message will not be printed.
9: The timestamp is in seconds granularity. */
10: bool shouldPrintMessage(int timestamp, string message) {
11: if (timestamp < mp[message]) return false;
12: mp[message] = timestamp + 10;
13: return true;
14: }
15: };
16: /**
17: * Your Logger object will be instantiated and called as such:
18: * Logger obj = new Logger();
19: * bool param_1 = obj.shouldPrintMessage(timestamp,message);
20: */
362. Design Hit Counter
For this design problem, I was thinking of use an 300-size array to keep the counts. However, this solution doesn't provide any information about if the hits in the array are expired. For example, we have a hit at 1s and we have another hit at 302s. Then when we count the hits in the last 300s, we'll get 2 because we don't know when to expire the hit at 1s. Therefore, we need to another array to record the timestamp for each count in last 300s. When we hit the counter, we'll wrap around the timestamp to 300s, say i, and then we check in the time[] array if time[i] matches the input timestamp. If so, we increase the hits[i] counter for that hit. If hits[i] is more than 1, it means there are multiple hits happening in the same second. On the other hand, if time[i] doesn't match the input timestamp, it means the time[i] has expired, we need to give it new time stamp and reset the hits[i] counter to 1. When counting the hits in last 300s, we just need to sum up all the hits in last 300s.
1: class HitCounter {
2: private:
3: vector<int> time;
4: vector<int> hits;
5: public:
6: /** Initialize your data structure here. */
7: HitCounter() {
8: time = vector<int>(300, 0);
9: hits = vector<int>(300, 0);
10: }
11: /** Record a hit.
12: @param timestamp - The current timestamp (in seconds granularity). */
13: void hit(int timestamp) {
14: int i = timestamp % 300;
15: if (time[i] != timestamp) {
16: time[i] = timestamp;
17: hits[i] = 1;
18: } else {
19: hits[i]++;
20: }
21: }
22: /** Return the number of hits in the past 5 minutes.
23: @param timestamp - The current timestamp (in seconds granularity). */
24: int getHits(int timestamp) {
25: int count = 0;
26: for (int i = 0 ; i < 300; i++) {
27: if (timestamp - time[i] < 300) {
28: count += hits[i];
29: }
30: }
31: return count;
32: }
33: };
34: /**
35: * Your HitCounter object will be instantiated and called as such:
36: * HitCounter obj = new HitCounter();
37: * obj.hit(timestamp);
38: * int param_2 = obj.getHits(timestamp);
39: */
Saturday, July 16, 2016
353. Design Snake Game
After visiting the top rated solutions, I know all we need to do is to maintain a double linked queue. Every move, we get the front node's row index and column index. Then we compute the new front's row and column index. And we also need to pop out the tail node. If the new front node is valid, i.e. it is in the board and also it doesn't hit the snake. Then the question is how to know if it hits the snake? This can be done by hash set. The hash set caches all the nodes' positions. As long as the new node can be found in the hash set, we know it hits the snake itself. Since we have a hash set to keep all the nodes' position, whenever we remove/insert a new node from/into the queue, we need to erase/insert it from/into the hash set too. Note, we need to remove the tail BEFORE checking otherwise the snake is one longer than it should be. If the new node is valid, we push the new node to the front and insert it into hash set. And then we check if the new node hits a food. If so, we increment the score and we push the tail back to the queue back.
When I revisited this problem, I missed line 35. It's important to check the index before accessing an array.
When I revisited this problem, I missed line 35. It's important to check the index before accessing an array.
1: class SnakeGame { 2: private: 3: int w, h, i; 4: deque<pair<int, int>> q; 5: vector<pair<int, int>> f; 6: set<pair<int, int>> s; 7: public: 8: /** Initialize your data structure here. 9: @param width - screen width 10: @param height - screen height 11: @param food - A list of food positions 12: E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */ 13: SnakeGame(int width, int height, vector<pair<int, int>> food) { 14: w = width, h = height, i = 0; 15: f = food; 16: q.push_back(make_pair(0, 0)); 17: } 18: /** Moves the snake. 19: @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down 20: @return The game's score after the move. Return -1 if game over. 21: Game over when snake crosses the screen boundary or bites its body. */ 22: int move(string direction) { 23: pair<int, int> head = q.front(); 24: pair<int, int> tail = q.back(); 25: int r = head.first, c = head.second; 26:q.pop_back();27:s.erase(tail);28: if (direction == "U") r--; 29: else if (direction == "D") r++; 30: else if (direction == "R") c++; 31: else if (direction == "L") c--; 32: if (r < 0 || r == h || c < 0 || c == w || s.count(make_pair(r, c))) return -1; 33: q.push_front(make_pair(r, c)); 34: s.insert(make_pair(r, c)); 35:if (i == f.size()) return q.size()-1;36: if (f[i].first == r && f[i].second == c) { 37: q.push_back(tail); 38: s.insert(make_pair(tail.first, tail.second)); 39: i++; 40: } 41: return q.size()-1; 42: } 43: }; 44: /** 45: * Your SnakeGame object will be instantiated and called as such: 46: * SnakeGame obj = new SnakeGame(width, height, food); 47: * int param_1 = obj.move(direction); 48: */
251. Flatten 2D Vector
I was thinking to maintain a queue. But soon, I realized I only need to maintain the row index and column index. In hasNext() we need to check if row index reaches the boundary and the column index reaches the boundary. If row index is not reaching the boundary and column index is on the boundary, we need to move one row below and initialize column index to 0. The reason we use while loop is there could be empty rows. We should return true if row index is not on the boundary.
1: class Vector2D {
2: private:
3: int i, j;
4: vector<vector<int>> vecs;
5: public:
6: Vector2D(vector<vector<int>>& vec2d) {
7: vecs = vec2d;
8: i = 0, j = 0;
9: }
10: int next() {
11: return vecs[i][j++];
12: }
13: bool hasNext() {
14: while (i < vecs.size() && vecs[i].size() == j) {
15: i++, j = 0;
16: }
17: return i < vecs.size();
18: }
19: };
20: /**
21: * Your Vector2D object will be instantiated and called as such:
22: * Vector2D i(vec2d);
23: * while (i.hasNext()) cout << i.next();
24: */
272. Closest Binary Search Tree Value II
The O(n) solution will be straight forward. We can output all the nodes into an array, find the position where target is supposed in and move two pointers as predecessor and successor to output the closest k numbers. This also can be done by two stacks.
There is another way to maintain the predecessor and successor stack by traversing the tree in inorder and reverse-inorder.
And this problem actually can be converted to a design problem with two methods getPredecessor() and getSuccessor(). We can stop searching the BST when we find the closest predecessor and successor to target. And we can update the predecessor stack and successor stack in these two methods respectively. So the running time will be O(klogn);
The second time I revisited this problem, I found that initPredecessor() and initSuccessor() can be combined into one function.
1: class Solution {
2: public:
3: vector<int> closestKValues(TreeNode* root, double target, int k) {
4: vector<int> nodes;
5: vector<int> res;
6: inorder(root, nodes);
7: if (nodes.size() == 0) return res;
8: int l = 0, r = nodes.size()-1;
9: if (target < nodes[l]) {
10: while (k--) res.push_back(nodes[l++]);
11: return res;
12: }
13: if (target > nodes[r]) {
14: while (k--) res.push_back(nodes[r--]);
15: return res;
16: }
17: while (l <= r) {
18: int mid = l + (r - l) / 2;
19: if (nodes[mid] == target) {r = mid; break;}
20: else if (nodes[mid] > target) r = mid - 1;
21: else l = mid+1;
22: }
23: l = r;
24: r = l+1;
25: while (k--) {
26: if (l < 0) res.push_back(nodes[r++]);
27: else if (r == nodes.size()) res.push_back(nodes[l--]);
28: else if (abs(nodes[l]-target) < abs(nodes[r]-target)) {
29: res.push_back(nodes[l--]);
30: } else {
31: res.push_back(nodes[r++]);
32: }
33: }
34: return res;
35: }
36: void inorder(TreeNode *root, vector<int> &nodes) {
37: if (root == NULL) return;
38: inorder(root->left, nodes);
39: nodes.push_back(root->val);
40: inorder(root->right, nodes);
41: }
42: };
There is another way to maintain the predecessor and successor stack by traversing the tree in inorder and reverse-inorder.
1: /**
2: * Definition for a binary tree node.
3: * struct TreeNode {
4: * int val;
5: * TreeNode *left;
6: * TreeNode *right;
7: * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8: * };
9: */
10: class Solution {
11: public:
12: vector<int> closestKValues(TreeNode* root, double target, int k) {
13: stack<int> predecessor;
14: stack<int> successor;
15: inorder(root, false, predecessor, target);
16: inorder(root, true, successor, target);
17: vector<int> res;
18: while (k--) {
19: if (predecessor.empty()) {
20: res.push_back(successor.top());
21: successor.pop();
22: } else if (successor.empty()) {
23: res.push_back(predecessor.top());
24: predecessor.pop();
25: } else if (abs(predecessor.top()-target) < abs(successor.top()-target)) {
26: res.push_back(predecessor.top());
27: predecessor.pop();
28: } else {
29: res.push_back(successor.top());
30: successor.pop();
31: }
32: }
33: return res;
34: }
35: void inorder(TreeNode *root, bool reverse, stack<int> &stk, double target) {
36: if (root == NULL) return;
37: inorder(reverse ? root->right : root->left, reverse, stk, target);
38: if ((reverse && root->val <= target) || ((!reverse) && root->val > target)) return;
39: stk.push(root->val);
40: inorder(reverse ? root->left : root->right, reverse, stk, target);
41: }
42: };
And this problem actually can be converted to a design problem with two methods getPredecessor() and getSuccessor(). We can stop searching the BST when we find the closest predecessor and successor to target. And we can update the predecessor stack and successor stack in these two methods respectively. So the running time will be O(klogn);
1: /**
2: * Definition for a binary tree node.
3: * struct TreeNode {
4: * int val;
5: * TreeNode *left;
6: * TreeNode *right;
7: * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8: * };
9: */
10: class Solution {
11: private:
12: stack<treenode> pred;
13: stack<treenode> succ;
14: public:
15: vector<int> closestKValues(TreeNode* root, double target, int k) {
16: vector<int> res;
17: initPredecessor(root, target);
18: initSuccessor(root, target);
19: if (!succ.empty() && !pred.empty() && succ.top()->val == pred.top()->val) {
20: getNextPredecessor();
21: }
22: while (k--) {
23: if (succ.empty()) res.push_back(getNextPredecessor());
24: else if (pred.empty()) res.push_back(getNextSuccessor());
25: else if (abs(succ.top()->val - target) < abs(pred.top()->val - target)) {
26: res.push_back(getNextSuccessor());
27: } else {
28: res.push_back(getNextPredecessor());
29: }
30: }
31: return res;
32: }
33: void initPredecessor(TreeNode *root, double target) {
34: while (root) {
35: if (root->val == target) {
36: pred.push(root);
37: break;
38: } else if (root->val < target) {
39: pred.push(root);
40: root = root->right;
41: } else {
42: root = root->left;
43: }
44: }
45: }
46: void initSuccessor(TreeNode *root, double target) {
47: while (root) {
48: if (root->val == target) {
49: succ.push(root);
50: break;
51: } else if (root->val > target) {
52: succ.push(root);
53: root = root->left;
54: } else {
55: root = root->right;
56: }
57: }
58: }
59: int getNextPredecessor() {
60: TreeNode *root = pred.top();
61: pred.pop();
62: int res = root->val;
63: root = root->left;
64: while (root) {
65: pred.push(root);
66: root = root->right;
67: }
68: return res;
69: }
70: int getNextSuccessor() {
71: TreeNode *root = succ.top();
72: succ.pop();
73: int res = root->val;
74: root = root->right;
75: while (root) {
76: succ.push(root);
77: root = root->left;
78: }
79: return res;
80: }
81: };
The second time I revisited this problem, I found that initPredecessor() and initSuccessor() can be combined into one function.
1: /**
2: * Definition for a binary tree node.
3: * struct TreeNode {
4: * int val;
5: * TreeNode *left;
6: * TreeNode *right;
7: * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8: * };
9: */
10: class Solution {
11: private:
12: stack<TreeNode *> pred;
13: stack<TreeNode *> succ;
14: public:
15: vector<int> closestKValues(TreeNode* root, double target, int k) {
16: vector<int> res;
17: if (root == NULL) return res;
18: initStacks(root, target);
19: while (k) {
20: if (pred.empty()) res.push_back(getNextPredecessor());
21: else if (succ.empty()) res.push_back(getNextSuccessor());
22: else if (abs(pred.top()->val-target) < abs(succ.top()->val-target)) {
23: res.push_back(getNextPredecessor());
24: } else {
25: res.push_back(getNextSuccessor());
26: }
27: k--;
28: }
29: return res;
30: }
31: void initStacks(TreeNode *root, double target) {
32: while (root != NULL) {
33: if (root->val <= target) {
34: pred.push(root);
35: root = root->right;
36: } else {
37: succ.push(root);
38: root = root->left;
39: }
40: }
41: }
42: int getNextPredecessor() {
43: TreeNode *t = pred.top();
44: int ret = t->val;
45: pred.pop();
46: t = t->left;
47: while (t) {
48: pred.push(t);
49: t = t->right;
50: }
51: return ret;
52: }
53: int getNextSuccessor() {
54: TreeNode *t = succ.top();
55: int ret = t->val;
56: succ.pop();
57: t = t->right;
58: while (t) {
59: succ.push(t);
60: t = t->left;
61: }
62: return ret;
63: }
64: };
Friday, July 15, 2016
271. Encode and Decode Strings
The idea is easy. To have a fixed length header to contain the length of the string. When decode, parse the header and get the string whose length is specified by the header.
When I revisited this problem, I made mistake in
line 9: I mistakenly had "res += to_string(strs[i].size()) + string(HEAD_SIZE-strs[i].size(), '.' + strs[i]". Note, the head size should be the size of the converted head size number.
line 17: I mistakenly had "i++" in the end.
When I revisited this problem, I made mistake in
line 9: I mistakenly had "res += to_string(strs[i].size()) + string(HEAD_SIZE-strs[i].size(), '.' + strs[i]". Note, the head size should be the size of the converted head size number.
line 17: I mistakenly had "i++" in the end.
1: #define HEAD_SIZE 16 2: class Codec { 3: public: 4: // Encodes a list of strings to a single string. 5: string encode(vector<string>& strs) { 6: string res; 7: for (int i = 0; i < strs.size(); i++) { 8: string s = to_string(strs[i].size()); 9:string append = string(HEAD_SIZE-s.size(), '.');10: res += s + append + strs[i]; 11: } 12: return res; 13: } 14: // Decodes a single string to a list of strings. 15: vector<string> decode(string s) { 16: vector<string> res; 17:for (int i = 0; i < s.size();){ 18: string head = s.substr(i, HEAD_SIZE); 19: int len = stol(head, NULL, 10); 20: i += HEAD_SIZE; 21: if (len > 0) res.push_back(s.substr(i, len)); 22: else res.push_back(""); 23: i += len; 24: } 25: return res; 26: } 27: }; 28: // Your Codec object will be instantiated and called as such: 29: // Codec codec; 30: // codec.decode(codec.encode(strs));
346. Moving Average from Data Stream
A typical application for queue. When queue is not full, we keep pushing the new number to the queue and compute the sum. When the queue is full, we subtract the front from the sum, pop out the front, push the new number to the end and add the new number to the sum.
1: class MovingAverage {
2: private:
3: queue<int> que;
4: int m_size;
5: int sum;
6: public:
7: /** Initialize your data structure here. */
8: MovingAverage(int size) {
9: m_size = size;
10: sum = 0;
11: }
12: double next(int val) {
13: if (que.size() != m_size) {
14: que.push(val);
15: sum += val;
16: } else {
17: sum -= que.front();
18: que.pop();
19: que.push(val);
20: sum += val;
21: }
22: return sum * 1.0 / que.size();
23: }
24: };
25: /**
26: * Your MovingAverage object will be instantiated and called as such:
27: * MovingAverage obj = new MovingAverage(size);
28: * double param_1 = obj.next(val);
29: */
158. Read N Characters Given Read4 II - Call multiple times
I was thinking every time you call read, it will read the file from beginning, but it seems not. The following solution fails case ["ab", read(1), read(2)], output should be ["a", "b"]. From the output, I realized that when calling read(), it should maintain the file offset.
So we need to have a 4 bytes buffer and its pointer as the file offset.
1: class Solution {
2: public:
3: /**
4: * @param buf Destination buffer
5: * @param n Maximum number of characters to read
6: * @return The number of characters read
7: */
8: int read(char *buf, int n) {
9: int i = 0;
10: int m = 0;
11: int rc = 0;
12: while (i < n && (m = read4(buf)) > 0) {
13: buf += m;
14: i += m;
15: }
16: return i >= n ? n : i;
17: }
18: };
So we need to have a 4 bytes buffer and its pointer as the file offset.
1: // Forward declaration of the read4 API.
2: int read4(char *buf);
3: class Solution {
4: private:
5: char buffer[4];
6: int ib = 0;
7: int nb = 0;
8: public:
9: /**
10: * @param buf Destination buffer
11: * @param n Maximum number of characters to read
12: * @return The number of characters read
13: */
14: int read(char *buf, int n) {
15: int i = 0;
16: while ((i < n) && (ib < nb || (ib = 0) < (nb = read4(buffer)))) {
17: buf[i++] = buffer[ib++];
18: }
19: return i;
20: }
21: };
Thursday, July 14, 2016
380. Insert Delete GetRandom O(1)
1: class RandomizedSet {
2: private:
3: unordered_map<int, int> mp;
4: vector<int> nums;
5: public:
6: /** Initialize your data structure here. */
7: RandomizedSet() {
8: }
9: /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
10: bool insert(int val) {
11: if (mp.find(val) != mp.end()) return false;
12: nums.push_back(val);
13: mp[val] = nums.size()-1;
14: return true;
15: }
16: /** Removes a value from the set. Returns true if the set contained the specified element. */
17: bool remove(int val) {
18: if (mp.find(val) == mp.end()) return false;
19: int i = mp[val];
20: int j = nums.size()-1;
21: swap(nums[i], nums[j]);
22: mp[nums[i]] = i;
23: mp.erase(nums[j]);
24: nums.pop_back();
25: return true;
26: }
27: /** Get a random element from the set. */
28: int getRandom() {
29: return nums[rand()%nums.size()];
30: }
31: };
32: /**
33: * Your RandomizedSet object will be instantiated and called as such:
34: * RandomizedSet obj = new RandomizedSet();
35: * bool param_1 = obj.insert(val);
36: * bool param_2 = obj.remove(val);
37: * int param_3 = obj.getRandom();
38: */
Saturday, July 9, 2016
208. Implement Trie (Prefix Tree)
There is a very good video explaining what tries is though the implementation is Java.
https://www.youtube.com/watch?v=EjD5PJJoeLU
I followed the way video does to implement trie. I made a mistake in first place to initialize the TrieNode* array. I used 26 instead of sizeof(next). The third argument for memset actually should be computed as 26*sizeof(TrieNode*). Otherwise, you'll get run time error because of accessing invalid memory.
Also, there is iterative way to implement it.
https://www.youtube.com/watch?v=EjD5PJJoeLU
I followed the way video does to implement trie. I made a mistake in first place to initialize the TrieNode* array. I used 26 instead of sizeof(next). The third argument for memset actually should be computed as 26*sizeof(TrieNode*). Otherwise, you'll get run time error because of accessing invalid memory.
1: class TrieNode { 2: public: 3: TrieNode *next[26]; 4: bool isEnd; 5: // Initialize your data structure here. 6: TrieNode(bool b = false) { 7: memset(next, 0,sizeof(next)); 8: isEnd = b; 9: } 10: }; 11: class Trie { 12: public: 13: Trie() { 14: root = new TrieNode(); 15: } 16: // Inserts a word into the trie. 17: void insert(string word) { 18: _insert(root, word, 0); 19: } 20: // Returns if the word is in the trie. 21: bool search(string word) { 22: return _search(root, word, 0); 23: } 24: // Returns if there is any word in the trie 25: // that starts with the given prefix. 26: bool startsWith(string prefix) { 27: return _startsWith(root, prefix, 0); 28: } 29: private: 30: TrieNode* root; 31: void _insert(TrieNode *node, string &word, int i) { 32: if (i == word.size()) { 33: node->isEnd = true; 34: return; 35: } 36: int j = word[i]-'a'; 37: if (node->next[j] == NULL) node->next[j] = new TrieNode(); 38: _insert(node->next[j], word, i+1); 39: } 40: bool _search(TrieNode *node, string &word, int i) { 41: if (i == word.size()) return node->isEnd; 42: int j = word[i]-'a'; 43: if (node->next[j] == NULL) return false; 44: return _search(node->next[j], word, i+1); 45: } 46: bool _startsWith(TrieNode *node, string &prefix, int i) { 47: if (i == prefix.size()) return true; 48: int j = prefix[i]-'a'; 49: if (node->next[j] == NULL) return false; 50: return _startsWith(node->next[j], prefix, i+1); 51: } 52: };
Also, there is iterative way to implement it.
1: #define R 26
2: class TrieNode {
3: public:
4: TrieNode *next[R];
5: bool isEnd;
6: // Initialize your data structure here.
7: TrieNode() {
8: memset(next, 0, R*sizeof(TrieNode*));
9: isEnd = false;
10: }
11: };
12: class Trie {
13: public:
14: Trie() {
15: root = new TrieNode();
16: }
17: // Inserts a word into the trie.
18: void insert(string word) {
19: TrieNode *p = root;
20: for (int i = 0; i < word.size(); i++) {
21: if (p->next[word[i]-'a'] == NULL) {
22: p->next[word[i]-'a'] = new TrieNode();
23: }
24: p = p->next[word[i]-'a'];
25: }
26: p->isEnd = true;
27: }
28: // Returns if the word is in the trie.
29: bool search(string word) {
30: TrieNode *p = find(word);
31: return p && p->isEnd;
32: }
33: // Returns if there is any word in the trie
34: // that starts with the given prefix.
35: bool startsWith(string prefix) {
36: return find(prefix) != NULL;
37: }
38: private:
39: TrieNode* root;
40: TrieNode *find(string word) {
41: TrieNode *p = root;
42: for (int i = 0; i < word.size() && p; i++) {
43: p = p->next[word[i]-'a'];
44: }
45: return p;
46: }
47: };
48: // Your Trie object will be instantiated and called as such:
49: // Trie trie;
50: // trie.insert("somestring");
51: // trie.search("key");*/
Wednesday, July 6, 2016
352. Data Stream as Disjoint Intervals
Well, I have to say the implementation of this problem depends. If there are many addNum() calls and only a few getIntervals() calls, we may want O(1) for addNum() and allows longer processing time for getIntervals(). The first implementation follows this idea.
On the other hand, if there are many getIntervals() calls but a few addNum() calls, we want O(1) for getIntervals() adn allows longer processing time for addNum(). The second implementation follows this way.
1: /**
2: * Definition for an interval.
3: * struct Interval {
4: * int start;
5: * int end;
6: * Interval() : start(0), end(0) {}
7: * Interval(int s, int e) : start(s), end(e) {}
8: * };
9: */
10: class SummaryRanges {
11: private:
12: vector<Interval> intervals;
13: public:
14: /** Initialize your data structure here. */
15: SummaryRanges() {
16: }
17: void addNum(int val) {
18: intervals.push_back(Interval(val, val));
19: }
20: vector<Interval> getIntervals() {
21: sort(intervals.begin(), intervals.end(), [](Interval a, Interval b) { return a.start < b.start;});
22: for (int i = 1; i < intervals.size(); i++) {
23: if (intervals[i-1].end >= intervals[i].start-1) {
24: intervals[i-1].end = max(intervals[i-1].end, intervals[i].end);
25: intervals.erase(intervals.begin()+i);
26: i--;
27: }
28: }
29: return intervals;
30: }
31: };
32: /**
33: * Your SummaryRanges object will be instantiated and called as such:
34: * SummaryRanges obj = new SummaryRanges();
35: * obj.addNum(val);
36: * vector<Interval> param_2 = obj.getIntervals();
37: */
On the other hand, if there are many getIntervals() calls but a few addNum() calls, we want O(1) for getIntervals() adn allows longer processing time for addNum(). The second implementation follows this way.
1: /**
2: * Definition for an interval.
3: * struct Interval {
4: * int start;
5: * int end;
6: * Interval() : start(0), end(0) {}
7: * Interval(int s, int e) : start(s), end(e) {}
8: * };
9: */
10: class SummaryRanges {
11: private:
12: vector<Interval> intervals;
13: public:
14: void addNum(int val) {
15: vector<Interval>::iterator it = lower_bound(intervals.begin(), intervals.end(), Interval(val, val),
16: [](Interval a, Interval b){ return a.start < b.start; });
17: intervals.insert(it, Interval(val, val));
18: for (int i = 1; i < intervals.size(); i++) {
19: if (intervals[i-1].end >= intervals[i].start-1) {
20: intervals[i-1].end = max(intervals[i-1].end, intervals[i].end);
21: intervals.erase(intervals.begin()+i);
22: i--;
23: }
24: }
25: }
26: vector<Interval> getIntervals() {
27: return intervals;
28: }
29: };
30: /**
31: * Your SummaryRanges object will be instantiated and called as such:
32: * SummaryRanges obj = new SummaryRanges();
33: * obj.addNum(val);
34: * vector<Interval> param_2 = obj.getIntervals();
35: */
Monday, July 4, 2016
355. Design Twitter
We need to use hash map to store the mapping between one follower and followees. Each follower has multiple followees so we need set to store all followees for one follower. For tweets, we need to add timeline for each tweet such that we know which is the latest one. When popping out top latest 10 tweets of a user, all we need to do is:
(1). Get all friends of this user.
(2). Iterate the friend list.
(3). For each friend, iterate his/her tweets list.
(4). We use a priority queue with least recent tweets on top to keep the 10 most recent tweets. If the queue is not full, we keep pushing. If the queue is full, we check the top tweet is less recent than the incoming tweet. If so, push the incoming tweet into the queue. If not, we stop scanning this friend's tweets because his/her tweets are ordered from most recent to least recent. If the queue size is large than 10, we pop out the top.
(5). At the end, we output tweets in the queue in reverse order.
Also, one important point that can be easy to miss is that user herself need to follow herself! Why? Because she must be able to see her own tweets. Also when doing unfollow, we need to make sure that user mustn't unfollow herself.
Note, line 14 is an optimization for getNewsFeed(), so that line 22 can detect early break.
(1). Get all friends of this user.
(2). Iterate the friend list.
(3). For each friend, iterate his/her tweets list.
(4). We use a priority queue with least recent tweets on top to keep the 10 most recent tweets. If the queue is not full, we keep pushing. If the queue is full, we check the top tweet is less recent than the incoming tweet. If so, push the incoming tweet into the queue. If not, we stop scanning this friend's tweets because his/her tweets are ordered from most recent to least recent. If the queue size is large than 10, we pop out the top.
(5). At the end, we output tweets in the queue in reverse order.
Also, one important point that can be easy to miss is that user herself need to follow herself! Why? Because she must be able to see her own tweets. Also when doing unfollow, we need to make sure that user mustn't unfollow herself.
Note, line 14 is an optimization for getNewsFeed(), so that line 22 can detect early break.
1: class Twitter { 2: private: 3: unordered_map<int, unordered_set<int>> friends; 4: unordered_map<int, vector<pair<int, int>>> tweets; 5: int time; 6: public: 7: /** Initialize your data structure here. */ 8: Twitter() { 9: time = 0; 10: } 11: /** Compose a new tweet. */ 12: void postTweet(int userId, int tweetId) { 13:follow(userId, userId);14:tweets[userId].insert(tweets[userId].begin(), pair<int, int>(++time, tweetId));15: } 16: /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */ 17: vector<int> getNewsFeed(int userId) { 18: vector<int> res; 19: priority_queue<pair<int, int>, vector<pair<int, int>>, std::greater<pair<int, int>>> que; 20: for (int f : friends[userId]) { 21: for (pair<int, int> t : tweets[f]) { 22:if (que.size() == 10 && que.top().first > t.first) break;23: que.push(t); 24: if (que.size() > 10) que.pop(); 25: } 26: } 27: while (!que.empty()) { 28: res.push_back(que.top().second); 29: que.pop(); 30: } 31: reverse(res.begin(), res.end()); 32: return res; 33: } 34: /** Follower follows a followee. If the operation is invalid, it should be a no-op. */ 35: void follow(int followerId, int followeeId) { 36: friends[followerId].insert(followeeId); 37: } 38: /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */ 39: void unfollow(int followerId, int followeeId) { 40:if (followerId != followeeId){ 41: friends[followerId].erase(followeeId); 42: } 43: } 44: }; 45: /** 46: * Your Twitter object will be instantiated and called as such: 47: * Twitter obj = new Twitter(); 48: * obj.postTweet(userId,tweetId); 49: * vector<int> param_2 = obj.getNewsFeed(userId); 50: * obj.follow(followerId,followeeId); 51: * obj.unfollow(followerId,followeeId); 52: */
Sunday, June 26, 2016
341. Flatten Nested List Iterator
Since there could be a lot of nested list, the intuition is to use stack, i.e. stack up the nested list and deal with the most inner list first.
The idea is keep stacking up all the elements in the list until the top element in the stack is not a nested list any more.
So in the constructor, we stack up all the elements in the list. Since we call hasNext() before next(), we'll process the stack mainly in the hasNext() interface. We get the top element in the stack. There'll be two cases:
Case 1: top element is an integer.
This is the easiest case where we return true. Since the next() interface needs this element so we'll leave the pop action in next().
Case 2: top element is a list.
Now we need to get the list and pop out this element in the stack. And then push all the elements in the list into stack. And then go back and check the top element again.
When I revisited this problem, I tried to flat the list in next() function as following. However, it will get a runtime error if the input is "[[]]". The reason is the hasNext() simply checks if the stack is empty and thus will return true here. But in fact, it should be false. So we must flat the list in hasNext() function. Also I made a syntax error in line 32.
The idea is keep stacking up all the elements in the list until the top element in the stack is not a nested list any more.
So in the constructor, we stack up all the elements in the list. Since we call hasNext() before next(), we'll process the stack mainly in the hasNext() interface. We get the top element in the stack. There'll be two cases:
Case 1: top element is an integer.
This is the easiest case where we return true. Since the next() interface needs this element so we'll leave the pop action in next().
Case 2: top element is a list.
Now we need to get the list and pop out this element in the stack. And then push all the elements in the list into stack. And then go back and check the top element again.
1: /**
2: * // This is the interface that allows for creating nested lists.
3: * // You should not implement it, or speculate about its implementation
4: * class NestedInteger {
5: * public:
6: * // Return true if this NestedInteger holds a single integer, rather than a nested list.
7: * bool isInteger() const;
8: *
9: * // Return the single integer that this NestedInteger holds, if it holds a single integer
10: * // The result is undefined if this NestedInteger holds a nested list
11: * int getInteger() const;
12: *
13: * // Return the nested list that this NestedInteger holds, if it holds a nested list
14: * // The result is undefined if this NestedInteger holds a single integer
15: * const vector<NestedInteger> &getList() const;
16: * };
17: */
18: class NestedIterator {
19: private:
20: stack<NestedInteger> stk;
21: public:
22: NestedIterator(vector<NestedInteger> &nestedList) {
23: for (int i = nestedList.size()-1; i >= 0; i--) {
24: stk.push(nestedList[i]);
25: }
26: }
27: int next() {
28: int val = stk.top().getInteger();
29: stk.pop();
30: return val;
31: }
32: bool hasNext() {
33: while (!stk.empty()) {
34: NestedInteger cur = stk.top();
35: if (cur.isInteger()) return true;
36: stk.pop();
37: vector<NestedInteger> &list = cur.getList();
38: for (int i = list.size()-1; i >= 0; i--) {
39: stk.push(list[i]);
40: }
41: }
42: return false;
43: }
44: };
45: /**
46: * Your NestedIterator object will be instantiated and called as such:
47: * NestedIterator i(nestedList);
48: * while (i.hasNext()) cout << i.next();
49: */
When I revisited this problem, I tried to flat the list in next() function as following. However, it will get a runtime error if the input is "[[]]". The reason is the hasNext() simply checks if the stack is empty and thus will return true here. But in fact, it should be false. So we must flat the list in hasNext() function. Also I made a syntax error in line 32.
1: /** 2: * // This is the interface that allows for creating nested lists. 3: * // You should not implement it, or speculate about its implementation 4: * class NestedInteger { 5: * public: 6: * // Return true if this NestedInteger holds a single integer, rather than a nested list. 7: * bool isInteger() const; 8: * 9: * // Return the single integer that this NestedInteger holds, if it holds a single integer 10: * // The result is undefined if this NestedInteger holds a nested list 11: * int getInteger() const; 12: * 13: * // Return the nested list that this NestedInteger holds, if it holds a nested list 14: * // The result is undefined if this NestedInteger holds a single integer 15: * const vector<NestedInteger> &getList() const; 16: * }; 17: */ 18: class NestedIterator { 19: private: 20: stack<NestedInteger> stk; 21: public: 22: NestedIterator(vector<NestedInteger> &nestedList) { 23: int n = nestedList.size(); 24: for (int i = n-1; i >= 0; i--) { 25: stk.push(nestedList[i]); 26: } 27: } 28: int next() { 29: while (!stk.top().isInteger()) { 30: NestedInteger t = stk.top(); 31: stk.pop(); 32: vector<NestedInteger>&list= t.getList(); 33: int n = list.size(); 34: for (int i = n-1; i >= 0; i--) { 35: stk.push(list[i]); 36: } 37: } 38: int ret = stk.top().getInteger(); 39: stk.pop(); 40: return ret; 41: } 42: bool hasNext() { 43:return !stk.empty();44: } 45: }; 46: /** 47: * Your NestedIterator object will be instantiated and called as such: 48: * NestedIterator i(nestedList); 49: * while (i.hasNext()) cout << i.next(); 50: */
Saturday, June 25, 2016
284. Peeking Iterator
This is a good problem to evaluate C++ knowledge.
A derived class can inherit public and protected member from base class except private member.
In this problem, PeekingIterator constructor calls Iterator constructor to store and initialize data. All the data will be stored in private member "data" of Iterator so I don't have to create a new member to hold the data but simply call the API from the base class.
To call the public member of base class, I need to use base::public_member.
When I revisited the code and found the solution above is actually not a good one in interview. Here is how Google Guava does.
A derived class can inherit public and protected member from base class except private member.
In this problem, PeekingIterator constructor calls Iterator constructor to store and initialize data. All the data will be stored in private member "data" of Iterator so I don't have to create a new member to hold the data but simply call the API from the base class.
To call the public member of base class, I need to use base::public_member.
1: class PeekingIterator : public Iterator {
2: // Below is the interface for Iterator, which is already defined for you.
3: // **DO NOT** modify the interface for Iterator.
4: lass Iterator {
5: struct Data;
6: Data* data;
7: public:
8: Iterator(const vector<int>& nums);
9: Iterator(const Iterator& iter);
10: virtual ~Iterator();
11: // Returns the next element in the iteration.
12: int next();
13: // Returns true if the iteration has more elements.
14: bool hasNext() const;
15: };
16: public:
17: PeekingIterator(const vector<int>& nums) : Iterator(nums) {
18: // Initialize any member here.
19: // **DO NOT** save a copy of nums and manipulate it directly.
20: // You should only use the Iterator interface methods.
21: }
22: // Returns the next element in the iteration without advancing the iterator.
23: int peek() {
24: return Iterator(*this).next();
25: }
26: // hasNext() and next() should behave the same as in the Iterator interface.
27: // Override them if needed.
28: int next() {
29: return Iterator::next();
30: }
31: bool hasNext() const {
32: return Iterator::hasNext();
33: }
34: };
When I revisited the code and found the solution above is actually not a good one in interview. Here is how Google Guava does.
1: // Below is the interface for Iterator, which is already defined for you.
2: // **DO NOT** modify the interface for Iterator.
3: class Iterator {
4: struct Data;
5: Data* data;
6: public:
7: Iterator(const vector<int>& nums);
8: Iterator(const Iterator& iter);
9: virtual ~Iterator();
10: // Returns the next element in the iteration.
11: int next();
12: // Returns true if the iteration has more elements.
13: bool hasNext() const;
14: };
15: class PeekingIterator : public Iterator {
16: private:
17: bool peeked;
18: int peekedElement;
19: public:
20: PeekingIterator(const vector<int>& nums) : Iterator(nums) {
21: // Initialize any member here.
22: // **DO NOT** save a copy of nums and manipulate it directly.
23: // You should only use the Iterator interface methods.
24: peeked = false;
25: }
26: // Returns the next element in the iteration without advancing the iterator.
27: int peek() {
28: peekedElement = peeked ? peekedElement : Iterator::next();
29: peeked = true;
30: return peekedElement;
31: }
32: // hasNext() and next() should behave the same as in the Iterator interface.
33: // Override them if needed.
34: int next() {
35: peekedElement = peeked ? peekedElement : Iterator::next();
36: peeked = false;
37: return peekedElement;
38: }
39: bool hasNext() const {
40: return peeked || Iterator::hasNext();
41: }
42: };
Subscribe to:
Posts (Atom)