Re: [algogeeks] Re: Google Q : all anagrams next to each other

[shashi kant]

A solution given below taken from cracking the Coding interview  book...

Solution is create a Comparator and a small change in compare method is
that u sort the characters of that string and then compare.

and just sort the arrays, using this compareTo method instead of the usual
one.
Arrays.sort(array, new AnagramComparator());



public class AnagramComparator implements ComparatorString {
public String sortChars(String s) {
char[] content = s.toCharArray();
Arrays.sort(content);
return new String(content);
}
public int compare(String s1, String s2) {
return sortChars(s1).compareTo(sortChars(s2));
}
}






*Shashi Kant *
***Think positive and find fuel in failure*
http://thinkndoawesome.blogspot.com/
*System/Software Engineer*
*Hewlett-Packard India Software Operations.
*



On Sun, May 27, 2012 at 2:56 AM, Navin Gupta navin.nit...@gmail.com wrote:

 @jalaj :-  we will be sorting a copy of the word and then matching the
 sorted_sequence with the sorted_sequence of the copy of other words.
 It will still be in-place, because we are using a space of Word size where
 the input is a dictionary.
 This is an amortized in-place.

 --
 Navin Kumar Gupta
 Computer Science  Engg.
 National Institute of Technology,Jamshedpur

  --
 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/-/n2tGzVxSLIYJ.

 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


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

Re: [algogeeks] Re: Google Q : all anagrams next to each other

[Navin Gupta]

@jalaj :-  we will be sorting a copy of the word and then matching the 
sorted_sequence with the sorted_sequence of the copy of other words.
It will still be in-place, because we are using a space of Word size where 
the input is a dictionary.
This is an amortized in-place.

-- 
Navin Kumar Gupta
Computer Science  Engg.
National Institute of Technology,Jamshedpur

-- 
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/-/n2tGzVxSLIYJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Google Q : all anagrams next to each other

[Gene]

This will work in fine, but multiplying primes requires arbitrary
precision arithmetic for keys of any significant length.

You don't need to compute a hash at all.  Just maintain two buffers
long enough to hold the longest word and an O(n) sort like counting
sort.  If you are using Latin (8-bit) characters, you don't even need
to complete the counting sort.  Just do the counting into arrays of
256 ints.  You'll end up with character histograms.  It's easy to
compare these rather than sorted strings.  They require O(2 log C) =
O(log C) storage and comparing them needs O(log C) int comparisons,
where C is the number of characters in the alphabet.  Since C is a
constant, this would normally be considered O(1) time and space.

