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==m-1 && b==n-1){
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
}
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(k-right->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 k-1 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 k-right->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,sum-i);
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,end-1,s);
else return a = min(1+minChars(start+1,end,s),1+minChars(start,end-1,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 n-index. 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, 2010
Replcarton941, Android test engineer at 8x8
My name is Lilly. I grew up in Somerset and currently live in the US. One desire that has always ...
RepAvyuktBurk, photographer at Precious Moments
Confident and dedicated photographer with experience in both professional and freelance photography. I like to explore Black Magic Spell To ...
Repjbacklit, abc at 247quickbookshelp
I am working as a news anchor and i love my job i an working from last 4 years under ...
RepI graduated from College with a master’s degree in arthrogryposis. After graduation I am working as a manager in ...
RepRuthMitchell, Applications Developer at ASAPInfosystemsPvtLtd
My name is Mitchell working as a technical sales support worker in the USA. I identify and establish new business ...
RepGlennPCannon, Applications Developer at Techlogix
Hi everyone, I am a professor in Houston, USA. I like to explore new things about Hire Someone To Break ...
RepGiannaDavid, Author at The times
I am an Author, I have a passion for reading and creative writing and attend many workshops and conventions surrounding ...
This is a exponential solution.
- python.c.madhav November 05, 2010