python.c.madhav
BAN USER 0of 0 votes
AnswersConvert a binary search tree to a sorted doubly linked list in O(n) time and in place. Manipulate the existing tree. Donot create a new tree.
 python.c.madhav in India Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Data Structures Trees and Graphs Algorithm  0of 0 votes
AnswersFind the maximum continuous sum in an array. The array will contain at least one positive integer. Report the actual sequence. If there are multiple sequences report any one.
 python.c.madhav in India Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm Arrays Coding  0of 0 votes
AnswersSort a link list using merge sort.
 python.c.madhav in India Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm Linked Lists  0of 0 votes
AnswersDesign and implement a garbage collector in c++.
 python.c.madhav in India Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer C++
This is a exponential solution.
 python.c.madhav November 05, 2010You are write but that would take O(n^2) extra space. The dynamic programming algo takes O(n) extra space only
 python.c.madhav November 05, 2010You are write but that would take O(n^2) extra space. The dynamic programming algo takes O(n) extra space only
 python.c.madhav November 05, 2010You are write but that would take O(n^2) extra space. The dynamic programming algo takes O(n) extra space only
 python.c.madhav November 05, 2010sorry dude.I made a small mistake in code.Instead of writing V[j]<V[i] I should have written V[i][0]>V[j][0] &&
V[i][1]>V[j][1] && V[i][2]>V[j][2]. I'm sure it will work now
I think its maximum sum of a sub matrix
 python.c.madhav November 03, 2010initially the mice is at (0,0) we push the unvisited neighbours of it into the queue(also the neighbour should not be blocked) and we note that they are at distance 1 unit from the source(0,0). Now we remove one element from the queue and push all its neighbours which havent been pushed into the queue earlier into the queue and note that they are at distance 2 units from source. We keep on doing this until we reach the final position or until the queue becomes empty. if the queue becomes empty it means that we cannot reach the destination at all.
This is the code for the rough idea.
int minDistance(const vector<vector<int> > &Input){
int m = Input.size();
int n = Input[0].size();
queue<int> x,y,L;
vector<vector<bool> > visit(m,vector<bool>(n,0));
x.push(0),y.push(0),L.push(0);
visit[0][0]=1;
static int dx[]={1,0,1,0};
/*if diagonal movement is allowed u need to add 4 more values*/
static int dy[]={0,1,0,1};
while(!x.empty()){
int a=x.front(),b=y.front(),l=L.front();
x.pop(),y.pop(),L.pop();
if(a==m1 && b==n1){
cout<<"Destionation is reachable"<<endl;
return l;//l is the minimum distance.
}
for(int i=0;i<4;i++){
int t1 = a+dx[i],t2=b+dy[i],m=l+1;
if(t1>=0 && t1<m && t2>=0 && t2<n && !visit[t1][t2] && Input[t1][t2]){
x.push(t1),y.push(t2),L.push(m),visit[t1][t2]=1;
visit[t1][t2]=1;
}
}
}
return 1;//queue is empty, so path is not found
}

python.c.madhav
November 01, 2010 I think there would be a good mathematical solution to this problem. But we can solve it in another way. Simply run a bfs from (1000,1000) until the queue becomes.While you dequeue from the queue keep incrementing the number of points visited.
 python.c.madhav November 01, 2010Part 1 can be solved by using simple dynamic programming technique. It's in Mark Allen Weiss text book.
The second problem can be solved in variety of ways and there is O(m*n) algo to solve the second question too. It is same as this problem CTGAME in spoj online judge
I don't think there is any better solution than O(n^2) time. Sort all elements of A and B. Now for each element in C find if u can get a sum of C using one element each from A,B (which can be done in O(n) time since A,B are sorted now).
bool isPossible(int value,const vector<int> &A,const vector<int> &B){
int index1=0,index2=(int)B.size()1.
bool flag=0;
for(;index1<(int)A.size() && index2>=0;){
if(sum==A[index1]+B[index2]){
flag = 1;
break;
}
else if(sum>A[index1]+B[index2]) index1++;
else index2;
}
return flag;
}
Run the above function for each element of C. That's it.
 python.c.madhav November 01, 2010Don't u think its very easy!!