On May 26, 2:52 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
 If you sort every word , then you will lose the original word as Ankita
 pointed out and if you keep a hashmap to track that it will not be inplace
 .,

 Is there any problem in the solution I gave Above , please point it out .









 On Fri, May 25, 2012 at 1:14 AM, Anika Jain anika.jai...@gmail.com wrote:
  I have a doubt. If u r doing inplace sorting of a word during checks for a
  word, wouldnt that change that word there itself? then how will the
  original anagram get restored to arrange in the output in sorted manner?

  On Thu, May 24, 2012 at 5:54 PM, Jitender Kumar 
  jitender...@gmail.comwrote:

  The complexity will be (N^2)W because the sorting can be done linear time
  O(W) for strings.

  On Thu, May 24, 2012 at 3:44 PM, WgpShashank bshashank7andr...@gmail.com
   wrote:

  Yeah , its the in-place approach strikes in mind at first look , just
  slightly clearing the complexity to O(N^2* Wlog(W)) , N is number of
  words in array  W is length of longest word in array , let me know i
  missed something ?

   original                 eat I ate att I the eel eth het
   after sorting          I I ate att can eat eel eth het the

  output should be  I I ate eat att can eel eth het the

  Shashank Mani Narayan
  Computer Science  Engineering
  Birla Institute of Technology,Mesra
  Founder Cracking The Code Lab  http://shashank7s.blogspot.com/;
  FB Pagehttp://www.facebook.com/pages/LestCode
  Google+http://gplus.to/wgpshashank
  Twitter https://twitter.com/wgpshashank;
  Puzzled Guy @ http://ashutosh7s.blogspot.com;
  FB Pagehttp://www.facebook.com/Puzzles.For.Puzzled.Minds

  On May 22, 8:18 am, Navin Gupta navin.nit...@gmail.com wrote:
   It can be done inplace, then Time Complexity will be O( N^2 x W )
  where N
   is no. of words and  W is word size.
   Start from the left and sort the current word.
   Keep a pointer  PTR  to the first index of the element left to process.
   Initially it will be 0.As we add words this pointer moves forwards.
   Now iterate the whole list of words to find all those words having same
   sorted sequence i.e. anagrams
   Whenver we get a word which is anagram of the current string, swap it
  with
   the string  pointed by PTR, move PTR forward.

   pseudoCode :-

   func( vectorstring v)
   {
      int n=v.size();
      for(int i=0;in;i++)
      {
         string currentWord = v[i];
         sort(currentWord);
         for(int j=i+1;jn;j++)
         {
             if ( sort(v[j]) == currentWord )    // anagrams found,
             {
                  swap( v[i] , v[j] );                 //move this string
  to
   the position next to pos of currentWord
                    i++;                                //and move the
  index
   of currentWord forward
             }
        }

   }

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

  --
  With regards,

  Jitender Kumar
  3rd year (Computer Engineering)
  NIT Kurukshetra
  Kurukshetra- 136119
   Mobile  +91-8529035751

   --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from 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
  Anika Jain

   --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from 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,

 Jalaj Jaiswal
 Software Developer,
  Adobe Systems
 +91-9019947895
 *
 *
 FACEBOOK http://www.facebook.com/jalaj.jaiswal89
 

Re: [algogeeks] Re: Google Q : all anagrams next to each other

[Anika Jain]

I have a doubt. If u r doing inplace sorting of a word during checks for a
word, wouldnt that change that word there itself? then how will the
original anagram get restored to arrange in the output in sorted manner?

On Thu, May 24, 2012 at 5:54 PM, Jitender Kumar jitender...@gmail.comwrote:

 The complexity will be (N^2)W because the sorting can be done linear time
 O(W) for strings.


 On Thu, May 24, 2012 at 3:44 PM, WgpShashank 
 shashank7andr...@gmail.comwrote:

 Yeah , its the in-place approach strikes in mind at first look , just
 slightly clearing the complexity to O(N^2* Wlog(W)) , N is number of
 words in array  W is length of longest word in array , let me know i
 missed something ?

  original eat I ate att I the eel eth het
  after sorting  I I ate att can eat eel eth het the

 output should be  I I ate eat att can eel eth het the

 Shashank Mani Narayan
 Computer Science  Engineering
 Birla Institute of Technology,Mesra
 Founder Cracking The Code Lab  http://shashank7s.blogspot.com/;
 FB Page http://www.facebook.com/pages/LestCode
 Google+ http://gplus.to/wgpshashank
 Twitter https://twitter.com/wgpshashank;
 Puzzled Guy @ http://ashutosh7s.blogspot.com;
 FB Page http://www.facebook.com/Puzzles.For.Puzzled.Minds


 On May 22, 8:18 am, Navin Gupta navin.nit...@gmail.com wrote:
  It can be done inplace, then Time Complexity will be O( N^2 x W ) where
 N
  is no. of words and  W is word size.
  Start from the left and sort the current word.
  Keep a pointer  PTR  to the first index of the element left to process.
  Initially it will be 0.As we add words this pointer moves forwards.
  Now iterate the whole list of words to find all those words having same
  sorted sequence i.e. anagrams
  Whenver we get a word which is anagram of the current string, swap it
 with
  the string  pointed by PTR, move PTR forward.
 
  pseudoCode :-
 
  func( vectorstring v)
  {
 int n=v.size();
 for(int i=0;in;i++)
 {
string currentWord = v[i];
sort(currentWord);
for(int j=i+1;jn;j++)
{
if ( sort(v[j]) == currentWord )// anagrams found,
{
 swap( v[i] , v[j] ); //move this string
 to
  the position next to pos of currentWord
   i++;//and move the
 index
  of currentWord forward
}
   }
 
 
 
 
 
 
 
  }

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




 --
 With regards,

 Jitender Kumar
 3rd year (Computer Engineering)
 NIT Kurukshetra
 Kurukshetra- 136119
  Mobile  +91-8529035751

  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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
Anika Jain

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Google Q : all anagrams next to each other

[Navin Gupta]

It can be done inplace, then Time Complexity will be O( N^2 x W ) where N 
is no. of words and  W is word size.
Start from the left and sort the current word.
Keep a pointer  PTR  to the first index of the element left to process. 
Initially it will be 0.As we add words this pointer moves forwards.
Now iterate the whole list of words to find all those words having same 
sorted sequence i.e. anagrams 
Whenver we get a word which is anagram of the current string, swap it with 
the string  pointed by PTR, move PTR forward.

pseudoCode :- 

func( vectorstring v)
{
   int n=v.size();
   for(int i=0;in;i++)
   {
  string currentWord = v[i];
  sort(currentWord);
  for(int j=i+1;jn;j++)
  {
  if ( sort(v[j]) == currentWord )// anagrams found, 
  {
   swap( v[i] , v[j] ); //move this string to 
the position next to pos of currentWord 
 i++;//and move the index 
of currentWord forward
  }
 }
}

-- 
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/-/h04_lKqCILQJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Google Q: longest word made of subwords within the list

[Abhishek]

@prem: can you please explain the approach clearly, I did't get the
approach.

regards
Abhishek

On May 23, 7:43 pm, Doom duman...@gmail.com wrote:
 I am trying to understand the question.. please let me know the answer for
 the following cases..

 case1:
 test
 testlong
 testlongtest
 testlongtestlong
 testtesttest

 case2:
 test
 testlong
 testlongtest

 case3:
 test
 longest

 case4:
 test
 testtes
 ttes
 testtesttes







 On Tuesday, 22 May 2012 18:15:16 UTC+5:30, ashgoel wrote:

  write a program to find the longest word made of other words. For
  instance, If my file has the following words (sorted):
  test
  tester
  testertest
  testing
  testingtester

  The longest word should be testingtester. Trie is the solution, what is
  the best Order possible?
  Best Regards
  Ashish Goel
  Think positive and find fuel in failure
  +919985813081
  +919966006652

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

Re: [algogeeks] Re: GOOGLE Q

[surender sanke]

Hi, here i maintained two pair of indexes with respect to a and b, reply if
u found any test case which fails..

int npairs()
{
 int a[] = {0,1,4,5,9,11,20};
 int b[] = {0,2,3,6,8,11,15};
 int c[20];
 int len = sizeof(a)/sizeof(a[0]);
 int i1,j1,i2,j2;
 i1=len-1;
 j1=len-2;
 i2=len-2;
 j2=len-1;

 int count = 0;
c[count++] = a[len-1]+b[len-1]; //obvious
 while(count=len)
 {
  if( (a[i1-1]+a[j2-1]  a[i1]+b[j1])   (a[i1-1]+a[j2-1]  a[i1]+b[j1]) )
  {
   c[count++] = a[i1-1]+b[j2-1];  //highest  sum with higher numbers
have exhausted
   i1 = i1-1,j2=j2-1,j1=j2-1,i2=i1-1;
   continue;
  }
  if(a[i1]+b[j1] = a[i2]+b[j2] )
  {
   c[count++] = a[i1]+b[j1];
   j1--;
  }
  else
  {
   c[count++] = a[i2]+b[j2];
   i2--;
  }
 }

 for(int i =0;ilen;i++)
  printf(%d ,c[i]);
 return 0;
}

surender
On Mon, Jul 11, 2011 at 10:46 AM, sunny agrawal sunny816.i...@gmail.comwrote:

 A = 0, 1, 4, 5, 9, 11, 20
 B = 0, 2, 3, 6, 8, 13, 15

 (20, 15)  (20, 15) - (20,15)
 (20,13)   (11,15)  - (20,13)
 (20,8) (11,15)  - (20,8)
 (20,6) (11,15)  - assume (20,6)
 (20,3) (11,15)  - (11,15)
 (20,3) (9,15)- (9,15)
 (20,3) (5,15)- (20,3)  .problem (11,13) has higher value but

 did i missed something ??


 --
 Sunny Aggrawal
 B-Tech IV year,CSI
 Indian Institute Of Technology,Roorkee

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


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

Re: [algogeeks] Re: GOOGLE Q

[shambo]

Find the largest ceil(sqrt(n)) elements of A and B using a sliding window in
time O(n) and then take their cross in time sqrt(n)^2 ie O(n).

--Shambo

On Mon, Jul 11, 2011 at 12:37 PM, surender sanke surend...@gmail.comwrote:

 Hi, here i maintained two pair of indexes with respect to a and b, reply if
 u found any test case which fails..

 int npairs()
 {
  int a[] = {0,1,4,5,9,11,20};
  int b[] = {0,2,3,6,8,11,15};
  int c[20];
  int len = sizeof(a)/sizeof(a[0]);
  int i1,j1,i2,j2;
  i1=len-1;
  j1=len-2;
  i2=len-2;
  j2=len-1;

  int count = 0;
 c[count++] = a[len-1]+b[len-1]; //obvious
  while(count=len)
  {
   if( (a[i1-1]+a[j2-1]  a[i1]+b[j1])   (a[i1-1]+a[j2-1]  a[i1]+b[j1]) )
   {
c[count++] = a[i1-1]+b[j2-1];  //highest  sum with higher numbers
 have exhausted
i1 = i1-1,j2=j2-1,j1=j2-1,i2=i1-1;
continue;
   }
   if(a[i1]+b[j1] = a[i2]+b[j2] )
   {
c[count++] = a[i1]+b[j1];
j1--;
   }
   else
   {
c[count++] = a[i2]+b[j2];
i2--;
   }
  }

  for(int i =0;ilen;i++)
   printf(%d ,c[i]);
  return 0;
 }

 surender
 On Mon, Jul 11, 2011 at 10:46 AM, sunny agrawal 
 sunny816.i...@gmail.comwrote:

 A = 0, 1, 4, 5, 9, 11, 20
 B = 0, 2, 3, 6, 8, 13, 15

 (20, 15)  (20, 15) - (20,15)
 (20,13)   (11,15)  - (20,13)
 (20,8) (11,15)  - (20,8)
 (20,6) (11,15)  - assume (20,6)
 (20,3) (11,15)  - (11,15)
 (20,3) (9,15)- (9,15)
 (20,3) (5,15)- (20,3)  .problem (11,13) has higher value but

 did i missed something ??


 --
 Sunny Aggrawal
 B-Tech IV year,CSI
 Indian Institute Of Technology,Roorkee

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


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


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

Re: [algogeeks] Re: GOOGLE Q

[DK]

@Shambo: That doesn't work.
Consider:
A = 1 10 100 1000
B = 1 2 3 4

The top 4 pairs are: (1000,4), (1000,3), (1000,2) and (1000,1)

--
DK

http://twitter.com/divyekapoor
http://www.divye.in

-- 
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/-/WyVibLRFx9kJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: GOOGLE Q

[DK]

@Sunny: Thanks for this counterexample. The O(N) algorithm currently seems 
unfeasible to me. 
@Piyush: Are you sure an O(N) algo exists?

Here's an O(N log N) algo (without the N^2 memory requirements of Sunny's 
algo as it doesn't generate duplicates)

For arrays
A = a1 a2 ... an
B = b1 b2  bn

Maintain a max priority_queue ordered by Val(a,b). (Use a BST for this).
Insert (an, bn).

Repeat N Times {
   Pop off and output the max value from the priority queue. Let that be 
(ai, bj) // O(log N)
   if(i == j) {
  Insert (ai-1, bj), (ai, bj-1), (ai-1, bj-1) in the priority queue. // 
O(log n)
   } else if(i  j) {
  Insert (ai-1, bj) in the priority queue. // O(log n)
   } else {
  Insert (ai, bj-1) in the priority queue. // O(log n)
   }
}

Time complexity: O(N log N)
Space complexity: O(N) ??

--
DK

http://twitter.com/divyekapoor
http://www.divye.in

-- 
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/-/XCjyFaTFD-UJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: GOOGLE Q

[Piyush Sinha]

@Dk..i dint frame the question buddy...:P

I found it over here
http://geeksforgeeks.org/forum/topic/google-interview-question-for-software-engineerdeveloper-about-algorithms-75

On Mon, Jul 11, 2011 at 3:14 PM, DK divyekap...@gmail.com wrote:

 @Sunny: Thanks for this counterexample. The O(N) algorithm currently seems
 unfeasible to me.
 @Piyush: Are you sure an O(N) algo exists?

 Here's an O(N log N) algo (without the N^2 memory requirements of Sunny's
 algo as it doesn't generate duplicates)

 For arrays
 A = a1 a2 ... an
 B = b1 b2  bn

 Maintain a max priority_queue ordered by Val(a,b). (Use a BST for this).
 Insert (an, bn).

 Repeat N Times {
Pop off and output the max value from the priority queue. Let that be
 (ai, bj) // O(log N)
if(i == j) {
   Insert (ai-1, bj), (ai, bj-1), (ai-1, bj-1) in the priority queue. //
 O(log n)
} else if(i  j) {
   Insert (ai-1, bj) in the priority queue. // O(log n)
} else {
   Insert (ai, bj-1) in the priority queue. // O(log n)
}
 }

 Time complexity: O(N log N)
 Space complexity: O(N) ??

 --
 DK

 http://twitter.com/divyekapoor
 http://www.divye.in

  --
 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/-/XCjyFaTFD-UJ.

 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926 *

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

Re: [algogeeks] Re: GOOGLE Q

[surender sanke]

small mistake change a to b
if( (a[i1-1]+b[j2-1]  a[i1]+b[j1])   (a[i1-1]+a[j2-1]  a[i1]+b[j1]) )

surender
On Mon, Jul 11, 2011 at 3:54 PM, DK divyekap...@gmail.com wrote:

 @surender: Your algo fails. See the counterexample posted by Sunny.

 --
 DK

 http://twitter.com/divyekapoor
 http://www.divye.in

  --
 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/-/ITTX48LIzcUJ.

 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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.

[algogeeks] Re: GOOGLE Q

[Dumanshu]

how about this?
take pointer p1 set to end of array A and pointer p2 set to end of
array B.

while(you get n values)
{
print A(p1),B(p2)
now if(  A(p1-1)+B(p2)A(p1)+B(p2-1)  ) then print A(p1-1),B(p2)
followed by print A(p1),B(p2-1)
decrement p2 and p1 both
}

m i missing something?
On Jul 9, 4:24 am, Piyush Sinha ecstasy.piy...@gmail.com wrote:
 Given two sorted positive integer arrays A(n) and B(n). We define a
 set S = {(a,b) | a in
 A and b in B}. Obviously there are n^2 elements in S. The value of such
 a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs
 from S with largest values. The tricky part is that we need an O(n)
 algorithm.

 --
 *Piyush Sinha*
 *IIIT, Allahabad*
 *+91-8792136657*
 *+91-7483122727*
 *https://www.facebook.com/profile.php?id=10655377926*

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: GOOGLE Q

[DK]

Largest value is of course A(n) + B(n).
Second largest value is either A(n) + B(n-1) or A(n-1) + B(n).

Select the largest among both and continue down that array. 
Maintain 2 pairs:
Pair 1: Hold first value constant, go down the second array. Pair 2: Hold 
2nd value const. and go down the first array.
Whenever one element of a pair cannot find a partner, that implies that all 
pairs containing that element have been considered. 
Discard that partner-less element and continue down the array. Take special 
care that duplicate elements are not output. See the output below so that 
things are clearer. (The duplicates case arises when the pair chosen in both 
cases is the same).

eg.

1 7 9
2 3 4


Pair 1: (9,4) Pair 2: (9,4) - Output (9,4) = 13
Pair 1: (9, 3) Pair 2: (7,4) - Output (9,3) = 12
Pair 1: (9, 2) Pair 2: (7,4) - Output (7,4) or (9,2) -- assume (9,2) was 
output = 11
Pair 1: (7,4) Pair 2: (7,4) - Ouput (7,4) = 11
Pair 1: (7,3) Pair 2: (1, 4) - Output (7, 3) = 10
Pair 1: (7,2) Pair 2: (1,4) - Output (7,2) = 9
Pair 1: (1,4) Pair 2: (1,4) - Output (1,4) = 5
Pair 1: (1,3) Pair 2: (1,3) - Output (1,3) = 4
Pair 1: (1,2) Pair 2: (1,2) - Output (1,2) = 3
Pair 1: (empty) Pair 2: (empty) - End

O(N) algorithm. Descending order printing of pairs.

@Sunny: Your time complexity is O(N^2) as creating that array will take 
O(N^2) time.
@Dumanshu: Your algorithm misses cases. Eg. (9,4) will be printed but (9,3) 
will not.

--
DK

http://twitter.com/divyekapoor
http://www.divye.in

-- 
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/-/uJEiQKMYJnMJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: GOOGLE Q

[sunny agrawal]

@DK sir
I was just assuming n^2 values as the 2D matrix..not creating

although i am using a O(n^2) space that keep track of which cell is already
in heap and need not be inserted againso initially all the need to
be initialized..that will make it O(n^2)

Now I have a Doubt - Is there any way i can initialize this space so that
overall complexity is O(nlgn)
like making this space static or global (so all memory will be initialized
to zero) or using memset
is that still O(n^2) ??

On Mon, Jul 11, 2011 at 12:34 AM, DK divyekap...@gmail.com wrote:

 Largest value is of course A(n) + B(n).
 Second largest value is either A(n) + B(n-1) or A(n-1) + B(n).

 Select the largest among both and continue down that array.
 Maintain 2 pairs:
 Pair 1: Hold first value constant, go down the second array. Pair 2: Hold
 2nd value const. and go down the first array.
 Whenever one element of a pair cannot find a partner, that implies that all
 pairs containing that element have been considered.
 Discard that partner-less element and continue down the array. Take special
 care that duplicate elements are not output. See the output below so that
 things are clearer. (The duplicates case arises when the pair chosen in both
 cases is the same).

 eg.

 1 7 9
 2 3 4


 Pair 1: (9,4) Pair 2: (9,4) - Output (9,4) = 13
 Pair 1: (9, 3) Pair 2: (7,4) - Output (9,3) = 12
 Pair 1: (9, 2) Pair 2: (7,4) - Output (7,4) or (9,2) -- assume (9,2) was
 output = 11
 Pair 1: (7,4) Pair 2: (7,4) - Ouput (7,4) = 11
 Pair 1: (7,3) Pair 2: (1, 4) - Output (7, 3) = 10
 Pair 1: (7,2) Pair 2: (1,4) - Output (7,2) = 9
 Pair 1: (1,4) Pair 2: (1,4) - Output (1,4) = 5
 Pair 1: (1,3) Pair 2: (1,3) - Output (1,3) = 4
 Pair 1: (1,2) Pair 2: (1,2) - Output (1,2) = 3
 Pair 1: (empty) Pair 2: (empty) - End

 O(N) algorithm. Descending order printing of pairs.

 @Sunny: Your time complexity is O(N^2) as creating that array will take
 O(N^2) time.
 @Dumanshu: Your algorithm misses cases. Eg. (9,4) will be printed but (9,3)
 will not.

 --
 DK

 http://twitter.com/divyekapoor
 http://www.divye.in

  --
 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/-/uJEiQKMYJnMJ.

 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee

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

Re: [algogeeks] Re: GOOGLE Q

[DK]

Well, technically, if you have to initialize O(N^2) space with *any* 
value, then your algo is O(N^2).
In practice, memset is pretty fast, however, that just reduces the constant 
factor - it will not (eventually) beat an O(N) algo.
BTW, my solution is O(N).

--
DK

http://twitter.com/divyekapoor
http://www.divye.in

-- 
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/-/XnCZNAePQokJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: GOOGLE Q

[sunny agrawal]

A = 0 1 4 5 9 11 20
B = 0 2 3 6 8 13 15

(20, 15)  (20, 15) - (20,15)
(20,13)   (11,15)  - (20,13)
(20,8) (11,15)  - (20,8)
(20,6) (11,15)  - assume (20,6)
(20,3) (11,15)  - (11,15)
(20,3) (9,15)-

On Mon, Jul 11, 2011 at 1:06 AM, sunny agrawal sunny816.i...@gmail.comwrote:

 @DK sir
 I was just assuming n^2 values as the 2D matrix..not creating

 although i am using a O(n^2) space that keep track of which cell is already
 in heap and need not be inserted againso initially all the need to
 be initialized..that will make it O(n^2)

 Now I have a Doubt - Is there any way i can initialize this space so that
 overall complexity is O(nlgn)
 like making this space static or global (so all memory will be initialized
 to zero) or using memset
 is that still O(n^2) ??

 On Mon, Jul 11, 2011 at 12:34 AM, DK divyekap...@gmail.com wrote:

 Largest value is of course A(n) + B(n).
 Second largest value is either A(n) + B(n-1) or A(n-1) + B(n).

 Select the largest among both and continue down that array.
 Maintain 2 pairs:
 Pair 1: Hold first value constant, go down the second array. Pair 2: Hold
 2nd value const. and go down the first array.
 Whenever one element of a pair cannot find a partner, that implies that
 all pairs containing that element have been considered.
 Discard that partner-less element and continue down the array. Take
 special care that duplicate elements are not output. See the output below so
 that things are clearer. (The duplicates case arises when the pair chosen in
 both cases is the same).

 eg.

 1 7 9
 2 3 4


 Pair 1: (9,4) Pair 2: (9,4) - Output (9,4) = 13
 Pair 1: (9, 3) Pair 2: (7,4) - Output (9,3) = 12
 Pair 1: (9, 2) Pair 2: (7,4) - Output (7,4) or (9,2) -- assume (9,2) was
 output = 11
 Pair 1: (7,4) Pair 2: (7,4) - Ouput (7,4) = 11
 Pair 1: (7,3) Pair 2: (1, 4) - Output (7, 3) = 10
 Pair 1: (7,2) Pair 2: (1,4) - Output (7,2) = 9
 Pair 1: (1,4) Pair 2: (1,4) - Output (1,4) = 5
 Pair 1: (1,3) Pair 2: (1,3) - Output (1,3) = 4
 Pair 1: (1,2) Pair 2: (1,2) - Output (1,2) = 3
 Pair 1: (empty) Pair 2: (empty) - End

 O(N) algorithm. Descending order printing of pairs.

 @Sunny: Your time complexity is O(N^2) as creating that array will take
 O(N^2) time.
 @Dumanshu: Your algorithm misses cases. Eg. (9,4) will be printed but
 (9,3) will not.

 --
 DK

 http://twitter.com/divyekapoor
 http://www.divye.in

  --
 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/-/uJEiQKMYJnMJ.

 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




 --
 Sunny Aggrawal
 B-Tech IV year,CSI
 Indian Institute Of Technology,Roorkee




-- 
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee

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

Re: [algogeeks] Re: GOOGLE Q

[sunny agrawal]

A = 0, 1, 4, 5, 9, 11, 20
B = 0, 2, 3, 6, 8, 13, 15

(20, 15)  (20, 15) - (20,15)
(20,13)   (11,15)  - (20,13)
(20,8) (11,15)  - (20,8)
(20,6) (11,15)  - assume (20,6)
(20,3) (11,15)  - (11,15)
(20,3) (9,15)- (9,15)
(20,3) (5,15)- (20,3)  .problem (11,13) has higher value but

did i missed something ??

-- 
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: GOOGLE Q

[bittu]

Study Trie  Then Apply It..It Will Work
PS: We already have dictionary congaing all the possible words if its
not given then we can make the dictionary  then we can find out the
all possible anagram of word in constant time O(K) where K is length
of each anagram of word W.


Hope i m correct


Thanks
Shashank  The Best Way to Escape From The Problem is to Solve It
CSE,BIT Mesra

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

Re: [algogeeks] Re: Google Q

[saurabh agrawal]

Thanks Dave.

On Wed, May 18, 2011 at 8:01 PM, Dave dave_and_da...@juno.com wrote:

 @Saurabh: You look at the top elements in the two heaps. If the new
 number is between the values of the top of the heaps, you add it to
 the shorter of the two heaps, or to either heap if they are of equal
 length. If the new number is larger than the min of the min-heap, you
 add it to the min-heap. If it is smaller than the max of the max-heap,
 you add it to the max heap. If the resulting two heaps differ in
 length by more than one element, you move the top element from the
 longer heap into the shorter heap. Since the heaps start off empty and
 you add only one number at a time, the result of a step of the
 algorithm is that the two heaps will differ in size by at most one
 element. Thus, the smaller half of the numbers will be in the max-heap
 and the larger half will be in the min-heap.

 Dave

 On May 18, 8:29 am, saurabh agrawal saurabh...@gmail.com wrote:
  Dave,
  u said: a max-heap of the smallest
  half of the elements
  but if the number are randomply generated, then how will you get to know
  whether a number belongs to smallest half OR lager half..
  i didnt got it...
 
 
 
  On Sat, May 14, 2011 at 9:10 PM, Dave dave_and_da...@juno.com wrote:
   @Ashish: The idea is to keep two heaps, a max-heap of the smallest
   half of the elements and a min-heap of the largest elements. You
   insert incoming elements into the appropriate heap. If the result is
   that the number of elements in the two heaps differs by more than 1,
   then you move the top element from the longer heap into the other one,
   thereby equalzing the number of elements. Thus, inserting an element
   is an O(log n) operation. To get the median, it is the top element of
   the longer heap, or, if the heaps are of equal length, it is the
   average of the two top elements. This is O(1).
 
   Dave
 
   On May 14, 8:34 am, Ashish Goel ashg...@gmail.com wrote:
not clear, can u elaborate..
 
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
 
On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal 
 agr.bhav...@gmail.com
   wrote:
 
 This problem can be solved using 2 heaps and the median can always
 be
 accessed in O(1) time ,the first node.
 
 --
 You received this message because you are subscribed to the Google
   Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.-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.- 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.



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

Re: [algogeeks] Re: Google Q

[Anand]

@ Dave. Nice explanation

On Fri, May 20, 2011 at 6:06 AM, saurabh agrawal saurabh...@gmail.comwrote:

 Thanks Dave.

 On Wed, May 18, 2011 at 8:01 PM, Dave dave_and_da...@juno.com wrote:

 @Saurabh: You look at the top elements in the two heaps. If the new
 number is between the values of the top of the heaps, you add it to
 the shorter of the two heaps, or to either heap if they are of equal
 length. If the new number is larger than the min of the min-heap, you
 add it to the min-heap. If it is smaller than the max of the max-heap,
 you add it to the max heap. If the resulting two heaps differ in
 length by more than one element, you move the top element from the
 longer heap into the shorter heap. Since the heaps start off empty and
 you add only one number at a time, the result of a step of the
 algorithm is that the two heaps will differ in size by at most one
 element. Thus, the smaller half of the numbers will be in the max-heap
 and the larger half will be in the min-heap.

 Dave

 On May 18, 8:29 am, saurabh agrawal saurabh...@gmail.com wrote:
  Dave,
  u said: a max-heap of the smallest
  half of the elements
  but if the number are randomply generated, then how will you get to know
  whether a number belongs to smallest half OR lager half..
  i didnt got it...
 
 
 
  On Sat, May 14, 2011 at 9:10 PM, Dave dave_and_da...@juno.com wrote:
   @Ashish: The idea is to keep two heaps, a max-heap of the smallest
   half of the elements and a min-heap of the largest elements. You
   insert incoming elements into the appropriate heap. If the result is
   that the number of elements in the two heaps differs by more than 1,
   then you move the top element from the longer heap into the other one,
   thereby equalzing the number of elements. Thus, inserting an element
   is an O(log n) operation. To get the median, it is the top element of
   the longer heap, or, if the heaps are of equal length, it is the
   average of the two top elements. This is O(1).
 
   Dave
 
   On May 14, 8:34 am, Ashish Goel ashg...@gmail.com wrote:
not clear, can u elaborate..
 
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
 
On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal 
 agr.bhav...@gmail.com
   wrote:
 
 This problem can be solved using 2 heaps and the median can always
 be
 accessed in O(1) time ,the first node.
 
 --
 You received this message because you are subscribed to the Google
   Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.-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.- 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.


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


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

Re: [algogeeks] Re: GOOGLE Q

[immanuel kingston]

Preprocess the Dictionary into a hash table where the key is the sorted
string of each word and the value being the A list that contains that
particular word.(O(nlogn * linked list insertion time some k)  )

Now for each given word, sort it(O(nlogn)) and find get the list of words
that are anagrams to the given word by looking up the HashTable(O(1)).

Thanks,
Immanuel

On Thu, May 19, 2011 at 11:11 PM, pacific :-) pacific4...@gmail.com wrote:

 If we were given two strings and asked to check if they have the same
 characters (anagrams) :

 @ gene : you are sorting them both ,and trying to match.
 cost : sort the first string + sort the second string + compare i.e k * k +
 k * k + k .. k is the length of the string.
 I presume that bubble sort is nearly optimal for smaller strings if u
 consider the overall performance ( its O(n^2) but smaller constants than the
 O(nlogn) with larger constants in say quicksort.

 Rather i would suggest , take each character and check that in the other
 string. O( k * k) ..in the average case you might do even less than nearly
 O(k * k/ 2) if the two strings are not same.

 On Wed, May 18, 2011 at 10:31 AM, anuj agarwal coolbuddy...@gmail.comwrote:

 Same method as Gene told.
 Only enhancement u can made is start from the word nearer to sorted string
 and compare till the nearest word of the reverse of sorted string.
 You don't need to check the whole dictionary.

 Anuj Agarwal

 Engineering is the art of making what you want from things you can get.



 On Wed, May 18, 2011 at 6:01 AM, Gene gene.ress...@gmail.com wrote:

 Sort the characters in the string. Go through the dictionary sorting the
 characters in each word in turn.  Print the words whose sorted versions
 match the sorted string.

 You can quickly print all equivalence classes of anagrams in the
 dictionary by hashing with the sorted strings as keys. It only takes a few
 seconds to get them all this way with a 2-line perl or ruby script.

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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,
 chinna.

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


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

Re: [algogeeks] Re: Google Q

[MK]

On Sat, May 14, 2011 at 12:55 PM, pacific :-) pacific4...@gmail.com wrote:
 Will not a balanced binary tree do the job ? if we will pick the root each
 time for the median.


You cannot do it with a vanilla balanced binary tree.

But you can, if you use an augmented tree in the following sense - In
each node of the tree, store the number of nodes in the subtree rooted
at that node.
So , for eg,
- the root node will store N where N is the total number of nodes in the tree,
- number stored in left child of root + number stored in right child
of root = N - 1

Then, to find the element appearing at the N/2th position in an
inorder walk (i.e. the median) is given by Find(root, N/2) where Find
is defined like so -

Node* Find(Node* ptr, int position)
{
int ptrpos = ptr-left-numchildren + 1;
if(ptrpos == position) return ptr;
else if(ptrpos position) return Find(ptr-left, position);
else return Find(ptr-right, position - ptrpos);
}



 On Sat, May 14, 2011 at 9:10 PM, Dave dave_and_da...@juno.com wrote:

 @Ashish: The idea is to keep two heaps, a max-heap of the smallest
 half of the elements and a min-heap of the largest elements. You
 insert incoming elements into the appropriate heap. If the result is
 that the number of elements in the two heaps differs by more than 1,
 then you move the top element from the longer heap into the other one,
 thereby equalzing the number of elements. Thus, inserting an element
 is an O(log n) operation. To get the median, it is the top element of
 the longer heap, or, if the heaps are of equal length, it is the
 average of the two top elements. This is O(1).

 Dave

 On May 14, 8:34 am, Ashish Goel ashg...@gmail.com wrote:
  not clear, can u elaborate..
 
  Best Regards
  Ashish Goel
  Think positive and find fuel in failure
  +919985813081
  +919966006652
 
  On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal
  agr.bhav...@gmail.comwrote:
 
 
 
   This problem can be solved using 2 heaps and the median can always be
   accessed in O(1) time ,the first node.
 
   --
   You received this message because you are subscribed to the Google
   Groups
   Algorithm Geeks group.
   To post to this group, send email to algogeeks@googlegroups.com.
   To unsubscribe from this group, send email to
   algogeeks+unsubscr...@googlegroups.com.
   For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.- 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.




 --
 regards,
 chinna.

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


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

Re: [algogeeks] Re: GOOGLE Q

[pacific :-)]

If we were given two strings and asked to check if they have the same
characters (anagrams) :

@ gene : you are sorting them both ,and trying to match.
cost : sort the first string + sort the second string + compare i.e k * k +
k * k + k .. k is the length of the string.
I presume that bubble sort is nearly optimal for smaller strings if u
consider the overall performance ( its O(n^2) but smaller constants than the
O(nlogn) with larger constants in say quicksort.

Rather i would suggest , take each character and check that in the other
string. O( k * k) ..in the average case you might do even less than nearly
O(k * k/ 2) if the two strings are not same.

On Wed, May 18, 2011 at 10:31 AM, anuj agarwal coolbuddy...@gmail.comwrote:

 Same method as Gene told.
 Only enhancement u can made is start from the word nearer to sorted string
 and compare till the nearest word of the reverse of sorted string.
 You don't need to check the whole dictionary.

 Anuj Agarwal

 Engineering is the art of making what you want from things you can get.



 On Wed, May 18, 2011 at 6:01 AM, Gene gene.ress...@gmail.com wrote:

 Sort the characters in the string. Go through the dictionary sorting the
 characters in each word in turn.  Print the words whose sorted versions
 match the sorted string.

 You can quickly print all equivalence classes of anagrams in the
 dictionary by hashing with the sorted strings as keys. It only takes a few
 seconds to get them all this way with a 2-line perl or ruby script.

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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,
chinna.

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

Re: [algogeeks] Re: Google Q

[saurabh agrawal]

Dave,
u said: a max-heap of the smallest
half of the elements
but if the number are randomply generated, then how will you get to know
whether a number belongs to smallest half OR lager half..
i didnt got it...





On Sat, May 14, 2011 at 9:10 PM, Dave dave_and_da...@juno.com wrote:

 @Ashish: The idea is to keep two heaps, a max-heap of the smallest
 half of the elements and a min-heap of the largest elements. You
 insert incoming elements into the appropriate heap. If the result is
 that the number of elements in the two heaps differs by more than 1,
 then you move the top element from the longer heap into the other one,
 thereby equalzing the number of elements. Thus, inserting an element
 is an O(log n) operation. To get the median, it is the top element of
 the longer heap, or, if the heaps are of equal length, it is the
 average of the two top elements. This is O(1).

 Dave

 On May 14, 8:34 am, Ashish Goel ashg...@gmail.com wrote:
  not clear, can u elaborate..
 
  Best Regards
  Ashish Goel
  Think positive and find fuel in failure
  +919985813081
  +919966006652
 
  On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal agr.bhav...@gmail.com
 wrote:
 
 
 
   This problem can be solved using 2 heaps and the median can always be
   accessed in O(1) time ,the first node.
 
   --
   You received this message because you are subscribed to the Google
 Groups
   Algorithm Geeks group.
   To post to this group, send email to algogeeks@googlegroups.com.
   To unsubscribe from this group, send email to
   algogeeks+unsubscr...@googlegroups.com.
   For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.- 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.



-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Google Q

[Dave]

@Saurabh: You look at the top elements in the two heaps. If the new
number is between the values of the top of the heaps, you add it to
the shorter of the two heaps, or to either heap if they are of equal
length. If the new number is larger than the min of the min-heap, you
add it to the min-heap. If it is smaller than the max of the max-heap,
you add it to the max heap. If the resulting two heaps differ in
length by more than one element, you move the top element from the
longer heap into the shorter heap. Since the heaps start off empty and
you add only one number at a time, the result of a step of the
algorithm is that the two heaps will differ in size by at most one
element. Thus, the smaller half of the numbers will be in the max-heap
and the larger half will be in the min-heap.

Dave

On May 18, 8:29 am, saurabh agrawal saurabh...@gmail.com wrote:
 Dave,
 u said: a max-heap of the smallest
 half of the elements
 but if the number are randomply generated, then how will you get to know
 whether a number belongs to smallest half OR lager half..
 i didnt got it...



 On Sat, May 14, 2011 at 9:10 PM, Dave dave_and_da...@juno.com wrote:
  @Ashish: The idea is to keep two heaps, a max-heap of the smallest
  half of the elements and a min-heap of the largest elements. You
  insert incoming elements into the appropriate heap. If the result is
  that the number of elements in the two heaps differs by more than 1,
  then you move the top element from the longer heap into the other one,
  thereby equalzing the number of elements. Thus, inserting an element
  is an O(log n) operation. To get the median, it is the top element of
  the longer heap, or, if the heaps are of equal length, it is the
  average of the two top elements. This is O(1).

  Dave

  On May 14, 8:34 am, Ashish Goel ashg...@gmail.com wrote:
   not clear, can u elaborate..

   Best Regards
   Ashish Goel
   Think positive and find fuel in failure
   +919985813081
   +919966006652

   On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal agr.bhav...@gmail.com
  wrote:

This problem can be solved using 2 heaps and the median can always be
accessed in O(1) time ,the first node.

--
You received this message because you are subscribed to the Google
  Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
   http://groups.google.com/group/algogeeks?hl=en.-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.- 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.

[algogeeks] Re: GOOGLE Q

[Gene]

Sort the characters in the string. Go through the dictionary sorting the 
characters in each word in turn.  Print the words whose sorted versions 
match the sorted string.

You can quickly print all equivalence classes of anagrams in the dictionary 
by hashing with the sorted strings as keys. It only takes a few seconds to 
get them all this way with a 2-line perl or ruby script.

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

Re: [algogeeks] Re: GOOGLE Q

[anuj agarwal]

Same method as Gene told.
Only enhancement u can made is start from the word nearer to sorted string
and compare till the nearest word of the reverse of sorted string.
You don't need to check the whole dictionary.

Anuj Agarwal

Engineering is the art of making what you want from things you can get.


On Wed, May 18, 2011 at 6:01 AM, Gene gene.ress...@gmail.com wrote:

 Sort the characters in the string. Go through the dictionary sorting the
 characters in each word in turn.  Print the words whose sorted versions
 match the sorted string.

 You can quickly print all equivalence classes of anagrams in the dictionary
 by hashing with the sorted strings as keys. It only takes a few seconds to
 get them all this way with a 2-line perl or ruby script.

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


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

Re: [algogeeks] Re: Google Q

[Anand]

Your sliding window should not be small enough to get the median. For a free
running stream, your window should be of size not less than 100.

On Sun, May 15, 2011 at 7:35 PM, Akshata Sharma
akshatasharm...@gmail.comwrote:

 @Anand:
 if the stream is let 1,2,3,4,6,7,9

 and let we choose k=3

 then your algo is giving 7 as the median.

 On Mon, May 16, 2011 at 4:39 AM, Anand anandut2...@gmail.com wrote:

 Complexity will be O(logK) to insert, delete and finding the predecessor
 or successor of current median value in the BST.


 On Sun, May 15, 2011 at 4:08 PM, Anand anandut2...@gmail.com wrote:

 1. Create a BST for first K elements of the running stream.
 2. Find the median of first K elements.
 3. With every new element from the stream, Insert the new element in
 Binary search Tree.
 4. Delete the first element from BST.
 5. if the new element is greater than the current median value, find the
 successor of current median value.
 6. else if the new elment is less than the current median value, find the
 predecessor of the currend median value in BST.



 On Sun, May 15, 2011 at 2:51 AM, pacific :-) pacific4...@gmail.comwrote:

 perfect.

 Thanks for the effort in explanation.


 On Sun, May 15, 2011 at 12:20 AM, Dave dave_and_da...@juno.com wrote:

 @Pacific: A balanced binary tree is commonly defined as a binary tree
 in which the height of the two subtrees of every node never differ by
 more than 1. Thus, there could be more nodes in one subtree than in
 the other. E.g., a balanced binary tree with 11 nodes could have 7
 nodes in the left subtree and only 3 nodes in the right subtree. Thus,
 the root would not be the median.

 An additional condition is needed: the number of nodes in the left
 subtree differs by at most one from the number of nodes in the right
 subtree.

 In fact, given that the heap structure is a balanced binary tree
 structure with implicit pointers to the left and right subtrees, the
 two-heap algorithm I described results in a balanced binary tree
 satisfying this additional condition, with an implicit root node equal
 to the median.

 Dave

 On May 14, 11:55 am, pacific :-) pacific4...@gmail.com wrote:
  Will not a balanced binary tree do the job ? if we will pick the root
 each
  time for the median.
 
 
 
 
 
  On Sat, May 14, 2011 at 9:10 PM, Dave dave_and_da...@juno.com
 wrote:
   @Ashish: The idea is to keep two heaps, a max-heap of the smallest
   half of the elements and a min-heap of the largest elements. You
   insert incoming elements into the appropriate heap. If the result
 is
   that the number of elements in the two heaps differs by more than
 1,
   then you move the top element from the longer heap into the other
 one,
   thereby equalzing the number of elements. Thus, inserting an
 element
   is an O(log n) operation. To get the median, it is the top element
 of
   the longer heap, or, if the heaps are of equal length, it is the
   average of the two top elements. This is O(1).
 
   Dave
 
   On May 14, 8:34 am, Ashish Goel ashg...@gmail.com wrote:
