[algogeeks] DS question

[yash]

wap a program in efficient manner to remove all occurrence of
duplicate character in the word and all occurrence of duplicate word
in the file.

i break the problem in two section( this is my approach it may be
better one )

wap to remove all duplicate character in the word. (order is important)
[i don't know which DS we use for this program your suggestion has
highly appreciated]
wap to remove all duplicate word in the file. (order is important)[we
use tries to remove all duplicate word in the file]

input in file

we welcome your feedback, suggestions comment to make better your
world

After run the above compression algo output will be

we welcom your fedback, sugtion coment to make betr world





--
Kind Regards
  ^_^
Yashpal Jain
Software Developer-IDC Risk
PayPal - an ebay company


--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: random number...

[Dave]

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 )
U2 += 5;
}
while( U2 > 7 );
// At this point, U2 is a uniform random integer in the range 1 to 7.

It takes on average 45/14 1_to_5 random numbers to make a 1_to_7
random number.

Dave


On Sep 7, 10:56 am, ankur aggarwal  wrote:
>   Given a random number generator that generates numbers in the range 1 to
> 5, how can u create a random number generator to generate numbers in the
> range 1 to 7. (remember that the generated random numbers should follow a
> uniform distribution in the corresponding range)
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: random number...

[Nagendra Kumar]

@ankur: u r right.

On Mon, Sep 7, 2009 at 9:36 PM, ankur aggarwal wrote:
> I KNow a sol for given a rand_5() function which generates 0 to 5
> and we have to find rand_7() for 0 to 7
>
> could not think about it...
>
>
>
> On Mon, Sep 7, 2009 at 9:26 PM, ankur aggarwal 
> wrote:
>>
>> Given a random number generator that generates numbers in the range 1 to
>> 5, how can u create a random number generator to generate numbers in the
>> range 1 to 7. (remember that the generated random numbers should follow a
>> uniform distribution in the corresponding range)
>
> >
>

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: addition without using arithmetic operators

[ayush chauhan]

Cud u plz explain the logic behind this?

On Mon, Sep 7, 2009 at 9:44 PM, Gokul  wrote:

>
> you can try this..
>  int  add(int x, int y)
> {
>if (!x) return y;
>else
> return add((x & y) << 1, x ^ y);
>   }
>
>
>
> On Sep 7, 4:01 pm, ritter  wrote:
> > how to add two integers without using arithmetic operators?
> > can anyone help me.
>
> >
>

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: addition without using arithmetic operators

[Gokul]

you can try this..
  int  add(int x, int y)
 {
if (!x) return y;
else
 return add((x & y) << 1, x ^ y);
  }



On Sep 7, 4:01 pm, ritter  wrote:
> how to add two integers without using arithmetic operators?
> can anyone help me.

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] random number...

[ankur aggarwal]

  Given a random number generator that generates numbers in the range 1 to
5, how can u create a random number generator to generate numbers in the
range 1 to 7. (remember that the generated random numbers should follow a
uniform distribution in the corresponding range)

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: random number...

[ankur aggarwal]

I KNow a sol for given a rand_5() function which generates *0* to 5
and we have to find rand_7() for *0* to 7

could not think about it...



On Mon, Sep 7, 2009 at 9:26 PM, ankur aggarwal wrote:

>  Given a random number generator that generates numbers in the range 1 to
> 5, how can u create a random number generator to generate numbers in the
> range 1 to 7. (remember that the generated random numbers should follow a
> uniform distribution in the corresponding range)
>

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: find triangle in a graph

[Nagendra Kumar]

is it not finding a cycle in a graph of length 3.

