Re: [algogeeks] Road crossing algorithm
I think this will help: http://en.wikipedia.org/wiki/Frogger Consider the roads to be n-laned and of constant width with constant time traffic coming on each lane.For example,say after 1 minute,a car comes on each lane but in a arithmetic sequence and not all at same time.To make it more clear, at t=1 minute,car at lane 1 travelling with constant velocity v and takes T time to cross the screen/lane1. at t=2 minute,another car comes now in lane 2 with same constant velocity and so on.. Now the frog can cross one lane either back or forth in one jump.These are the only movements allowed.The jump time is considerable(say in above case 1 minute only).Note that times are all not correctly mentioned and consider times which are appropriate for the problem.The time details are mentioned to make everyone understand the problem. Design an algorithm to guarantee that the frog crosses the road safely. Think first..Hint is downwards. . . . . . . . . . . . . .. . . . . . . . . . . . . Hint: Think in terms of multithreading,semaphores,mutex and vectors etc.. On Wed, Jul 14, 2010 at 11:33 PM, Tech Id tech.login@gmail.com wrote: A frog has to cross a road to meet its beloved she-frog at the other end. The road however has cars coming and can crush the frog. Road is two lanes wide. Devise an algorithm to help the frog carry on its family. (I am sorry but it seems that I have missed some parts of the problem here. If someone remembers the complete question, please help me). Thanks in advance! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Ashish -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sort in O(n) array which increases and then decreased and then increases...5,10,15,14,9,4,1,3,6,7,11,9,8,2
try merging this array [{5,9,10},{3,6,7,9}]... On Wed, Jul 14, 2010 at 9:30 AM, Ashish Goel ashg...@gmail.com wrote: int dstart = -1; int dend = -1; int istart=-1; int iend = -1; bool decreasing = false; for (int i=1;in;i++) { if (a[i] =a[i-1]) { if (decreasing) { dend =i-1; istart=i; reverse (a, dstart, dend); merge(a,0,dstart-1, dstart, dend); ///merge 0, dstart-1 array with array starting at dstart ending at dend decreasing = false; } // else continue; } if (!decreasing) //first decreasing { decreasing = true; dstart = i; iend=i-1; merge(a,0, istart-1, istart, iend); } } the number of comparison in each merge would be max O(m+n) where m is int number of elements in first list and n in second. so if the merge is happening k times the order would become O(k*(m+n)) types merge will do the merging from bottom so that shift downs are not needed. int r1= end1; int r2=end2; //for every write position, only 1 comparison is done while (r2=start1) { if (a[r1]a[r2]) { swap(a[r1],a[r2]); r2--;//r2 is also write position } else { r1--; } if (r1==r2) r1--; } so fr 5,10,9,14,13,12,17,16,21,20 what would be the order? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jul 13, 2010 at 6:00 AM, Gene gene.ress...@gmail.com wrote: On Jul 12, 10:48 am, Tech Id tech.login@gmail.com wrote: This is a good solution. Reversing the arrays will be O(n) Then merging will be O(n) too. In place merge is something like this. Have two indices as start1 and start2 start1 points to beginning of mini-sorted portion1 start2 points to beginning of mini-sorted portion2 Increase both start1 and start2 and swap when necessary. adjust start1 and start2 accordingly. Do the same for other mini-sorted arrays. So the complexity of this is mO(n) where m is the number of mini arrays. For m=1, it becomes O(n^2) as expected for a normal sort! Correct algorithms for in-place merge are much harder than what you're describing here. Think it through carefully, and you'll see this. And don't forget that if you are merging K lists, you need at least K log K comparisons to decide the merge order at each step. So if the lists being merged have about N items each, the cost of merging is O(N K log K) . In other words, the K in K-tonic makes a difference. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] stack
Another way in which this can be thought is in terms of Tower of Hanoi problem.Just introduce two more stacks of same size as input stack and get the sorted output as result. On Mon, Jun 14, 2010 at 9:18 AM, Anurag Sharma anuragvic...@gmail.comwrote: Why not just pop all elements from stack ( O(n) ) and insert it in a self balancing Binary Search Tree (like RB Tree) (O(log(n) ) and then do and inorder traversal ( O(n) )and push elements in stack again. Time = O(nlog(n) + n) Space=O(n) (for storing the tree) Anurag Sharma On Sun, Jun 13, 2010 at 9:25 PM, Jitendra Kushwaha jitendra.th...@gmail.com wrote: Stack can be sorted in O(n^2). @sankalp: Stack can always be sorted. Why do you think it cant be in some cases ? One can think like insertion sort algo : 1. for i in (1,n) 2. Pop up the top n-1 element and keep nth element in global variable say hold 3. while pushing get the position for hold and push it there for loop will take O(n) and step 2 will take take O(n) time. So overall O(n^2) complexity Program can be done with recursion using a variable (hence O(1) space). But it will use system stack :) Any comments OR better solution is welcomed?? -- Regards Jitendra Kushwaha MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Ashish -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] b tree:
its b tree not binary tree On Wed, Jul 14, 2010 at 10:45 AM, naveen naveen.cse@gmail.com wrote: if I do two traversals of a tree inorder wise i can get it in O(n). Questions should be one traversal i think . Then we should use a tree where nodes contain links to parents. On Tue, Jul 13, 2010 at 6:58 PM, sharad kumar sharad20073...@gmail.comwrote: Find the median in B-tree of order n -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *D.S.Naveen Trainee Engineer SQA* *My Blog: **http://www.naveends.blogspot.com*http://www.naveends.blogspot.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Difference b/w two elements in a array
I have one more question here , suppose we have some dynamic array ( of const size ) where insertions and removal is happening dynamically --- you want the 2 elements from the array having least difference. Design a data structure for this. Less than O(n) solution appreciated. i have a nlogn solution for it... as the insertion and deletion is happening dynamically... thinkin of O(n) is ...a bit tedious i think On Jul 14, 9:27 am, Ashish Goel ashg...@gmail.com wrote: count sort and then find mindiff fot (int i=1;in;i++) if (a[i]-a[i-1] mindiff) { mindiff =a[i]-a[i-1]; ele1=a[i-1]; ele2=a[i];} Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jul 13, 2010 at 2:47 PM, Tech Id tech.login@gmail.com wrote: Construct a BST for the array - O(nlogn) Traverse the tree and find a node which has minimum difference with either its left or right child in whole of the tree. (Because the required numbers have to be adjacent to each other in a sorted array). - O(n) = Total order:O(nlogn) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Interview Question
@harit.. logic plz.. not the code.. On Wed, Jul 14, 2010 at 9:50 PM, harit agarwal agarwalha...@gmail.comwrote: this is O(n) solution and using O(n) space... #includeiostream #includevector #includestack using namespace std; void leader_count(vectorint v,int *ar) { stackint s; int n=v.size(); int i=n-1; while(i=0) { if(s.empty()) { ar[--n]=0; s.push(i); i--; } else { if(v[i] = v[s.top()]) { ar[--n]=s.top(); s.push(i); i--; } else { s.pop(); } } } for(int i=v.size()-1;i=0;i--) if(ar[i]!=0) ar[i]=ar[ar[i]]+1; } main() { int i; vectorint v; while(cini) v.push_back(i); int *ar=new int[v.size()]; leader_count(v,ar); for(int i=0;iv.size();i++) coutar[i] ; } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards Ankur Aggarwal -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Finding latitude and longitude
Hi If I have a (latitude, langitude) as well as pixel positions of those locations, then how can (longitude, latitude) or pixel coordinates of a point x metres away can be found ? If this information is not enough, what else information might be required ? -- Siddharth Srivastava When you have learned to snatch the error code from the trap frame, it will be time for you to leave. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] online movies streaming
Hey moderator.. try 2 avoid these members... On Thu, Jul 15, 2010 at 1:01 AM, X +18 mai...@jadidnet.net wrote: http://bit.ly/aRDr4E Streaming entertainment network with lots of video clips. ... Use a software called qvod player, you can watch the DVD movies online for free. ... http://bit.ly/aRDr4E Watch free Movies, TV-shows, Anime, Documentaries and Cartoons online on alluc.org - Worlds biggest video stream Database! http://bit.ly/aRDr4E -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards Ankur Aggarwal -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Google Interview Question
@varun c should also be in the array -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Google Interview Question
Hi, suppose we have given n distinct numbers are a[n]. 1. sort them using quick or any other sort in O(nlogn) 2. use then int find(int *arr, int n) /* return largest number if fing it otheriwse retirn 0*/ { int i,j,k, temp; for(k=n-1; k2;k--) { j = k-1 i=0; while(i!=j) { temp = arr[i]+arr[j]; if(temp== arr[k]) return arr[k]; else if(temparr[k]) i++; else j--; } } return 0; } -- Thanks Regards Umesh kewat Hyderabad On Thu, Jul 15, 2010 at 9:07 AM, Ashish Goel ashg...@gmail.com wrote: sort using counting sort or quickselect now a and b are less than c so find c first suppose c's index is k the start two indexes i=0 and j=k-1, if a[i]+a[j] ==a[k] return these numbers, else add elements at i,j if the sum is greater than c reduce j, if less than c increase i alternatively sort array, find index of c, make a BST or a hash table, starting from index 0 of the sorted array, find c-athis is overhead on second thoughts, i will proceed with first approach Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 14, 2010 at 9:55 PM, siddharth shankar siddharth.shanka...@gmail.com wrote: O ( n^2 ) soln can be done step : 1 . sort array in n*log(n) . 2. for every C from last find two number A B such that A+B=C ... O( n^2 ) Total :- O(N^2) can we improve it further ?? any help please On Wed, Jul 14, 2010 at 10:57 AM, Debajyoti Sarma sarma.debajy...@gmail.com wrote: An array contains the set of positive integer. Find the largest number c such that c=a+b where a,b,c are distinct number of the set? [Consider , reducing complexity] -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- siddharth shankar -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Stock prices.
int MaxStockGain(int arr[], int size) { if(size = 0) return 0; int curMin = arr[0]; int MaxGain = 0; for(int i = 1; i size; ++i) { if (arr[i] curMin) { curMin = arr[i]; } int currGain = arr[i] - curMin; if(currGain MaxGain) { MaxGain = currGain; } } return MaxGain; } On Tue, Jul 13, 2010 at 4:02 PM, srikanth sg srikanthini...@gmail.comwrote: how you do that in O(n)... can you explain ??? On Mon, Jul 12, 2010 at 11:37 PM, amit amitjaspal...@gmail.com wrote: Stock prices are given to you at various time intervals. p1, p2, p3,... you are allowed to buy and sell only once each. So write a program to find the index where you would buy and where you would sell to maximize profit Correct me if i am wrong -- I think we can solve it in O(n) we simple have to find max(A[j]-A[i]) with ji. This is already discussed or am i missing something?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] b tree:
sorry i didnt see it .. On Thu, Jul 15, 2010 at 4:18 AM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: its b tree not binary tree On Wed, Jul 14, 2010 at 10:45 AM, naveen naveen.cse@gmail.com wrote: if I do two traversals of a tree inorder wise i can get it in O(n). Questions should be one traversal i think . Then we should use a tree where nodes contain links to parents. On Tue, Jul 13, 2010 at 6:58 PM, sharad kumar sharad20073...@gmail.comwrote: Find the median in B-tree of order n -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *D.S.Naveen Trainee Engineer SQA* *My Blog: **http://www.naveends.blogspot.com*http://www.naveends.blogspot.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- D.S.Naveen Trainee Engineer SQA My Blog: http://www.naveends.blogspot.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Finding latitude and longitude
This seems to be asked in context of google maps. While drawing map at a particular zoom level, ratio of map-area-on- screen and shown-latitudes/longitudes-area is known. So, x meters can be converted to latitiude/longitude difference easily by this ratio. On Jul 15, 12:59 pm, siddharth srivastava akssps...@gmail.com wrote: Hi If I have a (latitude, langitude) as well as pixel positions of those locations, then how can (longitude, latitude) or pixel coordinates of a point x metres away can be found ? If this information is not enough, what else information might be required ? -- Siddharth Srivastava When you have learned to snatch the error code from the trap frame, it will be time for you to leave. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Stock prices.
technically i can sell first and buy later also so this solution doesnot consider shorts and long.. my algo would be return max(MaxStockGain(a,size), MaxStockGain(reverse(a,size),size)); can be done better..without reverse too :) lol Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Jul 15, 2010 at 4:29 AM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: int MaxStockGain(int arr[], int size) { if(size = 0) return 0; int curMin = arr[0]; int MaxGain = 0; for(int i = 1; i size; ++i) { if (arr[i] curMin) { curMin = arr[i]; } int currGain = arr[i] - curMin; if(currGain MaxGain) { MaxGain = currGain; } } return MaxGain; } On Tue, Jul 13, 2010 at 4:02 PM, srikanth sg srikanthini...@gmail.comwrote: how you do that in O(n)... can you explain ??? On Mon, Jul 12, 2010 at 11:37 PM, amit amitjaspal...@gmail.com wrote: Stock prices are given to you at various time intervals. p1, p2, p3,... you are allowed to buy and sell only once each. So write a program to find the index where you would buy and where you would sell to maximize profit Correct me if i am wrong -- I think we can solve it in O(n) we simple have to find max(A[j]-A[i]) with ji. This is already discussed or am i missing something?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Finding latitude and longitude
Hi On 15 July 2010 07:37, Tech Id tech.login@gmail.com wrote: This seems to be asked in context of google maps. I asked in terms of OSM. While drawing map at a particular zoom level, ratio of map-area-on- screen and shown-latitudes/longitudes-area is known. So, x meters can be converted to latitiude/longitude difference easily by this ratio. would it change then ? On Jul 15, 12:59 pm, siddharth srivastava akssps...@gmail.com wrote: Hi If I have a (latitude, langitude) as well as pixel positions of those locations, then how can (longitude, latitude) or pixel coordinates of a point x metres away can be found ? If this information is not enough, what else information might be required ? -- Siddharth Srivastava When you have learned to snatch the error code from the trap frame, it will be time for you to leave. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Siddharth Srivastava When you have learned to snatch the error code from the trap frame, it will be time for you to leave. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sort in O(n) array which increases and then decreased and then increases...5,10,15,14,9,4,1,3,6,7,11,9,8,2
good one shifting array is the solution but i want to do it without shifting, is there a solution!!! Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Jul 15, 2010 at 4:26 AM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: try merging this array [{5,9,10},{3,6,7,9}]... On Wed, Jul 14, 2010 at 9:30 AM, Ashish Goel ashg...@gmail.com wrote: int dstart = -1; int dend = -1; int istart=-1; int iend = -1; bool decreasing = false; for (int i=1;in;i++) { if (a[i] =a[i-1]) { if (decreasing) { dend =i-1; istart=i; reverse (a, dstart, dend); merge(a,0,dstart-1, dstart, dend); ///merge 0, dstart-1 array with array starting at dstart ending at dend decreasing = false; } // else continue; } if (!decreasing) //first decreasing { decreasing = true; dstart = i; iend=i-1; merge(a,0, istart-1, istart, iend); } } the number of comparison in each merge would be max O(m+n) where m is int number of elements in first list and n in second. so if the merge is happening k times the order would become O(k*(m+n)) types merge will do the merging from bottom so that shift downs are not needed. int r1= end1; int r2=end2; //for every write position, only 1 comparison is done while (r2=start1) { if (a[r1]a[r2]) { swap(a[r1],a[r2]); r2--;//r2 is also write position } else { r1--; } if (r1==r2) r1--; } so fr 5,10,9,14,13,12,17,16,21,20 what would be the order? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jul 13, 2010 at 6:00 AM, Gene gene.ress...@gmail.com wrote: On Jul 12, 10:48 am, Tech Id tech.login@gmail.com wrote: This is a good solution. Reversing the arrays will be O(n) Then merging will be O(n) too. In place merge is something like this. Have two indices as start1 and start2 start1 points to beginning of mini-sorted portion1 start2 points to beginning of mini-sorted portion2 Increase both start1 and start2 and swap when necessary. adjust start1 and start2 accordingly. Do the same for other mini-sorted arrays. So the complexity of this is mO(n) where m is the number of mini arrays. For m=1, it becomes O(n^2) as expected for a normal sort! Correct algorithms for in-place merge are much harder than what you're describing here. Think it through carefully, and you'll see this. And don't forget that if you are merging K lists, you need at least K log K comparisons to decide the merge order at each step. So if the lists being merged have about N items each, the cost of merging is O(N K log K) . In other words, the K in K-tonic makes a difference. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Road crossing algorithm
An inefficient but working method is the brute force one. Do a recursive test for all the cases possible and if you find one which helps the frog cross the road, then that is it. Let int car_times[numLanes] store the time each car will take to reach the path where the frog is crossing the road. Frog has 3 commands at his disposal: a) jump_fwd b) jump_back c) wait Let Vector command cmds be the desired sequence of commands to reach the destination. We need to write a function which will produce the above global vector as its output. enum command {F, B, W}; Vector command cmds; int car_times[numLanes]; //given in the beginning bool try_remaining_path (int lane_num, int time_passed) { int orig_time = time_passed; int orig_lanes = lane_num; while (car_times[lane_num] - time_passed= 1) { cmds.push_back (F); bool rest_is_possible = try_remaining_path (time_passed+1, lane_num+1); if (rest_is_possible) return true; cmds.pop(); cmds.push_back (W); time_passed++; } // if we come here, means that there was no point // in waiting in this lane_num, as the frog will be // killed at one point or the other. // let us try by jumping back one step. time_passed = orig_time; while (lane_num 0) { cmds.push_back (B); time_passed++; lane_num--; bool rest_is_possible = try_remaining_path (time_passed, lane_num); if (rest_is_possible) return true; } // Nothing is possible in this lane. // Empty the commands B from the vector and try something else. while (orig_lanes 0 ) { cmds.pop(); orig_lanes--; } return false; } Above seems very inefficient to me because it calculates all the possible jumps at each lane. Please help in improving it. On Jul 15, 9:24 am, Ashish kumar Jain akjlucky4...@gmail.com wrote: I think this will help: http://en.wikipedia.org/wiki/Frogger Consider the roads to be n-laned and of constant width with constant time traffic coming on each lane.For example,say after 1 minute,a car comes on each lane but in a arithmetic sequence and not all at same time.To make it more clear, at t=1 minute,car at lane 1 travelling with constant velocity v and takes T time to cross the screen/lane1. at t=2 minute,another car comes now in lane 2 with same constant velocity and so on.. Now the frog can cross one lane either back or forth in one jump.These are the only movements allowed.The jump time is considerable(say in above case 1 minute only).Note that times are all not correctly mentioned and consider times which are appropriate for the problem.The time details are mentioned to make everyone understand the problem. Design an algorithm to guarantee that the frog crosses the road safely. Think first..Hint is downwards. . . . . . . . . . . . . .. . . . . . . . . . . . . Hint: Think in terms of multithreading,semaphores,mutex and vectors etc.. On Wed, Jul 14, 2010 at 11:33 PM, Tech Id tech.login@gmail.com wrote: A frog has to cross a road to meet its beloved she-frog at the other end. The road however has cars coming and can crush the frog. Road is two lanes wide. Devise an algorithm to help the frog carry on its family. (I am sorry but it seems that I have missed some parts of the problem here. If someone remembers the complete question, please help me). Thanks in advance! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Ashish -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Road crossing algorithm
http://code.google.com/p/frogger-game/source/browse/trunk/ can it be interview question?? the frong will wait and this would vary at run time, the car_times is storing just one value, multiple cars can come in a lane so it should be hash map one thought: for each lane we know when the car would not be there we only need to consider the time t+delta in a lane when frong is in lane n at time t so it implies that if there are n lanes, and we know all the time when the car is not at the crossing point, we need to find a monotonically increasing sequence eg lane1 4 7 10 lane2 2 5 9 lane3 3 6 11 lane4 1 4 7 so the times when the car is not there will be lan1 1 2 3 5 6 8 9 11 12 lan2 1 3 4 6 7 8 10 11 12 lan3 1 2 4 5 7 8 9 10 12 lan4 2 3 5 6 8 9 10 11 12 so 1-345 gives one solution 2-3-4-5 another solution Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Jul 15, 2010 at 9:56 PM, Tech Id tech.login@gmail.com wrote: An inefficient but working method is the brute force one. Do a recursive test for all the cases possible and if you find one which helps the frog cross the road, then that is it. Let int car_times[numLanes] store the time each car will take to reach the path where the frog is crossing the road. Frog has 3 commands at his disposal: a) jump_fwd b) jump_back c) wait Let Vector command cmds be the desired sequence of commands to reach the destination. We need to write a function which will produce the above global vector as its output. enum command {F, B, W}; Vector command cmds; int car_times[numLanes]; //given in the beginning bool try_remaining_path (int lane_num, int time_passed) { int orig_time = time_passed; int orig_lanes = lane_num; while (car_times[lane_num] - time_passed= 1) { cmds.push_back (F); bool rest_is_possible = try_remaining_path (time_passed+1, lane_num+1); if (rest_is_possible) return true; cmds.pop(); cmds.push_back (W); time_passed++; } // if we come here, means that there was no point // in waiting in this lane_num, as the frog will be // killed at one point or the other. // let us try by jumping back one step. time_passed = orig_time; while (lane_num 0) { cmds.push_back (B); time_passed++; lane_num--; bool rest_is_possible = try_remaining_path (time_passed, lane_num); if (rest_is_possible) return true; } // Nothing is possible in this lane. // Empty the commands B from the vector and try something else. while (orig_lanes 0 ) { cmds.pop(); orig_lanes--; } return false; } Above seems very inefficient to me because it calculates all the possible jumps at each lane. Please help in improving it. On Jul 15, 9:24 am, Ashish kumar Jain akjlucky4...@gmail.com wrote: I think this will help: http://en.wikipedia.org/wiki/Frogger Consider the roads to be n-laned and of constant width with constant time traffic coming on each lane.For example,say after 1 minute,a car comes on each lane but in a arithmetic sequence and not all at same time.To make it more clear, at t=1 minute,car at lane 1 travelling with constant velocity v and takes T time to cross the screen/lane1. at t=2 minute,another car comes now in lane 2 with same constant velocity and so on.. Now the frog can cross one lane either back or forth in one jump.These are the only movements allowed.The jump time is considerable(say in above case 1 minute only).Note that times are all not correctly mentioned and consider times which are appropriate for the problem.The time details are mentioned to make everyone understand the problem. Design an algorithm to guarantee that the frog crosses the road safely. Think first..Hint is downwards. . . . . . . . . . . . . .. . . . . . . . . . . . . Hint: Think in terms of multithreading,semaphores,mutex and vectors etc.. On Wed, Jul 14, 2010 at 11:33 PM, Tech Id tech.login@gmail.com wrote: A frog has to cross a road to meet its beloved she-frog at the other end. The road however has cars coming and can crush the frog. Road is two lanes wide. Devise an algorithm to help the frog carry on its family. (I am sorry but it seems that I have missed some parts of the problem here. If someone remembers the complete question, please help me). Thanks in advance! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
[algogeeks] Re: Road crossing algorithm
Hi Ashish, Your algo does not have a chance for jump_back. This may be required for certain cases, especially when multiple cars are running on one lane. My solution was for one car on one lane, hence car_times[i] gives the car in i-th lane will take to hit the path frog is trying to cross. It should not be too difficult to put multiple cars on single lane in my algo. Actually, from a game perspective, the problem can have many parts like: speed of cars vary, frog can move sideways too instead of vertically on the road. frog can make upto m jumps etc etc. Regards Techie -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Finding latitude and longitude
Think about it more carefully. If you are 1m south of the north pole, then walk pi meters east or west, your longitude changes by 180 degrees. At the equator it changes hardly at all. This is hard to do accurately and correctly over the whole earth. Google geographic coordinate transformations. There is free software available at http://earth-info.nga.mil/GandG/geotrans/index.html . If you only need approximate answers or your distances are short, you can use spherical geometry, which is not so bad. On Jul 15, 11:03 am, siddharth srivastava akssps...@gmail.com wrote: Hi On 15 July 2010 07:37, Tech Id tech.login@gmail.com wrote: This seems to be asked in context of google maps. I asked in terms of OSM. While drawing map at a particular zoom level, ratio of map-area-on- screen and shown-latitudes/longitudes-area is known. So, x meters can be converted to latitiude/longitude difference easily by this ratio. would it change then ? On Jul 15, 12:59 pm, siddharth srivastava akssps...@gmail.com wrote: Hi If I have a (latitude, langitude) as well as pixel positions of those locations, then how can (longitude, latitude) or pixel coordinates of a point x metres away can be found ? If this information is not enough, what else information might be required ? -- Siddharth Srivastava When you have learned to snatch the error code from the trap frame, it will be time for you to leave. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Siddharth Srivastava When you have learned to snatch the error code from the trap frame, it will be time for you to leave. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: graph
Construct the transitive closure of the graph. You can use Warshall's algorithm, which is O(v^3) in run time. If any row of the adjacency matrix is all 1's, the corresponding vertex can reach all others. You can ignore the diagonal element if you don't care whether vertices are reachable from themselves (i.e. whether they are contained in a cycle). On Jul 12, 1:06 pm, Love-143 lovekesh6mn...@gmail.com wrote: 1.Give an efficient algorithm which takes as input a directed graph G = (V,E), and determines whether or not there is a vertex s is in V from which all other vertices are reachable.? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] The strong NO to circular lists argument
http://groups.google.com/group/comp.lang.misc/browse_thread/thread/35967349de8446c1# -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming Problem on Strings
@Ajeet * Google Dyck words* Mohit On Mon, Jul 12, 2010 at 1:43 PM, aejeet aej...@gmail.com wrote: A string can contain only the characters A and B. The string formation must follow the following rules 1. The number of occurrences of A and that of B must be equal in the string 2. For any prefix of string, the number occurrences of A must be greater than or equal to the number of occurrences of B. Now given an integer of length N, find the number of possible string formations adhering the rules above. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] 0-1 knapsack problem: uniqueness of optimal solutions
Hello: This is a problem in theoretical computer science and algorithms. When solving the 0-1 knapsack problem using dynamic programming, how can you use the resulting table to determine whether the optimal solution is unique? The problem is the following: A thief is going to steal some items and put them in his knapsack, which has a maximum weight capacity of W, a positive integer. He must select from a finite set of items, each of which has a positive integer weight and a positive integer value (in dollars, say). The thief has to determine which collection of items light enough for him to carry has the maximum total value. The solution method is described at http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf . The thief makes a table indexed by item number i (from 0 to the total number of items N) and total weight j (from 0 to W). Let c(i,j) be the number in the ith row and jth column. c(i,j) is the maximum total value of items chosen from among items #1, 2, ... i whose total weight is less than or equal to j. The 0 row and 0 column of the table are of course zero. It is a simple matter to fill in the table in row-major order. After the table is complete, c(N,W) is the maximum value of loot the thief can carry away. The completed table is then used to determine which items the thief should choose. My question is, how can you use the table to determine whether the optimal solution is unique? For example, suppose the knapsack capacity is 5 pounds, and there are four items, with weight/value pairs (1 lb, $1), (2 lb., $3), (3 lb., $3), (4 lb., $5). The thief should take either the first and fourth, or the second and third items, for a total weight of 5 lb. and value of $6. The solutions which I have read use a deterministic process for determining which items the thief takes, which gives you one solution but does not tell whether it is unique. Greg Spradlin -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic Programming Problem on Strings
that would be the Catlan number... Anil On Thu, Jul 15, 2010 at 11:41 PM, mohit ranjan shoonya.mo...@gmail.comwrote: @Ajeet * Google Dyck words* Mohit On Mon, Jul 12, 2010 at 1:43 PM, aejeet aej...@gmail.com wrote: A string can contain only the characters A and B. The string formation must follow the following rules 1. The number of occurrences of A and that of B must be equal in the string 2. For any prefix of string, the number occurrences of A must be greater than or equal to the number of occurrences of B. Now given an integer of length N, find the number of possible string formations adhering the rules above. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.