Re: [algogeeks] stack. Mid element in o(1)
Code is here http://codebin.org/view/30e9f2c0. Logic is made clear by the variable names. Idea is similar to the one which is used to build a queue using 2 stacks. On Wed, May 22, 2013 at 8:45 AM, MAC macatad...@gmail.com wrote: I think this is only possible if you make sure that at push you store the middle element with the top element as well .. this would mean push would cease to be o(1)become o(n) .. . or is there some other trick ? Veni Vedi Slumber ! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] stack. Mid element in o(1)
I think there is no need for such a complex code. use length() method to get the size of the stack and return the middle element i.e. m=S.length() if(m is even) return arr[m/2] else return arr[m+1/2] it can be done in O(const) time On Thu, May 23, 2013 at 12:54 PM, Avi Dullu avi.du...@gmail.com wrote: Code is here http://codebin.org/view/30e9f2c0. Logic is made clear by the variable names. Idea is similar to the one which is used to build a queue using 2 stacks. On Wed, May 22, 2013 at 8:45 AM, MAC macatad...@gmail.com wrote: I think this is only possible if you make sure that at push you store the middle element with the top element as well .. this would mean push would cease to be o(1)become o(n) .. . or is there some other trick ? Veni Vedi Slumber ! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] stack. Mid element in o(1)
Using two stacks to simulate the getmiddle behavior. Amortized analysis can show each geimiddle is O(1) time complexity. Best, 2013/5/23 Prateek Jain prateek10011...@gmail.com I think there is no need for such a complex code. use length() method to get the size of the stack and return the middle element i.e. m=S.length() if(m is even) return arr[m/2] else return arr[m+1/2] it can be done in O(const) time On Thu, May 23, 2013 at 12:54 PM, Avi Dullu avi.du...@gmail.com wrote: Code is here http://codebin.org/view/30e9f2c0. Logic is made clear by the variable names. Idea is similar to the one which is used to build a queue using 2 stacks. On Wed, May 22, 2013 at 8:45 AM, MAC macatad...@gmail.com wrote: I think this is only possible if you make sure that at push you store the middle element with the top element as well .. this would mean push would cease to be o(1)become o(n) .. . or is there some other trick ? Veni Vedi Slumber ! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] PLease suggest the Algo for this problem
I have a list of N teams T1, T2, T3 … Tn. Each of these teams has played a match against every other team. I have a function displayResult(Team T1, Team T2), it returns the team which won the match between any two given teams T1 and T2. I have to write the teams in an order such the (n-1)th team (in the order) had lost to the nth team which in turn had lost to (n+1)th team. I want optimize code for this, please help. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: PLease suggest the Algo for this problem
This is not necessarily possible. If you have teams A, B, and C, it is possible that A beat B B beat C C beat A. Based on the first two games the ranking should be A,B,C. But based on the third game, C should be ranked higher than A. Don On May 23, 11:06 am, Nishant Pandey nishant.bits.me...@gmail.com wrote: I have a list of N teams T1, T2, T3 … Tn. Each of these teams has played a match against every other team. I have a function displayResult(Team T1, Team T2), it returns the team which won the match between any two given teams T1 and T2. I have to write the teams in an order such the (n-1)th team (in the order) had lost to the nth team which in turn had lost to (n+1)th team. I want optimize code for this, please help. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: PLease suggest the Algo for this problem
@DON, For example if in a particular order, the teams appeared as T1, T2, T3, T4 … then team T1 had lost to T2, T2 had lost to T3, and T3 had lost to T4… It may be possible that T3 lost to T1 .. but that need not be taken into consideration while writing the order. Only the neighboring elements should be such that the element on the left has lost to the element on the right. On Thu, May 23, 2013 at 8:47 PM, Don dondod...@gmail.com wrote: This is not necessarily possible. If you have teams A, B, and C, it is possible that A beat B B beat C C beat A. Based on the first two games the ranking should be A,B,C. But based on the third game, C should be ranked higher than A. Don On May 23, 11:06 am, Nishant Pandey nishant.bits.me...@gmail.com wrote: I have a list of N teams T1, T2, T3 … Tn. Each of these teams has played a match against every other team. I have a function displayResult(Team T1, Team T2), it returns the team which won the match between any two given teams T1 and T2. I have to write the teams in an order such the (n-1)th team (in the order) had lost to the nth team which in turn had lost to (n+1)th team. I want optimize code for this, please help. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: PLease suggest the Algo for this problem
http://www.careercup.com/question?id=14804702 On Thu, May 23, 2013 at 8:53 PM, Nishant Pandey nishant.bits.me...@gmail.com wrote: @DON, For example if in a particular order, the teams appeared as T1, T2, T3, T4 … then team T1 had lost to T2, T2 had lost to T3, and T3 had lost to T4… It may be possible that T3 lost to T1 .. but that need not be taken into consideration while writing the order. Only the neighboring elements should be such that the element on the left has lost to the element on the right. On Thu, May 23, 2013 at 8:47 PM, Don dondod...@gmail.com wrote: This is not necessarily possible. If you have teams A, B, and C, it is possible that A beat B B beat C C beat A. Based on the first two games the ranking should be A,B,C. But based on the third game, C should be ranked higher than A. Don On May 23, 11:06 am, Nishant Pandey nishant.bits.me...@gmail.com wrote: I have a list of N teams T1, T2, T3 … Tn. Each of these teams has played a match against every other team. I have a function displayResult(Team T1, Team T2), it returns the team which won the match between any two given teams T1 and T2. I have to write the teams in an order such the (n-1)th team (in the order) had lost to the nth team which in turn had lost to (n+1)th team. I want optimize code for this, please help. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: PLease suggest the Algo for this problem
If you create a directed graph where each node is a team and an edge exists from A-B if A lost to B, then find a Hamiltonian Path in the graph. That path will be the sequence you need. Don On May 23, 12:02 pm, bharat b bagana.bharatku...@gmail.com wrote: http://www.careercup.com/question?id=14804702 On Thu, May 23, 2013 at 8:53 PM, Nishant Pandey nishant.bits.me...@gmail.com wrote: @DON, For example if in a particular order, the teams appeared as T1, T2, T3, T4 … then team T1 had lost to T2, T2 had lost to T3, and T3 had lost to T4… It may be possible that T3 lost to T1 .. but that need not be taken into consideration while writing the order. Only the neighboring elements should be such that the element on the left has lost to the element on the right. On Thu, May 23, 2013 at 8:47 PM, Don dondod...@gmail.com wrote: This is not necessarily possible. If you have teams A, B, and C, it is possible that A beat B B beat C C beat A. Based on the first two games the ranking should be A,B,C. But based on the third game, C should be ranked higher than A. Don On May 23, 11:06 am, Nishant Pandey nishant.bits.me...@gmail.com wrote: I have a list of N teams T1, T2, T3 … Tn. Each of these teams has played a match against every other team. I have a function displayResult(Team T1, Team T2), it returns the team which won the match between any two given teams T1 and T2. I have to write the teams in an order such the (n-1)th team (in the order) had lost to the nth team which in turn had lost to (n+1)th team. I want optimize code for this, please help. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: PLease suggest the Algo for this problem
@Don : you are correct but hamiltanion path problem is NPC right? quicksort algorithm is good solution. I already shared algorithm in above link. On Thu, May 23, 2013 at 10:25 PM, Don dondod...@gmail.com wrote: If you create a directed graph where each node is a team and an edge exists from A-B if A lost to B, then find a Hamiltonian Path in the graph. That path will be the sequence you need. Don On May 23, 12:02 pm, bharat b bagana.bharatku...@gmail.com wrote: http://www.careercup.com/question?id=14804702 On Thu, May 23, 2013 at 8:53 PM, Nishant Pandey nishant.bits.me...@gmail.com wrote: @DON, For example if in a particular order, the teams appeared as T1, T2, T3, T4 … then team T1 had lost to T2, T2 had lost to T3, and T3 had lost to T4… It may be possible that T3 lost to T1 .. but that need not be taken into consideration while writing the order. Only the neighboring elements should be such that the element on the left has lost to the element on the right. On Thu, May 23, 2013 at 8:47 PM, Don dondod...@gmail.com wrote: This is not necessarily possible. If you have teams A, B, and C, it is possible that A beat B B beat C C beat A. Based on the first two games the ranking should be A,B,C. But based on the third game, C should be ranked higher than A. Don On May 23, 11:06 am, Nishant Pandey nishant.bits.me...@gmail.com wrote: I have a list of N teams T1, T2, T3 … Tn. Each of these teams has played a match against every other team. I have a function displayResult(Team T1, Team T2), it returns the team which won the match between any two given teams T1 and T2. I have to write the teams in an order such the (n-1)th team (in the order) had lost to the nth team which in turn had lost to (n+1)th team. I want optimize code for this, please help. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] amazon f2f round question ..
On Sat, May 11, 2013 at 10:29 AM, Aman Jain pureama...@gmail.com wrote: 2. from this no*de u*, again apply* dfs* to find longest distant node from this node.Let us say that node is v. Small doubt about the solution. Consider this graph a - b - c - d You randomly choose vertex 'b' and do a DFS. Your u will be vertex 'd'. Then you do DFS from d, but its out degree is 0. So your DFS ends at 'd' itself and you report the solution as b-c-d. But the solution is a-b-c-d. What did I miss? My proposal: Topological Sort http://en.wikipedia.org/wiki/Topological_sorting the graph and keep removing the nodes from vertices which have out degree of 0 (given the DAG, there will always be atleast one such vertex). Rest is self explanatory :) Veni Vedi Slumber ! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