not clear, can u elaborate..
 
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
 
On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal 
 agr.bhav...@gmail.com
   wrote:
 
 This problem can be solved using 2 heaps and the median can
 always be
 accessed in O(1) time ,the first node.
 
 --
 You received this message because you are subscribed to the
 Google
   Groups
 Algorithm Geeks group.
 To post to this group, send email to
 algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.-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.
 
  --
  regards,
  chinna.- 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.




 --
 regards,
 chinna.

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



  

Re: [algogeeks] Re: Google Q

[Akshata Sharma]

@Dave:
without using comparison operator,

int sign = (a  (sizeof(int) * CHAR_BIT - 1));

sign=0 if a is +ive or 0
else sign=-1;

int mult(int x, int y)
{
   int p = 0, s = y;
   int sign = (y  (sizeof(int) * CHAR_BIT - 1));
   if(sign) y = add(~y,1);
   while(y)
   {
   if(y  1) p = add(x, p);
   x = 1;
   y = 1;
   }
   sign=(s(sizeof(int)*CHAR_BIT - 1));
   if(sign) p = add(~p,1);
   return(p);
}

On Sat, May 14, 2011 at 2:28 AM, Dave dave_and_da...@juno.com wrote:

 @Ashish: Here's addition, subtraction, and multiplication with bit
 manipulation and comparisons. I doubt if you can do them without
 comparisons.

 int add(int x, int y)
 {
int c;
while(y)
{
c = x  y;
x ^= y;
y = c  1;
}
return(x);
 }

 int sub(int x, int y)
 {
return(add(x,add(~y,1));
 }

 int mult(int x, int y)
 {
int p = 0, s = y;
if(y  0) y = add(~y,1);
while(y)
{
if(y  1) p = add(x, p);
x = 1;
y = 1;
}
if(s  0) p = add(~p,1);
return(p);
 }

 Dave

 On May 12, 10:03 pm, Ashish Goel ashg...@gmail.com wrote:
  Using bit manipulation, implement add, subtract and multiply on two
  integers. You cannot use any arithmetic operations, such as +, - or *.
 
  Best Regards
  Ashish Goel
  Think positive and find fuel in failure
  +919985813081
  +919966006652

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



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

Re: [algogeeks] Re: Google Q

[pacific :-)]

