Jason
BAN USER1) man, I think minheap 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(sv[i]) != h.end() && h[sv[i]] != i)
{
retV[0] = sv[i];
retV[1] = v[i];
return retV;
}
return retV;
}

Jason
November 20, 2013 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;
}

Jason
November 09, 2013 using a priority queue or minheap, 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] <= N1, 1 means all integers in [0,n1] 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[i1]+1)
{
int interval = A[i]  A[i1]1;
sampleSize += interval;
int temp = 1+ rand()%sampleSize; // temp in [1, sampleSize]
if(temp <= interval) // pick a number in the interval [A[i1]+1, A[i]1] with prob. interval/sampleSize;
retVal = A[i1] + temp;
}
return retVal;
}
}

Jason
November 02, 2013 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;
}

Jason
October 24, 2013 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;
}

Jason
October 23, 2013 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);
}

Jason
October 21, 2013 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(yx+1 < i h[sum])
{
x = h[sum]+1;
y = i;
}
}
else
h[sum] = i;
}
}
cout<<"from\t"<<x << "to\t"<<y<<"\n";

Jason
October 16, 2013 //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, remainnums[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;
}

Jason
October 16, 2013 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[i1][j]);
if(j>0)
A[i][j] = min(A[i][j], A[i][j1]);
if(i>0 && j>0)
retV = max(retV, M[i][j]  A[i1][j1]);
}
return retV;
}

Jason
October 15, 2013 Open Chat in New Window
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