Hi,
Please let me know is there any standard algorithm to solve the below
mentioned problem.
Problem statement:
I am having 10 apples and 4 basket each basket capacity is as mentioned below:
Basket1 : capacity can hold maximum of 2 apples
Basket2 : capacity can hold maximum of 4 apples
Baske
Not that I am trying to prove a point...but just trying to clarify
what I said...
A uniform random number generator,
say rand_5() produces a value 2 with probability 1/5
it can produce a sequence of two 2s with probability (1/5)^2
it can produce a sequence of three 2s with probability (1/5)^3
extra space is sol to this problem..
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email
@bharath
apply your logic at
"abbaabba"
show me your steps
On Tue, Sep 8, 2009 at 8:04 PM, Bharath wrote:
>
> Q: Check whether given singly linked list is palindrome or not in
> single pass.
>
> Instead of making two passes, can we do it in single pass on a list?
>
> One method i can think of
@bharath
how will u recognize
which "a" to compare to which "a"
or apply on "malayalam"
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegr
Manish, your first approach doesn't work. You will notice that b1, b2,
and b3 each are 0 2/5 of the time and 1 3/5 of the time, so the return
value is not uniformly distributed.
For approach 2, what do you have to do if you want an exactly uniform
distribution as a result? Or what would the code
Ramaswamy, summing seven uniform random numbers doesn't give a uniform
result. Even the sum of two random numbers is not uniform. Consider
rolling two dice. 2 occurs only 1 out of 36 times, while 7 occurs 6
out of 36 times.
Dave
On Sep 8, 2:34 pm, Ramaswamy R wrote:
> Generate the random number
Generate the random number 7 times. Sum them all and divide by 5.
Theoritically it should be evenly distributed over 1-7. But owing to random
number generators characteristics the sum of rand(5) called 7 times may not
be perfectly evenly distributed over 1-7.
A nice discussion on some neat options
From: ankur aggarwal
To: algogeeks@googlegroups.com
Sent: Tuesday, 8 September, 2009 9:02:45 PM
Subject: [algogeeks] Re: n balls having k colors
int num_balls[K] = {0}; // one entry per color.
Use num_balls[] to count balls for each color. Now we just need to
Are we able to store the incoming characters?
On Tue, Sep 8, 2009 at 11:51 AM, Bharath wrote:
>Slightly modifying first question.
>
>Check whether a string is palindrome in single pass.
>
>Meaning an online algorithm is required, i.e. it must be able to read
>one character at a time from a stre
I can think of 2 appraches.
[1] Similar to something already suggested. Just adding my 2 cents.
1 to 7 digits can be represented by 3 bits. So going by that,
int rand_1_7() {
b1 = rand_1_5()*(7/5) > (7/2) ? 1 : 0;
b2 = rand_1_5()*(7/5) > (7/2) ? 1 : 0;
b3 = rand_1_5()*(7/5) > (7/2
Huh? You'll note his posting is appended to mine, just as your
posting, my posting, and part of his posting are appended to this one.
On Sep 8, 10:34 am, ankur aggarwal wrote:
> @dave
> plz quote the name of the person u r taking / pointing..
>
>
>
> On Tue, Sep 8, 2009 at 8:11 PM, Dave wrote:
yeah a[i] == a[n-i] will work if you know the length of the list in advance.
What if we dont know the length in advance. One has to to make two passes on
a list ,first to find the length or midpoint and another pass for
comparison.
Can we do it in a single pass?
On Tue, Sep 8, 2009 at 9:01 PM,
On Tue, Sep 8, 2009 at 9:04 PM, ankur aggarwal wrote:
> @dave
> plz quote the name of the person u r *talking* / pointing..
>
>
> On Tue, Sep 8, 2009 at 8:11 PM, Dave wrote:
>
>>
>> Your comment is moot, since if any random number generator returns the
>> same number forever, you are not going to
@manish
wat is the complexity ??
think about it...
"sort balls[] on the basis of code[color_tag]"
wat r u doing here ??
On Tue, Sep 8, 2009 at 8:35 PM, manish bhatia wrote:
> Assign 0 to K numbers to all K colors, such that color -> color_tag (a
> number b/w [0,K-1]).
> code[k] = {0,2,..,k-1}
@dave
plz quote the name of the person u r taking / pointing..
On Tue, Sep 8, 2009 at 8:11 PM, Dave wrote:
>
> Your comment is moot, since if any random number generator returns the
> same number forever, you are not going to be able to use it to
> generate other random numbers with a uniform d
@barath
u r using extra space..
wat is new about this sol
change to array..
then do as simple
using a[i]==a[n-i] ???
On Tue, Sep 8, 2009 at 8:04 PM, Bharath wrote:
>
> Q: Check whether given singly linked list is palindrome or not in
> single pass.
>
> Instead of making two passes, can we do it
@karthik
but look at the prob part..
it seems ok 2 me..
it is random generator u cannot guarntee which number is going 2 come..
On Tue, Sep 8, 2009 at 7:34 PM, Karthik Singaram Lakshmanan <
karthiksinga...@gmail.com> wrote:
>
> The rejection technique may never halt...(with an infinitesimall
1st ques
struct Node
{ datatype DATA
struct Node * next;
struct Node * random;
};
struct Node * cloneList(Node * original)
{
struct Node *p,*q,*r;
for(p = original; p != null; p = p->next->next)
{
q = p->next;
p->next = getNewNode();
p->next->next = q;
}
for(p = origin
Q: Check whether given singly linked list is palindrome or not in
single pass.
Instead of making two passes, can we do it in single pass on a list?
One method i can think of is, hashing character to its postion and
check for the sum.
abccba
123456
a: 1+6=7
b: 2+5=7
c: 3+4=7
On Sep 8, 5:33 pm,
how about finding all the connected-components and checking which all have 3
edges?
From: ankur aggarwal
To: "i...@mca_2007" ;
lets-talk-g...@googlegroups.com; algogeeks@googlegroups.com
Sent: Sunday, 6 September, 2009 2:58:40 PM
Subject: [algogeeks] find tri
Assign 0 to K numbers to all K colors, such that color -> color_tag (a number
b/w [0,K-1]).
code[k] = {0,2,..,k-1}
foreach (permutation from all possible-permuations of code[])
sort balls[] on the basis of code[color_tag]
print balls[]
From: ankur aggarw
Your comment is moot, since if any random number generator returns the
same number forever, you are not going to be able to use it to
generate other random numbers with a uniform density.
On Sep 8, 9:04 am, Karthik Singaram Lakshmanan
wrote:
> The rejection technique may never halt...(with
The rejection technique may never halt...(with an infinitesimally
small probability of course)...
In the case of Dave's algorithm:
if the following random_1_to_5() keeps returning 5.
U1 = random_1_to_5();
while( U1 == 5 );
In the case of Ankur's algorithm
if rand_5() keeps return
for 1st
use hare and tortoise algo to find the mid point of the linklist ...
and reverse the other end
like
a->b-->c->d->v->u
a->b-->c<-d<-v<-u
pointer 1 will point to a and other pointer will point to u
then it is done ..
u can check..
2nd
for(p = original; p != null; p = p->next->next)
p
Can we do it like this?
Random_bit()
{
..int x= rand_5()%3;
..if(x== 2)
.return Random_bit();
..else
return x;
}
This will generate 0 and 1 each with probability 2/5.
Rand_7()
{
int b1,b2,b3;
b1 = Random_bit();
b2 = Ra
@bharat
your statement is not clear..
On Tue, Sep 8, 2009 at 11:51 AM, Bharath wrote:
>
> Slightly modifying first question.
>
> Check whether a string is palindrome in single pass.
>
> Meaning an online algorithm is required, i.e. it must be able to read
> one character at a time from a stream
@dufus
tell me 1 thing
do we have to make algo so that the prob is 1/7 or do we have to make so
that prob of generating number between 1 to 7 is same may be( 1/10) etc ???
On Tue, Sep 8, 2009 at 11:42 AM, Dufus wrote:
>
> Hardest part of this problem is to prove that the generated number
> INDE
You can use Hash but then you have to design a hash function such that hash
clashes should be less which I think will depend on your input set. Hash
clashes will increase time complexity of searching.
In counting sort space requirement is very high, so instead of taking too
much of space you can u
Hashing for words,
and a mapping to ASCII values for characters (make array of size
256... if (A[(int)string[i]] == 0), an original char, A[(int)string[i]]
++, else a duplicate char)
Go through string and delete duplicate chars and when you reach the
end of a word hash it and add it to output if
Hardest part of this problem is to prove that the generated number
INDEED follow uniform distribution :D
_dufus
On Sep 8, 6:57 am, Dave wrote:
> Use the rejection technique, something like this:
>
> do
> {
> do
> U1 = random_1_to_5();
> while( U1 == 5 );
> // At this point, U1
Slightly modifying first question.
Check whether a string is palindrome in single pass.
Meaning an online algorithm is required, i.e. it must be able to read
one character at a time from a stream and tells whether string read so
far is palindrome or not.
--~--~-~--~~~---
You can use a hash map. What do u mean by preserving order?
Keep inserting the characters into hash, whenever u find a duplicate,
delete it. The order is maintained still. Can you please elaborate on
what is mean by preserving order?
On Sep 8, 10:47 am, yash wrote:
> wap a program in efficient
@dave
*
*On Tue, Sep 8, 2009 at 7:27 AM, Dave wrote:
>
> Use the rejection technique, something like this:
>
> do
> {
>do
>U1 = random_1_to_5();
>while( U1 == 5 );
> // At this point, U1 is a uniform integer in the range 1 to 4.
>U2 = random_1_to_5();
> * if( U1 > 2 )//* pl
@Nagendra: I think thats exactly what needs to be done.
Triangle is a 3-clique.
Not sure if the interviewer had the same definition in mind.
@Ankur: Please comment.
_dufus
On Sep 7, 8:25 pm, Nagendra Kumar wrote:
> is it not finding a cycle in a graph of length 3.
>
> On Sun, Sep 6, 2009 at
35 matches
Mail list logo