perfect.

Thanks for the effort in explanation.

On Sun, May 15, 2011 at 12:20 AM, Dave dave_and_da...@juno.com wrote:

 @Pacific: A balanced binary tree is commonly defined as a binary tree
 in which the height of the two subtrees of every node never differ by
 more than 1. Thus, there could be more nodes in one subtree than in
 the other. E.g., a balanced binary tree with 11 nodes could have 7
 nodes in the left subtree and only 3 nodes in the right subtree. Thus,
 the root would not be the median.

 An additional condition is needed: the number of nodes in the left
 subtree differs by at most one from the number of nodes in the right
 subtree.

 In fact, given that the heap structure is a balanced binary tree
 structure with implicit pointers to the left and right subtrees, the
 two-heap algorithm I described results in a balanced binary tree
 satisfying this additional condition, with an implicit root node equal
 to the median.

 Dave

 On May 14, 11:55 am, pacific :-) pacific4...@gmail.com wrote:
  Will not a balanced binary tree do the job ? if we will pick the root
 each
  time for the median.
 
 
 
 
 
  On Sat, May 14, 2011 at 9:10 PM, Dave dave_and_da...@juno.com wrote:
   @Ashish: The idea is to keep two heaps, a max-heap of the smallest
   half of the elements and a min-heap of the largest elements. You
   insert incoming elements into the appropriate heap. If the result is
   that the number of elements in the two heaps differs by more than 1,
   then you move the top element from the longer heap into the other one,
   thereby equalzing the number of elements. Thus, inserting an element
   is an O(log n) operation. To get the median, it is the top element of
   the longer heap, or, if the heaps are of equal length, it is the
   average of the two top elements. This is O(1).
 
   Dave
 
   On May 14, 8:34 am, Ashish Goel ashg...@gmail.com wrote:
not clear, can u elaborate..
 
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
 
On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal 
 agr.bhav...@gmail.com
   wrote:
 
 This problem can be solved using 2 heaps and the median can always
 be
 accessed in O(1) time ,the first node.
 
 --
 You received this message because you are subscribed to the Google
   Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.-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.
 
  --
  regards,
  chinna.- 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.




-- 
regards,
chinna.

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

Re: [algogeeks] Re: Google Q

[Anand]

1. Create a BST for first K elements of the running stream.
2. Find the median of first K elements.
3. With every new element from the stream, Insert the new element in Binary
search Tree.
4. Delete the first element from BST.
5. if the new element is greater than the current median value, find the
successor of current median value.
6. else if the new elment is less than the current median value, find the
predecessor of the currend median value in BST.



On Sun, May 15, 2011 at 2:51 AM, pacific :-) pacific4...@gmail.com wrote:

 perfect.

 Thanks for the effort in explanation.


 On Sun, May 15, 2011 at 12:20 AM, Dave dave_and_da...@juno.com wrote:

 @Pacific: A balanced binary tree is commonly defined as a binary tree
 in which the height of the two subtrees of every node never differ by
 more than 1. Thus, there could be more nodes in one subtree than in
 the other. E.g., a balanced binary tree with 11 nodes could have 7
 nodes in the left subtree and only 3 nodes in the right subtree. Thus,
 the root would not be the median.

 An additional condition is needed: the number of nodes in the left
 subtree differs by at most one from the number of nodes in the right
 subtree.

 In fact, given that the heap structure is a balanced binary tree
 structure with implicit pointers to the left and right subtrees, the
 two-heap algorithm I described results in a balanced binary tree
 satisfying this additional condition, with an implicit root node equal
 to the median.

 Dave

 On May 14, 11:55 am, pacific :-) pacific4...@gmail.com wrote:
  Will not a balanced binary tree do the job ? if we will pick the root
 each
  time for the median.
 
 
 
 
 
  On Sat, May 14, 2011 at 9:10 PM, Dave dave_and_da...@juno.com wrote:
   @Ashish: The idea is to keep two heaps, a max-heap of the smallest
   half of the elements and a min-heap of the largest elements. You
   insert incoming elements into the appropriate heap. If the result is
   that the number of elements in the two heaps differs by more than 1,
   then you move the top element from the longer heap into the other one,
   thereby equalzing the number of elements. Thus, inserting an element
   is an O(log n) operation. To get the median, it is the top element of
   the longer heap, or, if the heaps are of equal length, it is the
   average of the two top elements. This is O(1).
 
   Dave
 
   On May 14, 8:34 am, Ashish Goel ashg...@gmail.com wrote:
not clear, can u elaborate..
 
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
 
On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal 
 agr.bhav...@gmail.com
   wrote:
 
 This problem can be solved using 2 heaps and the median can always
 be
 accessed in O(1) time ,the first node.
 
 --
 You received this message because you are subscribed to the Google
   Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.-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.
 
  --
  regards,
  chinna.- 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.




 --
 regards,
 chinna.

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


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

Re: [algogeeks] Re: Google Q

[Anand]

Complexity will be O(logK) to insert, delete and finding the predecessor or
successor of current median value in the BST.

On Sun, May 15, 2011 at 4:08 PM, Anand anandut2...@gmail.com wrote:

 1. Create a BST for first K elements of the running stream.
 2. Find the median of first K elements.
 3. With every new element from the stream, Insert the new element in Binary
 search Tree.
 4. Delete the first element from BST.
 5. if the new element is greater than the current median value, find the
 successor of current median value.
 6. else if the new elment is less than the current median value, find the
 predecessor of the currend median value in BST.



 On Sun, May 15, 2011 at 2:51 AM, pacific :-) pacific4...@gmail.comwrote:

 perfect.

 Thanks for the effort in explanation.


 On Sun, May 15, 2011 at 12:20 AM, Dave dave_and_da...@juno.com wrote:

 @Pacific: A balanced binary tree is commonly defined as a binary tree
 in which the height of the two subtrees of every node never differ by
 more than 1. Thus, there could be more nodes in one subtree than in
 the other. E.g., a balanced binary tree with 11 nodes could have 7
 nodes in the left subtree and only 3 nodes in the right subtree. Thus,
 the root would not be the median.

 An additional condition is needed: the number of nodes in the left
 subtree differs by at most one from the number of nodes in the right
 subtree.

 In fact, given that the heap structure is a balanced binary tree
 structure with implicit pointers to the left and right subtrees, the
 two-heap algorithm I described results in a balanced binary tree
 satisfying this additional condition, with an implicit root node equal
 to the median.

 Dave

 On May 14, 11:55 am, pacific :-) pacific4...@gmail.com wrote:
  Will not a balanced binary tree do the job ? if we will pick the root
 each
  time for the median.
 
 
 
 
 
  On Sat, May 14, 2011 at 9:10 PM, Dave dave_and_da...@juno.com wrote:
   @Ashish: The idea is to keep two heaps, a max-heap of the smallest
   half of the elements and a min-heap of the largest elements. You
   insert incoming elements into the appropriate heap. If the result is
   that the number of elements in the two heaps differs by more than 1,
   then you move the top element from the longer heap into the other
 one,
   thereby equalzing the number of elements. Thus, inserting an element
   is an O(log n) operation. To get the median, it is the top element of
   the longer heap, or, if the heaps are of equal length, it is the
   average of the two top elements. This is O(1).
 
   Dave
 
   On May 14, 8:34 am, Ashish Goel ashg...@gmail.com wrote:
