Re: [algogeeks] Appropriate data structure
I think by using min/max heap we can fetch the kth largest/smallest data from the heap. But here there is one more point how to ensure that the data is smallest in last kth day. Here you can use interval/segment(augmented version of heap tree) tree, where u can store the interval/segment on the basis of date and retrieve the same information. On Sunday, 15 July 2012 12:46:02 UTC+5:30, adarsh kumar wrote: Min or max heap accordingly. This will do the job in O(log n) time. On Sun, Jul 15, 2012 at 1:25 AM, Navin Kumar algorithm.i...@gmail.comwrote: A set of integer values are being received (1 per day). Store these values and at any given time, retrieve the min and max value over the last k days. What data structures would you use for storing and retrieving ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/2AhV1Xn3jD8J. To post to this group, send email to algogeeks@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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/ypiCXt9_1BQJ. To post to this group, send email to algogeeks@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: [amazon ] Finding Sub segment
just have a look on segment tree ( u can found good study material on segment tree at topcoder algorithm tutorial) On Monday, 25 June 2012 18:13:50 UTC+5:30, Navin Kumar wrote: please provide some good data structure to solve this problem: http://www.careercup.com/question?id=14062676 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/oqwFm1L_OMwJ. To post to this group, send email to algogeeks@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: MS Question: Add two large numbers where the numbers are stored in an array format
- in general we use polynomial addition for the same. If the numbers are carrying some additional information as ( particular base or pattern) another mechanise can be designed On Tuesday, 26 June 2012 15:40:39 UTC+5:30, ashgoel wrote: Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/eBEuUWRASgwJ. To post to this group, send email to algogeeks@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] How can we rank the players in a relative game Ranking Players
This is a live problem from interviewstreet.com: In the game challenges that we host, one practial problem that we face is to rank the contestants. Contestants need to submit code for a game problem and we pair up them against each other to see their relative performance. The aim of this tournament is to rank the players on the quality of code they submit. The task for you is to come up with an approach to rank the players using as few matches as possible. Submission Notes: You have to complete the function game given for this task. You can also create your own data structures and functions as needed. The function game is passed as parameter the number of players nPlayers and players have ids from 0 to nPlayers-1( 0 and nPlayers-1 included ). This function should return a vector of player ids. In this vector better players have lower indices. You can make calls to a hidden function gameResult which takes as argument the id of two players and conduct a match, this function returns the id of winner among the two players. Scoring: The list of player that you produce is compared against the hidden expected list, and for each player the difference in their position from both lists is added. If this sum is less than 3*nPlayers you get a score based on the number of calls you made to function gameResult. Less number of calls fetches higher score. Further Notes: This is approx-type problem so compile and test option might not work, so directly submit your code ans see the score in submissions tab. Since there is no deterministic minimal number of comparison, you may see you submission as wrong bu the score you get will give you an idea of your code's performance. The language shown for submission is C++, but it should not be a problem to the programmers of other language since the i/o and other details has been taken care of and you just need to write the appropriate functions. You can refer to http://www.cplusplus.com/doc/tutorial/ for more details if necessary. Standard header files/STL have already been included so you need not include/import additional header files. Note: nPlayers is not greater than 100. Different calls to gameResult between same pair of players may not necessarily return same winner always. We have tried to tweak a real game data by incorporate the elo rating system to determine the winner of matches. So in a call to gameResult, the winner is determined by that probability. Note: Don't give the the exact solution...jut m looking for an approach. Some of the approach I have followed are as: First Approach Have n/2 matches among n players then n/4 matches among previous looser and n/4 among previous winner Continue recursively. Second Approach Each player play against each other. The players having the maximum winning appear above in the returning queue Both the above approach doesn't seem working...can u please suggest what's going wrong here...and how to proceed further... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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] find the sum of very large binary sequence in O(n)
I have two binary sequences x and y (10 bits long)...I am taking a bool array to store it.I have to implement the summation operation( at most 40 summation operation)...while the bits patter in changing in x and yin my approach before performing a sum I am taking care of a. to check is sequence A or B is changed b. is the sum operations are continuousso i have not to sum up it again bcz in between there is no change in A and B But the output is killingwhat could be the better approach to implement the sum operation. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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] how can we check for primality for very large number
How can we check for the primality for very large number like 10^20 or more. It is not stored in integer So integer operation would not work on it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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] Practical way to check the primality in efficent time
what are the efficient ways to check that a given number is primer assuming the numbers can be large. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: How many ways n points can be connected
@Terence: The DP approach is nice. if we have constraint likewhile choosing the first 3 edges if it makes a triangle so we will require n edges to connect the graph completely...in the same fashion...after selecting 2 more edgesagain we have to check that is it making more trianglethen no. of total edges will increase by 1 and now we will require total n+1 edges. So in such a scenario how we can compute the sample space for every cases. so for all the all the valid m what should be the sample space for f(n,m). if M(m1,m2,...) is all the vaild m. Then how we can calcualte the dependency between sample space for f(n,m1) and f(n,m2). @Terence On Feb 9, 8:22 am, Terence technic@gmail.com wrote: Here is an DP solution: (consider only simple graph, with at most 1 line between any 2 distinct points, and no point connect to itself) Suppose f(n,m) is the number of ways m lines can connect n points. Then f(n,m) = 0 when m n-1 or m n(n-1)/2; For graph with n vertices and m edges (connected or disconnected), the overall count is C(n*(n-1)/2, m). There are 2 types: 1) connected: The number is f(n,m) that to be computed. 2) disconnected: Consider the connected component containing vertex 1, suppose it has n' vertices and m' edges. Then: a. there are C(n-1, n'-1) ways to select the points in the component b. there f(n',m') ways to connect the n' points using m' edges c. the rest n-n' vertices and m-m' edges can be arbitrarily placed. In summary, f(n,m) = C(n*(n-1)/2, m) - ∑(∑C(n-1, n'-1) * f(n', m') * C((n-n')*(n-n'-1)/2, m-m') for m' in [n'-1,m]) for n' in [1, n-1] (C(N, K) is binomial coefficient choosing K from N) The overall time complexity is O(m^2*n^2), and space complexity is O(mn) On 2012-2-8 12:03, rspr wrote: Hi All, can there be a formulato which we can estimate how many ways (n-1) lines can connect n points in the same way how many ways n lines can connect n points and so onthere is one way that we store the information in adjacency list or in adjacency matrixand will check for the same for every event in sample space.is there any other way that can optimize this calculation or may it possible that we can directly calculate it. . rspr- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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] How many ways n points can be connected
Hi All, can there be a formulato which we can estimate how many ways (n-1) lines can connect n points in the same way how many ways n lines can connect n points and so onthere is one way that we store the information in adjacency list or in adjacency matrixand will check for the same for every event in sample space.is there any other way that can optimize this calculation or may it possible that we can directly calculate it. . rspr -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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.