On Sun, Sep 6, 2009 at 9:02 PM, Dufus wrote:
>
> The following approach might work.
> Let K be the maximum degree of a vertex in the graph
> Enumerate each of the n vertex as 1...n
> Enumerate undirected edge between vertex i and j  (i.e. i--j) as
> (i,j)
>
> Sort all the |E| edges in O(|V| + |E|) time // radix sort.
> Now (i1,i2,i3) form a triangle iff there exist edges
> (i1,i2)
> (i1,i3)
> (i2,i3)
>
> For any vertex i1 we need to check C(k,2) pair of vertices {(i1,i2),
> (i1,i3)}
> By maintaining a hash table we can check if edge exists between
> (i2,i3) in O(1) time.
>
> Hence we can determine 3-clique from sorted list in (V.C(k,2)) time
> which is O(|E|) if k=O(n) or O(|V|) if k=O(1)
>
> Hence we can determine all the triangles in O(|V| + |K|) time and O(|
> E|) space.
>
> _dufus
>
>
> On Sep 6, 2:28 pm, ankur aggarwal  wrote:
>>  google question : find triangle in a graph Given an undirected graph,
>> design a O(V+E) algo to detect whether there is a triangle in the graph ot
>> not.
>
> >
>

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: n balls having k colors

[Bharath]

How about using a hash. Hash element to its position in the array.
This way we can preserve the order.

On Sep 7, 4:33 pm, gaurav gupta <1989.gau...@googlemail.com> wrote:
> Counting Sort is a good solution. This problem is same like :
>
> you have an array 1,3,1,3,2,6,5,7,8,5,6,4,5,2 You have to arrange them such
> that all number having same value should occur together and order of
> occurrence in series should conserve. So result will be :
>
> 1,1 ,3,3,2,2,6,6,5,5,5,7,8 ,4
>
>
>
> On Sun, Sep 6, 2009 at 11:39 AM, Dufus  wrote:
>
> > How about counting sort in O(N+K) time and O(K) space.
>
> > _dufus
>
> > On Sep 6, 1:06 pm, ankur aggarwal  wrote:
> > > You have N balls having one of K colors. Arrange them into groups of same
> > > colors. e.g.
>
> > > RRGRG
> > > can be arranged as
> > > RRRGG (Answer)
> > > GGRRR
>
> --
> GAURAV GUPTA
> B.Tech IV Yr. , Department of Computer Science & Engineering
> IT BHU , Varanasi
> Contacts
> Phone No: +91-99569-49491
>
> e-mail :
> gaurav.gu...@acm.org
> gaurav.gupta.cs...@itbhu.ac.in

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: addition without using arithmetic operators

[gaurav gupta]

To Add two integer you can use full adder at bit level.

if bit1 and bit2 are kth bits and car is previous carry then

sum = bit1 ^ bit2 ^ carry;
carry = bit1.carry + bit2.carry + bit1.bit2;

here ^ = bitwise zor
   .  = bitwise and
   + = bitwise or

repeat it for all bits of two integer, initially prev carry will be 0;

On Mon, Sep 7, 2009 at 7:01 AM, ritter  wrote:

>
> how to add two integers without using arithmetic operators?
> can anyone help me.
>
> >
>


-- 
GAURAV GUPTA
B.Tech IV Yr. , Department of Computer Science & Engineering
IT BHU , Varanasi
Contacts
Phone No: +91-99569-49491

e-mail :
gaurav.gu...@acm.org
gaurav.gupta.cs...@itbhu.ac.in

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: n balls having k colors

[gaurav gupta]

Counting Sort is a good solution. This problem is same like :

you have an array 1,3,1,3,2,6,5,7,8,5,6,4,5,2 You have to arrange them such
that all number having same value should occur together and order of
occurrence in series should conserve. So result will be :

1,1 ,3,3,2,2,6,6,5,5,5,7,8 ,4

On Sun, Sep 6, 2009 at 11:39 AM, Dufus  wrote:

>
> How about counting sort in O(N+K) time and O(K) space.
>
> _dufus
>
>
> On Sep 6, 1:06 pm, ankur aggarwal  wrote:
> > You have N balls having one of K colors. Arrange them into groups of same
> > colors. e.g.
> >
> > RRGRG
> > can be arranged as
> > RRRGG (Answer)
> > GGRRR
>
> >
>