not clear, can u elaborate..
 
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
 
On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal 
 agr.bhav...@gmail.com
   wrote:
 
 This problem can be solved using 2 heaps and the median can
 always be
 accessed in O(1) time ,the first node.
 
 --
 You received this message because you are subscribed to the
 Google
   Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.-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.
 
  --
  regards,
  chinna.- 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.




 --
 regards,
 chinna.

  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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.

[algogeeks] Re: Google Q

[Dave]

@Ashish: The idea is to keep two heaps, a max-heap of the smallest
half of the elements and a min-heap of the largest elements. You
insert incoming elements into the appropriate heap. If the result is
that the number of elements in the two heaps differs by more than 1,
then you move the top element from the longer heap into the other one,
thereby equalzing the number of elements. Thus, inserting an element
is an O(log n) operation. To get the median, it is the top element of
the longer heap, or, if the heaps are of equal length, it is the
average of the two top elements. This is O(1).

Dave

On May 14, 8:34 am, Ashish Goel ashg...@gmail.com wrote:
 not clear, can u elaborate..

 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652

 On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal agr.bhav...@gmail.comwrote:



  This problem can be solved using 2 heaps and the median can always be
  accessed in O(1) time ,the first node.

  --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.- 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.

Re: [algogeeks] Re: Google Q

