lasthope
BAN USERWe need to process the data from right to left and create a relationship tree in the following manner for 6 7 8 1 2 3 9 10.
If smaller than current chains smallest element, cost O(1)
1. 10
2. 10 9
3. 10 9 3
4. 10 9 3 2
5. 10 9 3 2 1
If greater than current chains smallest element, binary search cost O(log n)
6. 10 9 3 2 1
----------8
7. 10 9 3 2 1
----------8 7
7. 10 9 3 2 1
----------8 7 6
Now the answer is in one of the root to leaf paths, which can be found in O(n). So, total time O(n log n) and space O(n).
It can be done in O(n) time and O(1) space using two pointers.
1. Count # of 0's, #Z, and 1's, #O.
2. Initially "start" pointer points to position 0, "end" points to n-1. This is current window.
3. If #Z > #O,
3.a) if any of the pointers point to 0, move the pointer and reduce #Z.
3.b) If none of the pointers point to 0, skip 1's from the end where there are fewer 1's to skip to get to a 0. Once you get to zero 3.a applies. Update counters accordingly.
4. Similar logic applies to #Z < #O.
Basically the idea is that for the max window there is a #Z = #O, we try to reach that number from the possible max.
Instead of numbers we should work with segments of positive or negative numbers. Lets say the numbers are [1 2 -1 -2 -3 4 5 6 -7 -8 -9].
initial segments: [1 2], [-1 -2 -3]*, [4 5 6], [-7 -8 -9]
step 1. [-1 -2], [1 2]*, [-3], [4 5 6], [-7 -8 -9] ... pushed right seg to left, 2 swaps
step 2. [-1 -2 -3], [1 2 4 5 6]*, [-7 -8 -9] ... pushed left seg to right, 2 swaps
step 3. [-1 -2 -3], [1 2], [-7 -8 -9]*, [4 5 6] ... pushed left seg to right, 3 swaps
step 4. [-1 -2 -3 -7 -8], [1 2]*, [-9], [4 5 6] ... pushed right seg to left, 2 swaps
step 5. [-1 -2 -3 -7 -8 -9], [1 2 4 5 6] ... pushed left seg to right, 2 swaps
Total 11 swaps.
Lets say the negative segment is N and the positive segment is P. Now, given a situation like "[all negative], P, N, [unknown]", we need to do the following.
1. If |N| >= |P|, send right segment to left, total swap needed |N|+|P|
2. If |N| < |P|, send left segment to right, total swap needed |N|+|P|
Amortized O(n).
//with overflow error
unsigned long long next_largest(unsigned long long n)
{
unsigned long long m = n, x = 0;
while(true)
{
if( !(n&2) && (n&1) )
return (m & ~(3<<x)) | (2<<x);
n >>= 1;
x++;
}
}
//with underflow error
unsigned long long next_smallest(unsigned long long n)
{
unsigned long long m = n, x = 0;
while(true)
{
if( (n&2) && !(n&1) )
return (m & ~(3<<x)) | (1<<x);
n >>= 1;
x++;
}
}
Smith-Waterman algorithm (a modified longest common sub-sequence problem) can be used to find the best possible match.
dp[i][0] = dp [0][j] = 0;
dp[i][j] = min( dp[i-1][j-1] + ( S1[i] != S2[j] ), dp[i-1][j] + 1, dp[i][j-1]+1);
We also need back pointers so that start/end position of the matched sub-sequence can be recovered. It is possible that strPat does not a full sub-sequence with strDNA.
- lasthope November 25, 2013//assume x1 < x2 || y1 <= y2
struct line_seg
{
double x1, y1, x2, y2;
};
struct comp
{
bool operator() (const line_seg ls1, const line_seg ls2) const
{
if( slope(ls1) != slope(ls2) )
return slope(s1) < slope(s2);
if(ls1.x1 != ls2.x1)
return ls1.x1 < ls2.x1;
return ls1.y1 < ls2.y1;
}
};
line_seg max_seg;
multi_set< line_seg, comp > lsegs;
line_seg findMaxSegment()
{
return max_seg;
}
void addSegment(line_seg ls)
{
//1. insert segment in the set.
//2. check if the segment has same slope and overlaps with the previous and/or next segments (could me multiple of them)
//3. if yes, combine them to create a new larger segment
//4. insert the larger segment and remove the smaller ones inside it
//5. update max_seg if necessary
}
By maintaining an ordered set of segments we can add new segments in O( log n ) time** and report max in O(1) time (here n means at most n segments have been processed so far).
**Find/insert/remove in ordered set (actually balanced BST) is O( log n ). Since the total number of merged segments cannot be more than n, merging operation should be amortized O( log n ).
If we simulate 2-3 digits we can see the pattern of generated numbers. The code follows from observing how the range of positive/negative numbers changes. Time O( log n ).
long convert(long n)
{
if(n == 0 || n == 1)
return n;
long res = 0, low, high, range;
long digits = required_digits(n, low, high, range);
while(digits--)
{
res <<= 1;
if(digits&1)
{
if( low <= n && n < low + range)
{
res |= 1;
n += range;
}
low += range;
}
else
{
if( high >= n && n > high - range)
{
res |= 1;
n -= range;
}
high -= range;
}
range>>=1;
}
return res;
}
long required_digits(long n, long& low, long& high, long& range)
{
long digit = 1;
range = 1, low = 0, high = 1;
while( low > n || n > high )
{
digit++;
range <<= 1;
if(digit&1)
high += range;
else
low -= range;
}
return digit;
}
Lets say strings are X = { S1, S2, ... Sn}, sum(|S1|+...+|Sn|) = L and max{ |Si| } = M.
1. Compute longest common sub-sequence between S1 and S2. O( M^2 )
2. Create a string M2 by merging S1 and S2. Include chars from LCS once. For other letters lexicographically smallest one comes first maintaining their order in the original string. It can be done considering string as a implicit linked list. O( L )
3. Remove S1, S2 from set X, and add M2 to the set.
4. Do the same thing for [S3, S4], [S5, S6]..... We have effectively reduced the set size to n/2. By successively doing this we will get n/4, n/8, ... elements, and finally X = {Mn} which is the answer. O( L^2 log n ).
There could be some other easier way to get rid of the common sub-sequences between strings except using LCS. I can't think of one though.
Not sure why we need to deal with 'expected' time. Algorithm is deterministic O( N ) time and space.
int pivot(int n, int* A)
{
int pivot = -1;
int* smaller = new int[n];
int* greater = new int[n];
greater[0] = A[0];
for(int i=1; i < n; i++)
greater[i] = (A[i] > greater[i-1]? A[i]: greater[i-1]);
smaller[n-1] = A[n-1];
for(int i=n-2; i >= 0; i--)
smaller[i] = (A[i] < smaller[i+1]? A[i]: smaller[i+1]);
for(int i = 0; pivot == -1 && i < n; i++)
if(greater[i]<=A[i] && smaller[i]>=A[i])
pivot = i;
delete [] smaller;
delete [] greater;
return pivot;
}
vector< pair<int, int> > pair_sum(vector<int> arr, int s)
{
vector< pair<int, int> > result;
unordered_map< int, bool> present;
for(int i=0; i<arr.size(); i++)
{
if(present.count(s-arr[i]) != 0)
result.push_back( make_pair(arr[i], s-arr[i]) );
present[arr[i]] = true;
}
return result;
}
You are doing extra work for repeated rows and/or columns.
void force_zero(int m, int n, int** matrix, int k, int* x, int* y)
{
bool* row_flag = new bool[m];
bool* col_flag = new bool[n];
fill_n(row_flag, m, false);
fill_n(col_flag, n, false);
for(int i=0; i<k; i++)
{
row_flag[x[i]]=true;
col_flag[y[i]]=true;
}
for(int i=0; i<m; i++)
if(row_flag[i])
fill_n(matrix[i], n, 0);
for(int i=0; i < n; i++)
for(int j=0; col_flag[i] && j < m; j++)
matrix[j][i]=0;
delete [] row_flag;
delete [] col_flag;
}
I was thinking as if it was the "lowest" common ancestor problem, which is actually defined on trees. Since we need two parents to get a child, the graph becomes a dag, and most of what I said above is sort of like some observations, but not really a true solution :)
- lasthope November 19, 2013I was thinking as if it was the "lowest" common ancestor problem, which is actually defined on trees. Since we need two parents to get a child, the graph becomes a dag, and most of what I said above is sort of like some observations, but not really a true solution :)
- lasthope November 19, 2013Approach 1. Count frequency of words in one pass. Store them in a hashmap. In the second pass find out the longest unique word using the hashmap. Assuming constant time map operations, complexity is O( |S| ), where |S| is the sum of the word lengths.
Approach 2. Can be done using a suffix trie. Order O( |S| ).
The only thing we can do is maintaining a list of candidates in a count array[char]. A binary search tree can be used to maintain a list of chars with count 1
(c++ set< pair<long, char> > will do; pair will be sorted based on the position (long) )
With this setup, the first element in the set will always contain the first non-repeated char from the stream seen so far. O( log 256 ) = O( 1 ), since set update is logarithmic.
- lasthope November 19, 2013Adam and Eve are the only nodes in directed acyclic graph (DAG) with in-degree zero. Start from 'you' or Einstein, follow the child to parent pointers in a dfs like manner. Eventually you will find the special nodes 'Adam' and 'Eve'. Now run another dfs starting with 'Adam'/'Eve', this time following parent to child pointers. The first node for which one of it's child reports having you in it's sub-tree, and another child reports having Einstein in sub-tree, is "a" first common ancestor. This is where it gets complicated because of a lack of "first common ancestor" definition (partly because of possible weirdo relationships in the history). There could be multiple candidates in a DAG unlike trees.
- lasthope November 19, 2013We need k-nearest neighbor search methods. If it's always 10 may be we can use some fancy algorithms, but in general kd-tree or locality sensitive hashing (LSH) would be a good option, specially with the assumption that the world is a 2-dimensional flat surface. Don't know about the complexity of LSH, but kd-tree can be used to find "the" nearest neighbor in O( log N ) time. For the remaining (k-1), I guess in total O( k log N) will do (not 100% sure).
- lasthope November 19, 2013@subbu, I understand that the table construction is O(T). But, if you want to find the lowest non -1 entry of 'h' (which is greater than p) in the table, you have a problem. You may have to pass through many values less than equal to p or simply -1 before you meet your criteria. Hope I'm making sense.
- lasthope November 18, 2013Oh no, van emde boas is for making tree access cache oblivious. It is not required here.
In step 1 we "pre-process" T so that array[X] holds the positions (sorted if you go from left to right) where char X appears in T. O( T )
Then for each char S_i = 'd' in S (processing chars one by one from left to right), do a binary search in array['d']. Lets say we find it in location l of array['d']. O( log T )
The trick is to remember the location l and next time when we look for 'd' again we have to search array['d'][ l+1: END]. If found we update l. There should be an last found position similar to 'l' for each char processed from S so far.
If the process doesn't fail we return true at the end. O( S log T )
1. Create a sorted array of the positions where char X is present in T. Do it for all possible chars X (assuming 256).
2. For each char Y in S, do a binary search over the sorted array created for char Y in the first step. Note the position where it is found. Next time we look for Y again, we have look beyond this position.
3. If we do not find a viable position for Y in the sorted array, return false.
Runs in O( |S| log |T| ).
1. "heapify" (build heap in place in the input array) a max heap in O(n).
- lasthope February 24, 20142. Keep extracting the max elements and compute the sum. If the x number of max elements sum to at least K then the complexity is O( x log n).
Overall complexity is O( n + x log n ).