int index=1;//index where the first zero has occured
for(i=0;i<n;i++){
if(!a[i]){
if(index==1) index =i;
continue;
}
else{
if(index==1)continue;
else swap(arr[index],arr[i]);
index++;
}
}
The time complexity wont be O(nk) in this solution.Thats the major drawback I find with this solution
 python.c.madhav November 01, 2010We can solve this problem in O(logn) if we have given the oppurtunity to modify the insert routine of the BST. I'll introduce a variable by name size in every node which keep tracks of number elements present below that subtree.
t>size = t>left>size+t>right>size+1 obviously.Note that while doing insertion size value of all nodes donot change. Only those nodes which were visited in the path of insertion will change.(It is similar to the updation of height variable in AVL tree data structure)
Now coming to the actual question the logic is very simple.
int getsize(){
return this?size:0;
}
tree* findkthmaximum(int k){
if(!this) return NULL;
if(right>getsize()>=k) return right>findkthmaximum(k);
else if(right>getsize()+1==k) return this;
else return left>findkthmaximum(kright>getsize()1);
}
The logic is that consider the root node. if the number of elements to its right is greater than or equal to k then obviously kthmaximum must be in the right subtree.
if the number of elements in the right subtree is exactly k1 then obviously the current node must be your result.If neither of this happens then the required node must be in the left subtree. and it must be kright>getsize()1 th node in the left subtree obviously. Now observe that every time we either choose to go towards left or towards right given a node. Hence the run time of the algorithm will be O(logn) :D :D
The problem can be solved very easily by dynamic programming by just keeping track of which position are we filling currently and what is the sum of the digits filled till now.
int dp[6][28];
void init(){
for(int i=0;i<6;i++) for(int j=0;j<=27;j++) dp[i][j]=1;
}
int no_solutions(int index=0,int sum=0){
if(index==6) return sum==0;
if(sum<0) return 0;
int &ans = dp[index][sum];
if(ans!=1) return ans;
ans=0;
for(int i=((index==0)?1:0);i<10;i++){
if(index>2)
ans+=no_solutions(index+1,sumi);
else
ans+=no_solutions(index+1,sum+i);
}
return ans;
}
main(){
init();
cout<<no_solutions()<<endl;
}
As we can see the code takes 10*27*6=1620 iterations to run The code can be very easily modified for a general n digit number!
the solution is very easy. We can solve it in O(n^2).
int dp[100][100];
void init(int l){
for(int i=0;i<l;i++) for(int j=0;j<l;j++) dp[i][j]=1;
}
int minChars(int start,int end,char *s){
if(start>=end) return 0;
//check if already calculated
int &a=dp[start][end];
if(a!=1) return a;
if(s[start]==s[end]) return a=minChars(start+1,end1,s);
else return a = min(1+minChars(start+1,end,s),1+minChars(start,end1,s));
}
main(){
char s[100];
cin>>s;
init(strlen(s));
cout<<minChars(0,strlen(s)1,s)<<endl;
}
We can solve the problem in O(nlogn)using tree
 python.c.madhav August 22, 2010We can solve the problem in O(nlogn)
 python.c.madhav August 22, 2010We can do it without using any colour variable :D
 python.c.madhav August 22, 2010If all the elements are equal then there cannot be a unique solution. Otherwise we can simply use binary search kind of technique to solve the problem in O(logn). The problem can be rephrased as find the least index in the given array such that arr[index]<arr[0].
The answer will be nindex. index is 0 based!. I suppose it is very easy to solve the new problem I phrased.
yes it can be done in O(nlogm+m) with a heap . There is also a O(n+m) algo my friend told me
 python.c.madhav August 22, 2010We can solve the problem in O(n^2) :D. It requires a very clever idea though
 python.c.madhav August 22, 2010We can solve the problem in O(n^2) :D. It requires a very clever idea though
 python.c.madhav August 22, 2010Open Chat in New Window
This is a exponential solution.
 python.c.madhav November 05, 2010