Re: [algogeeks] Re: Amazon Question
I don't understand what you mean. Consider a simple inorder traversal of a balanced binary tree. Using recursion, the code is simply: void inorder(Node *node) { if (node == NULL) return; inorder(node->left); print(node->val); inorder(node->right); } What do you consider to be the above code's space complexity? It is O(log n) but what you are saying is that it is O(1)!! On Wed, Jan 26, 2011 at 2:23 AM, juver++ wrote: > @abovew NO! > > -- > 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. > -- 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.
Re: [algogeeks] Re: Amazon Question
@abovew NO! -- 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.
Re: [algogeeks] Re: Amazon Question
Theoretically, the internal stack used by recursive functions must be considered for space complexity. On Mon, Jan 24, 2011 at 5:40 AM, juver++ wrote: > internal stack != extra space > > -- > 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. > -- 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: Prime Numbers
The most efficient approach is to google "millionth prime number" and select the first hit. Dave On Jan 25, 6:00 am, siddharth srivastava wrote: > Hi > > Its an easy one but still I am looking for the most efficient approach. > > Find first 1 million prime numbers. > > -- > 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 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: find a line
@Sankalp: So what is your code? And what is the equation of the line? As I said, you can't always use a line through the origin. Dave On Jan 25, 5:49 am, sankalp srivastava wrote: > @dave > In this case , I could just shift my origin to the lowermost point :) > > On Jan 25, 10:14 am, Dave wrote: > > > > > @Sankalp: I wanted a point far enough outside the region that a line > > from any point in the region could not contain any other point in the > > region. There are several implications: 1) if the point is to the left > > of the region, it can't have an integer y coordinate between 0 and B. > > That is where the 0.5 comes from. Second, it seemed reasonable, but > > not necessary, to put Y near the middle of the range [0, B]. Then I > > just solved for an X that guaranteed that the slope of the line from > > any point in the region to the point (X, Y) had slope m satisfying -1/ > > A < m < 1/A. Then a line through any point (x1,y) could not intersect > > any point (x2,y-1) or (x3,y+1) within the region. > > > Regarding your algorithm: What does it do with A = B = 5 and points > > {(1,1), (2,2), (3,3), (4,4), (1,4)}. This example shows that you can't > > always use a line through (0,0). > > > Dave > > > On Jan 24, 10:15 pm, sankalp srivastava > > wrote: > > > > @ > > > Dave > > > How did you come up with this solution? > > > Also Y=floor(B)/2+.5 , X=-A*(B-Y) or X=-AB +AY or Y=X/A+B . this is > > > the equation of a line with slope 1/A and an intercept of B on Y > > > axis .I don't quite get this.!!Please elaborate . > > > Meanwhile , this is my approach . > > > > The slope of the line wil be between the maximum's of the two points > > > i.e in the case of (10,0)..(10,10)...It will be between 0 and 90 > > > degrees as all the points lie between them . Now we can just binary > > > search over this slope checking for the slope values . The slope and > > > set cardinality is also a monotonic function , so I guess binary > > > search approach will work , but the time taken will be nlog n . Please > > > correct me if I'm wrong . > > > #include > > > struct point > > > { > > > int x ; > > > int y ;}; > > > > using namespace std ; > > > // the given points > > > point p[100]; > > > int main() > > > { > > > int n; > > > cin>>n;//number of points > > > for(int i=0;i > > { > > > cin>>p[i].x>>p[i].y; > > > } > > > int high=90; > > > int low=0; > > > int mid; > > > //the line is supposed to start from 0,0 > > > while(low<=high) > > > { > > > mid=(high+low)/2; > > > if(haspoints(mid)<0) > > > //upper has less points than below > > > low=mid+1; > > > else if(haspoints(mid)>0) > > > //lower has more points than upper > > > high=mid-1; > > > else > > > {//we found our answer > > > cout< > > return 0; > > > } > > > } > > > return 0; > > > > } > > > > On Jan 24, 9:30 am, Dave wrote: > > > > > Generalizing the problem, let there be n points (x_i, y_i), where x_i > > > > and y_i are integers with 1 <= x_i <= A and 1 <= y_i <= B. A line > > > > separating the points into two sets of equal cardinality can be found > > > > as follows: Let Y = floor(B/2) + 0.5, and let X = -A * (B - Y). Find > > > > the slopes of the lines from the point (X, Y) to each (x_i, y_i). The > > > > point (X, Y) is constructed so that each of these slopes will be > > > > distinct. Find the median M of these slopes. Then the line > > > > > y = M(x - X) + Y > > > > > will separate the points as desired. It will pass through exactly one > > > > of the points if n is odd, and will miss all of the points if n is > > > > even. This is O(n) in time and O(n) in space, where n is the number of > > > > points. > > > > > Dave > > > > > On Jan 21, 11:45 pm, Divya Jain wrote: > > > > > > assume the region to be (0,0) , (10,0), (0,10), (10,10) > > > > > > On 22 January 2011 08:33, Dave wrote: > > > > > > > @Divya: The coordinates of the points are between 0 and 1 and are > > > > > > integers. That can't be right. > > > > > > > Dave > > > > > > > On Jan 21, 1:46 pm, divya wrote: > > > > > > > Within a 2D space, there is a batch of points(no duplicate) in the > > > > > > > region (0,0),(0,1),(1,0),(1,1), try to find a line which can > > > > > > > divide > > > > > > > the region to 2 parts with half points in each .the input will be > > > > > > > an > > > > > > > array of points and the length of the array. > > > > > > > struct point{ > > > > > > > int x; > > > > > > > int y;}; > > > > > > > > input : struct point * points, int length > > > > > > > -- > > > > > > You received this message because you are subscribed to the Google > > > > > > Groups > > > > > > "Algorithm Geeks" group. > >
Re: [algogeeks] NAGARRO CODING QUES............
thanks On 25 January 2011 01:50, Balaji Ramani wrote: > We do not compare to a value. We compare each pair to current min and if > the absolute sum of the current pair is less than the current min, we make > the current pair sum the current min. > > Do checkout this link: http://geeksforgeeks.org/?p=4034 > > Thanks, > Balaji. > > On Tue, Jan 25, 2011 at 9:35 AM, siddharth srivastava > wrote: > >> Hi >> >> On 24 January 2011 12:55, Balaji Ramani wrote: >> >>> @Siddharth >>> >>> However if the input range is unknown, it can be solved through an >>> entirely different approach after sorting and then using two pointers moving >>> either side from the positive-negative boundary. O(nlogn) + O(n) = O(nlogn) >>> >> >> yes I meant this case only. But to what value would you compare if you >> want the sum to be closest to zero and lets say that none of the elements >> sum up to zero. >> >>> >>> Thanks, >>> Balaji. >>> >>> >>> On Mon, Jan 24, 2011 at 11:03 PM, siddharth srivastava < >>> akssps...@gmail.com> wrote: >>> If the same question is modified as: Find two numbers whose sum is closest to zero in the given array. On 24 January 2011 16:08, juver++ wrote: > Its name is meet-in-the-middle technique. > > -- > 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. > -- 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 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 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. >>> >> >> >> >> -- >> 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 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 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. > -- 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 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] Prime Numbers
Hi Its an easy one but still I am looking for the most efficient approach. Find first 1 million prime numbers. -- 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 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: find a line
@dave In this case , I could just shift my origin to the lowermost point :) On Jan 25, 10:14 am, Dave wrote: > @Sankalp: I wanted a point far enough outside the region that a line > from any point in the region could not contain any other point in the > region. There are several implications: 1) if the point is to the left > of the region, it can't have an integer y coordinate between 0 and B. > That is where the 0.5 comes from. Second, it seemed reasonable, but > not necessary, to put Y near the middle of the range [0, B]. Then I > just solved for an X that guaranteed that the slope of the line from > any point in the region to the point (X, Y) had slope m satisfying -1/ > A < m < 1/A. Then a line through any point (x1,y) could not intersect > any point (x2,y-1) or (x3,y+1) within the region. > > Regarding your algorithm: What does it do with A = B = 5 and points > {(1,1), (2,2), (3,3), (4,4), (1,4)}. This example shows that you can't > always use a line through (0,0). > > Dave > > On Jan 24, 10:15 pm, sankalp srivastava > wrote: > > > > > @ > > Dave > > How did you come up with this solution? > > Also Y=floor(B)/2+.5 , X=-A*(B-Y) or X=-AB +AY or Y=X/A+B . this is > > the equation of a line with slope 1/A and an intercept of B on Y > > axis .I don't quite get this.!!Please elaborate . > > Meanwhile , this is my approach . > > > The slope of the line wil be between the maximum's of the two points > > i.e in the case of (10,0)..(10,10)...It will be between 0 and 90 > > degrees as all the points lie between them . Now we can just binary > > search over this slope checking for the slope values . The slope and > > set cardinality is also a monotonic function , so I guess binary > > search approach will work , but the time taken will be nlog n . Please > > correct me if I'm wrong . > > #include > > struct point > > { > > int x ; > > int y ;}; > > > using namespace std ; > > // the given points > > point p[100]; > > int main() > > { > > int n; > > cin>>n;//number of points > > for(int i=0;i > { > > cin>>p[i].x>>p[i].y; > > } > > int high=90; > > int low=0; > > int mid; > > //the line is supposed to start from 0,0 > > while(low<=high) > > { > > mid=(high+low)/2; > > if(haspoints(mid)<0) > > //upper has less points than below > > low=mid+1; > > else if(haspoints(mid)>0) > > //lower has more points than upper > > high=mid-1; > > else > > {//we found our answer > > cout< > return 0; > > } > > } > > return 0; > > > } > > > On Jan 24, 9:30 am, Dave wrote: > > > > Generalizing the problem, let there be n points (x_i, y_i), where x_i > > > and y_i are integers with 1 <= x_i <= A and 1 <= y_i <= B. A line > > > separating the points into two sets of equal cardinality can be found > > > as follows: Let Y = floor(B/2) + 0.5, and let X = -A * (B - Y). Find > > > the slopes of the lines from the point (X, Y) to each (x_i, y_i). The > > > point (X, Y) is constructed so that each of these slopes will be > > > distinct. Find the median M of these slopes. Then the line > > > > y = M(x - X) + Y > > > > will separate the points as desired. It will pass through exactly one > > > of the points if n is odd, and will miss all of the points if n is > > > even. This is O(n) in time and O(n) in space, where n is the number of > > > points. > > > > Dave > > > > On Jan 21, 11:45 pm, Divya Jain wrote: > > > > > assume the region to be (0,0) , (10,0), (0,10), (10,10) > > > > > On 22 January 2011 08:33, Dave wrote: > > > > > > @Divya: The coordinates of the points are between 0 and 1 and are > > > > > integers. That can't be right. > > > > > > Dave > > > > > > On Jan 21, 1:46 pm, divya wrote: > > > > > > Within a 2D space, there is a batch of points(no duplicate) in the > > > > > > region (0,0),(0,1),(1,0),(1,1), try to find a line which can divide > > > > > > the region to 2 parts with half points in each .the input will be an > > > > > > array of points and the length of the array. > > > > > > struct point{ > > > > > > int x; > > > > > > int y;}; > > > > > > > input : struct point * points, int length > > > > > > -- > > > > > 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 > > > > .com> > > > > > . > > > > > For more options, visit this group at > > > > >http://groups.google.com/group/algogeeks?hl=en.-Hidequotedtext - > > > > > - Show quoted text -- Hide quoted text - > > > - Show quoted text - -- You received
[algogeeks] Re: Good Maths Question
Correct me if I'm wrong dp[i][j]=how many numbers of length i with the last digit j(int base 10) dp[0][j]=0 dp[i][0]=dp[i-1][0] , last digit can't be zero otherwise the number has i-1 digits , not j; now the recursion to pass from one state to the next dp[i][j]=dp[i-1][k]+1(for each value of k such that k is less than j , from 0 to k) That is to say , the number of numbers with length i and last digit j , will be equal to the number of numbers with the last digit k , for each k less than j .One is added because , we must not have included the 0 in the last case , but we will include the zero case here . this one corresponds to zero case . Finally , the answer will be dp[n][j] , 1<=j<=9 , sum up all these and u have the answer For example for 2 digits dp[1][1-9]=1 , as nothing preceeds them and as said in the problem , one digit numbers are always increasing/decreasing . next dp[2][1]=dp[1][1](As only 1 is less than , equal to 1 , the last digit in this state) dp[2][2]=dp[1][1]+dp[1][2] =2( 1,2 and 2,2) Continuing this way , we will get the answer , may be 50 , though i din code it . similarly , for 3 digits Correct me if not! On Jan 25, 12:06 am, juver++ wrote: > dp[i][j] - how many numbers of length i and with the last digit j. > Apply the scheme to increasing and decreasing number, then find ratio. -- 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] Very Urgently Required: Oracle Retek consultant
Very Hot Requirement Immed Need (Interview) Send resume on *stevewoods...@gmail.com* Job Title:Oracle Retek Consultant Location: SCOTT LANGFORD,SC Duration:6+Months Job Description: come in and assist with BI Integration of Tetradata - specifically, client has an Oracle backend and integrates Tetradata with MicroStrategy - experience with Oracle, Tetradata and Microstrategy -- 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] Very Urgently Required: SAP FI/CO-MO
Very Hot Requirement Immed Need (Interview) Send resume on *stevewoods...@gmail.com* Job Title:*SAP FICO *Consultant Location:Saint Charles,*MO* Duration:3+Months *SAP FICO Consultant with Asset Accounting Experience* Job Description: *5+ years of SAP FICO* implementation experience; Strong SAP FICO experience with ability to blueprint and configure enhancements to add additional functionality; Implementation experience with SAp Asset Accounting; ECC 6.0 experience; Ability to work in a team environment and deliver enhancements on time; Ability to train business users on new functionality; Excellent verbal and written communication skills. -- 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] Very Urgently Required: SAP FI/CO-MO
Strong SAP FICO experience with ability to blueprint and configure enhancements to add additional functionality;Implementation experience with SAp Asset Accounting; ECC 6.0 experience;Ability to work in a team environment and deliver enhancements on time;Ability to train business users on new functionality;Excellent verbal and written communication skills. Send resumes on stevewoods...@gmail.com -- 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] Call for Papers: Special Track on Software Engineering Entrepreneurship (STSEE’11), USA, July 18-21, 2011
Special Track on Software Engineering Entrepreneurship (STSEE’11) July 18-21, 2011, Las Vegas, USA A number of Special Sessions on Software Engineering Entrepreneurship will be organized within the 2011 International Conference on Software Engineering Research and Practice (SERP’11), July 18-21, 2011, Monte Carlo Resort, Las Vegas, USA. This conference is an annual meeting featuring quality papers focusing on the latest developments in Software Engineering. The goal of the Special Sessions is to encourage entrepreneurship education, practice, and implementation within the software engineering community in both industry and academia. All papers that address entrepreneurship or innovation in a software engineering context are welcome. Papers that address one or more of the following broad themes are of particular interest: • Innovation in Software Engineering • Integrating Software Business and Research Perspectives • New Opportunities within the Software Industry • Strategic Planning Processes in the Software Firms • International/Global Software Engineering Entrepreneurship • Software Engineering Entrepreneurship Education • Software Idea Evaluation • Creating Software Engineering Entrepreneurial Networks • Software Engineering Entrepreneurial Process • Green Software Innovation • Methods and Tools for Software Innovation • Developing Winning Software Marketing Plan • Software Re-Engineering Entrepreneurship • Software Entrepreneurial Finance and Venture Capital Submission Guidelines _ • Prospective authors are invited to submit their draft paper (5-8 pages - single space, font size of 10 to 12) via email to daim...@udmercy.edu (Kevin Daimi). MS document and PDF formats are preferable • Papers must not have been previously published or currently submitted for publication elsewhere • The first page of the draft paper should include: o The title of the paper o Name, affiliation, postal address, E-mail address, telephone number, and fax number for each author o The name of the author who will be presenting the paper (if accepted) and a maximum of 5 keywords. • Authors of accepted papers should submit their Camera-Ready papers in PDF format. The maximum number of pages in the final papers is 7. Papers must conform to IEEE style guidelines at www.ieee.org/portal/cms_docs_iportals/iportals/publications/journmag/transactions/TRANS-JOUR.doc Conference Proceedings __ Accepted papers will appear in the SERP’11 Conference Proceedings – The proceedings will be indexed by major databases (including: Inspec / IET / The Institute for Engineering and Technology, DBLP / Computer Science Bibliography). The proceedings (with ISBN in printed copy) will be available for distribution at the conference as well as it will be made available online (after the conference) for the world-wide access. WorldComp annual conferences are now listed as "Top Conferences in Computer Science" by Microsoft Academic Search (based on the number of citations to papers). These include PDPTA, ICAI/IC-AI, IPCV/CISST, GEM, SAM, BIOCOMP, CDES, ICOMP/IC, SERP, SWWS, ICWN, CSC, DMIN, ERSA, ESA, FECS, FCS, and others. Important Dates ___ Submission deadline: March 10, 2011 Notification of Acceptance: April 03, 2011 Final papers Due: April 24, 2011 Website ___ www.worldacademyofscience.org/worldcomp11/ws/conferences/serp11/Workshops%20-%20Sessions -- 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: distinct substring
suffix trees. -- 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.
Re: [algogeeks] 2 d matrix
@snehal can elements can be in any order?? i mean if ith row contains {1,2,3,4} and jth column contains {4,3, 2,1} it will be a match or not >> On Tue, Jan 25, 2011 at 7:02 PM, snehal jain wrote: > you have a matrix containing integers (no range provided). The matrix > is randomly populated with integers. We need to devise an algorithm > where by we find a row number which matches exactly with a column > within the matrix. We need to return the row number and the column > number for the match. The order of of the matching elements is the > same. For example, If, i'th row matches with j'th column, and i'th row > contains the elements - [1,4,5,6,3]. Then jth column would also > contain the elements - [1,4,5,6,3]. Given an n x n matrix . > > -- > 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. > > -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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] 2 d matrix
you have a matrix containing integers (no range provided). The matrix is randomly populated with integers. We need to devise an algorithm where by we find a row number which matches exactly with a column within the matrix. We need to return the row number and the column number for the match. The order of of the matching elements is the same. For example, If, i'th row matches with j'th column, and i'th row contains the elements - [1,4,5,6,3]. Then jth column would also contain the elements - [1,4,5,6,3]. Given an n x n matrix . -- 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] distinct substring
given a string find the number of distinct substrings of the string. ex: input-> output-> 4(a, aa, aaa, ) input->abcd output->10(a, b, c, d, ab, bc, cd, abc, bcd, abcd) -- 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.
Re: [algogeeks] Re: Good Maths Question
I remember solving this @ spoj Here is an O(1) solution #!/usr/bin/python def solve(n): val=1 for i in range(1,9): val*=(n+i) return float((n+9)/9.0-(40320.0/val)) cases=int(raw_input()) while(cases): cases-=1 n=int(raw_input()) print '%.6f'%(solve(n)) On Tue, Jan 25, 2011 at 6:28 PM, juver++ wrote: > @Skywalker your solution is ok. But is works only for the small value of n. > Cause amount of desired numbers with n=10^6 digits is very big )) > After n=27 there is a regularity for the ratio. > However, here is more simplified dp - http://codepad.org/9bzFzDtV > > -- > 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. > -- 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.
Re: [algogeeks] Re: Good Maths Question
@Skywalker your solution is ok. But is works only for the small value of n. Cause amount of desired numbers with n=10^6 digits is very big )) After n=27 there is a regularity for the ratio. However, here is more simplified dp - http://codepad.org/9bzFzDtV -- 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.
Re: [algogeeks] Re: Good Maths Question
If the below link does not work- http://codepad.org/MDoQ8Kry ~Shiv. ** Hi, > > Here is a solution I have coded- http://codepad.org/bPOoakm3 > > Please let me know if you see any errors. > > *Logic for decreasing numbers-* > Number of 'n' digit valid numbers (say 2), starting with digit 'k' (say 5); > will be sum of number of 'n' digit valid numbers starting with 'k-1' and > number of 'n-1' digit number starting with 'k' [not k-1 as 55 is a valid > decreasing number.]. > > I have used the same thought process for increasing numbers. > > ~Shiv. > > P.S. To avoid using too much memory, I have used only two int[10] arrays. I > keep overwriting them. And to know which array is being filled now, I am > using even/odd criteria. > > -- 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.
Re: [algogeeks] Re: Good Maths Question
Hi, Here is a solution I have coded- http://codepad.org/bPOoakm3 Please let me know if you see any errors. *Logic for decreasing numbers-* Number of 'n' digit valid numbers (say 2), starting with digit 'k' (say 5); will be sum of number of 'n' digit valid numbers starting with 'k-1' and number of 'n-1' digit number starting with 'k' [not k-1 as 55 is a valid decreasing number.]. I have used the same thought process for increasing numbers. ~Shiv. P.S. To avoid using too much memory, I have used only two int[10] arrays. I keep overwriting them. And to know which array is being filled now, I am using even/odd criteria. -- 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.
Re: [algogeeks] NAGARRO CODING QUES............
We do not compare to a value. We compare each pair to current min and if the absolute sum of the current pair is less than the current min, we make the current pair sum the current min. Do checkout this link: http://geeksforgeeks.org/?p=4034 Thanks, Balaji. On Tue, Jan 25, 2011 at 9:35 AM, siddharth srivastava wrote: > Hi > > On 24 January 2011 12:55, Balaji Ramani wrote: > >> @Siddharth >> >> However if the input range is unknown, it can be solved through an >> entirely different approach after sorting and then using two pointers moving >> either side from the positive-negative boundary. O(nlogn) + O(n) = O(nlogn) >> > > yes I meant this case only. But to what value would you compare if you want > the sum to be closest to zero and lets say that none of the elements sum up > to zero. > >> >> Thanks, >> Balaji. >> >> >> On Mon, Jan 24, 2011 at 11:03 PM, siddharth srivastava < >> akssps...@gmail.com> wrote: >> >>> If the same question is modified as: >>> Find two numbers whose sum is closest to zero in the given array. >>> >>> >>> On 24 January 2011 16:08, juver++ wrote: >>> Its name is meet-in-the-middle technique. -- 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. >>> >>> >>> >>> -- >>> 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 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 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. >> > > > > -- > 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 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 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.