Re: [algogeeks] Networking:suggest some book
On Sat, Sep 17, 2011 at 8:58 AM, hary rathor harry.rat...@gmail.com wrote: 1 frozen Hahahaha. It's not 'FROZEN', it is Forouzan :P (http://books.google.com/books/about/Data_Communications_and_Networking.html?id=U3Gcf65Pu9IC) 2 steven Vol 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. -- Gaurav Menghani -- 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] I want resources to learn algorithms on Permutation and Combination problems and Graph algorithms except CLRS..
Skiena's Algorithm Design Manual? On Fri, Sep 16, 2011 at 12:07 PM, kumar raja rajkumar.cs...@gmail.com wrote: -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in 7797137043. 09491690115. -- 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. -- Gaurav Menghani -- 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] SPOJ PIE
One small observation, you can use the M_PI constant already available
when you #include cmath
On Thu, Sep 15, 2011 at 3:57 PM, KK kunalkapadi...@gmail.com wrote:
http://www.spoj.pl/problems/PIE/
I solved this using Binary Search its similar to shake shake shaky of
spoj... but still get WA :(
Plzz help...
#includeiostream
#includealgorithm
using namespace std;
bool solve(int *pie, int n, int mid,int f)
{
int sum = 0;
for (int i=0; in; i++)
sum += pie[i] / mid;
if (sum = f)
return true;
else
return false;
}
int binary_search(int *pie, int n, int f)
{
int low = 0, high = pie[n-1], mid;
while (low high)
{
mid = low + (high - low + 1)/2;
if (solve(pie, n, mid, f))
low = mid;
else
high = mid - 1;
}
return low;
}
int main()
{
//freopen(input.txt, r, stdin);
//freopen(output.txt, w, stdout);
const double pi = 3.14159265358979323846264338327950;
int T;
cin T;
while (T--)
{
int n, f, pie[10001];
cin n f;
for (int i=0; in; i++)
{
cin pie[i];
pie[i] *= pie[i];
}
f++;
sort(pie, pie + n);
int largest = binary_search(pie, n, f);
//cout largest is largest endl;
double ans = largest * pi;
printf(%.4lf\n, ans);
}
return 0;
}
--
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.
--
Gaurav Menghani
--
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] Party Lamps
On Thu, Sep 15, 2011 at 4:44 PM, Blackwizard mohammadreza.rahman...@gmail.com wrote: Hi I want to solve this problem but I'm not sure about the algorithm... I think It can be complete search... Is the anybody to help me? what's the algorithm for this question... Problem Link: http://olympiads.win.tue.nl/ioi/ioi98/contest/day1/party/party.html I think BFS should work, but then some pruning would be required since the number of lamps is large. I'm not sure how the pruning would be done though. Thank's -- 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. -- Gaurav Menghani -- 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] How can we find second largest element in an array... in O(n+logn-2)... give me proof.....
It can be done trivially in O(n). On Sat, Sep 10, 2011 at 10:18 AM, praveen raj praveen0...@gmail.com wrote: How can we find second largest element in an array... in O(n +logn-2)... give me proof. -- 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. -- Gaurav Menghani -- 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] MICROSOFT WRITTEN QUESTION
On Sat, Sep 10, 2011 at 11:22 AM, Neha Singh neha.ndelhi.1...@gmail.com wrote: O(n/a) For every n, it would add values for W(n-v1), W(n-v2),..., W(n-vm), if there are m denominations of coins. So the complexity would be O(nm). Also, this can be implemented in two ways. Top-down (which is what I mentioned), and Bottom-up. Search for Bottom-up DP. -- Gaurav Menghani -- 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] Find th gcd of 2 nos in the most efficient way
C'mon http://en.wikipedia.org/wiki/Greatest_common_divisor On Sat, Sep 10, 2011 at 11:24 AM, Neha Singh neha.ndelhi.1...@gmail.com wrote: -- 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. -- Gaurav Menghani -- 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] MICROSOFT WRITTEN QUESTION
On Sat, Sep 10, 2011 at 11:28 AM, teja bala pawanjalsa.t...@gmail.com wrote: @Gaurav wat if here is n=1 den W(0)=? i dint get that See, when you get to W(0) state, that means, you have created a valid combination. That means, you have gone through one 'path' through the various possibilities. That is why W(0)=1. It is the 'tail' of the recursion, i.e. the base case. When n=1, then, W(1)=W(1-50)+W(1-25)+...+W(1-1) All but the last factors would call W(n') where n' 0, and would result in 0. But the last part would be W(0), which is a valid state. So W(1) = 0+0+...+W(0) = 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. -- Gaurav Menghani -- 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: How can we find second largest element in an array... in O(n+logn-2)... give me proof.....
Well you can avoid that condition by comparing the number by:
1. Keeping two numbers, largest and second largest.
2. Comparing with the second largest. If it is greater than the second
largest, set second_largest = num. Else continue.
3. If second_largest largest, swap(largest,second_largest).
O(n) complexity. Not sure, how to put a bound on the number of comparisons.
On Sat, Sep 10, 2011 at 11:36 AM, abhinav gupta
guptaabhinav...@gmail.com wrote:
sort it in quicksort (descending order)...den take arr[1] --second largest
On Sat, Sep 10, 2011 at 8:34 AM, Akhilesh Vedhera akhileshn...@gmail.com
wrote:
Then the complexity will be nlogn not n and if it is the worst case
then it would be O(n^2)...
On Sat, Sep 10, 2011 at 8:58 PM, abhinav gupta guptaabhinav...@gmail.com
wrote:
Oops ..no u hav to quicksort it.
On Sat, Sep 10, 2011 at 8:24 AM, Dave dave_and_da...@juno.com wrote:
@Abhinav: Does it work correctly on {1, 3, 2}, or, for that matter, on
any array where the second largest comes after the largest?
Dave
On Sep 10, 10:16 am, abhinav gupta guptaabhinav...@gmail.com wrote:
temp2 is second largest element.
On Sat, Sep 10, 2011 at 8:00 AM, abhinav gupta
guptaabhinav...@gmail.comwrote:
I can solve this problem in O(n)
i=0;
temp1=arr[0];
while(i != len)
{
if(arr[i] temp1)
{
temp2=temp1;
temp1=arr[i]
}
i++;
}
On Sat, Sep 10, 2011 at 7:42 AM, Dave dave_and_da...@juno.com
wrote:
@Replying to my own posting: remove the words one of the numbers
that
lost to, so that the explanation reads
The question should be How can we find the second largest element
in
an array in n + ceiling(log_2(n)) - 2 comparisons? The answer is
to
use a tournament to select the largest number. The second largest
number will have lost to the largest. It takes n - 1 comparisons to
determine the largest number. There are ceiling(log_2(n)) numbers
that
have lost to the largest, and it takes ceiling(log_2(n)) - 1
comparisons to find the largest of them.
Dave
On Sep 10, 9:28 am, Dave dave_and_da...@juno.com wrote:
@Praveen: The question should be How can we find the second
largest
element in an array in n + ceiling(log_2(n)) - 2 comparisons?
The
answer is to use a tournament to select the largest number. The
second
largest number will have lost to one of the numbers that lost to
the
largest. It takes n - 1 comparisons to determine the largest
number.
There are ceiling(log_2(n)) numbers that have lost to the
maximum, and
it takes ceiling(log_2(n)) - 1 comparisons to find the largest of
them.
Dave
On Sep 10, 9:18 am, praveen raj praveen0...@gmail.com wrote:
How can we find second largest element in an array... in O(n
+logn-2)... give me proof.- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
@ |3 # ! /\/ @ \./
--
@ |3 # ! /\/ @ \./- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
@ |3 # ! /\/ @ \./
--
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.
--
Akhilesh
NSIT-COE
--
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.
--
@ |3 # ! /\/ @ \./
--
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.
--
Gaurav Menghani
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post
Re: [algogeeks] Write a function to find the least common multiple of integers in an array
http://tinyurl.com/3hm3gug On Sat, Sep 10, 2011 at 10:46 AM, Neha Singh neha.ndelhi.1...@gmail.com wrote: -- 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. -- Gaurav Menghani -- 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] MICROSOFT WRITTEN QUESTION
No. I think you should revisit complexity. That's not how it works. Factoring a million digit number outputs two numbers. It should take O(1), right? :D On Sat, Sep 10, 2011 at 11:56 AM, Neha Singh neha.ndelhi.1...@gmail.com wrote: we hv to just fill an array of size n, so complexity should be O(n) in worst case -- 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. -- Gaurav Menghani -- 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] Digest for algogeeks@googlegroups.com - 25 Messages in 9 Topics
are OBVIOUSLY wrong. Obviously. Don dondod...@gmail.com Sep 07 07:00AM -0700 ^ Figure out the man days per painting: 5/2 artists working for 5/2 days is 25/4 man days. They produce 5/2 paintings, so that is 5/2 man days per painting. Thus to make 25 paintings will require 25*5/2 man days. To complete that work in 25 days will require 5/2 painters. Don -- 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 sushaanth.s phone:9790832251 -- 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. -- Gaurav Menghani -- 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] SPOJ
Description of the problem and your solution could help others.
On Wed, Sep 7, 2011 at 12:01 AM, Akshata Sharma
akshatasharm...@gmail.com wrote:
I am getting WA in this problem, I am not getting what i am doing wrong
.
http://www.spoj.pl/problems/AE2A/
My dp is:
dp[n][k] = (dp[n - 1][k - 1] + dp[n - 1][k - 2] + dp[n - 1][k - 3] + dp[n -
1][k - 4] + dp[n - 1][k - 5] + dp[n - 1][k - 6])
and my code:
#includeiostream
using namespace std;
int solve(int n, int k)
{
int** dp;
dp = (int **)malloc(2*sizeof(int*));
dp[0]=(int*)malloc(111*sizeof(int));
dp[1]=(int*)malloc(111*sizeof(int));
for(int i=1;i=6;i++)
dp[0][i]=1;
int throws=n;
n--;
int sum=0;
while(n--)
{
for(int i=1;i=k;i++)
{
dp[1][i]=0;
sum=0;
for(int j=1;j=6;j++)
{
if((i-j)0) break;
sum+=dp[0][i-j];
}
dp[1][i]=sum;
}
for(int i=1;i=k;i++)
dp[0][i]=dp[1][i];
}
dp[0][k]*=100;
for(int i=0;ithrows;i++)
dp[0][k]/=6;
return dp[0][k];
}
int main()
{
int cases;
cincases;
while(cases--)
{
long n,k;
cinnk;
coutsolve(n,k)endl;
}
return 0;
}
--
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.
--
Gaurav Menghani
--
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] SPOJ Problem DIVSUM
Yeah, sorry I was giving a hint for DIVSUM2, which is a much harder version of DIVSUM. You are checking all numbers less than n for divisibility. This is O(n). Figure out how can you find the set of divisors using primes. This can be done in O(2^d), if there are d prime divisors. On Sat, Aug 27, 2011 at 11:10 PM, saurabh modi saurabhmodi102...@gmail.com wrote: you could use seiving.its fast.its practical. -- 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. -- Gaurav Menghani -- 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] Adding Two no without using any operator...??
I guess you mean without using any 'arithmetic operator'. If yes, it can be done with XOR and AND operators. Not sure how it can be done otherwise, without using any kind of operators AT ALL. On Sun, Aug 28, 2011 at 12:37 AM, Brijesh brijeshupadhyay...@gmail.com wrote: How to add two nos without using any operator...? -- 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/-/MpNKzlE3UuwJ. 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. -- Gaurav Menghani -- 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] Remove all Duplicates Words
Do you mean even O(1) isn't good? On Wed, Aug 24, 2011 at 8:43 PM, UMESH KUMAR kumar.umesh...@gmail.com wrote: Qn. Remove all duplicates words from given a line without using extra memory ? Ex:-Hello word hello hi Out put:- Hello word hi -- 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. -- Gaurav Menghani -- 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] Factorial Algorithms
Sure. On Wed, Aug 17, 2011 at 4:33 PM, Nitin Nizhawan nitin.nizha...@gmail.com wrote: @Gaurav , if you are able to find any resource that explains the logic of these algos, please let me know. On Sat, Aug 13, 2011 at 9:50 AM, Gaurav Menghani gaurav.mengh...@gmail.com wrote: Thanks for the link. I was unaware of such algorithms. These would come handy in programming contests. On Fri, Aug 12, 2011 at 3:00 PM, Nitin Nizhawan nitin.nizha...@gmail.com wrote: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm Does anyone know of resource for good/detailed explanation of factorial algorithms on this site? -- 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. -- Gaurav Menghani -- 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. -- Gaurav Menghani -- 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] GSOC
Wrong place On Tue, Aug 16, 2011 at 7:58 PM, dilip makwana dilipmakwa...@gmail.com wrote: Ya please some one share info regarding this . @saurabh thanks for askin this On 16 August 2011 19:00, saurabh chhabra saurabh131...@gmail.com wrote: can anyone help me in preparing for GSOC(Summer of Code),2012? Please give me a description of what exactly it is and what all we need to know to get selected in it. kindly throw some light. -- 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. -- Dilip Makwana VJTI BTech Computers Engineering 2009-2013 -- 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. -- Gaurav Menghani -- 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] How to hash Strings
The easiest one is to take the sum of their ASCII values. On Sun, Aug 14, 2011 at 12:36 PM, rohit raman.u...@gmail.com wrote: I came accross a problem where i need to hash strings.. What is the best way to hash strings?? -- 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/-/LlcN35L2Su8J. 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. -- Gaurav Menghani -- 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 mean by %2.3d in scanf
http://lmgtfy.com/?q=scanf+float+precision+format On Sat, Aug 13, 2011 at 5:42 PM, SuDhir mIsHra sudhir08.mis...@gmail.com wrote: e g: scanf(%2.4d,a); -- 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. -- Gaurav Menghani -- 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]
Knapsack DP On Sat, Aug 13, 2011 at 8:35 PM, Kamakshii Aggarwal kamakshi...@gmail.com wrote: yes On Sat, Aug 13, 2011 at 8:30 PM, Puneet Goyal puneetgoya...@gmail.com wrote: 1 or 2 stairs? On Sat, Aug 13, 2011 at 8:24 PM, Kamakshii Aggarwal kamakshi...@gmail.com wrote: Given n stairs, how many number of ways can you climb if u use either 1 or 2 at a time? -- Regards, Kamakshi kamakshi...@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. -- --- Puneet Goyal Student of B. Tech. III Year (Software Engineering) Delhi Technological University, 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Kamakshi kamakshi...@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. -- Gaurav Menghani -- 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 mean by %2.3d in scanf
@Anika: Check out lmgtfy.com One can use this if the desired answer is provided by a google query. On Sat, Aug 13, 2011 at 9:49 PM, Anika Jain anika.jai...@gmail.com wrote: @gaurav: nyc one ;) how u made this one well? On Sat, Aug 13, 2011 at 6:14 PM, SANDEEP CHUGH sandeep.aa...@gmail.com wrote: lol On Sat, Aug 13, 2011 at 6:12 PM, Gaurav Menghani gaurav.mengh...@gmail.com wrote: http://lmgtfy.com/?q=scanf+float+precision+format On Sat, Aug 13, 2011 at 5:42 PM, SuDhir mIsHra sudhir08.mis...@gmail.com wrote: e g: scanf(%2.4d,a); -- 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. -- Gaurav Menghani -- 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. -- Gaurav Menghani -- 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 mean by %2.3d in scanf
It is just displaying the floating point in the specified precision format. The internal representation is obviously unchanged. On Sat, Aug 13, 2011 at 10:44 PM, Prakash D cegprak...@gmail.com wrote: i dont think we can set precision during scanf On Sat, Aug 13, 2011 at 9:49 PM, Anika Jain anika.jai...@gmail.com wrote: @gaurav: nyc one ;) how u made this one well? On Sat, Aug 13, 2011 at 6:14 PM, SANDEEP CHUGH sandeep.aa...@gmail.com wrote: lol On Sat, Aug 13, 2011 at 6:12 PM, Gaurav Menghani gaurav.mengh...@gmail.com wrote: http://lmgtfy.com/?q=scanf+float+precision+format On Sat, Aug 13, 2011 at 5:42 PM, SuDhir mIsHra sudhir08.mis...@gmail.com wrote: e g: scanf(%2.4d,a); -- 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. -- Gaurav Menghani -- 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. -- 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. -- Gaurav Menghani -- 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] logic???????????
After finding the pivot, can't we just use the normal binary search, just change the array notation to use modular arithmetic. i.e, instead of arr[i], use arr[(i+k)%n], where n is the number of elements in the array. Rest of the code remains same. On Sun, Aug 14, 2011 at 10:41 AM, sagar pareek sagarpar...@gmail.com wrote: arey mean original array. array without rotation :D and if u know the pivot point then how u will came to know its position in rotated array... like in above example we have to search 12 then how will u know abt position of 2? On Sun, Aug 14, 2011 at 6:15 AM, Yasir yasir@gmail.com wrote: @Sagar ..an array which is sorted but rotated by some k places which is nt kwn Kindly note that: ARRAY IS KNOWN, k is NOT known. If the array is not known then where will you search an item??? :P :P -- 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/-/TfoI2uYkGCAJ. 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 SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT 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. -- Gaurav Menghani -- 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] string confusion
Well, this can have undefined behavior. Technically you should append
- First allocate memory for a string
- Then append the terminating char
In this case, the memory location after the last character is set to
zero, but then you do not have control over it. It may not be zero
when you run it the next time. So it might not terminate.
On Sun, Aug 14, 2011 at 10:24 AM, Arshad Alam alam3...@gmail.com wrote:
program is running smooth but I have one confusion at line number 8.
why it is while(s[i]!=0) instead of while(s[i]!='\0')
1. #includestdio.h
2. #includeconio.h
3. void main()
4. {
5. clrscr();
6. char s[]=No two viruses;
7. int i=0;
8. while(s[i]!=0)
9. {
10. printf(\n%c %c,s[i],*(s+i));
11. printf ( \n%c %c,i[s],*(i+s));
12. i++;
13. }
14. getch();
15. }
Thanks Regards
Arshad Nadeem Alam
--
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.
--
Gaurav Menghani
--
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] Factorial Algorithms
Thanks for the link. I was unaware of such algorithms. These would come handy in programming contests. On Fri, Aug 12, 2011 at 3:00 PM, Nitin Nizhawan nitin.nizha...@gmail.com wrote: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm Does anyone know of resource for good/detailed explanation of factorial algorithms on this site? -- 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. -- Gaurav Menghani -- 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] find a solution
I guess we should learn to google first. On Thu, Aug 11, 2011 at 5:58 PM, surender sanke surend...@gmail.com wrote: concatenate both and find all permutations of that string surender On Thu, Aug 11, 2011 at 5:34 PM, Gayathri Anandan gayathriananda...@gmail.com wrote: Given two strings say AB and CD you should print all the possible combinations. Use any language. output: ABCD, ABDC, ACDB, ADBD, ADBC, ADCB 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.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. -- Gaurav Menghani -- 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] find a solution
In C++ it is done in the following way: - Concatenate all strings - Sort the string - Use next_permuation On Thu, Aug 11, 2011 at 7:01 PM, Gaurav Menghani gaurav.mengh...@gmail.com wrote: I guess we should learn to google first. On Thu, Aug 11, 2011 at 5:58 PM, surender sanke surend...@gmail.com wrote: concatenate both and find all permutations of that string surender On Thu, Aug 11, 2011 at 5:34 PM, Gayathri Anandan gayathriananda...@gmail.com wrote: Given two strings say AB and CD you should print all the possible combinations. Use any language. output: ABCD, ABDC, ACDB, ADBD, ADBC, ADCB 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.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. -- Gaurav Menghani -- Gaurav Menghani -- 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] find a solution
On Fri, Aug 12, 2011 at 12:09 AM, siddharam suresh siddharam@gmail.com wrote: @gaurav.menghani: google has answer for every interview question asked. if people know how to search, then no need to join this group. if people know how to search, then no need to join this group Okay, this is hilarious. Do you actually mean that people who have joined this group have joined because they don't know how to search? I don't know about you, but at least I know how to search, and I still joined. Jokes apart, basic forum etiquette suggests one should search if the same question has been answered already, before posting in the said forum. This question has been answered repeatedly. If you want to answer all repeated questions, I suggest you take the onus of doing so. On Thu, Aug 11, 2011 at 7:01 PM, Gaurav Menghani gaurav.mengh...@gmail.com wrote: I guess we should learn to google first. On Thu, Aug 11, 2011 at 5:58 PM, surender sanke surend...@gmail.com wrote: concatenate both and find all permutations of that string surender On Thu, Aug 11, 2011 at 5:34 PM, Gayathri Anandan gayathriananda...@gmail.com wrote: Given two strings say AB and CD you should print all the possible combinations. Use any language. output: ABCD, ABDC, ACDB, ADBD, ADBC, ADCB 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.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. -- Gaurav Menghani -- 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. -- Gaurav Menghani -- 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] find a solution
No its just that we avoid repetitive stuff. Saves energy for everyone. On Fri, Aug 12, 2011 at 11:06 AM, siddharam suresh siddharam@gmail.com wrote: gaurav: i feel we dont know when the people have joined this group and what they want. post the answer if you are willing, otherwise just ignore it. Its better that we should see/concentrate on the workability of the group.(my english is poor) Thank you Siddharam On Fri, Aug 12, 2011 at 11:02 AM, siddharam suresh siddharam@gmail.com wrote: gaurav: i feel we dont know when the people have joined this group and what they want. post the answer if you are willing, otherwise just ignore it. Its better we should see the workability of the group. Thank you, Siddharam On Fri, Aug 12, 2011 at 10:42 AM, Gaurav Menghani gaurav.mengh...@gmail.com wrote: On Fri, Aug 12, 2011 at 12:09 AM, siddharam suresh siddharam@gmail.com wrote: @gaurav.menghani: google has answer for every interview question asked. if people know how to search, then no need to join this group. if people know how to search, then no need to join this group Okay, this is hilarious. Do you actually mean that people who have joined this group have joined because they don't know how to search? I don't know about you, but at least I know how to search, and I still joined. Jokes apart, basic forum etiquette suggests one should search if the same question has been answered already, before posting in the said forum. This question has been answered repeatedly. If you want to answer all repeated questions, I suggest you take the onus of doing so. On Thu, Aug 11, 2011 at 7:01 PM, Gaurav Menghani gaurav.mengh...@gmail.com wrote: I guess we should learn to google first. On Thu, Aug 11, 2011 at 5:58 PM, surender sanke surend...@gmail.com wrote: concatenate both and find all permutations of that string surender On Thu, Aug 11, 2011 at 5:34 PM, Gayathri Anandan gayathriananda...@gmail.com wrote: Given two strings say AB and CD you should print all the possible combinations. Use any language. output: ABCD, ABDC, ACDB, ADBD, ADBC, ADCB 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.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. -- Gaurav Menghani -- 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. -- Gaurav Menghani -- 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. -- Gaurav Menghani -- 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] pls help
I am just increasing the size of the current string by one. So that a
new character can be appended.
On Sat, Aug 6, 2011 at 11:01 AM, Tushar Bindal tushicom...@gmail.com wrote:
@gaurav
didn't get this:
Just to increase the size of the string by one.
Then you can put any character at the the new last position, which is 'l'.
can u pls explain that?
On Fri, Aug 5, 2011 at 2:57 PM, Nitin Nizhawan nitin.nizha...@gmail.com
wrote:
Ok, Thanks
On Fri, Aug 5, 2011 at 2:53 PM, Gaurav Menghani
gaurav.mengh...@gmail.com wrote:
Even if the number of elements is more than two, it is possible with
bitwise operations, but it gets clumsy.
Suppose your alphabet has 4 characters. You can either:
- Count from 0 to (14*n)-1 and use four bits to denote the selection
of the alphabet. Also, only one bit amongst those four should be set.
It is highly inefficient.
- Keep n nested loops and inside each loop you iterate from 0 to
(14)-1 and use the standard bitwise operations. The con here is that
you have to hardcode the number of nested loops.
On Fri, Aug 5, 2011 at 2:44 PM, Nitin Nizhawan nitin.nizha...@gmail.com
wrote:
@Varun I think it can be done using bits, if input character set has
only
two elements. Or could u plz explain?
On Fri, Aug 5, 2011 at 2:29 PM, Varun Jakhoria
varunjakho...@gmail.com
wrote:
I think it can be done using bitwise ANDing with a mask
On Fri, Aug 5, 2011 at 12:58 PM, Gaurav Menghani
gaurav.mengh...@gmail.com wrote:
An Implementation:
#includeiostream
#includestring
using namespace std;
string alphabet;
int maxlen;
void backtrack(string s,int l)
{
if(l==maxlen) { coutsendl; return; }
s.push_back('-');
for(int i=0;ialphabet.size();i++)
{ s[l]=alphabet[i]; backtrack(s,l+1); }
}
int main()
{
maxlen=3;
alphabet=op;
backtrack(,0);
return 0;
}
On Fri, Aug 5, 2011 at 12:42 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
@gaurav:i could not understand ur sol.can u explain it again..
On Fri, Aug 5, 2011 at 12:32 PM, Gaurav Menghani
gaurav.mengh...@gmail.com
wrote:
On Fri, Aug 5, 2011 at 12:20 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
given a set of letters and a length N, produce all possible
output.(Not
permutation). For example, give the letter (p,o) and length of
3,
produce
the following output(in any order you want, not just my example
order)
ppp ppo poo pop opp opo oop ooo
another example would be given (a,b) and length 2
answer: ab aa bb ba
--
Regards,
Kamakshi
kamakshi...@gmail.com
This can be done easily by backtracking
void backtrack(string s, int l)
{
if(l == maxlen) { coutsendl; return; }
s.push_back('-');
for(int i=0;ialphabet.size();i++)
{
s[l]=alphabet[i];
backtrack(s,l+1);
}
}
--
Gaurav Menghani
--
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,
Kamakshi
kamakshi...@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.
--
Gaurav Menghani
--
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.
--
Varun Jakhoria
...it's only about 0's 1's
--
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.
--
Gaurav Menghani
--
You
Re: [algogeeks] help--code
If the dimensions are same, both will execute equally fast. On Mon, Aug 8, 2011 at 3:21 PM, Kamakshii Aggarwal kamakshi...@gmail.com wrote: which code executes faster? code1:- for(i=0;in;i++) for(j=0;jn;j++) large_array[i][j]=0; code2:- for(j=0;jn;j++) for(i=0;in;i++) large_array[i][j]=0; -- Regards, Kamakshi kamakshi...@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. -- Gaurav Menghani -- 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] help--code
Sorry, I was thinking something else. Code 1 should be faster since arrays are stored in row-major fashion, the entire row will fit in cache, and accessing sequentially in the row would be faster because of higher cache hits than Code 2. On Mon, Aug 8, 2011 at 3:25 PM, Gaurav Menghani gaurav.mengh...@gmail.com wrote: If the dimensions are same, both will execute equally fast. On Mon, Aug 8, 2011 at 3:21 PM, Kamakshii Aggarwal kamakshi...@gmail.com wrote: which code executes faster? code1:- for(i=0;in;i++) for(j=0;jn;j++) large_array[i][j]=0; code2:- for(j=0;jn;j++) for(i=0;in;i++) large_array[i][j]=0; -- Regards, Kamakshi kamakshi...@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. -- Gaurav Menghani -- Gaurav Menghani -- 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] help--code
The principle of locality of reference suggests if a reference is made to a memory location, next reference is close to it. So, it is a basic assumption that processors fetch memory locations close to it, to optimize fetch time. Since the array is stored in row-major form AFAIK, elements in the same row are closer to each other and more likely to be in cache together, as compared to elements in different rows. On Mon, Aug 8, 2011 at 5:12 PM, Prakash D cegprak...@gmail.com wrote: @gaurav: are u sure? On Mon, Aug 8, 2011 at 3:40 PM, Amir pkpat...@gmail.com wrote: Both Will take same time. -- 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/-/hwcTUmMW_zsJ. 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. -- Gaurav Menghani -- 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] Random number
The space complexity is O(1)
I know about hash-tables. Can you implement with O(1) space complexity?
On Mon, Aug 8, 2011 at 10:56 AM, 석문기 smgs2...@gmail.com wrote:
Box-muller method is the good solution without a lot of computation overhead
2011/8/8 Puneet Gautam puneet.nsi...@gmail.com
You may be right..we cant remove collisions in O(1) time...
But hey, hash table is still an effective way..
On 8/8/11, Puneet Gautam puneet.nsi...@gmail.com wrote:
Hey avoiding collisions using hash table can be real easy :
eg:
if 192 is the no generated let it hash to say index 7 of hash
table...so when it is again generated, it hashes to the same 7th index
of hash table, but we have a non zero value already present at that
index , 192 so we can reject this generated no. and proceed to the
next one..
Whereas in an array , avoiding collision is a really hectic way...u
need to scan all the previously generated no.s for duplicacy...well
that aint gonna run in O(1) time..
So implementing hash table reduces that overhead and runs it in O(1)
time..(it just has to check one if condition)with a bigger
constant.
And moreover, we may even dont want an ordered sequence...just put the
generated no.s in hash table as soon as they are generated...dats it..
then afterwards display that hash table..
Did u get me...?
On 8/7/11, Gaurav Menghani gaurav.mengh...@gmail.com wrote:
We can have a sorted sequence and display them in random order, but
that is the same problem. How do we display them in random order? We
need to have a sequence of random indices, that is the same problem as
having random numbers, isn't it.
Moreover, I don't think collisions can be avoided in less than O(n).
We can have an efficient hash-table, but I am not sure how it can be
done in O(1) or better.
On Sat, Aug 6, 2011 at 12:37 PM, Puneet Gautam
puneet.nsi...@gmail.com
wrote:
I rhink to avoid collisions altogether we should generate an ordered
sequence , in a dec. or inc. order and
display them randomly, i mean:
Let say a[10] contains all the random no.s , map all the 10 indexes to
a hash table and then display the arrays with the hashed index...
I think it may work...
what say..?
On 8/5/11, Gaurav Menghani gaurav.mengh...@gmail.com wrote:
1. Get a good seed.
2. Increase the degree of the polynomial.
This is no fixed algorithm, if you find that more than T steps have
passed and a new number has not been generated, you can always change
the polynomial. And, please remember it is a 'pseudo-random number
generator'. You can read the theory about PRNGs and LFSRs, all of
them
repeat.
On Fri, Aug 5, 2011 at 7:14 PM, payel roy smithpa...@gmail.com
wrote:
How do you guarantee termination of your algorithm if duplication
occurs
??
On 5 August 2011 18:25, Gaurav Menghani gaurav.mengh...@gmail.com
wrote:
You might want to read the theory on Pseudo-Random Number
Generators
[0] and Linear Feedback Shift Register [1]
The basic way of generating a random number is taking up a
polynomial,
f(x) = ax^n + bx^(n-1) + .. + yx + z, and finding f(i + seed) % N,
where i is the ith random number you want, and seed can be anything
random available, for example, you can find the current millisecond
using time.h functions.
A simple implementation, without the time thing is below:
#includeiostream
using namespace std;
int poly[10],pn,N,M;
int get(int seed)
{
int t=0;
for(int i=0;ipn;i++)
{
int res=poly[i];
for(int j=1;j=(i+1);j++) { res = (res*seed);
if(res=N)
res%=N; }
t+=res;
if(t=N) t%=N;
}
t=(t+seed);
t%=N;
return t;
}
void setup_prng()
{
pn=5;
poly[0]=2; poly[1]=3; poly[2]=5; poly[3]=7; poly[4]=11;
N=200; M=100;
}
int main()
{
setup_prng();
for(int i=1;i=M;i++)
coutget(i)endl;
return 0;
}
Whenever there is a collision, you can increment the value passed
to
the random number generator and continue. However, I am not sure
how
to check for collisions in O(1) space.
[0] http://en.wikipedia.org/wiki/Pseudorandom_number_generator
[1] http://en.wikipedia.org/wiki/Linear_feedback_shift_register
On Fri, Aug 5, 2011 at 5:19 PM, payel roy smithpa...@gmail.com
wrote:
Given a range 0-N, generate 'M' random numbers from the range
without
any
duplication. The space complexity is O(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] os
I would rather not discuss non-algorithm questions on this group :) On Mon, Aug 8, 2011 at 6:02 PM, dilip makwana dilipmakwa...@gmail.com wrote: Thanx for correction ... :D On 8 August 2011 17:50, dilip makwana dilipmakwa...@gmail.com wrote: Yes NAMED PIPES ... is correct On 8 August 2011 17:43, Himanshu Srivastava himanshusri...@gmail.com wrote: named pipes!!! On Mon, Aug 8, 2011 at 5:36 PM, Kamakshii Aggarwal kamakshi...@gmail.com wrote: Fastest IPC mechanism is ?shared memory ?pipes ?named pipes ?Semaphores -- Regards, Kamakshi kamakshi...@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. -- 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. -- Dilip Makwana VJTI BTech Computers Engineering 2009-2013 -- Dilip Makwana VJTI BTech Computers Engineering 2009-2013 -- 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. -- Gaurav Menghani -- 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] shift left nd right
http://lmgtfy.com/?q=Bitwise+left+and+right+shift+operators On Mon, Aug 8, 2011 at 10:20 PM, Shashank Jain shashan...@gmail.com wrote: thx dipankar, its a gud 1! Bt tell me wat does '' and '' operators do? eg: 202 = 1 can u explain nd wat is this operator called? Shashank Jain IIIrd year Computer Engineering Delhi College of Engineering On Mon, Aug 8, 2011 at 12:54 AM, Dipankar Patro dip10c...@gmail.com wrote: This link I think is a good one: http://msdn.microsoft.com/en-us/library/336xbhcz.aspx On 8 August 2011 00:37, Shashank Jain shashan...@gmail.com wrote: plz sum1 explain me shift left nd shift right operators? Shashank Jain IIIrd year Computer Engineering Delhi College of Engineering -- 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. -- ___ Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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. -- Gaurav Menghani -- 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] max product!
Also, when using a greedy strategy, it is best when you can PROVE why the strategy works. On Sun, Aug 7, 2011 at 10:25 PM, Gaurav Menghani gaurav.mengh...@gmail.comwrote: O(n) solution is pretty simple, without using a greedy strategy. prod[i] denotes product of ith, i+1th and i+2th elements. prod[i+1] is simply (prod[i]/arr[i])*(arr[(i+1)+2]). Answer would be the maximum product value. Do note that if prod[i] is zero, do not use the above formula, instead simply multiply the ith, i+1th and i+2th elements. On Sun, Aug 7, 2011 at 8:28 PM, Debabrata Das debabrata.barunhal...@gmail.com wrote: why do you need three smallest number, two would suffice ? On Sun, Aug 7, 2011 at 7:47 PM, Amol Sharma amolsharm...@gmail.comwrote: yes...it should work !! -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad On Sun, Aug 7, 2011 at 7:13 PM, Prakash D cegprak...@gmail.com wrote: 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. -- 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. -- Gaurav Menghani -- Gaurav Menghani -- 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: max product!
Greedy doesn't work here On Mon, Aug 8, 2011 at 1:35 AM, Dave dave_and_da...@juno.com wrote: @Coder: What if the data are -6, -5, -4, and -3. Then the largest product is (-5)*(-4)*(-3) = -60. The number with largest absolute value, -6, doesn't enter into the solution. Dave On Aug 7, 1:19 pm, coder dumca coder.du...@gmail.com wrote: 1: choose 4 biggest numbers with abs value following situations will arise 1: all 4 numbers are +ve then choose the biggest 3 2: 1 -ve 3 +ve choose 3 positive numbers 3: 3 -ve 1 +ve choose 2 -ve(with largest abs value) and 1 +ve 4: 2 +ve 2 -ve choose accordingly 4 all are -ve choose 2 -ve(with largest abs value) and scna the arry to finf largest +ve int pls let me know if i m wrong On Sun, Aug 7, 2011 at 6:09 AM, Nikhil Veliath nve...@gmail.com wrote: given an array that has n nos . . . . find the maximum product of 3 nos and display the 3 nos . . . 25 9 6 8 -20 -5 -10 so max product 5000 the nos are -20 -10 25 give an O(n) solution and if possible try avoid using sort -- 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. -- Gaurav Menghani -- 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]
The Postman's sort is a variant of bucket sort that takes advantage of a hierarchical structure of elements, typically described by a set of attributes. It is just a variant of Bucket Sort. On Sun, Aug 7, 2011 at 12:42 AM, rahul rai raikra...@gmail.com wrote: http://www.rrsd.com/software_development/postmans_sort/cuj/cuj.htm On 8/5/11, Gaurav Menghani gaurav.mengh...@gmail.com wrote: I agree with Dilip. It depends upon what type of input you have at hand. - Suppose you have an array having a million elements, where the elements are in the range 1-3, counting sort would be perfect. - However, if the range is from -10^18 to +10^18, counting sort, which requires O(R) memory, where R is the range of the elements, would be laughable. Here quick-sort or merge-sort would be better. Again, quick-sort is good for randomized inputs, such that the pivot lies roughly in the middle of every sub-array. For certain inputs, the performance of quick-sort degrades to O(N^2). For this reason, the default implementation of sort function in STL, uses 'Intro-Sort' [0] which is a combination of quick-sort and heap-sort (switches between the two depending upon the input) [0] http://en.wikipedia.org/wiki/Introsort On Fri, Aug 5, 2011 at 6:54 AM, dilip makwana dilipmakwa...@gmail.com wrote: But beware all linear sort algo have some prior constraints (such as range of input is predefined or such ...) So choose one properly On 4 August 2011 23:12, Samba Ganapavarapu sambasiv...@gmail.com wrote: Merget Sort sorts O(n log n) time, Counting sort, Radix sort sorts in O (n) time... On Thu, Aug 4, 2011 at 1:40 PM, Rohit jalan jalanha...@gmail.com wrote: Merge Sort On Thu, Aug 4, 2011 at 11:09 PM, parag khanna khanna.para...@gmail.com wrote: Which is fastest sorting method? -- 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 : ROHIT JALAN B.E. Graduate, Computer Science Department, RVCE, Bangalore -- 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. -- Dilip Makwana VJTI BTech Computers Engineering 2009-2013 -- 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. -- Gaurav Menghani -- 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 -- 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. -- Gaurav Menghani -- 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] Random number
We can have a sorted sequence and display them in random order, but
that is the same problem. How do we display them in random order? We
need to have a sequence of random indices, that is the same problem as
having random numbers, isn't it.
Moreover, I don't think collisions can be avoided in less than O(n).
We can have an efficient hash-table, but I am not sure how it can be
done in O(1) or better.
On Sat, Aug 6, 2011 at 12:37 PM, Puneet Gautam puneet.nsi...@gmail.com wrote:
I rhink to avoid collisions altogether we should generate an ordered
sequence , in a dec. or inc. order and
display them randomly, i mean:
Let say a[10] contains all the random no.s , map all the 10 indexes to
a hash table and then display the arrays with the hashed index...
I think it may work...
what say..?
On 8/5/11, Gaurav Menghani gaurav.mengh...@gmail.com wrote:
1. Get a good seed.
2. Increase the degree of the polynomial.
This is no fixed algorithm, if you find that more than T steps have
passed and a new number has not been generated, you can always change
the polynomial. And, please remember it is a 'pseudo-random number
generator'. You can read the theory about PRNGs and LFSRs, all of them
repeat.
On Fri, Aug 5, 2011 at 7:14 PM, payel roy smithpa...@gmail.com wrote:
How do you guarantee termination of your algorithm if duplication occurs
??
On 5 August 2011 18:25, Gaurav Menghani gaurav.mengh...@gmail.com wrote:
You might want to read the theory on Pseudo-Random Number Generators
[0] and Linear Feedback Shift Register [1]
The basic way of generating a random number is taking up a polynomial,
f(x) = ax^n + bx^(n-1) + .. + yx + z, and finding f(i + seed) % N,
where i is the ith random number you want, and seed can be anything
random available, for example, you can find the current millisecond
using time.h functions.
A simple implementation, without the time thing is below:
#includeiostream
using namespace std;
int poly[10],pn,N,M;
int get(int seed)
{
int t=0;
for(int i=0;ipn;i++)
{
int res=poly[i];
for(int j=1;j=(i+1);j++) { res = (res*seed); if(res=N)
res%=N; }
t+=res;
if(t=N) t%=N;
}
t=(t+seed);
t%=N;
return t;
}
void setup_prng()
{
pn=5;
poly[0]=2; poly[1]=3; poly[2]=5; poly[3]=7; poly[4]=11;
N=200; M=100;
}
int main()
{
setup_prng();
for(int i=1;i=M;i++)
coutget(i)endl;
return 0;
}
Whenever there is a collision, you can increment the value passed to
the random number generator and continue. However, I am not sure how
to check for collisions in O(1) space.
[0] http://en.wikipedia.org/wiki/Pseudorandom_number_generator
[1] http://en.wikipedia.org/wiki/Linear_feedback_shift_register
On Fri, Aug 5, 2011 at 5:19 PM, payel roy smithpa...@gmail.com wrote:
Given a range 0-N, generate 'M' random numbers from the range without
any
duplication. The space complexity is O(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.
--
Gaurav Menghani
--
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.
--
Gaurav Menghani
--
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.
--
Gaurav Menghani
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post
Re: [algogeeks] pls help
On Fri, Aug 5, 2011 at 12:20 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
given a set of letters and a length N, produce all possible output.(Not
permutation). For example, give the letter (p,o) and length of 3, produce
the following output(in any order you want, not just my example order)
ppp ppo poo pop opp opo oop ooo
another example would be given (a,b) and length 2
answer: ab aa bb ba
--
Regards,
Kamakshi
kamakshi...@gmail.com
This can be done easily by backtracking
void backtrack(string s, int l)
{
if(l == maxlen) { coutsendl; return; }
s.push_back('-');
for(int i=0;ialphabet.size();i++)
{
s[l]=alphabet[i];
backtrack(s,l+1);
}
}
--
Gaurav Menghani
--
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] pls help
The basic idea is that for every position of the string, you fill it
with all possible alphabets in your set of allowed alphabets, let the
set be called alphabet.
Now, you can do this recursively.
backtrack(s,l) denotes, a string s has been formed, and is of length
l. Now we need to add more letters to it. If l is equal to the maximum
length, then you just print the string s, and return.
Otherwise, append the characters available to you. For example, if in
the current scenario, the call is backtrack(po,2), and alphabet =
{'o','p'} and maxlen=3, then we can append 'o' and 'p' to the string
po, and hence call backtrack(poo,3) and backtrack(pop,3).
You start the process by calling backtrack(,0), and setting maxlen
and alphabet to the appropriate values.
On Fri, Aug 5, 2011 at 12:42 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
@gaurav:i could not understand ur sol.can u explain it again..
On Fri, Aug 5, 2011 at 12:32 PM, Gaurav Menghani gaurav.mengh...@gmail.com
wrote:
On Fri, Aug 5, 2011 at 12:20 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
given a set of letters and a length N, produce all possible output.(Not
permutation). For example, give the letter (p,o) and length of 3,
produce
the following output(in any order you want, not just my example order)
ppp ppo poo pop opp opo oop ooo
another example would be given (a,b) and length 2
answer: ab aa bb ba
--
Regards,
Kamakshi
kamakshi...@gmail.com
This can be done easily by backtracking
void backtrack(string s, int l)
{
if(l == maxlen) { coutsendl; return; }
s.push_back('-');
for(int i=0;ialphabet.size();i++)
{
s[l]=alphabet[i];
backtrack(s,l+1);
}
}
--
Gaurav Menghani
--
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,
Kamakshi
kamakshi...@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.
--
Gaurav Menghani
--
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] pls help
An Implementation:
#includeiostream
#includestring
using namespace std;
string alphabet;
int maxlen;
void backtrack(string s,int l)
{
if(l==maxlen) { coutsendl; return; }
s.push_back('-');
for(int i=0;ialphabet.size();i++)
{ s[l]=alphabet[i]; backtrack(s,l+1); }
}
int main()
{
maxlen=3;
alphabet=op;
backtrack(,0);
return 0;
}
On Fri, Aug 5, 2011 at 12:42 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
@gaurav:i could not understand ur sol.can u explain it again..
On Fri, Aug 5, 2011 at 12:32 PM, Gaurav Menghani gaurav.mengh...@gmail.com
wrote:
On Fri, Aug 5, 2011 at 12:20 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
given a set of letters and a length N, produce all possible output.(Not
permutation). For example, give the letter (p,o) and length of 3,
produce
the following output(in any order you want, not just my example order)
ppp ppo poo pop opp opo oop ooo
another example would be given (a,b) and length 2
answer: ab aa bb ba
--
Regards,
Kamakshi
kamakshi...@gmail.com
This can be done easily by backtracking
void backtrack(string s, int l)
{
if(l == maxlen) { coutsendl; return; }
s.push_back('-');
for(int i=0;ialphabet.size();i++)
{
s[l]=alphabet[i];
backtrack(s,l+1);
}
}
--
Gaurav Menghani
--
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,
Kamakshi
kamakshi...@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.
--
Gaurav Menghani
--
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: remove duplicate words in a string
Vaibhav, please don't dynamically alter the requirements of the problem :-) Better to say them up front. On Fri, Aug 5, 2011 at 2:10 PM, vaibhav shukla vaibhav200...@gmail.com wrote: provide a solution whether greater than O(n) On Fri, Aug 5, 2011 at 2:09 PM, saurabh singh saurab...@gmail.com wrote: use maps for implementation of hash table... if no extra memory allowed then no possible solution within o(n) i think. On Fri, Aug 5, 2011 at 2:07 PM, ankit sambyal ankitsamb...@gmail.com wrote: First traverse the string and hash each word into a hash table if it is not present in the hash table. Then again traverse the string and hash each word. If the word is not present in the hash table, output it to the console. -- 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. -- Saurabh Singh B.Tech (Computer Science) 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. -- best wishes!! Vaibhav MCA -- 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. -- Gaurav Menghani -- 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] pls help
Just to increase the size of the string by one.
Then you can put any character at the the new last position, which is 'l'.
On Fri, Aug 5, 2011 at 2:34 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
@gaurav:can u please explain what is the purpose of this line..
s.push_back('-');
On Fri, Aug 5, 2011 at 1:10 PM, Nitin Nizhawan nitin.nizha...@gmail.com
wrote:
Or one could just simulate a counting from 0 to (numchars^N)-1 in base
numchars.
...
code:
void printit(int N,char chars[],int index[]){
for(int i=0;iN;i++){
printf(%c,chars[index[i]]);
}
printf(\n);
}
void generate(int numchars,char chars[],int N){
int index[100]={0};
int allmax=0;
int maxdigit=numchars-1;
printit(N,chars,index);
while(!allmax){
// add one;
index[0]++;
allmax=0;
for(int i=0;iN;i++){
if(index[i]=numchars){
index[i]=0; index[i+1]++;
}
if(i==0index[i]==maxdigit){
allmax=1;
}
allmax = (index[i]==maxdigit)?allmax1:0;
}
printit(N,chars,index);
}
}
int main(){
char chars [] ={'p','o'};
int numchars =sizeof(chars)/sizeof(char);
int N=3;
generate(numchars,chars,N);
}
On Fri, Aug 5, 2011 at 12:58 PM, Gaurav Menghani
gaurav.mengh...@gmail.com wrote:
An Implementation:
#includeiostream
#includestring
using namespace std;
string alphabet;
int maxlen;
void backtrack(string s,int l)
{
if(l==maxlen) { coutsendl; return; }
s.push_back('-');
for(int i=0;ialphabet.size();i++)
{ s[l]=alphabet[i]; backtrack(s,l+1); }
}
int main()
{
maxlen=3;
alphabet=op;
backtrack(,0);
return 0;
}
On Fri, Aug 5, 2011 at 12:42 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
@gaurav:i could not understand ur sol.can u explain it again..
On Fri, Aug 5, 2011 at 12:32 PM, Gaurav Menghani
gaurav.mengh...@gmail.com
wrote:
On Fri, Aug 5, 2011 at 12:20 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
given a set of letters and a length N, produce all possible
output.(Not
permutation). For example, give the letter (p,o) and length of 3,
produce
the following output(in any order you want, not just my example
order)
ppp ppo poo pop opp opo oop ooo
another example would be given (a,b) and length 2
answer: ab aa bb ba
--
Regards,
Kamakshi
kamakshi...@gmail.com
This can be done easily by backtracking
void backtrack(string s, int l)
{
if(l == maxlen) { coutsendl; return; }
s.push_back('-');
for(int i=0;ialphabet.size();i++)
{
s[l]=alphabet[i];
backtrack(s,l+1);
}
}
--
Gaurav Menghani
--
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,
Kamakshi
kamakshi...@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.
--
Gaurav Menghani
--
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,
Kamakshi
kamakshi...@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.
--
Gaurav Menghani
--
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
Re: [algogeeks] pls help
Great.
On Fri, Aug 5, 2011 at 2:42 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
@gaurav:i got it..thanks for the solution
On Fri, Aug 5, 2011 at 2:34 PM, Kamakshii Aggarwal kamakshi...@gmail.com
wrote:
@gaurav:can u please explain what is the purpose of this line..
s.push_back('-');
On Fri, Aug 5, 2011 at 1:10 PM, Nitin Nizhawan nitin.nizha...@gmail.com
wrote:
Or one could just simulate a counting from 0 to (numchars^N)-1 in base
numchars.
...
code:
void printit(int N,char chars[],int index[]){
for(int i=0;iN;i++){
printf(%c,chars[index[i]]);
}
printf(\n);
}
void generate(int numchars,char chars[],int N){
int index[100]={0};
int allmax=0;
int maxdigit=numchars-1;
printit(N,chars,index);
while(!allmax){
// add one;
index[0]++;
allmax=0;
for(int i=0;iN;i++){
if(index[i]=numchars){
index[i]=0; index[i+1]++;
}
if(i==0index[i]==maxdigit){
allmax=1;
}
allmax = (index[i]==maxdigit)?allmax1:0;
}
printit(N,chars,index);
}
}
int main(){
char chars [] ={'p','o'};
int numchars =sizeof(chars)/sizeof(char);
int N=3;
generate(numchars,chars,N);
}
On Fri, Aug 5, 2011 at 12:58 PM, Gaurav Menghani
gaurav.mengh...@gmail.com wrote:
An Implementation:
#includeiostream
#includestring
using namespace std;
string alphabet;
int maxlen;
void backtrack(string s,int l)
{
if(l==maxlen) { coutsendl; return; }
s.push_back('-');
for(int i=0;ialphabet.size();i++)
{ s[l]=alphabet[i]; backtrack(s,l+1); }
}
int main()
{
maxlen=3;
alphabet=op;
backtrack(,0);
return 0;
}
On Fri, Aug 5, 2011 at 12:42 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
@gaurav:i could not understand ur sol.can u explain it again..
On Fri, Aug 5, 2011 at 12:32 PM, Gaurav Menghani
gaurav.mengh...@gmail.com
wrote:
On Fri, Aug 5, 2011 at 12:20 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
given a set of letters and a length N, produce all possible
output.(Not
permutation). For example, give the letter (p,o) and length of 3,
produce
the following output(in any order you want, not just my example
order)
ppp ppo poo pop opp opo oop ooo
another example would be given (a,b) and length 2
answer: ab aa bb ba
--
Regards,
Kamakshi
kamakshi...@gmail.com
This can be done easily by backtracking
void backtrack(string s, int l)
{
if(l == maxlen) { coutsendl; return; }
s.push_back('-');
for(int i=0;ialphabet.size();i++)
{
s[l]=alphabet[i];
backtrack(s,l+1);
}
}
--
Gaurav Menghani
--
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,
Kamakshi
kamakshi...@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.
--
Gaurav Menghani
--
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,
Kamakshi
kamakshi...@gmail.com
--
Regards,
Kamakshi
kamakshi...@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.
--
Gaurav Menghani
--
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
Re: [algogeeks] pls help
Even if the number of elements is more than two, it is possible with
bitwise operations, but it gets clumsy.
Suppose your alphabet has 4 characters. You can either:
- Count from 0 to (14*n)-1 and use four bits to denote the selection
of the alphabet. Also, only one bit amongst those four should be set.
It is highly inefficient.
- Keep n nested loops and inside each loop you iterate from 0 to
(14)-1 and use the standard bitwise operations. The con here is that
you have to hardcode the number of nested loops.
On Fri, Aug 5, 2011 at 2:44 PM, Nitin Nizhawan nitin.nizha...@gmail.com wrote:
@Varun I think it can be done using bits, if input character set has only
two elements. Or could u plz explain?
On Fri, Aug 5, 2011 at 2:29 PM, Varun Jakhoria varunjakho...@gmail.com
wrote:
I think it can be done using bitwise ANDing with a mask
On Fri, Aug 5, 2011 at 12:58 PM, Gaurav Menghani
gaurav.mengh...@gmail.com wrote:
An Implementation:
#includeiostream
#includestring
using namespace std;
string alphabet;
int maxlen;
void backtrack(string s,int l)
{
if(l==maxlen) { coutsendl; return; }
s.push_back('-');
for(int i=0;ialphabet.size();i++)
{ s[l]=alphabet[i]; backtrack(s,l+1); }
}
int main()
{
maxlen=3;
alphabet=op;
backtrack(,0);
return 0;
}
On Fri, Aug 5, 2011 at 12:42 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
@gaurav:i could not understand ur sol.can u explain it again..
On Fri, Aug 5, 2011 at 12:32 PM, Gaurav Menghani
gaurav.mengh...@gmail.com
wrote:
On Fri, Aug 5, 2011 at 12:20 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
given a set of letters and a length N, produce all possible
output.(Not
permutation). For example, give the letter (p,o) and length of 3,
produce
the following output(in any order you want, not just my example
order)
ppp ppo poo pop opp opo oop ooo
another example would be given (a,b) and length 2
answer: ab aa bb ba
--
Regards,
Kamakshi
kamakshi...@gmail.com
This can be done easily by backtracking
void backtrack(string s, int l)
{
if(l == maxlen) { coutsendl; return; }
s.push_back('-');
for(int i=0;ialphabet.size();i++)
{
s[l]=alphabet[i];
backtrack(s,l+1);
}
}
--
Gaurav Menghani
--
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,
Kamakshi
kamakshi...@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.
--
Gaurav Menghani
--
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.
--
Varun Jakhoria
...it's only about 0's 1's
--
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.
--
Gaurav Menghani
--
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] Random number
You might want to read the theory on Pseudo-Random Number Generators
[0] and Linear Feedback Shift Register [1]
The basic way of generating a random number is taking up a polynomial,
f(x) = ax^n + bx^(n-1) + .. + yx + z, and finding f(i + seed) % N,
where i is the ith random number you want, and seed can be anything
random available, for example, you can find the current millisecond
using time.h functions.
A simple implementation, without the time thing is below:
#includeiostream
using namespace std;
int poly[10],pn,N,M;
int get(int seed)
{
int t=0;
for(int i=0;ipn;i++)
{
int res=poly[i];
for(int j=1;j=(i+1);j++) { res = (res*seed); if(res=N)
res%=N; }
t+=res;
if(t=N) t%=N;
}
t=(t+seed);
t%=N;
return t;
}
void setup_prng()
{
pn=5;
poly[0]=2; poly[1]=3; poly[2]=5; poly[3]=7; poly[4]=11;
N=200; M=100;
}
int main()
{
setup_prng();
for(int i=1;i=M;i++)
coutget(i)endl;
return 0;
}
Whenever there is a collision, you can increment the value passed to
the random number generator and continue. However, I am not sure how
to check for collisions in O(1) space.
[0] http://en.wikipedia.org/wiki/Pseudorandom_number_generator
[1] http://en.wikipedia.org/wiki/Linear_feedback_shift_register
On Fri, Aug 5, 2011 at 5:19 PM, payel roy smithpa...@gmail.com wrote:
Given a range 0-N, generate 'M' random numbers from the range without any
duplication. The space complexity is O(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.
--
Gaurav Menghani
--
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] Random number
1. Get a good seed.
2. Increase the degree of the polynomial.
This is no fixed algorithm, if you find that more than T steps have
passed and a new number has not been generated, you can always change
the polynomial. And, please remember it is a 'pseudo-random number
generator'. You can read the theory about PRNGs and LFSRs, all of them
repeat.
On Fri, Aug 5, 2011 at 7:14 PM, payel roy smithpa...@gmail.com wrote:
How do you guarantee termination of your algorithm if duplication occurs ??
On 5 August 2011 18:25, Gaurav Menghani gaurav.mengh...@gmail.com wrote:
You might want to read the theory on Pseudo-Random Number Generators
[0] and Linear Feedback Shift Register [1]
The basic way of generating a random number is taking up a polynomial,
f(x) = ax^n + bx^(n-1) + .. + yx + z, and finding f(i + seed) % N,
where i is the ith random number you want, and seed can be anything
random available, for example, you can find the current millisecond
using time.h functions.
A simple implementation, without the time thing is below:
#includeiostream
using namespace std;
int poly[10],pn,N,M;
int get(int seed)
{
int t=0;
for(int i=0;ipn;i++)
{
int res=poly[i];
for(int j=1;j=(i+1);j++) { res = (res*seed); if(res=N)
res%=N; }
t+=res;
if(t=N) t%=N;
}
t=(t+seed);
t%=N;
return t;
}
void setup_prng()
{
pn=5;
poly[0]=2; poly[1]=3; poly[2]=5; poly[3]=7; poly[4]=11;
N=200; M=100;
}
int main()
{
setup_prng();
for(int i=1;i=M;i++)
coutget(i)endl;
return 0;
}
Whenever there is a collision, you can increment the value passed to
the random number generator and continue. However, I am not sure how
to check for collisions in O(1) space.
[0] http://en.wikipedia.org/wiki/Pseudorandom_number_generator
[1] http://en.wikipedia.org/wiki/Linear_feedback_shift_register
On Fri, Aug 5, 2011 at 5:19 PM, payel roy smithpa...@gmail.com wrote:
Given a range 0-N, generate 'M' random numbers from the range without
any
duplication. The space complexity is O(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.
--
Gaurav Menghani
--
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.
--
Gaurav Menghani
--
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: Give an efficient search algo
Problem 2 can be solved in O(n/k). If you want to search for x, look at the first element. If the element is not found, find the difference between the current element and x, let this be stored in diff. Now, x will be atleast diff number of positions ahead in the array. So, the next position is current position + diff. If the element is still not found, continue. On Thu, Aug 4, 2011 at 5:27 PM, Dave dave_and_da...@juno.com wrote: @Amit: It is given that the array is decreasing, then increasing. An array of constants is neither increasing nor decreasing. Dave On Aug 3, 11:41 pm, amit karmakar amit.codenam...@gmail.com wrote: Can you show how to find k for an array containing n 2's using binary search. On Aug 4, 6:29 am, Dave dave_and_da...@juno.com wrote: @Amit: If k is not known, you can find it with another binary search. Dave On Aug 3, 3:02 pm, amit karmakar amit.codenam...@gmail.com wrote: I think for question 1, the value of k is not provided, right? On Aug 4, 12:53 am, Ankur Garg ankurga...@gmail.com wrote: Dave's solution looks gud to me :) On Wed, Aug 3, 2011 at 3:52 PM, Ankur Garg ankurga...@gmail.com wrote: Q1 can be looked as rotated sorted array...check whether the no is less or greater than kth element ..if greater search using binary search with low =0 high k-1 and if less earch in right with low=k+1 high =n; q2) Dont know :( On Wed, Aug 3, 2011 at 3:44 PM, Dave dave_and_da...@juno.com wrote: @Tushar: For problem 1, do a binary search on elements 1 to k, and if no hit is found, do a binary search on elements k+1 to n. For problem 2, suppose that you are searching the given array for the number 2. The idea is to take big steps when you are far from the target, and small steps when you are close. Start with i = 0. If a[i] ! = 2, then add abs(a[i]-2) to i and try again. This is because it will take at least abs(a[i]-2) steps to get to 2. In this case, i = 0 and a[0] = 6, so add 4 to i, getting 4. a[4] = 4, so add 2 to i, getting 6. a[6] = 3, so add 1. a[7] = 2. Dave On Aug 3, 2:09 pm, TUSHAR tusharkanta.r...@gmail.com wrote: 1. Given an array of n-elements ? the 1st k -elements are in descending order and k+1 to n elements are in ascending order. give an efficient algo for searching an element ? 2. Given an array of n-elements ? each element in the array is either same or less by 1 or larger by 1 from the previous element . give an efficient algo for searching an element ? e.g : 6 6 6 5 4 4 3 2 3 4 3 4 -- 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.-Hidequoted text - - Show quoted text -- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Gaurav Menghani -- 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: Tug of War
On Thu, Aug 4, 2011 at 7:37 PM, saurabh singh saurab...@gmail.com wrote: Its a classical 0/1 knapsack problem which can be implemented either as a greedy solution or dp It has been stated earlier in the thread that this is an 'NP-Complete' problem. [0] It means, there is no known polynomial-time algorithm for this problem. If you think you have a greedy solution to this problem, think again. The DP solution is also, 'pseudo-polynomial-time' [0] http://en.wikipedia.org/wiki/Partition_problem -- Gaurav Menghani -- 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: Tug of War
On Thu, Aug 4, 2011 at 7:42 PM, Gaurav Menghani gaurav.mengh...@gmail.com wrote: On Thu, Aug 4, 2011 at 7:37 PM, saurabh singh saurab...@gmail.com wrote: Its a classical 0/1 knapsack problem which can be implemented either as a greedy solution or dp It has been stated earlier in the thread that this is an 'NP-Complete' problem. [0] It means, there is no known polynomial-time algorithm for this problem. If you think you have a greedy solution to this problem, think again. The DP solution is also, 'pseudo-polynomial-time' Just adding, greedy solutions are always possible, but the thing to ponder over is, whether they give optimal solutions _for_every_case_ or not. -- Gaurav Menghani -- 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: Tug of War
On Thu, Aug 4, 2011 at 8:13 PM, saurabh singh saurab...@gmail.com wrote: think its NP complete once the number of teams become varaible, corrct me if wrong i am weak with the theoritical stuffs... Err, it is NP-complete, the thing is when the set of integers is small, a DP solution runs in reasonable time. When you increase the set size, the time taken increases. -- Gaurav Menghani Stony Brook University -- 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 Telephonic interview
to say linked to maintain all time task with its corresponding
running time and associate function. In that case how will find the task
which has the closed running time.
If you use min heap it would be easy to find the task that has closest
runing time in O(1) complexity.
On Thu, Aug 4, 2011 at 10:57 AM, mohit verma mohit89m...@gmail.com
wrote:
why are u maintaining heap? can't we use link list here?
On Thu, Aug 4, 2011 at 11:16 PM, Anand Shastri
anand.shastr...@gmail.com wrote:
You have given a structure which has two member, One which stores the
time and other stores the function pointer Your function has to call
the
function stored in the fuction poitner after the time given in the
structure elapses.
Design that function?
Approach: To design this function I would use a min Heap data
structure. Each node of a heap has
two parameters one is the running time and other one
is the function pointer.
// Initialise a function pointer
typedef void (*functionToBeCalled)(int arg1, int arg2);
// Timer structure
typedef struct timer
{
float runingTime; // in terms of seconds
functionToBeCalled funcToBeCall; // function pointer
}TIMER;
void initTimer()
{
Initialise few nodes with running time and its corresponding
function
Initialise a MIN heap data structure
}
void addTimer(uint32 runingTime, functionToBeCalled func)
{
TIMER *temp;
temp = (TIMER *)malloc(sizeof(TIMER));
temp-runingTime = runningTime
temp-funcToBeCall = func;
HeapAdd(temp);
Heapify();
}
void scheduler()
{
uint32 currentTime = ObtainCurrentTime();
// Obtain the runing time of top most element of the min
Heap
uint32 runingTime = PeakHeap();
// if the runningTime is equal to current time then
extract the top most
// element of the heap and execute the function associate
with it
// Heapify the MIN heap data structure
// Obtain the runing time of top most element of the min
heap
// scheduler sleep for that much amount of time.
if(runingTime == currentTime)
{
TIMER * node = ExtractMinHeap();
CreateThread(node-func, Thread);
Heapify();
runingTime = PeakHeap();
sleep(runningTime);
}
else
{
// scheduler updates its sleep time
// if runing time is not equal to current time
sleep(runningTime);
}
}
Let me know your comments
--
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.
--
MOHIT VERMA
--
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.
--
MOHIT VERMA
--
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.
--
Gaurav Menghani
--
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 Telephonic interview
Then that has to be mentioned in the question. Premature optimization
is the root of all evil, in the words of Don Knuth.
On Fri, Aug 5, 2011 at 9:38 AM, Anand Shastri anand.shastr...@gmail.com wrote:
what if new task gets added every time.
On Thu, Aug 4, 2011 at 8:24 PM, Gaurav Menghani gaurav.mengh...@gmail.com
wrote:
Instead of a heap, sort the array once. Pick the first element every
time, and remove it from the array, or just move the 'head pointer'
ahead.
On Fri, Aug 5, 2011 at 8:01 AM, Anand Shastri anand.shastr...@gmail.com
wrote:
/* Create a Timer Task that takes in the running time and it's
associated
function to be called after its running time is elapsed */
#include time.h
#define NUM 5
typedef void (*funcToBeCalled)(void);
typedef struct timer TIMER;
struct timer
{
int runningTime;
funcToBeCalled func;
};
static TIMER timerArray[NUM];
static time_t reference;
static int count;
int LEFT(int index)
{
if(index NUM)
return (index * 2 + 1);
}
int RIGHT(int index)
{
if(index NUM)
return (index * 2 + 2);
}
static void print(void)
{
printf(Timer task has been called\n);
}
// Initialise the timer data structure
void Init()
{
int index;
count = NUM;
// Note down the reference time
reference = time(0);
printf(reference : %ld\n, reference);
// Initialise the data structure such that associate function gets
// called after 3, 6, 9, 12, 15 seconds respectively.
for(index = 0; index count; index++)
{
timerArray[index].runningTime = (index + 1) * 3;
timerArray[index].func = print;
}
}
// This function check the min heap property and arrange
// the element such that at every node, root node should be
// less than its right and left child element.
Heapify(int index)
{
int left, right, minIndex;
TIMER temp;
left = LEFT(index);
right = RIGHT(index);
if(left (count)
(timerArray[left].runningTime timerArray[index].runningTime))
{
minIndex = left;
}
else
{
minIndex = index;
}
if(right (count)
(timerArray[right].runningTime timerArray[minIndex].runningTime))
{
minIndex = right;
}
if(minIndex != index)
{
temp.runningTime = timerArray[index].runningTime;
temp.func = timerArray[index].func;
timerArray[index].runningTime = timerArray[minIndex].runningTime;
timerArray[index].func = timerArray[minIndex].func;
timerArray[minIndex].runningTime = temp.runningTime;
timerArray[minIndex].func = temp.func;
Heapify(minIndex);
}
}
// This function builds the MIN heap data structure
void BuildHeap()
{
int len, i;
len = sizeof(timerArray)/sizeof(timerArray[0]);
i = (len - 1)/2;
while(i = 0)
{
Heapify(i);
i--;
}
Heapify(0);
}
// This function extract the top element of the heap
// Min heap has the min element at the top always.
int HeapExtract()
{
TIMER temp;
// Swap the 0 the element with last element of the array
temp.runningTime = timerArray[0].runningTime;
temp.func = timerArray[0].func;
timerArray[0].runningTime = timerArray[count-1].runningTime;
timerArray[0].func = timerArray[count-1].func;
timerArray[count-1].runningTime = temp.runningTime;
timerArray[count-1].func = temp.func;
count--;
// Check the heap property heapify if it got violated
Heapify(0);
// return the minimum element of the heap
return (count);
}
void scheduler()
{
time_t now;
int diff_time, minIndex;
while(count = 0)
{
now = time(0);
printf(Current Time: %ld\n, time(0));
diff_time = now- reference;
printf(diff_time : %ld\n, diff_time);
if(diff_time = timerArray[0].runningTime)
{
minIndex = HeapExtract();
timerArray[minIndex].func();
}
else
{
sleep(timerArray[0].runningTime - diff_time);
}
}
}
main()
{
int index, minIndex;
TIMER temp;
// Initialise the data structure
Init();
// Build MIn heap data structure
BuildHeap(timerArray);
// Run the scheduler
scheduler();
return;
}
The ouput of above code is
Timer Task is about to run
reference : 1312510772
Current Time: 1312510775
diff_time : 3
Timer task has been called
Current Time: 1312510778
diff_time : 6
Timer task has been called
Current Time: 1312510781
diff_time : 9
Timer task has been called
Current Time: 1312510784
diff_time : 12
Timer task has been called
Current Time: 1312510787
diff_time : 15
Timer task has been called
Please share your comments
On Thu, Aug 4, 2011 at 11:43 AM, Anand Shastri
anand.shastr...@gmail.com
wrote:
Obviously you need to run the task that a closet running time.
For Example
Task
Re: [algogeeks] Data Structure to design logn LCA
On Fri, Aug 5, 2011 at 9:41 AM, Aman Goyal aman.goya...@gmail.com wrote: You receive a series of online queries : Give nearest common ancestor of u,v . Your objective is to preprocess the tree in O(n) time to get a data structure of size O(n) so that you can answer any such query in O(log n) time. Segment tree [0] is what you are looking for. [0] http://www.topcoder.com/tc?module=Staticd1=tutorialsd2=lowestCommonAncestor -- Gaurav Menghani -- 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]
I agree with Dilip. It depends upon what type of input you have at hand. - Suppose you have an array having a million elements, where the elements are in the range 1-3, counting sort would be perfect. - However, if the range is from -10^18 to +10^18, counting sort, which requires O(R) memory, where R is the range of the elements, would be laughable. Here quick-sort or merge-sort would be better. Again, quick-sort is good for randomized inputs, such that the pivot lies roughly in the middle of every sub-array. For certain inputs, the performance of quick-sort degrades to O(N^2). For this reason, the default implementation of sort function in STL, uses 'Intro-Sort' [0] which is a combination of quick-sort and heap-sort (switches between the two depending upon the input) [0] http://en.wikipedia.org/wiki/Introsort On Fri, Aug 5, 2011 at 6:54 AM, dilip makwana dilipmakwa...@gmail.com wrote: But beware all linear sort algo have some prior constraints (such as range of input is predefined or such ...) So choose one properly On 4 August 2011 23:12, Samba Ganapavarapu sambasiv...@gmail.com wrote: Merget Sort sorts O(n log n) time, Counting sort, Radix sort sorts in O (n) time... On Thu, Aug 4, 2011 at 1:40 PM, Rohit jalan jalanha...@gmail.com wrote: Merge Sort On Thu, Aug 4, 2011 at 11:09 PM, parag khanna khanna.para...@gmail.com wrote: Which is fastest sorting method? -- 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 : ROHIT JALAN B.E. Graduate, Computer Science Department, RVCE, Bangalore -- 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. -- Dilip Makwana VJTI BTech Computers Engineering 2009-2013 -- 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. -- Gaurav Menghani -- 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] Least Common Ancestor in an n ary tree
If there are N nodes and it is an n-ary tree, O(N) pre-processing is required for every node, storing its parent in each step. Subsequently, if LCA(u,v) is to be found, produce the list of ancestors A(u) and A(v), which can be done in O(log-n N) steps. Then compare A(u) and A(v) to find the furthest element in A(u) and A(v) that matches. So O(N) pre-processing and O(log-n N) query time complexity. On Fri, Aug 5, 2011 at 10:22 AM, ankit sambyal ankitsamb...@gmail.com wrote: Find LCA in n ary tree ? -- 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. -- Gaurav Menghani -- 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] compiler
Yes. On Fri, Aug 5, 2011 at 11:06 AM, krishna meena krishna.meena...@gmail.com wrote: For any compiler generated temporaries the space is allocated in run time heap only? -- 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. -- Gaurav Menghani -- 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: Missing elements
On Aug 1, 6:25 pm, Deepak deepakthegi...@gmail.com wrote: Given an array of elements 'n'. some kn elements are replaced by elements such that the repalced elements are n. with o(n) find the missing elements, without wasting any extra memory. I think you did not phrase the question correctly. I am assuming you meant an array of n-numbers from [1,n]. Here, kn numbers are replaced by numbers are replaced. We need to find the missing numbers. I assume, we can take the space for a loop counter, even if we can't we can do the same thing by hard-coding, which will be just a little messy. Pseudocode: for i from 1 to n if(arr[i]!=i): arr[arr[i]]^=arr[i] arr[i]^=arr[arr[i]] arr[arr[i]]^=arr[i] for i from 1 to n if(arr[i]!=i) print i The logic being here is, whenever a number is found out of place, say, the number 2 is found at position 4, arr[4] and arr[2] are swapped (without the use of temp variables). Then another pass is made to check if i exists at arr[i]. If it does not, that implies, i was not present in arr, otherwise it would have been placed at arr[i]. -- 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.
