Re: [algogeeks] power of 3
Number exponentiation On Fri, Jan 21, 2011 at 1:05 PM, snehal jain learner@gmail.com wrote: Given M, find if M = 3^x for some positive integer x efficiently. DO NOT think of log, pow etc -- 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.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 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] Number Placement Problem.......
* Place N number from 1 to N, in 2N positions in such a way so that there are Exactly “a” number of cells between two placed locations of number “a”. Write a program to display numbers placed in this way. Example:- (1) One of the possible placement for 7 numbers in 14 positions is : 5 7 2 3 6 2 5 3 4 7 1 6 1 4 There are exactly five other numbers between two occurrences of 5, exactly seven other numbers between two occurrences of number 7 and the same is true for all other number placements. * -- Only G!! -- 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] Distance in a dictionary
You have a dictionary of N words each of 3 chars. Given 2 words you have to find the optimum path between the 2 words. The optimum path contains the words in the dictionary each word at a distance of 1 from the previous word. for eg source = cat , target = sun path is cat - bat - but - bun - sun given all these words are in the dictionary -- 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 path in two nodes of a binary search tree
Suppose you have a tree. A binary tree (for something like simplicity :p). You are traversing it (using infix, postfix or prefix) to search for a node. You find your required node. You just realized that you need to know the path from this node back to the root node (and/or vice versa). Given the following description of the structure of the tree node that you “cant” change: struct node{Data data; node *right,*left;}; what will you strategy be to tackle this problem. To make it more intresting (or maybe just the application of the above problem) suppose you find the node A and a node B in consecutive searches. Now what will your strategy be to show a path from A to B. (not neccesarily from the root of the whole tree, but possibly). -- 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: pairwise sum
Here is solution from Igor Naverniouk(Google): http://shygypsy.com/tools/pairsums.cpp -- 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] power of 3
binary search on the answer and then fast exponentiation. -- 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] power of 3
The most well done solution is to store possible powers of 3 in a table (this table will be small), and then try to find number M. -- 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] power of 3
@ above m nt getting binary search and fast exponentiation .. please elaborate. On Fri, Jan 21, 2011 at 2:07 PM, juver++ avpostni...@gmail.com wrote: The most well done solution is to store possible powers of 3 in a table (this table will be small), and then try to find number M. -- 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.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 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: pairwise sum
@ above cn u please explain your logic. On Fri, Jan 21, 2011 at 2:02 PM, juver++ avpostni...@gmail.com wrote: Here is solution from Igor Naverniouk(Google): http://shygypsy.com/tools/pairsums.cpp -- 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.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 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] top search queries
Magy! receives a huge amount of queries everyday. They don’t want to store all of them, since many of the queries are unique (submitted just one time by just one user). Anyway, for caching reason they want to understand what are the queries whose frequency exceed s=0.1%. How do you solve the problem? Remember we don’t want to store all the queries. Hint: split the stream into windows and accept some error in estimation. -- 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] Finding elements near the median
Given an unsorted array A of n distinct numbers and an integer k where 1 = k = n, design an algorithm that finds the k numbers in A that are closest in value to the median of A in O(n) time. -- 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] Minimum positive-sum subarray
In this variation of the Maximum-Sum Subarray Problem, you are given a one-dimensional array A[1 : n] of positive or negative numbers, and you are asked to find a subarray A[i : j] such that the sum of its elements is (1) strictly greater than zero, and (2) minimum. In other words, you want to find a subarray of smallest positive sum. Give an O(nlog^2n) Divide and Conquer algorithm and a O(nlogn) Dynamic Programming Algorithm. -- 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] merging 2 search trees
You are given two height balanced binary search trees T and T’, storing m and n elements respectively. Every element of tree T is smaller than every element of tree T’. Every node u also stores height of the subtree rooted at it. Using this extra information how can you merge the two trees in time O(log m + log n) (preserving both the height balance and the order)? -- 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] power of 3
int l = 0, r = ...; while (l r) { int m = (l + r) / 2; int p = power(3, m); if (p M) r = m - 1; else if (p M) l = m + 1; else print 3^m = M; } -- 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: pairwise sum
http://www.topcoder.com/tc?module=Staticd1=match_editorialsd2=srm182 -- 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] array
Given an array of integers where some numbers repeat 1 time, some numbers repeat 2 times and only one number repeats 3 times, how do you find the number that repeat 3 times. please give if you have solution other than hashing and sorting.. -- 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] power of 3
Below is code for modular exponentation in general // (a^b)%c int modexp(int a,int b,int c) { int ans=1; while(b) { if(b1) ans=(ans*a)%c; a=(a*a)%c; b=1; } return ans; } On Fri, Jan 21, 2011 at 3:27 PM, juver++ avpostni...@gmail.com wrote: int l = 0, r = ...; while (l r) { int m = (l + r) / 2; int p = power(3, m); if (p M) r = m - 1; else if (p M) l = m + 1; else print 3^m = M; } -- 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.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 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] zig zag
How about this dp solution? Let dp[i][j][k] be the lookup table. It is defined as the longest zigzag sequence in the range i and j. k is either 0 or 1. 0- if the sequence ends with a positive difference, i.e last element is greater than the last to one. 1- if the sequence ends with a negative difference. Now we can define the recursive formula as follows, for(k=i;kj;k++) dp[i][j][0]= max(dp[i][j][0],dp[i][k][1]+dp[k+1][j][0]) dp[i][j][1]= max(dp[i][j][1],dp[i][k][0]+dp[k+1][j][1]) correct me if i am wrong. On Fri, Jan 21, 2011 at 12:48 PM, snehal jain learner@gmail.com wrote: A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence. For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero. Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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] power of 3
this will be O(log(n) * log(n)) solution On Fri, Jan 21, 2011 at 4:29 PM, abhijith reddy abhijith200...@gmail.comwrote: Below is code for modular exponentation in general // (a^b)%c int modexp(int a,int b,int c) { int ans=1; while(b) { if(b1) ans=(ans*a)%c; a=(a*a)%c; b=1; } return ans; } On Fri, Jan 21, 2011 at 3:27 PM, juver++ avpostni...@gmail.com wrote: int l = 0, r = ...; while (l r) { int m = (l + r) / 2; int p = power(3, m); if (p M) r = m - 1; else if (p M) l = m + 1; else print 3^m = M; } -- 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.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 algogeeks@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 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] power of 3
@juvir++ it was mentioned in question not to use log or power. isnt there any approach using bitwise operators On Fri, Jan 21, 2011 at 5:24 PM, Manmeet Singh mans.aus...@gmail.comwrote: this will be O(log(n) * log(n)) solution On Fri, Jan 21, 2011 at 4:29 PM, abhijith reddy abhijith200...@gmail.comwrote: Below is code for modular exponentation in general // (a^b)%c int modexp(int a,int b,int c) { int ans=1; while(b) { if(b1) ans=(ans*a)%c; a=(a*a)%c; b=1; } return ans; } On Fri, Jan 21, 2011 at 3:27 PM, juver++ avpostni...@gmail.com wrote: int l = 0, r = ...; while (l r) { int m = (l + r) / 2; int p = power(3, m); if (p M) r = m - 1; else if (p M) l = m + 1; else print 3^m = M; } -- 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.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 algogeeks@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 algogeeks@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 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] power of 3
O(lg(n)*lg(n)) is the complexity of the solution ! Not the solution. M=3^x We binary search on x and then compute 3^x in log(x) time using exponentiation. Hence the complexity. On Fri, Jan 21, 2011 at 5:50 PM, snehal jain learner@gmail.com wrote: @juvir++ it was mentioned in question not to use log or power. isnt there any approach using bitwise operators On Fri, Jan 21, 2011 at 5:24 PM, Manmeet Singh mans.aus...@gmail.comwrote: this will be O(log(n) * log(n)) solution On Fri, Jan 21, 2011 at 4:29 PM, abhijith reddy abhijith200...@gmail.com wrote: Below is code for modular exponentation in general // (a^b)%c int modexp(int a,int b,int c) { int ans=1; while(b) { if(b1) ans=(ans*a)%c; a=(a*a)%c; b=1; } return ans; } On Fri, Jan 21, 2011 at 3:27 PM, juver++ avpostni...@gmail.com wrote: int l = 0, r = ...; while (l r) { int m = (l + r) / 2; int p = power(3, m); if (p M) r = m - 1; else if (p M) l = m + 1; else print 3^m = M; } -- 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.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 algogeeks@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 algogeeks@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 algogeeks@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 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] power of 3
@snehal .. misread it .. my apologies. On Fri, Jan 21, 2011 at 5:56 PM, abhijith reddy abhijith200...@gmail.comwrote: O(lg(n)*lg(n)) is the complexity of the solution ! Not the solution. M=3^x We binary search on x and then compute 3^x in log(x) time using exponentiation. Hence the complexity. On Fri, Jan 21, 2011 at 5:50 PM, snehal jain learner@gmail.comwrote: @juvir++ it was mentioned in question not to use log or power. isnt there any approach using bitwise operators On Fri, Jan 21, 2011 at 5:24 PM, Manmeet Singh mans.aus...@gmail.comwrote: this will be O(log(n) * log(n)) solution On Fri, Jan 21, 2011 at 4:29 PM, abhijith reddy abhijith200...@gmail.com wrote: Below is code for modular exponentation in general // (a^b)%c int modexp(int a,int b,int c) { int ans=1; while(b) { if(b1) ans=(ans*a)%c; a=(a*a)%c; b=1; } return ans; } On Fri, Jan 21, 2011 at 3:27 PM, juver++ avpostni...@gmail.com wrote: int l = 0, r = ...; while (l r) { int m = (l + r) / 2; int p = power(3, m); if (p M) r = m - 1; else if (p M) l = m + 1; else print 3^m = M; } -- 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.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 algogeeks@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 algogeeks@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 algogeeks@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 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] power of 3
@snehal : YUP On Fri, Jan 21, 2011 at 5:57 PM, abhijith reddy abhijith200...@gmail.comwrote: @snehal .. misread it .. my apologies. On Fri, Jan 21, 2011 at 5:56 PM, abhijith reddy abhijith200...@gmail.comwrote: O(lg(n)*lg(n)) is the complexity of the solution ! Not the solution. M=3^x We binary search on x and then compute 3^x in log(x) time using exponentiation. Hence the complexity. On Fri, Jan 21, 2011 at 5:50 PM, snehal jain learner@gmail.comwrote: @juvir++ it was mentioned in question not to use log or power. isnt there any approach using bitwise operators On Fri, Jan 21, 2011 at 5:24 PM, Manmeet Singh mans.aus...@gmail.comwrote: this will be O(log(n) * log(n)) solution On Fri, Jan 21, 2011 at 4:29 PM, abhijith reddy abhijith200...@gmail.com wrote: Below is code for modular exponentation in general // (a^b)%c int modexp(int a,int b,int c) { int ans=1; while(b) { if(b1) ans=(ans*a)%c; a=(a*a)%c; b=1; } return ans; } On Fri, Jan 21, 2011 at 3:27 PM, juver++ avpostni...@gmail.comwrote: int l = 0, r = ...; while (l r) { int m = (l + r) / 2; int p = power(3, m); if (p M) r = m - 1; else if (p M) l = m + 1; else print 3^m = M; } -- 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.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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 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] merging 2 search trees
Find the node in T which is the maximum(which is either the root or the rightmost in the right subtree). After finding this node, just make the right child of this node point to the root of T'. Correct me if i am wrong On Fri, Jan 21, 2011 at 2:43 PM, snehal jain learner@gmail.com wrote: You are given two height balanced binary search trees T and T’, storing m and n elements respectively. Every element of tree T is smaller than every element of tree T’. Every node u also stores height of the subtree rooted at it. Using this extra information how can you merge the two trees in time O(log m + log n) (preserving both the height balance and the order)? -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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] power of 3
@above it's a user-defined function using fast exponentiation -- 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] power of 3
@juver++ : the above is a user defined function. but its possible to the problem using bit wise operators. On Fri, Jan 21, 2011 at 7:29 PM, juver++ avpostni...@gmail.com wrote: @above it's a user-defined function using fast exponentiation -- 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.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 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] Distance in a dictionary
Its a state space search. Solve it by using any of the known search algorithms. BFS, Best first search, DFS, A* On Fri, Jan 21, 2011 at 2:00 PM, snehal jain learner@gmail.com wrote: You have a dictionary of N words each of 3 chars. Given 2 words you have to find the optimum path between the 2 words. The optimum path contains the words in the dictionary each word at a distance of 1 from the previous word. for eg source = cat , target = sun path is cat - bat - but - bun - sun given all these words are in the dictionary -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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] power of 3
@manmeet how? On Fri, Jan 21, 2011 at 7:36 PM, Manmeet Singh mans.aus...@gmail.comwrote: @juver++ : the above is a user defined function. but its possible to the problem using bit wise operators. On Fri, Jan 21, 2011 at 7:29 PM, juver++ avpostni...@gmail.com wrote: @above it's a user-defined function using fast exponentiation -- 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.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 algogeeks@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 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] Amazon Question
How do you find out the fifth maximum element in an binary search tree in efficient manner without using any 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.
[algogeeks] Re: Amazon Question
This question was posted some time ago. One solution is - start from the largest element (which is the righmost one in the tree). Then apply algorithm of searchin node's predecessor. It takes O(k) time to find k-th largest/smallest number. -- 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] power of 3
write n, n-1 to base 3 check if thr gives 0, if it gives no. is of form 3^n On Fri, Jan 21, 2011 at 8:04 PM, snehal jain learner@gmail.com wrote: @manmeet how? On Fri, Jan 21, 2011 at 7:36 PM, Manmeet Singh mans.aus...@gmail.comwrote: @juver++ : the above is a user defined function. but its possible to the problem using bit wise operators. On Fri, Jan 21, 2011 at 7:29 PM, juver++ avpostni...@gmail.com wrote: @above it's a user-defined function using fast exponentiation -- 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.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 algogeeks@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 algogeeks@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 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] OS galvin sol..
wow..thank you so much On Wed, Jan 19, 2011 at 2:08 PM, LALIT SHARMA lks.ru...@gmail.com wrote: -- Lalit Kishore Sharma, IIIT Allahabad (Amethi Capmus), 6th Sem. -- 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.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 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] Google Question
Assume you are writing number in ascending order to an array of constant size.once you reach the end of the array,you start writing from the beginning, thus writing over the oldest entries.Write an algorithm for finding a specific number in this array. -- 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] Sites for Interview Questions
http://www.ocf.berkeley.edu/~wwu/riddles/intro.shtml Rahul K Rai rahulpossi...@gmail.com On Tue, Jan 18, 2011 at 9:27 PM, Yellow Sapphire pukhraj7...@gmail.comwrote: Hi, Can someone suggest good books/websites/blogs for interview related questions. thanks-- YS -- 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.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 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: L values and r values
Thanks , btw the example was from Dragon Book of Compilers . . Any one knows an instructor manuall or some selected set of solutions for that . ? I have read it that they are not published On 1/21/11, Gene gene.ress...@gmail.com wrote: L and R values have great significance to language designers and compiler builders. They have some significance to language users, but most people don't have to think about them because the distinction is common sense. In your case, operates on L-values and always produces an R-value. Therefore (X) for any won't compile no matter what X is. -- 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. -- Rahul K Rai rahulpossi...@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.
RE: [algogeeks] Re: Sites for Interview Questions
One more interesting site is http://www.rawkam.com -Original Message- From: algogeeks@googlegroups.com [mailto:algogeeks@googlegroups.com] On Behalf Of awesomeandroid Sent: 19 January 2011 AM 09:15 To: Algorithm Geeks Subject: [algogeeks] Re: Sites for Interview Questions http://code-forum.blogspot.com On Jan 19, 7:10 am, rajeev kumar rajeevprasa...@gmail.com wrote: tryhttp://www.careercup.com/ http://www.careercup.com/Thanks, rajiv. On Tue, Jan 18, 2011 at 7:57 AM, Yellow Sapphire pukhraj7...@gmail.comwrote: Hi, Can someone suggest good books/websites/blogs for interview related questions. thanks-- YS -- 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.comalgogeeks%2Bunsubscribe@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thank You Rajeev Kumar -- 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] Sites for Interview Questions
Programming Interviews Exposed is a good one.. On Tue, Jan 18, 2011 at 9:27 PM, Yellow Sapphire pukhraj7...@gmail.comwrote: Hi, Can someone suggest good books/websites/blogs for interview related questions. thanks-- YS -- 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.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 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] Adobe Question
if sorted then a tweak in merge sort will work On 20 January 2011 23:23, nishaanth nishaant...@gmail.com wrote: Ya as Ashish said hashing is the best solution :) On Fri, Jan 14, 2011 at 6:00 PM, Ashish Goel ashg...@gmail.com wrote: ideally, a hashMap would be preferred walk through one array and set the corresponding entry, and then through another array, if any entry found, then they are not disjoint. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Fri, Jan 14, 2011 at 3:35 PM, bittu shashank7andr...@gmail.comwrote: how to find if two arrays of size n are disjoint or not in O(n) time ?? You can use only O(n) space The elements are +ve in the range 0 to n power 100.. Regards Shashank Mani -- 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.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 algogeeks@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. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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.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 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] merging 2 search trees
@ above height will not be balanced then On 21 January 2011 19:15, nishaanth nishaant...@gmail.com wrote: Find the node in T which is the maximum(which is either the root or the rightmost in the right subtree). After finding this node, just make the right child of this node point to the root of T'. Correct me if i am wrong On Fri, Jan 21, 2011 at 2:43 PM, snehal jain learner@gmail.comwrote: You are given two height balanced binary search trees T and T’, storing m and n elements respectively. Every element of tree T is smaller than every element of tree T’. Every node u also stores height of the subtree rooted at it. Using this extra information how can you merge the two trees in time O(log m + log n) (preserving both the height balance and the order)? -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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.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 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: Google Question
hope this works : #includestdio.h #define MAX(A,B) AB?A:B #defineMIN(A,B) AB?A:B int FindMaxA(int n) { int i,k,factor,max = 0,cur,prev; int* arr = new int[n+1]; int p = MIN(n,4); for( int j = 1;j = p;j++) arr[j] = j; for(i=5;i=n;i++) { k = i-4; factor = 2; prev = 0; while(k=1) { cur = arr[k]*factor; if( cur max ) //find max among multiples of Arr[k] for k i max = cur; if( cur prev ) break; // once the decreasing pattern starts its safe to break out of loop. k--; factor++; prev = cur; } arr[i] = MAX(i,max); } int result = arr[n]; delete[] arr; return result; } int main() { int n; scanf(%d,n); printf(%d\n,FindMaxA(n)); return 0; } -- On Fri, Jan 21, 2011 at 11:28 AM, Preetam Purbia preetam.pur...@gmail.comwrote: Hi, I think this method will work Possible Number of A's = N/2(1+R) where R=N-(N/2+3) assuming 11/2 = 5 Thanks Preetam On Fri, Jan 21, 2011 at 2:29 AM, Anand anandut2...@gmail.com wrote: but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20. Try this on a notepad. you will only 15A's On Thu, Jan 20, 2011 at 12:46 PM, Saikat Debnath saikat@gmail.comwrote: According to me Nishaanth's solution is incorrect, as let for n =10, your output : m=16 but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20. On Thu, Jan 20, 2011 at 9:24 PM, abhijith reddy d abhijith200...@gmail.com wrote: I think its correct. On Jan 19, 9:35 pm, nishaanth nishaant...@gmail.com wrote: How about the following dynamic programming solution. Let dp[i] be the max no of As with i keystrokes. dp[i]=max(dp[i-1]+1,2*dp[i-3]) dp[N] is the required solution. Correct me if i am wrong. On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com wrote: http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote: Given 1. A 2. Ctrl+A 3. Ctrl+C 4. Ctrl+V If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys. So the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce). Thanks Regards Shashank Mani -- 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.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. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Saikat Kumar Debnath IIIrd year, Computer Science Deptt., Delhi Technological University, (formerly Delhi College of Engineering) Delhi -- 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.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 algogeeks@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. -- Preetam Purbia http://twitter.com/preetam_purbia -- 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
Re: [algogeeks] Distance in a dictionary
@nishaanth can u give the outline?// On 1/21/11, nishaanth nishaant...@gmail.com wrote: Its a state space search. Solve it by using any of the known search algorithms. BFS, Best first search, DFS, A* On Fri, Jan 21, 2011 at 2:00 PM, snehal jain learner@gmail.com wrote: You have a dictionary of N words each of 3 chars. Given 2 words you have to find the optimum path between the 2 words. The optimum path contains the words in the dictionary each word at a distance of 1 from the previous word. for eg source = cat , target = sun path is cat - bat - but - bun - sun given all these words are in the dictionary -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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. -- Rahul K Rai rahulpossi...@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.
Re: [algogeeks] power of 3
@fight good solution. 3^n contains only one 1 in the 3-base representation. So write number M in base-3, and check if it contains only one digit(1). There is no need to find with M-1. -- 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] power of 3
@ juver++ : fight is my tc handle. here u can call me manmeet :) :) On Fri, Jan 21, 2011 at 9:35 PM, juver++ avpostni...@gmail.com wrote: @fight good solution. 3^n contains only one 1 in the 3-base representation. So write number M in base-3, and check if it contains only one digit(1). There is no need to find with M-1. -- 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.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 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] Adobe Question
how merge sort ?/ On Thu, Jan 20, 2011 at 11:23 PM, nishaanth nishaant...@gmail.com wrote: Ya as Ashish said hashing is the best solution :) On Fri, Jan 14, 2011 at 6:00 PM, Ashish Goel ashg...@gmail.com wrote: ideally, a hashMap would be preferred walk through one array and set the corresponding entry, and then through another array, if any entry found, then they are not disjoint. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Fri, Jan 14, 2011 at 3:35 PM, bittu shashank7andr...@gmail.comwrote: how to find if two arrays of size n are disjoint or not in O(n) time ?? You can use only O(n) space The elements are +ve in the range 0 to n power 100.. Regards Shashank Mani -- 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.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 algogeeks@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. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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.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 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] Distance in a dictionary
Ok lets define the following functions. movegen()- gives the list of next move given the state. This is basically all the 1 distance words given the current word. heuristic()- this gives the number of non-matching characters of the given word with the goal word. Start from start state and expand. Now always choose the move which gives a lesser heuristic valued state. Stop if you reach the goal. You can refer to Russel Norvig book on AI for detailed explanation. Regards, S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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] OS galvin sol..
Thanks so much On Wed, Jan 19, 2011 at 4:20 AM, jayapriya surendran priya7...@gmail.comwrote: wow..thank you so much On Wed, Jan 19, 2011 at 2:08 PM, LALIT SHARMA lks.ru...@gmail.com wrote: -- Lalit Kishore Sharma, IIIT Allahabad (Amethi Capmus), 6th Sem. -- 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.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 algogeeks@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. -- Thanks and many regards, Sreeprasad Govindankutty -- 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
@Juver..doesnt it require the parent information ? What if the data structure has only left and right pointers. On Fri, Jan 21, 2011 at 8:41 PM, juver++ avpostni...@gmail.com wrote: This question was posted some time ago. One solution is - start from the largest element (which is the righmost one in the tree). Then apply algorithm of searchin node's predecessor. It takes O(k) time to find k-th largest/smallest number. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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] Distance in a dictionary
whts complexity for this movegen() On Fri, Jan 21, 2011 at 9:52 PM, nishaanth nishaant...@gmail.com wrote: Ok lets define the following functions. movegen()- gives the list of next move given the state. This is basically all the 1 distance words given the current word. heuristic()- this gives the number of non-matching characters of the given word with the goal word. Start from start state and expand. Now always choose the move which gives a lesser heuristic valued state. Stop if you reach the goal. You can refer to Russel Norvig book on AI for detailed explanation. Regards, S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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.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 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] power of 3
@manmeet so, please choose your nickname at the forum :) -- 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
@above yes, posted solution needs parent links. Another solution is to process tree in reverse inorder: right subtree, root, left subtree and keeping counter k, when k is zero return current node -- 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] OS galvin sol..
It's really good. Thanks a lot On Fri, Jan 21, 2011 at 8:24 AM, Sreeprasad Govindankutty sreeprasad...@gmail.com wrote: Thanks so much On Wed, Jan 19, 2011 at 4:20 AM, jayapriya surendran priya7...@gmail.comwrote: wow..thank you so much On Wed, Jan 19, 2011 at 2:08 PM, LALIT SHARMA lks.ru...@gmail.comwrote: -- Lalit Kishore Sharma, IIIT Allahabad (Amethi Capmus), 6th Sem. -- 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.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 algogeeks@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. -- Thanks and many regards, Sreeprasad Govindankutty -- 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.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 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] OS galvin sol..
My Pleasure !! On Fri, Jan 21, 2011 at 11:22 PM, Anand anandut2...@gmail.com wrote: It's really good. Thanks a lot On Fri, Jan 21, 2011 at 8:24 AM, Sreeprasad Govindankutty sreeprasad...@gmail.com wrote: Thanks so much On Wed, Jan 19, 2011 at 4:20 AM, jayapriya surendran priya7...@gmail.com wrote: wow..thank you so much On Wed, Jan 19, 2011 at 2:08 PM, LALIT SHARMA lks.ru...@gmail.comwrote: -- Lalit Kishore Sharma, IIIT Allahabad (Amethi Capmus), 6th Sem. -- 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.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 algogeeks@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. -- Thanks and many regards, Sreeprasad Govindankutty -- 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.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 algogeeks@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. -- Lalit Kishore Sharma, IIIT Allahabad (Amethi Capmus), 6th Sem. -- 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] Amazon - Tree
You are given a bst where each node has a int value , parent pointer , and left and right pointers , write a function to find a path with a given sum value. Path can go from left subtree tree , include root and go to right tree as well . we need to find these paths also . 5 / \ 1 10 / \ / \ 0 2 6 11 so to find 16 we say it is 1 to 5 to 10 -- 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] Graph Theory+ DP
Given a distribution of packages on media and a list of dependences between packages, you have to calculate the minimal number of media changes required to install all packages. For your convenience, you may assume that the operating system comes on exactly 2 DVDs. http://www.spoj.pl/problems/ALL/ I think with Topological-sort + DP for find the maximun number of changes in each node for each DVD? -- 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: Graph Theory+ DP
Yes, you are right -- 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 a line
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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] OS galvin sol..
can u give me sipser solution mannual? On 1/21/11, Sreeprasad Govindankutty sreeprasad...@gmail.com wrote: Thanks so much On Wed, Jan 19, 2011 at 4:20 AM, jayapriya surendran priya7...@gmail.comwrote: wow..thank you so much On Wed, Jan 19, 2011 at 2:08 PM, LALIT SHARMA lks.ru...@gmail.com wrote: -- Lalit Kishore Sharma, IIIT Allahabad (Amethi Capmus), 6th Sem. -- 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.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 algogeeks@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. -- Thanks and many regards, Sreeprasad Govindankutty -- 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. -- Rahul K Rai rahulpossi...@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.
Re: [algogeeks] Symmetric matrix
We can also use jagged arrays for this purpose int[][] symmetric_matrix = new int[size][]; for (int i=0; i size; i++) ...symmetric_matrix[i]=new int[max_diagonal/(size)]; On Wed, Jan 12, 2011 at 9:30 AM, Sathaiah Dontula don.sat...@gmail.comwrote: 1 + 2 + + n ( max diagonal) = n ( n + 1) / 2. Max elements you can store is n ( n + 1) / 2 . You can take an array of size n (n + 1) / 2 and store them. Thanks, Sathaiah On Wed, Jan 12, 2011 at 9:50 AM, Azhar Hussain azhar...@gmail.com wrote: I have a symmetric matrix. I am wondering what would be the best data structure to store such a matrix? How many elements do I need to store for a nxn matrix? Thanks in advance for the help. - Azhar. -- 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.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 algogeeks@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. -- Umer -- 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] nearest points
Given n points on a 2D coordinate system . What is the most efficient way of finding nearest point for each point? How can we find all the points at a distance k from a given point efficiently? -- 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] Fwd: Indians r poor but India is not a poor country
-- *Piyush Verma* *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 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] Adobe Question
if both arrray are sorted. take two ptrs, one pointing to a[0] other to b[0]. if elements are same then nt disjoint. else increment ptr pointing to smaller element until it becomes equal or greater than the element pointed by other. repeat until either ptr reaches end of array.. On 21 January 2011 21:42, Manmeet Singh mans.aus...@gmail.com wrote: how merge sort ?/ On Thu, Jan 20, 2011 at 11:23 PM, nishaanth nishaant...@gmail.com wrote: Ya as Ashish said hashing is the best solution :) On Fri, Jan 14, 2011 at 6:00 PM, Ashish Goel ashg...@gmail.com wrote: ideally, a hashMap would be preferred walk through one array and set the corresponding entry, and then through another array, if any entry found, then they are not disjoint. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Fri, Jan 14, 2011 at 3:35 PM, bittu shashank7andr...@gmail.comwrote: how to find if two arrays of size n are disjoint or not in O(n) time ?? You can use only O(n) space The elements are +ve in the range 0 to n power 100.. Regards Shashank Mani -- 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.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 algogeeks@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. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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.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 algogeeks@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 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
@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 sweetdivya@gmail.com 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Google Question
It will be like a circularly sorted array.There exists a binary search type divide and conquer mechanism to find a specific number in such type of arrays. -- 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] sorted array inplace merge
Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space]. e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to: [-5,-2,1,3,3,6,8,8] i have thought of the following approach [1,3,6,8,-5,-2,3,8] || ptr1ptr2 *ptr1*ptr2 so shift as follows [ -5,1,3,6,8,-2,3,8] | | ptr1 ptr2 [-5,-2,1,3,,6,8,3,8] | | ptr1ptr2 [-5,-2,1,3,6,8,3,8] | | ptr1 ptr2 [-5,-2,1,3,6,8,3,8] | | ptr1 ptr2 [-5,-2,1,3,3,6,8,8] | | ptr1 ptr2 [-5,-2,1,3,3,6,8,8] | | ptr1 ptr2 {-5,-2,1,3,3,6,8,8] but i think there must be some O(n) algo for this.. -- 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.