Jason
BAN USER1) man, I think min-heap is better for this problem.
2) maintaining these values in memory
a) using multiple machines, each handles requests of a period of times slots
or
b) Memory might be saved considering the fast that some stock value can be top 5 in a time range. Can anyone suggest a good data structure to handle this case.
//find a pair of numbers in v, s.t. their sum equals s
vector<int> findPair(vector<int> v, int s)
{
vector<int> retV(2,-1);
unordered_map<int, int> h;
for(int i=0; i<v.size(); ++i)
h[v[i]] = i;
for(int i=0; i<v.size(); ++i)
if(h.find(s-v[i]) != h.end() && h[s-v[i]] != i)
{
retV[0] = s-v[i];
retV[1] = v[i];
return retV;
}
return retV;
}
How can the linked list be value(c1)->value(c2)-> ... -> value(cN)->value(c(N+1))?
if the input is c1,c2,c3,c4,...,cN,c1,c2,c3,c4,...cN,c(N+1),
the list is c2,c3,c4,…,cN, when encountering the second c1, ie. c1 is removed from the linked list but kept in the hash table when encountering a duplicate c1.
double linkedlist + hashtable. hash table maps the character to its pointer in linked list. Pointer NULL means duplicate.
When a character arrives, if it is in the hash table (pointer not NULL), remove it from the linkedist and reset the pointer, otherwise insert it into hash table and the tail of linked list. When answering an query, return the first character in the double linked list.
Time: all the operations are O(1),
space: O(s), s = number of DISTINCT characters,
Iterative version
ListNode* reverse(ListNode *head)
{
if(head == NULL)
return head;
ListNode dummyHead;
dummyHead.next = NULL;
ListNode *p = head;
while(p != NULL)
{
ListNode *temp = p->next;
p->next = dummyHead.next;
dummyHead.next = p;
p = temp;
}
return dummyHead.next;
}
using a priority queue or min-heap, stores the values of 2^2, 2^3, 2^4, .... 2^32. In each iterator, return the first element in the queue/heap, suppose the element is a^b, push (a+1)^b into the queue/heap. It takes (O(32log32)) to initialize the queue/heap, and each query takes O(log32) steps.
- Jason November 04, 2013This problem is an extension of standard reservoir sampling
//assme 0<= A[i] <= N-1, -1 means all integers in [0,n-1] are in A.
int randomNum(int n, vector<int> A)
{
int retVal = -1;
int sampleSize = 0;
A.insert(A.begin(), 0);
for(int i=1; i<A.size(); i++)
{
if(A[i] >A[i-1]+1)
{
int interval = A[i] - A[i-1]-1;
sampleSize += interval;
int temp = 1+ rand()%sampleSize; // temp in [1, sampleSize]
if(temp <= interval) // pick a number in the interval [A[i-1]+1, A[i]-1] with prob. interval/sampleSize;
retVal = A[i-1] + temp;
}
return retVal;
}
}
Sorry, did not notice the requirement "not use additional space".
ListNode *reverse(ListNode* head)
{
if(head == NULL || head->next == NULL)
return head;
ListNode *p = head;
while(p->next != NULL)
{
p->next = p->next ^ p->pre;
p->pre = p->next ^ p->pre;
p->next = p->next ^ p->pre;
p = p->pre;
}
p->next = p->prev;
p->prev = NULL;
return p;
}
bool checkAnagram(string s1, string s2)
{
if(s1.size() != s2.size())
return false;
int A[ALPH_SIZE];
for(int i=0; i<ALPH_SIZE; i++)
A[i] = 0;
for(int i=0; i<s1.size(); i++)
A[s1[i]]++;
for(int i=0; i<s2.size(); i++)
{
A[s2[i]]--;
if(A[s2[i]] < 0) return false;
}
return true;
}
Semaphore availableSem = 1000;
Semaphore usedSem = 0;
int A[1000] = {1001, 1002, ,,,, 2000};
int start = 0;
int end = 999;
int allocate_token()
{
int retToken = 0;
p(availableSem);
retToken = A[start];
start = (start+1)%1000;
v(usedSem);
}
void free_token(int token)
{
p(usedSem);
end = (end+1)%1000;
A[end] = token;
v(availableSem);
}
void printMaxCommonSubArray(const vector<int> &A, const vector<int> &B)
{
assert(A.size() != B.size());
vector<int> C(A.size(), 0);
for(int i=0; i<A.size(); ++i)
C[i] = A[i]-B[i];
unordered_map<int, int> h;
int sum = 0;
h[0] = -1;
int x = 0;
int y = 0;
for(int i=0; i<C.size(); ++i)
{
sum += C[i];
if(h.find(sum) != h.end())
{
if(y-x+1 < i- h[sum])
{
x = h[sum]+1;
y = i;
}
}
else
h[sum] = i;
}
}
cout<<"from\t"<<x << "to\t"<<y<<"\n";
//The results are stored in retVv. curV is the set of selected numbers.
void getSubSets(const vector<int> nums, vector<vector<int>> &retVv, vector<int> curV, int index, int remain)
{
if(index >= nums.size())
{
if(remain <=0)
retVv.push_back(curV);
return;
}
//in this case, remain will not be <=0 when index>=nums.size()
if(remain > 0 && nums[index] < 0)
return;
getSubSets(nums, retVv,curV, index+1, remain);
curV.push_back(nums[index]);
getSubSets(nums, retVv,curV,index+1, remain-nums[index]);
}
bool comp(const int &a ,const int &b)
{
return a>=b;
}
vector<vector<int>> findAllSubsetsLargetThanK(const vector<int>&nums, int target)
{
//elements in nums are sorted in descending order.
sort(nums.begin(), nums.end(), comp);
vector<vector<int>> retVv;
vector<int> curV;
getSubSets(retVv,curV,0,target);
return retVv;
}
int findMaxDiff(vector<vector<int>> M)
{
int row = M.size();
if(row == 0)
return INT_MIN;
int col = M[0].size();
if(row == 1 || col == 1)
return INT_MIN;
int A[row][col];
int retV = INT_MIN;
for(int i=0; i<row; i++)
for(int j=0; j<col; j++)
{
A[i][j] = M[i][j];
if(i>0)
A[i][j] = min(A[i][j], A[i-1][j]);
if(j>0)
A[i][j] = min(A[i][j], A[i][j-1]);
if(i>0 && j>0)
retV = max(retV, M[i][j] - A[i-1][j-1]);
}
return retV;
}
There are mainly two factors in a hashmap, an array as bucket and a hash function which maps a key value to a bucket index.
- Jason December 27, 2013