a.asudeh
BAN USER- 1of 1 vote
AnswersGiven an input BST, find the minimum value difference between any two nodes in the tree.
- a.asudeh in United States
e.g:
....10
5 16
........12 20
answer: 2 (it happens between nodes 12 and 10)
describe the test cases you would use here?| Report Duplicate | Flag | PURGE
Google Software Engineer Intern - 0of 0 votes
AnswersGiven a specific type of DAG that forms a pyramid (the links have up-down direction), in which the node labels are integer, find the path that has the maximum sum of node values. what is the time/space complexity of the algorithm?
- a.asudeh in United States
e.g:
3
/ \
9 4
/ \ / \
1 8 2
/ \ / \ / \
4 5 8 2
answer: <3,9,8,8>, sum = 3+9+8+8=28| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm
int Leftindex(vector<int> A, int K, int C)
{
// 1. apply the b-search to find the index of closest point to K
int b=0, e=A.size()-1, mid;
while(b<=e)
{
mid = (b+e)/2;
if(K==A[mid])
break;
if(K>A[mid]) b = mid+1;
else e = mid-1;
}
// 2. do the expansion
b = e = mid;
while(e-b<C-1)
{
if(K-A[b-1]>A[e+1]-K) e++;
else b--;
}
return b;
}
The Linear Median finding algorithm divides the input (A) into groups of size 5, finds the medians of medians, and use it as the pivot to partition the data; then according to the locations of pivot, it decides to proceed in the left or right of it.
This "Magical" algorithm (as explained in CLRS) is in O(n). Here is its implementation in c++. Please note that it works for ant k-th smallest value and for the median the input k should be A.size()/2
int FastMedian(int *A, int begin, int end, int k); // finds the k-th smallest
int main()
{
int A[] = { 14, 23, 13, 34, 15, 45, 65, 2};
cout << FastMedian(A,0,8,4)<<endl;
getchar();
return 0;
}
int FastMedian(int *A, int begin, int end,int k)
{
/*
Analysis:
T(n) = T(7n/10) + T(n/5) + O(n)
= O(n)
*/
// border condition
int size = end - begin;
if (end - begin <= 5)
{
sort(A + begin, A + end);
return A[k];
}
// break down to groups of size 5, sort each and find the median of median
int m = floor(size / 5), r = size % 5, *medians;
int count = m, tmp;
if (r) {
medians = new int[m + 1]; count++;
}
else medians = new int[m];
for (int i = 0; i < m; i++)
{
sort(A + begin + 5 * i, A + begin + 5 * i + 5);
medians[i] = A[begin + 5 * i + 2];
}
if (r)
{
sort(A + begin + 5 * m, A + end);
medians[m] = A[begin + (5 * m + end) / 2];
}
int mm = FastMedian(medians, 0, count, count / 2);
//find the location of median in matrxi A
tmp = -1;
for (int i = 0; i < m; i++)
if (A[begin + 5 * i + 2] == mm)
{
tmp = 5 * i + 2;
break;
}
if (r && tmp == -1) tmp = begin + (5 * m + end) / 2;
// apply the partition and divide and conqure
Swap(A, begin, tmp);
mm = Partition(A,begin,end);
if (mm == k) return A[mm];
if (mm<k) return FastMedian(A, mm+1, end, k);
return FastMedian(A, begin, mm-1, k);
}
vector<queue<pair<int,int > > > PathesAddToX(int** M, int n, int m, int x)
{
return FollowPath(M, n, m, x, 0, 0, queue<pair<int,int> >(), 0);
}
vector<queue<pair<int,int> > > FollowPath(int** M, int n, int m, int Target, int i, int j, queue<pair<int,int> > path, int residualSum)
{
vector<queue<pair<int, int> > > result;
path.push(pair<int, int>(i, j));
residualSum += M[i][j];
while (residualSum > Target)
{
pair<int, int> tmp = path.front(); path.pop();
residualSum -= M[tmp.first][tmp.second];
}
if (residualSum == Target)
result.push_back(path);
if (i + 1 < n)
for (auto path : FollowPath(M, n, m, Target, i + 1, j, path, residualSum))
result.push_back(path);
if (j + 1 < m)
for (auto path : FollowPath(M, n, m, Target, i, j + 1, path, residualSum))
result.push_back(path);
return result;
}
It is a bipartite matching problem.
Consider a bipartite graph in which the left partite are the movies and the right partite are the time slots. There is an edge b/w from the node M[i] to T[j] iff movie i is shown at time j.
Now, in order to solve the bipartite matching, one can transform it to Maximum Flow, by adding a source node in the left of the left partite and a destination in the right of the right partite. All the movies are connected to the source and all time slots are connected to the destination node. Finally, all the edge weights are set to 1.
The problem can get simply solved in the order of O((n+m)^3) using the push-relabel algorithm.
Really enjoyed thinking on this problem :)
The key is that the cell values are less than n. Thus, you can use a[i] to store value i.
What I did was swapping the a[i] with the value at cell a[i] (a[a[i]]), to keep track of repetition. Here is my code:
set<int> Repeated(vector<int> a)
{
set<int> ret;
int i=0;
while(i<a.size())
{
if(a[i]==i) i++; // go to next element
else if(a[i] == a[a[i]]){
ret.insert(a[i]);
i++;
}
else
{
int temp = a[a[i]];
a[a[i]] = a[i];
a[i]=temp;
}
}
return ret;
}
// To execute C++, please define "int main()"
int main() {
vector<int> a = {4, 2, 0, 5, 2, 0, 1};
vector<int> b = {1, 2, 3, 0, 0, 1, 3, 6, 6,6};
set<int> c = Repeated(a);
set<int> d = Repeated(b);
for(int const & item:c)
cout<<item<<' ';
cout<<endl;
for(int const & item:d)
cout<<item<<' ';
return 0;
}
The best known algorithm that uses fast-selection is in O(n).
1. compute the distance of the points with the origin.
in order to find the k-smallest values, use the k-selection version that at every iteration the pivot is the median.
Please note that you need to use the fast-median algorithm (that partitions the data in groups of size 5 and uses the median of median ....)
Thus the running-time is:
T(n) = T(n/2)+ O(n)
--> T(n) = O(n)
Another way of implementation (to get rid of median finding) is to use randomized k-selection. I.e., shuffle the distances first and then follow the regular k-selection.
The EXPECTED running time of the algorithms is O(n)
--
p.s.: using the k-heap should be fast in practice.
The Problem is an extension of Largest Sum Contiguous Subarray problem which can be solved using Kadane's Algorithm.
Here I put the adaptation for min-k size version (as well as the original Kadane's Algorithm, for comparison):
int MinsizeMaxSubarray(vector<int> a,int k)
{
int i,maxendhere=0,maxsofar,sumoflastk;
for(i=0;i<k;i++)maxendhere+=a[i];
maxsofar = maxendhere;
sumoflastk = maxendhere;
for(;i<a.size();i++)
{
maxendhere += a[i];
sumoflastk += a[i]-a[i-k];
if(maxendhere<sumoflastk) maxendhere = sumoflastk;
if(maxsofar<maxendhere) maxsofar = maxendhere;
}
return maxsofar;
}
int MaxSubarray(vector<int> a)
{
int maxendhere=0,maxsofar=0;
for(int i=0;i<a.size();i++)
{
maxendhere += a[i];
if(maxendhere<0) maxendhere = 0;
if(maxsofar<maxendhere) maxsofar = maxendhere;
}
return maxsofar;
}
The extension to the streaming env. is simple, using a circular list that maintains the last k elements in the stream.
- a.asudeh May 27, 2017
RepEarned praise for analyzing acne for the government. Earned praised for my work implementing mantra to get desired husband in ...
RepHad moderate success buying and selling weebles in Ohio. Had some great experience buying and selling wooden trains on Wall ...
RepLeonaDWilliams, Analyst at CCN
At the moment I'm building banjos in Deltona, FL. Once had a dream of analyzing easy-bake-ovens in Fort Walton ...
This is a simple extension of the BFS:
- a.asudeh August 04, 2017