-- 
GAURAV GUPTA
B.Tech IV Yr. , Department of Computer Science & Engineering
IT BHU , Varanasi
Contacts
Phone No: +91-99569-49491

e-mail :
gaurav.gu...@acm.org
gaurav.gupta.cs...@itbhu.ac.in

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: addition without using arithmetic operators

[Shobhit Bhatnagar]

I think this can be done by using XOR operations...or can be done by using a
loop and using increment operators (if they are allowed).

On Mon, Sep 7, 2009 at 4:31 PM, ritter  wrote:

>
> how to add two integers without using arithmetic operators?
> can anyone help me.
>
> >
>


-- 
Thanks and Regards
Shobhit Bhatnagar
MCA,Delhi 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
-~--~~~~--~~--~--~---

[algogeeks] Re: Find longest palindrom in a give n string in O(N)

[ankur aggarwal]

nagendra..
plz show the working using an example ..
take input

babbaabbc


On Sun, Sep 6, 2009 at 2:07 PM, Nagendra Kumar wrote:

>
> @all:
>
>   T(i,j) : denotes the length of longest palindrome with start index
> i  and end index  j index.
>  T(i,j )=
>  max {
> 1   ,  if   i == j;
>  2+T(i+1,j-1)  if x[i] == x[j];
>  max(T(i+1,j) T(i,j-1))
>
>  }
>   This is the recurrence relation
>Now algorithm:
>  T(i,i-1) = 0 for 1<= i <= n.
>
>for i=  1   to n
>   T(i)(i)  = 1;
> start with the distnace d
>for d =  1  to n
> for i = 1 to n -d
>{j  = i+d;
> if(x[i] == x[j])
>   T[i][j] = 2+ T[i+1][j-1];
>else
>T[i][j]  = max (T[i+1][j], T[i][j-1])
>
>}
>
>  return T[1][n];
>
> On Tue, Sep 1, 2009 at 12:01 AM, Dufus wrote:
> >
> > This is one of the most difficult dynamic programming problem I have
> > faced so far.
> >
> > A good discussion on this problem and different solutions can be found
> > at
> >
> http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/
> >
> > _dufus
> >
> >
> > On Aug 31, 6:01 pm, ankur aggarwal  wrote:
> >> @abhijeet
> >> dryrun on this
> >>
> >> abbaabba
> >>
> >> On Mon, Aug 31, 2009 at 5:45 PM, Abhijeet Kumar
> >> wrote:
> >>
> >> > u can push the string onto a stack ... so last element will be on top
> ...
> >> > den u can pop out element and compare ...
> >> > if u have 2 or more set of palindromes ..
> >> > u can keep a counter and keep a check on dat...
> >
> > >
> >
>
> >
>

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: find triangle in a graph

[ankur aggarwal]

*"
*
>
> *
> @kunzmilan *
>
* *

> *" What do you mean by polynomial of the graph ? "
> *
>
*
*

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Find longest palindrom in a give n string in O(N)

[Dufus]

@ Ankur,
IMHO suffix tree is ONE of the solution.


_dufus


On Sep 3, 7:37 am, ankur aggarwal  wrote:
> only suffix tree is the soln i think..
>
> On Wed, Sep 2, 2009 at 11:20 AM, nitin mathur
> wrote:
>
>
>
>
>
> > Hi everybody..
>
> > I am sorry as the algorithm I proposed takes O(n^2) and not O(n). But its
> > not wrong.
>
> > @Ankur         The algorithm given in cormen is for longest common
> > subsequence. But a similar algorithm exists for longest common substring
> > too.
>
> > you can find it following the link
> >http://en.wikipedia.org/wiki/Longest_common_substring_problem
>
> > Actually
> > these problems (that uses Dynamic Programming approach) are solved in two
> > stages. First, we need to build a table and then we need to traverse it in
> > particular fashion to retrieve all possible longest common substrings.
>
> > The second stage takes O(n) time.
> > But the preprocessing takes O(n^2) time.
> > So, overall it takes O(n^2) time.
>
> > I believe its worst approach for this problem (as it needs O(n^2) extra
> > spaces too). So not needed to discuss more about this approach. Better some
> > other method should be discovered.
>
> > Nitin Mathur

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] stock market

