Re: [algogeeks] Re: AMAZON: given col id, print col name in excel
@shiva: Nice thinking, man... :)
@Yq Zhang: this similar to base 26 apporch, i have tested below code for
boundary cases ,
0, 26(z), 27(aa), 26*26(yz), 26*27(zz)
public String getColName(int id) {
char ch[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k',
'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w',
'x', 'y', 'z' };
int i = 0;
int arr[] = new int[256];
while (id 0) {
arr[i++] = (id-1) % 26;
id = (id-1) / 26;
}
String result = ;
for (int x = i - 1; x = 0; x--)
result = result + ch[arr[x]];
return result;
}
On Thu, Aug 16, 2012 at 11:32 PM, shady sinv...@gmail.com wrote:
you can do it easily by counting the number that can be formed with 1
digit = 26, then 2 digit = 26*26... similarly find the length of the answer
and then can find the number by searching using bsearch over the number of
different characters.
if someone can do it with base % method,, then it is great :-P
On Thu, Aug 16, 2012 at 11:19 PM, Wei.QI qiw...@gmail.com wrote:
@yq, didn't I ask you this question before?
On Fri, Aug 10, 2012 at 4:48 PM, yq Zhang zhangyunq...@gmail.com wrote:
@shiv, your code is correct go compute the base 26 number. However, this
question is not base 26 number obviously.
On Wed, Aug 8, 2012 at 4:46 AM, shiv narayan narayan.shiv...@gmail.com
wrote:
this is similar to conversion of no in base 26.( where digits are
a,b,c,d...z) just think it like decimal to binary conversion here base
is
instead 26.
char Carr[26]={a,b,c...z}
i=0;
int arr[];
do
{
arrr[i++]=n%26;
n/=2;
}
while(n) ;
for(int i=n-1;i=0;i--)
coutCarr[a[i]];
correct me if i am wrong.
On Wednesday, 8 August 2012 12:56:56 UTC+5:30, ashgoel wrote:
Imagine a sequence like this: a, b, c...z, aa, ab, ac...zz, aaa, aab,
aac aax, aaz, aba, abc... (Its same as excel column names). Given
an
integer (n), generate n-th string from the above sequence.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/Z3kYiTZi_F8J.
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.
--
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.
--
--*
*
Regards
**
*Divesh Dixit*
*Software Developer
Webaroo Technology India Pvt Ltd,
* *cell:* +91-773895195 | +91-8291302034
div...@webaroo.com | www.smsgupshup.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]
what is the rational to do 5*rand5()
why not 4*rand5 or 6 *rand5??
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Fri, Jun 22, 2012 at 10:13 AM, Anant Sharma black.b...@gmail.com wrote:
The reason why finding a solution to this question is difficult is because
the combinations of rand5() function which we use ( eg. rand5() + rand5()%2
) leads to some numbers being generated more frequently than others. So the
problem would be solved if we could find a function which leads to each
output being generated an equal number of times ( once, or maybe more. )
5 * rand5() + rand5()
Looking at this function, it is easy to see that each value from 0 to 24
will be generated only once for every respective value that first and
second rand5() returns.
Suppose the first rand5() returns 0, then the second rand5() can return
any value from 0 - 4. Now see that no value from 0-4 could be generated by
any other combination. When the value returned by the second rand5() is 1,
corresponding to the value returned by second rand5(), we could get 5 - 9.
Now we have each number from 0-24 appearing once. But simply returning the
mod of this value with 7 wouldn't lead to equal probability distribution as
the values 0 - 3 would be returned more times than 4-6. So to fix this
inequality, we ignore when the value of the function is more than 20. Now
doing mod with 7 will result in every number 0 - 6 being returned with
equal probability.
We could even have ignored the values above 6, or the values above 13, the
only difference being that it would take more number of calls to return a
rand7() result.
This way is non-deterministic i.e. we cannot say how many times the
function will be called before we get the rand7() result, but we can be
sure that whenever the function returns a value, it would have been as
probable as any other value from 0 - 6. Taking the mod of the result of the
function, there would be 3 ways in which each digit 0 through 6 can be
generated.
Implementation:
int rand7 ( ) {
int num = 5 * rand5 ( ) + rand ( ) ;
if ( num 20 )
return rand7 ( ) ;
else
retutrn num % 7 ;
}
On Thu, Jun 21, 2012 at 12:44 PM, Abhishek Sharma abhi120...@gmail.comwrote:
@umer
it's not random,but biased
On Wed, Jun 20, 2012 at 11:16 AM, Umer Farooq the.um...@gmail.comwrote:
Hmmm, true. That's what I expected in this solution. Similarly, we can
get 3 by (3,3) (1,2)
However, did you take a look at the other solution I proposed? I guess
that solves the problem to some extent.
On Tue, Jun 19, 2012 at 7:18 PM, Sourabh Singh singhsourab...@gmail.com
wrote:
@Umer and Navin :
1 is generated by (1,3) only.
2 is generated by (1,1) and (2,3).
so given solution is wrong
On Tue, Jun 19, 2012 at 5:17 AM, Sourabh Singh
singhsourab...@gmail.com wrote:
@ *ALL*
please. post along with your method .
proof than it make's equal distribution over the given range.
On Tue, Jun 19, 2012 at 4:47 AM, Navin Kumar algorithm.i...@gmail.com
wrote:
@Umer:
rand(5) + (rand(5)%2): = it will never give 6 because for rand(7)
range will be 0-6.
So better try this: rand(5) + (rand(5)%3).
On Tue, Jun 19, 2012 at 2:45 PM, Umer Farooq the.um...@gmail.comwrote:
rand(5) + (rand(5)%2);
On Tue, Jun 19, 2012 at 12:30 PM, Sourabh Singh
singhsourab...@gmail.com wrote:
@ sry
condition should be:
if(20*prob = 500/7) :-)
On Tue, Jun 19, 2012 at 12:26 AM, Sourabh Singh
singhsourab...@gmail.com wrote:
@ALL
Given a random number generator say r(5) generates number between
1-5 uniformly at random , use it to in r(7) which should generate a
random
number between 1-7 uniformly at random
i have seen this on many site's but not a single correct solution.
all solution's posted got rejected by someone else.:
plz.. suggest some algo :
my aprroach:
let's assume a rectangle :
100 |___
|___|__
500/7 | ||
| ||
|___|__|
0 1 2 3 4 5 67
now :
let : num = rand(5);
prob = rand(5);
if(prob = rand(5))
print num
else
print 5 + num*(2/5)
--
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
Re: [algogeeks] O(n) solution is there or not!!
Just calculating the suffix array solves the problem if you do it with the LCP array as well. You don't need to 'use' the suffix array so to speak. On 19 August 2012 21:45, pankajsingh psingh...@gmail.com wrote: Is there any O(n) solution this question...I Cleared all the testcases but my solution is not O(n) and...I think there should be some O(n) solution..by seeing the constraint to this question..I tried to think for Kmp in this ..but didnt workand suffix array method will have more complexity..any suggestion For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings abc and abd is 2, while the similarity of strings aaa and aaab is 3. Calculate the sum of similarities of a string S with each of it's suffixes. *Input:* The first line contains the number of test cases T. Each of the next T lines contains a string each. *Output:* Output T lines containing the answer for the corresponding test case. *Constraints:* 1 = T = 10 The length of each string is at most 10 and contains only lower case characters. -- Pankaj Singh B.Tech in Computer Science and Engineering - lllrd year IIT Roorkee, India -- 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] O(n) solution is there or not!!
Or a suffix tree would work. Pre process it to answer Lowest common ancestor queries. On 19 August 2012 21:51, Carl Barton odysseus.ulys...@gmail.com wrote: Just calculating the suffix array solves the problem if you do it with the LCP array as well. You don't need to 'use' the suffix array so to speak. On 19 August 2012 21:45, pankajsingh psingh...@gmail.com wrote: Is there any O(n) solution this question...I Cleared all the testcases but my solution is not O(n) and...I think there should be some O(n) solution..by seeing the constraint to this question..I tried to think for Kmp in this ..but didnt workand suffix array method will have more complexity..any suggestion For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings abc and abd is 2, while the similarity of strings aaa and aaab is 3. Calculate the sum of similarities of a string S with each of it's suffixes. *Input:* The first line contains the number of test cases T. Each of the next T lines contains a string each. *Output:* Output T lines containing the answer for the corresponding test case. *Constraints:* 1 = T = 10 The length of each string is at most 10 and contains only lower case characters. -- Pankaj Singh B.Tech in Computer Science and Engineering - lllrd year IIT Roorkee, India -- 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] O(n) solution is there or not!!
@Carl- I didnt got ur point completely abt Lcp array..can you demonstrate on the below example... Example for ababaa answer shud be -11 suffix array wud be:- a aa abaa ababaa baa and Lcp array would be then 0 1 1 3 0 ..correct if wrong..whats next... -- 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] O(n) solution is there or not!!
Oh, I actually read the question totally wrong. I think this idea is linear, but it's late so I'm not sure. 1. Calculate suffix array and lcp array for the text. 2. Calculate the longest common prefix between your text and the first entry in your suffix array and initialise a variable called total with this value and another variable called last. Last is a variable to store the lcp between the text and the last suffix you considered. 3. Now traverse the suffix array using the lcp array. for some point, i, if the lcp between the text and the last entry is lcp[i+1] you can do total = total + lcp[i+1] if the lcp between the text and the last entry is lcp[i+1] you can do total = total + lcp[i-1] if the lcp between the text and the last entry is = lcp[i+1] you need to do some more work and try and extend the match from position lcp[i+1] I think that should be linear though? correctme if i'm wrong. On 19 August 2012 22:23, pankajsingh psingh...@gmail.com wrote: @Carl- I didnt got ur point completely abt Lcp array..can you demonstrate on the below example... Example for ababaa answer shud be -11 suffix array wud be:- a aa abaa ababaa baa and Lcp array would be then 0 1 1 3 0 ..correct if wrong..whats next... -- 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] O(n) solution is there or not!!
concatenate 2 strings adding wild character in between i.e A=aaa B=aaab A+B =aaa$aaab; wild character is $; now create longest prefix table(partial match table) as we do in KMP algo. now search for max value after $ index...in LPS table. I guess it would work On Sun, Aug 19, 2012 at 8:23 PM, Carl Barton odysseus.ulys...@gmail.comwrote: Oh, I actually read the question totally wrong. I think this idea is linear, but it's late so I'm not sure. 1. Calculate suffix array and lcp array for the text. 2. Calculate the longest common prefix between your text and the first entry in your suffix array and initialise a variable called total with this value and another variable called last. Last is a variable to store the lcp between the text and the last suffix you considered. 3. Now traverse the suffix array using the lcp array. for some point, i, if the lcp between the text and the last entry is lcp[i+1] you can do total = total + lcp[i+1] if the lcp between the text and the last entry is lcp[i+1] you can do total = total + lcp[i-1] if the lcp between the text and the last entry is = lcp[i+1] you need to do some more work and try and extend the match from position lcp[i+1] I think that should be linear though? correctme if i'm wrong. On 19 August 2012 22:23, pankajsingh psingh...@gmail.com wrote: @Carl- I didnt got ur point completely abt Lcp array..can you demonstrate on the below example... Example for ababaa answer shud be -11 suffix array wud be:- a aa abaa ababaa baa and Lcp array would be then 0 1 1 3 0 ..correct if wrong..whats next... -- 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. -- 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] O(n) solution is there or not!!
@carl- got ur point..but complexity is more..suffix array takes o(n^2lgn)..considering string comparisons. complexity to build...i already have o(n^2)..want o(n).. -- 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: Printing random word from file
@Dave sir, I didn't get your logic. Can you please elaborate it? On Sun, Aug 19, 2012 at 4:08 AM, Dave dave_and_da...@juno.com wrote: @Navin: Here is the algorithm: Save the first word. For i = 2, 3, ..., n = number of words in the file replace the saved word with the i-th word with probability 1/i. When EOF is reached, every word in the file will have probability 1/n of being the saved word. Print it. Dave On Saturday, August 18, 2012 1:28:56 AM UTC-5, Navin Kumar wrote: Print a *Random word* from a file. Input is path to a file, constraints- No extra memory like hashing etc. All the words in the file should have equal probability. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/HxO-wNzEP9gJ. 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.