[pacific :-)]

Will not a balanced binary tree do the job ? if we will pick the root each
time for the median.


On Sat, May 14, 2011 at 9:10 PM, Dave dave_and_da...@juno.com wrote:

 @Ashish: The idea is to keep two heaps, a max-heap of the smallest
 half of the elements and a min-heap of the largest elements. You
 insert incoming elements into the appropriate heap. If the result is
 that the number of elements in the two heaps differs by more than 1,
 then you move the top element from the longer heap into the other one,
 thereby equalzing the number of elements. Thus, inserting an element
 is an O(log n) operation. To get the median, it is the top element of
 the longer heap, or, if the heaps are of equal length, it is the
 average of the two top elements. This is O(1).

 Dave

 On May 14, 8:34 am, Ashish Goel ashg...@gmail.com wrote:
  not clear, can u elaborate..
 
  Best Regards
  Ashish Goel
  Think positive and find fuel in failure
  +919985813081
  +919966006652
 
  On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal agr.bhav...@gmail.com
 wrote:
 
 
 
   This problem can be solved using 2 heaps and the median can always be
   accessed in O(1) time ,the first node.
 
   --
   You received this message because you are subscribed to the Google
 Groups
   Algorithm Geeks group.
   To post to this group, send email to algogeeks@googlegroups.com.
   To unsubscribe from this group, send email to
   algogeeks+unsubscr...@googlegroups.com.
   For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.- 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.




-- 
regards,
chinna.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Google Q

[Dave]

@Pacific: A balanced binary tree is commonly defined as a binary tree
in which the height of the two subtrees of every node never differ by
more than 1. Thus, there could be more nodes in one subtree than in
the other. E.g., a balanced binary tree with 11 nodes could have 7
nodes in the left subtree and only 3 nodes in the right subtree. Thus,
the root would not be the median.

An additional condition is needed: the number of nodes in the left
subtree differs by at most one from the number of nodes in the right
subtree.

In fact, given that the heap structure is a balanced binary tree
structure with implicit pointers to the left and right subtrees, the
two-heap algorithm I described results in a balanced binary tree
satisfying this additional condition, with an implicit root node equal
to the median.

Dave

On May 14, 11:55 am, pacific :-) pacific4...@gmail.com wrote:
 Will not a balanced binary tree do the job ? if we will pick the root each
 time for the median.





 On Sat, May 14, 2011 at 9:10 PM, Dave dave_and_da...@juno.com wrote:
  @Ashish: The idea is to keep two heaps, a max-heap of the smallest
  half of the elements and a min-heap of the largest elements. You
  insert incoming elements into the appropriate heap. If the result is
  that the number of elements in the two heaps differs by more than 1,
  then you move the top element from the longer heap into the other one,
  thereby equalzing the number of elements. Thus, inserting an element
  is an O(log n) operation. To get the median, it is the top element of
  the longer heap, or, if the heaps are of equal length, it is the
  average of the two top elements. This is O(1).

  Dave

  On May 14, 8:34 am, Ashish Goel ashg...@gmail.com wrote:
   not clear, can u elaborate..

   Best Regards
   Ashish Goel
   Think positive and find fuel in failure
   +919985813081
   +919966006652

   On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal agr.bhav...@gmail.com
  wrote:

This problem can be solved using 2 heaps and the median can always be
accessed in O(1) time ,the first node.

--
You received this message because you are subscribed to the Google
  Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
   http://groups.google.com/group/algogeeks?hl=en.-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.

 --
 regards,
 chinna.- 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.

[algogeeks] Re: Google Q

[Dave]

@Ashish: Here's addition, subtraction, and multiplication with bit
manipulation and comparisons. I doubt if you can do them without
comparisons.

int add(int x, int y)
{
int c;
while(y)
{
c = x  y;
x ^= y;
y = c  1;
}
return(x);
}

int sub(int x, int y)
{
return(add(x,add(~y,1));
}

int mult(int x, int y)
{
int p = 0, s = y;
if(y  0) y = add(~y,1);
while(y)
{
if(y  1) p = add(x, p);
x = 1;
y = 1;
}
if(s  0) p = add(~p,1);
return(p);
}

Dave

On May 12, 10:03 pm, Ashish Goel ashg...@gmail.com wrote:
 Using bit manipulation, implement add, subtract and multiply on two
 integers. You cannot use any arithmetic operations, such as +, - or *.

 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652

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