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 updown 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 bsearch 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 = mid1;
}
// 2. do the expansion
b = e = mid;
while(eb<C1)
{
if(KA[b1]>A[e+1]K) e++;
else b;
}
return b;
}

a.asudeh
August 04, 2017 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 kth 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 kth 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, mm1, k);
}

a.asudeh
July 22, 2017 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;
}

a.asudeh
July 21, 2017 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 pushrelabel 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;
}

a.asudeh
May 27, 2017 The best known algorithm that uses fastselection is in O(n).
1. compute the distance of the points with the origin.
in order to find the ksmallest values, use the kselection version that at every iteration the pivot is the median.
Please note that you need to use the fastmedian algorithm (that partitions the data in groups of size 5 and uses the median of median ....)
Thus the runningtime 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 kselection. I.e., shuffle the distances first and then follow the regular kselection.
The EXPECTED running time of the algorithms is O(n)

p.s.: using the kheap 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 mink 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[ik];
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 easybakeovens in Fort Walton ...
Open Chat in New Window
This is a simple extension of the BFS:
 a.asudeh August 04, 2017