[ankur aggarwal]

1.Write a function to smooth out stock fluctuations.

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: n balls having k colors

[Dufus]

How about counting sort in O(N+K) time and O(K) space.

_dufus


On Sep 6, 1:06 pm, ankur aggarwal  wrote:
> You have N balls having one of K colors. Arrange them into groups of same
> colors. e.g.
>
> RRGRG
> can be arranged as
> RRRGG (Answer)
> GGRRR

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: find triangle in a graph

[Dufus]

The following approach might work.
Let K be the maximum degree of a vertex in the graph
Enumerate each of the n vertex as 1...n
Enumerate undirected edge between vertex i and j  (i.e. i--j) as
(i,j)

Sort all the |E| edges in O(|V| + |E|) time // radix sort.
Now (i1,i2,i3) form a triangle iff there exist edges
(i1,i2)
(i1,i3)
(i2,i3)

For any vertex i1 we need to check C(k,2) pair of vertices {(i1,i2),
(i1,i3)}
By maintaining a hash table we can check if edge exists between
(i2,i3) in O(1) time.

Hence we can determine 3-clique from sorted list in (V.C(k,2)) time
which is O(|E|) if k=O(n) or O(|V|) if k=O(1)

Hence we can determine all the triangles in O(|V| + |K|) time and O(|
E|) space.

_dufus


On Sep 6, 2:28 pm, ankur aggarwal  wrote:
>  google question : find triangle in a graph Given an undirected graph,
> design a O(V+E) algo to detect whether there is a triangle in the graph ot
> not.

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] phone numbers.

[ankur aggarwal]

3.You have 50,000 html files, some of which contain phone numbers. How would
you create a list of all the files which contain phone numbers?

Solutions should be optimal

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] addition without using arithmetic operators

[ritter]

how to add two integers without using arithmetic operators?
can anyone help me.

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Z[n^2]={such that z belongs to X+Y

[Dufus]

If Z[] is allowed to modify then i think we can do in O(1) space  //
quite clear from the link I have posted above
else we need O(k) space to restore Z[].

_dufus

On Sep 6, 2:32 pm, ankur aggarwal  wrote:
> @dufus
> wat is your complexity ??
>
> On Sat, Sep 5, 2009 at 8:17 PM, Dufus  wrote:
>
> > In that case I would sacrifice a little bit on time complexity and
> > instead of storing I would recompute the values.
>
> > _dufus
>
> > On Sep 5, 5:10 pm, ankur aggarwal  wrote:
> > > @dufus..
> > > if there is constant space requirement then ??
> > > wat will be your soln ??
>
> > > On Sat, Sep 5, 2009 at 12:35 PM, Dufus 
> > wrote:
>
> > > > It seems EXTRACT_MIN for Z[n^2] can be done in O(n) time.
> > > >http://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pdf
> > 
>
> > > > Then using it we can find the kth smallest element in O(nk) time.
>
> > > > _dufus
>
> > > > On Sep 4, 10:03 pm, ankur aggarwal  wrote:
> > > > >  Find nth smallest inO(n) Given two arrays of length n in sorted
> > order
> > > > > X[n] & Y[n].
> > > > > Now make another array Z[n^2]={such that z belongs to X+Y}.
> > > > > AS all possible sum of x+y is there in Z. You have to give the nth
> > > > smallest
> > > > > no of Z in O(n) time.
> > > > > Space complexity : No bound on it. But try to optimize it if
> > possible.

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---