[algogeeks] Re: Hash Table

[ligerdave]

from high level and with a very few collisions, it's O(1).

there isn't much to prove because this is based on a common sense.

for example, have the world as a hashtable and all countries as the keys of 
it. boxes(storage) marked by different country names(key) and you know 
where to locate them. now, you are given a mail and asked to put it into 
the box which goes to its destination country. 
so how many operations does it take you to put a mail in the box? 1
if you realized the mail wasn't misplaced and you need to take it out, how 
many operations does it take you to take the mail out of the box?

i hope this helps a bit

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

[ligerdave]

I am a bit confused. Are you talking about the runtime of hash function 
itself or to find the position. 
Agree on the efficient hash function design. However, no function could be 
designed to fit all cases. A key to make a particular hash function 
efficient is to know the potential data size.

-- 
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/-/G_0Wm4NQIyIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Find all possible combination of integers for a given sum

[ligerdave]

@meng You already have the pattern figured out. each time subtract 1
from the lowest digit and add to higher digit(only once), until the
lowest digit equals to closest higher digit. the selection of which
number to start could be figured out with given parameters sum and
combination

@Prem, no recursion needed here. it make it more complex than
necessary. one loop with a pointer should be able to resolve this

On Oct 24, 6:28 pm, Meng Yan mengyan.fu...@gmail.com wrote:
 Hi, my question is

 given sum=N and combination constraint=M (the number of elements), how to
 find all possible combinations of integers?

 For example, given sum=6, combination=3; how to get the result as following:
 1+1+4;
 1+2+3;
 2+2+2;

 We don't care about order of the elements, which means 1+1+4 and 1+4+1 are
 considered as same combination.

 Thanks a lot!

 Meng

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

[ligerdave]

Sorry, but this isn't a mysql group. all discussions need to be
algorithm related.

On Apr 28, 3:04 pm, Aniket aniket...@gmail.com wrote:
 I was trying to install mysql 5.5. in Windows XP.After installation
 during configuration phase when there was to apply security settings I
 m always getting an error

 Error No 1045
 Access Denied for user 'root'@localhost(using password: NO).

 I have tried all possibilities in Firewall but it dint work.Hope
 anybody here will help me out of this problem.I am totally screwed
 up!!!

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

[ligerdave]

Why make this overcomplicated?

There isn't a merge sort needed if two arrays were already sorted.

It takes only O(n). Each time, you compare the leading elements and
remove the smaller one and store it in a new array.


On Apr 12, 6:33 pm, Carl Barton odysseus.ulys...@gmail.com wrote:
 Very interesting link!

 As we only need to perform one merge we should be able to modify it to run
 in O(n) time?
 In a similar style as a strand sort?

 On 12 April 2011 22:55, hary rathor harry.rat...@gmail.com wrote:









 http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html

  take a glance on this merge sort this is Inplace and also stable

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

[ligerdave]

Folks,

here is an interesting puzzle:

A Rubick's Cube has owl heads on it, which can be misoriented. How
many (times) MORE combinations are there of this cube vs. one that has
blank stickers?


the major difference between the cube with owl's heads and the one
without is you might have the heads in 4 different directions depends
on how you rotate the cube.

Here is what i have:

I figured since the problem is asking how many times, it's asking
the relation between two cases. I also realized that the only the axis/
middle piece of the side matters and everything else is fixed because
you can only rotate the edges to make the direction of the middle
piece changing relatively.

Let's say the number of combination of the cube without heads is N. I
am thinking since you have 4 possible directions and Y middle pieces
and since the pieces are independent, wouldn't that be 4^Y*N
combination of the one with heads, which means 4^Y times more than the
one without?


What do you think?

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

[ligerdave]

Instead of looking for a common friend of A and B, look for someone
who has friends A and B.

if you are using relational DB, use count()


didn't quite understand your first part that only if A is friend of
B. i assume when A is a friend of B, B is a friend of A as well

On Mar 24, 6:43 am, snehal jain learner@gmail.com wrote:
 Suppose there are 2 persons A and B on FB . A should be able to view
 the pictures of B only if either A is friend of B or A and B have at
 least one common friend .

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

[ligerdave]

let's make this clear.

you have a total of N questions for K students, and each student gets
M questions, where M1+ M2 + M3 ++ Mn = N; Mx union My = {}empty

when you say the repeats should be minimized, i read it as eliminated,
unless you allow a few repeated questions(in a real number, saying 2
allowed)

to do this quickly without repeats,

boundary  = N.length

i = random() % boundary

pick N[i] and replace this element with current last element in the
array which is N[boundary-1]

then boundary--

one iteration completed here and you can repeat those steps.

this way, you would never have two same questions generated and run
time is O(1)


On Mar 24, 4:49 am, snehal jain learner@gmail.com wrote:
 A question set is given to you and you have to generate (question
 numbers are in an array) generate different set of question paper for
 k students.
 in other words From a total of n questions you have to give m
 questions to each of the k students such that both the number of
 repeated questions and the number of repetitions of each repeated
 question are minimized

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

[ligerdave]

I have to say: to prove the correctness of this hypotheses is a
wrong question and there isn't an algorithm for proving something
that's infinity.

even number is 2n, where n=1 to infinity.

you can only prove the hypotheses through mathematical methods.

you can verify the correctness. it's like a P=NP kinda thing.


On Mar 24, 1:49 am, bittu shashank7andr...@gmail.com wrote:
 yesterday one of the my friends asked this Q to me prove with
 correctness that
 Every even integer greater than 2 can be expressed as the sum of two
 primes
   e.g

       4 = 2 + 2
       6 = 3 + 3
     10 = 7 + 3 or 5 + 5
     14 = 3 + 11 or 7 + 7

 Explain   Derive The Time ,Space Complexity of Algorithm

 it seems to be that we have to find all possible prime factor of
 number  prints it its not big task , so by checking that number we
 have to generate the all prime factor of it seems O(n) ..Hope i m
 clear corrcet me if i am wrong here.??

 But  problem come when even number become bigger say 1 billion  10^9
 so for this choosing the a number as a prime factor has probability of
 1/ln(n)
 so say if for 1 billion number out of 21 only 1 is prime. .y question
 is we have to prove the time complexity for two
 choosing a number nearby such big number is 1/ln(n)..??

 with Heuristic justification it can be explained ro induction might
 help but guarantee here  but i need some
 mathematical proof for this

 Thank  Regards
 Shashank Mani
 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.

[algogeeks] Re: Find the first K smallest element from 1 million sized array ...Amazon Question..

[ligerdave]

@Ankit

Simplify what @Dave had said:

1.you build a max heap with first k numbers
2. always compare array[k+n] where n=1.array.size-k
   if array[k+n] = k, compare next element in the array
   else replace top with array[k+n] and heapify

so the worst case is like @Dave gave: O((N-5) * log k). in the real
case, very likely you get better coz for many numbers in the array,
you don't have to go down the heap for comparison

On Mar 24, 12:22 am, Ankit Sinha akki12...@gmail.com wrote:
 Guys,

 My intention was to understand how to manage max heap of k size into
 memory. Means we have millions of numbers that we can't load into RAM
 then how in the very first go we going to load only k size and how
 will track of rest numbers. Can anybody code it? Do we need file to
 store million numbers and then read say first k numbers and then take
 another chunk?

 Thanks,

 Ankit!!







 On Tue, Mar 22, 2011 at 10:13 AM, Rajeev Kumar rajeevprasa...@gmail.com 
 wrote:
 http://flexaired.blogspot.com/2011/03/big-file-containing-billions-of...

  On Mon, Mar 21, 2011 at 4:05 AM, Natansh Verma natansh.ve...@gmail.com
  wrote:

  @dave -was this a constraint since the beginning? In case it was, I am
  sorry I didn't notice.

  In that case, the heap method ought to work better. I dont think the
  quicksort method will work.

  Sent from my iPhone

  On 20-Mar-2011, at 23:00, Dave dave_and_da...@juno.com wrote:

   @Natansh: How do you do this with the constraint that your RAM is so
   small that you cannot accomodate all of the numbers at once?

   Dave

   On Mar 20, 9:04 am, Natansh Verma natansh.ve...@gmail.com wrote:
   There's another way... use the partitioning method for quicksort to
   find the
   k smallest elements. Then it should take expected time as O(n + klogk).
   Plus, it is in-place.

   On Wed, Mar 16, 2011 at 7:26 PM, asit lipu...@gmail.com wrote:
   I agree with munna

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

  --
  Thank You
  Rajeev Kumar

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

[ligerdave]

Nice @Don! That's something I was thinking but couldn't come up with
the name.

Finding a large prime itself is already an interesting and difficult
thing in number theory. To prove something on top of that could be
even more difficult

On Mar 24, 12:38 pm, Don dondod...@gmail.com wrote:
 This is called Goldbach's Conjecture, and has not yet been proven or
 disproven.

 Goldbach wrote a letter to Euler in 1742 suggesting that every integer
 n  5 is the sum of three primes.  Euler replied that this is
 equivalent to every even n  2 is the sum of two primes--this is now
 known as Goldbach's conjecture.  Schnizel showed that Goldbach's
 conjecture is equivalent to every integer n  17 is the sum of three
 distinct primes.

 It has been proven that every even integer is the sum of at most six
 primes and in 1966 Chen proved every sufficiently large even integer
 is the sum of a prime plus a number with no more than two prime
 factors (a P2).  In 1993 Sinisalo verified Goldbach's conjecture for
 all integers less than 4*10^11. More recently Jean-Marc Deshouillers,
 Yannick Saouter and Herman te Riele have verified this up to 10^14
 with the help, of a Cray C90 and various workstations.  In July 1998,
 Joerg Richstein completed a verification to 4*10^14 and placed a list
 of champions online. More recent work by Oliveira e Silva has extended
 this to at least 4*10^17.

 There has been substantial progress on proving that every odd integer 5 is 
 the sum of 3 primes, the easier case of Goldbach's conjecture.

 In 1937 Vinogradov proved that this is true for sufficiently large odd
 integers n.  In 1956 Borodzkin showed n  3^14348907 is sufficient
 (the exponent is 3^15).  In 1989 Chen and Wang reduced this bound to
 10^43000.  The exponent still must be reduced dramatically before we
 can use computers to take care of all the small cases.

 Don

 On Mar 24, 12:49 am, bittu shashank7andr...@gmail.com wrote:







  yesterday one of the my friends asked this Q to me prove with
  correctness that
  Every even integer greater than 2 can be expressed as the sum of two
  primes
    e.g

        4 = 2 + 2
        6 = 3 + 3
      10 = 7 + 3 or 5 + 5
      14 = 3 + 11 or 7 + 7

  Explain   Derive The Time ,Space Complexity of Algorithm

  it seems to be that we have to find all possible prime factor of
  number  prints it its not big task , so by checking that number we
  have to generate the all prime factor of it seems O(n) ..Hope i m
  clear corrcet me if i am wrong here.??

  But  problem come when even number become bigger say 1 billion  10^9
  so for this choosing the a number as a prime factor has probability of
  1/ln(n)
  so say if for 1 billion number out of 21 only 1 is prime. .y question
  is we have to prove the time complexity for two
  choosing a number nearby such big number is 1/ln(n)..??

  with Heuristic justification it can be explained ro induction might
  help but guarantee here  but i need some
  mathematical proof for this

  Thank  Regards
  Shashank Mani
  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.

[algogeeks] Re: generate ques set

[ligerdave]

in that case, the solution doesn't apply. however, it's part of the
solution becoz this guarantees you wont have two same questions
generated for a student.

So you have to ask the question again with clear requirements.

you have to define what will be the minimized number. minimized to
me is eliminated when it can go to 0.



On Mar 24, 12:20 pm, snehal jain learner@gmail.com wrote:
 m*kN . so Mx intersection My is not necessarily empty. so i think your
 solution is not optimized.
 please correct me if I am wrong.







 On Thu, Mar 24, 2011 at 7:10 PM, ligerdave david.c...@gmail.com wrote:
  let's make this clear.

  you have a total of N questions for K students, and each student gets
  M questions, where M1+ M2 + M3 ++ Mn = N; Mx union My = {}empty

  when you say the repeats should be minimized, i read it as eliminated,
  unless you allow a few repeated questions(in a real number, saying 2
  allowed)

  to do this quickly without repeats,

  boundary  = N.length

  i = random() % boundary

  pick N[i] and replace this element with current last element in the
  array which is N[boundary-1]

  then boundary--

  one iteration completed here and you can repeat those steps.

  this way, you would never have two same questions generated and run
  time is O(1)

  On Mar 24, 4:49 am, snehal jain learner@gmail.com wrote:
   A question set is given to you and you have to generate (question
   numbers are in an array) generate different set of question paper for
   k students.
   in other words From a total of n questions you have to give m
   questions to each of the k students such that both the number of
   repeated questions and the number of repetitions of each repeated
   question are minimized

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

[ligerdave]

the whole point of linked list is to use reference. so  just simply
replace values of current node with the next node's and have the
pointer pointing to the node that's next to next.

1-2-3-4-tail

saying you wanna remove 2, you have the pointer pointing to 3 and
became
1-3-4-tail



On Mar 13, 12:53 pm, UMESH KUMAR kumar.umesh...@gmail.com wrote:
 hi

  Given a singly Link list but Head of the List is
  unknown so my question is that 

           How to delete a given node from the List???

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

[ligerdave]

this is a tree traversal(depth first) problem.

as for the extra space, depends on how you see it. fifth can be the
counter and when the counter reaches 0, you have your fifth largest
element

On Jan 21, 9:58 am, nagaraj N nagaraj1...@gmail.com wrote:
 How do you find out the fifth maximum element in an binary search tree
 in efficient manner without using any extra space?

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

[ligerdave]

use linked list. to improve the look up performance, use a binary tree
to map the objects in the linked list

On Jan 13, 1:23 am, Davin dkthar...@googlemail.com wrote:
 Smaple Data :

 input : abcdacdc
 Output : cadb

 If the count is same for  characters. maintain the original order of
 the characters from input string.

 Please do let me know for any clarification.

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

[ligerdave]

@aditya
there is always trade-off. for what it's asking, TRIE is probably the
fastest. the problem already stated, using data structure, which to
me, means, you index a document. indexing is expensive, but it's
overhead process and it has nothing to do w/ finding an existing word
in a doc.

On Dec 10, 5:33 am, ADITYA KUMAR aditya...@gmail.com wrote:
 @ankit
 u can'nt use TRIE
 becoz , input will be given in form of text
 so generating the TRIE will be much expensive than linear search

 On Fri, Dec 10, 2010 at 3:13 PM, GOBIND KUMAR gobind@gmail.com wrote:
  Help me in solving this problem...       Define a data struct for the 
  search engine which will represent whether

  given word is there in the document or not .It  should be fast.

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

 --
 Regards
 Aditya Kumar
 B-tech 3rd year
 Computer Science  Engg.
 MNNIT, Allahabad.

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

[ligerdave]

@Dave
I hear ya. Im just saying in general, you would wanna have an
algorithm for all cases.
of coz, in this case, if the RAM isn't a consideration and heapsort is
what @Vinay wants, i guess we are coming up w/ one like that.
again, in general, you don't wanna have one version of program for
king james and another for something that's more right?

btw, do you have any new clue on the nth largest sum of two arrays? i
realized the solution i gave wasn't working for all cases. im on the
right track i think. however, there is something must be fixed and im
scratching my head now. :) let me know man!

On Oct 22, 11:19 pm, Dave dave_and_da...@juno.com wrote:
 @Ligerdave: Hey, the King James version of the Bible is only about
 600,000 words. I use the Bible as an example only because it is a
 fairly large book. Maybe we are talking 10 megabytes to store the
 whole thing, seeing that there are some long words such as Maher-
 shalal-hash-baz, a name that occurs in Isaiah 8:3. Ten megabytes
 hardly seems large, when compared to the 4 or 8 gigabytes or more of
 RAM on many computers. Besides, you don't have to keep all of the text
 in memory, but only the distinct words and an integer count of the
 number of occurrences. For the King James bible, this is less than
 5,000 words, so we're talking a pretty minimal amount of memory. A
 hash table might work fine for this, or build a balanced binary tree
 of the words. After you have scanned all of the input text and
 determined the number of occurrences of each word, it is fairly easy
 to scan the word counts and pick out the ten largest.

 Dave

 On Oct 22, 9:24 am, ligerdave david.c...@gmail.com wrote:







  for a large file, you probably would want to use external sort. kinda
  like a map-reduce concept. it's actually how sortuniq kinda stuff
  work in unix/linux when you try to find some TOP X

  again, we are talking about the memory might not hold the entire file

  On Oct 21, 9:35 am, Vinay... vinumars...@gmail.com wrote:

   how do u find 10 most repeating words on a large file containing words
   in most efficient way...if it can also be done using heapsort plz post
   ur answers..- 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 algoge...@googlegroups.com.
To unsubscribe from 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: Yahoo coding round question

[ligerdave]

@ravindra

agree!

On Oct 24, 2:20 pm, ravindra patel ravindra.it...@gmail.com wrote:
 @ Kishen
 So lets say you have 100 parallel processors and you are given an array of
 100 elements, then the loop will execute in 1 clock. Now lets say on the
 same machine you are given a problem array of 1 million elements. So how
 many clocks are you gonna consume, assuming all your 100 processors are
 running in parallel.

 Buddy, with parallel processors you can reduce total computation time at
 most by a factor of number of processors you have (which will always be a
 constant, no matter how big it is). It has nothing to do with time
 complexity.

 Thanks,
 - Ravindra



 On Fri, Oct 22, 2010 at 8:17 AM, Kishen Das kishen@gmail.com wrote:
  Ok, if you look at the inner loop, it is -

   for ( j = i to j = 0 ) {
   sum[j] +=  A[ i]
   product[j] *= A [ i]
  }

  This is as good as executing -
  sum[i] =   sum [ i ] + A[ i ] --- ( 1 )
  sum[i-1]= sum[i-1]+ A[i]   ( 2 )
  --
  ---
  ---
  sum[0]  = sum[ 0]+A[i]   -- ( i )

  Each of these assignments doesn't have any dependency with other
  computations i.e.,
  ( 1 ) is independent of ( 2 ) to ( i ) and so does ( 2 ) , ( 3 ) ,  ( i
  )
  and hence each of this can be assigned to a different processor.
  So, each of these statements( iterations) of the inner-loop j can be run in
  different processors, making it O(1).

  I am sorry, if people are still not getting my point !!!
  This is the best I can do !!!

  Kishen

  On Thu, Oct 21, 2010 at 9:08 AM, ligerdave david.c...@gmail.com wrote:

  @Kishen

  I don't have much knowledge on parallel computation in OpenCL or CUDA.
  Do you mean parallelised=not have to do the computation at all?
  did you mean without knowing the boundary of the inner loop which is
  depended on the outer loop, the inner loop would be smart enough to
  figure out the i and j?

  On Oct 20, 7:33 pm, Kishen Das kishen@gmail.com wrote:
   Well, looks like people are not understanding when I say run a loop in
   parallel !!!

   Please look at some of the examples on Nvidia website on how
  computations
   can be parallelised in OpenCL or CUDA.
   And also some of the high level programming languages like Scala which
  is
   also providing these parallel constructs.

   If you don't understand GPUs or not familiar with parallel constructs in
   Java, then my algorithm will definitely look like O ( n ^ 2 ).

   Kishen

   On Wed, Oct 20, 2010 at 4:25 PM, ligerdave david.c...@gmail.com
  wrote:
@Kishen
as long as you have one for loop in another, you wont have O(n). it
will most likely run O(n^2)

On Oct 19, 7:41 pm, Kishen Das kishen@gmail.com wrote:
 In the below code the jth and kth inner for loops can be run in
  parallel
 making them O(1) and the entire thing O(n).

 for ( i=0 to i=N-1 )
 {

 for ( j = i to j = 0 ) {
 sum[j] +=  A[ i]
 product[j] *= A [ i]

 }

 for( k=0 to k= i )
 if ( sum[k] == S and product[k] == P ) {
 Answer is the sub array A[k to i ]
 break

 }
 }

 Kishen

 On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh 
  iiita2007...@gmail.com
wrote:

  @ Rahul patil  ofcourse array may have negative or positive
  integers

  @ Kishen   both O(n) and O(n logn) solutions was asked in this
  yahoo
coding
  round question

  On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh 
  iiita2007...@gmail.com wrote:

  Given an array of length N. How will you find the minimum length
  contiguous sub - array of whose sum is S and whose product is P .
  Here
  S and P will be given to you.

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

  --
  ABHISHEK KUMAR SINGH
  BTECH (INFORMATION TECHNOLOGY)
  IIIT ALLAHABAD
  9956640538

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

[algogeeks] Re: 10 most repeating words

[ligerdave]

for a large file, you probably would want to use external sort. kinda
like a map-reduce concept. it's actually how sortuniq kinda stuff
work in unix/linux when you try to find some TOP X

again, we are talking about the memory might not hold the entire file

On Oct 21, 9:35 am, Vinay... vinumars...@gmail.com wrote:
 how do u find 10 most repeating words on a large file containing words
 in most efficient way...if it can also be done using heapsort plz post
 ur answers..

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

[ligerdave]

@Kishen

I don't have much knowledge on parallel computation in OpenCL or CUDA.
Do you mean parallelised=not have to do the computation at all?
did you mean without knowing the boundary of the inner loop which is
depended on the outer loop, the inner loop would be smart enough to
figure out the i and j?

On Oct 20, 7:33 pm, Kishen Das kishen@gmail.com wrote:
 Well, looks like people are not understanding when I say run a loop in
 parallel !!!

 Please look at some of the examples on Nvidia website on how computations
 can be parallelised in OpenCL or CUDA.
 And also some of the high level programming languages like Scala which is
 also providing these parallel constructs.

 If you don't understand GPUs or not familiar with parallel constructs in
 Java, then my algorithm will definitely look like O ( n ^ 2 ).

 Kishen



 On Wed, Oct 20, 2010 at 4:25 PM, ligerdave david.c...@gmail.com wrote:
  @Kishen
  as long as you have one for loop in another, you wont have O(n). it
  will most likely run O(n^2)

  On Oct 19, 7:41 pm, Kishen Das kishen@gmail.com wrote:
   In the below code the jth and kth inner for loops can be run in parallel
   making them O(1) and the entire thing O(n).

   for ( i=0 to i=N-1 )
   {

   for ( j = i to j = 0 ) {
   sum[j] +=  A[ i]
   product[j] *= A [ i]

   }

   for( k=0 to k= i )
   if ( sum[k] == S and product[k] == P ) {
   Answer is the sub array A[k to i ]
   break

   }
   }

   Kishen

   On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh iiita2007...@gmail.com
  wrote:

@ Rahul patil  ofcourse array may have negative or positive integers

@ Kishen   both O(n) and O(n logn) solutions was asked in this yahoo
  coding
round question

On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh 
iiita2007...@gmail.com wrote:

Given an array of length N. How will you find the minimum length
contiguous sub - array of whose sum is S and whose product is P . Here
S and P will be given to you.

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

--
ABHISHEK KUMAR SINGH
BTECH (INFORMATION TECHNOLOGY)
IIIT ALLAHABAD
9956640538

--
You received this message because you are subscribed to the Google
  Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups
 .com
  algogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from 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: linked lists

[ligerdave]

@Asquare

you were right. what about this?


public static char[] concat(char[] str1, char[] str2) {


boolean repeat = false;// indicates whether two neighbor chars
repeat in
// str1 array

int pointer = -1; // pointer for str2 array

for (int i = 0; i  str1.length; i++) {

if (pointer + 1 = str2.length) {
pointer = -1;
break;
}

if (str1[i] == str2[pointer + 1]) {

pointer++;
repeat = (i  0  (str1[i] == str1[i - 1]));

} else {

if (!repeat)
pointer = -1;

}

}

char[] result = null;

if (pointer != -1) {
result = new char[str1.length + str2.length - (pointer 
+ 1)];

System.arraycopy(str1, 0, result, 0, str1.length);
System.arraycopy(str2, pointer + 1, result, str1.length,
str2.length
- pointer - 1);
}

return result;

}
On Oct 20, 7:55 am, Asquare anshika.sp...@gmail.com wrote:
 @ligerdave -
 your algo will fail in the case the two arrays are:

 hellostl
 eeelexander

 ans : hellostlexander
 but according to ur method the answer would end up being
 hellostleeelexander

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

[ligerdave]

@asquare

basically i just added a flag to enable the window slide. good catch
btw!

On Oct 20, 7:55 am, Asquare anshika.sp...@gmail.com wrote:
 @ligerdave -
 your algo will fail in the case the two arrays are:

 hellostl
 eeelexander

 ans : hellostlexander
 but according to ur method the answer would end up being
 hellostleeelexander

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

[ligerdave]

i wanna get a clear picture of this before start.

when you say min length of contiguous sub of an array

let's say array A=[3,1,2,3,4,5], N=6

are below both good solutions?
A[0] to A[m] where m=N
A[i] to A[m] where i=m m=N


On Oct 19, 3:58 am, Abhishek Kumar Singh iiita2007...@gmail.com
wrote:
 Given an array of length N. How will you find the minimum length
 contiguous sub - array of whose sum is S and whose product is P . Here
 S and P will be given to you.

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

[ligerdave]

@Kishen
as long as you have one for loop in another, you wont have O(n). it
will most likely run O(n^2)

On Oct 19, 7:41 pm, Kishen Das kishen@gmail.com wrote:
 In the below code the jth and kth inner for loops can be run in parallel
 making them O(1) and the entire thing O(n).

 for ( i=0 to i=N-1 )
 {

 for ( j = i to j = 0 ) {
 sum[j] +=  A[ i]
 product[j] *= A [ i]

 }

 for( k=0 to k= i )
 if ( sum[k] == S and product[k] == P ) {
 Answer is the sub array A[k to i ]
 break

 }
 }

 Kishen

 On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh 
 iiita2007...@gmail.comwrote:



  @ Rahul patil  ofcourse array may have negative or positive integers

  @ Kishen   both O(n) and O(n logn) solutions was asked in this yahoo coding
  round question

  On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh 
  iiita2007...@gmail.com wrote:

  Given an array of length N. How will you find the minimum length
  contiguous sub - array of whose sum is S and whose product is P . Here
  S and P will be given to you.

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

  --
  ABHISHEK KUMAR SINGH
  BTECH (INFORMATION TECHNOLOGY)
  IIIT ALLAHABAD
  9956640538

  --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algoge...@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from 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: Duplicate in an array

[ligerdave]

what if two elements are not next to each other. would it work?

On Oct 20, 8:19 am, juver++ avpostni...@gmail.com wrote:
 Suggested approach by Anirvana doesn't work for this problem.
 It's ok if array contain numbers that are repeated twice except one
 element and we need to find it.
 For this version solution is simple - iterate over elements and find
 it's XOR value, so result = a[0] XOR a[1] ... XOR a[n - 1].
 Resulted value is an element which presented only once in the array.
 It works because of a property of XOR operation - a XOR a = 0 (so
 repeated twice pairs disappeared).

 On 20 окт, 14:44, Asquare anshika.sp...@gmail.com wrote:



  @Anirvana - In context to the XOR method u suggested, could u plz
  explain why does it so happen.. ??

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

[ligerdave]

like i said before, draw a table w/ x=a and y=b

come out w/ the matrix and you would see a patten

 30   29   4   3   2   1

30   60   59   34  33  32  31

29   59   58   33  32  31  30

434   338   7   6   5

333   327   6   5   4

232   316   5   4   3

131   305   4   3   2


you start from a[0] and b[0], compare them, take the bigger one, set
the smaller one(for next iteration) and set a limit.

for instance, in this case, either one works. let's say a[0] is
bigger, the limit will be a[1]+b[0]. limit is always the element next
to the bigger one in array, plus the biggest in another array.

you loop through a[0]+b[i] where i=0 to length of b. stop when the
outcome is less than limit.

now you take what is stored(the smaller one) to start the next
iteration(steps above)



On Oct 15, 7:56 pm, Gene gene.ress...@gmail.com wrote:
 Hi Arun.  Last time we discussed this problem I came up with the same
 idea.  Unfortunately it doesn't work.  The problem is that in order
 for the merge to be correct, each pair of pointers must be
 guarenteed to produce sums that are in non-increasing order.  They
 don't.  For example, if you run your program with

         int a[N] = { 1, 2, 3, 4,29,30};
         int b[N] = { 1, 2, 3, 4,29,30};

 It will produce

 (30,30)= 60 (30,29)= 59 (29,30)= 59 (30,4)= 34 (4,30)= 34
 (30,3)= 33

 This is wrong because the 4th pair should be (29,29) = 58.

 In fact, niether here nor in the previous discussion did we ever get a
 correct solution.

 If you figure it out, please post.

 On Oct 14, 5:54 am, arun raghavendar arun.s...@gmail.com wrote:



  Start merging A and B from the tail end for N elements, just like the way
  you would do it for a merge sort but with a different constraint based on
  the sum a[i] and b[i]

  This should work for any value of N, I just hard-coded it for simplicity.

  #includestdio.h
  #define N 6
  struct OutputType {
          int a;
          int b;
          int value;

  };

  int main() {
          int a[N] = {1,8,13,24,25,30};
          int b[N] = {5,6,17,28,29,29};
          struct OutputType s[N];
          int i, a_candidate_1 = N-1, a_candidate_2=N-2, b_candidate_1=N-1,
  b_candidate_2=N-2;
          s[0].a = a[N-1];
          s[0].b = b[N-1];
          s[0].value = a[N-1] + b[N-1];
          for (i=1;iN;i++) {
                  if ((a[a_candidate_1]+b[b_candidate_2]) =
  (a[a_candidate_2]+b[b_candidate_1])) {
                          s[i].a = a[a_candidate_1];
                          s[i].b = b[b_candidate_2];
                          s[i].value = a[a_candidate_1]+b[b_candidate_2];
                          b_candidate_2--;
                          if (b_candidate_2  0) { a_candidate_1--; }
                  } else {
                          s[i].a = a[a_candidate_2];
                          s[i].b = b[b_candidate_1];
                          s[i].value = a[a_candidate_2]+b[b_candidate_1];
                          a_candidate_2--;
                          if (a_candidate_2  0) { b_candidate_1--; }
                  }
          }

          for (i=0;iN;i++) printf((%d,%d)=%3d , s[i].a, s[i].b,
  s[i].value);

          return 0;

  }

  -Arun

  On Thu, Oct 14, 2010 at 1:25 PM, Harshal hc4...@gmail.com wrote:

   Given two sorted postive integer arrays A[n] and B[n] (W.L.O.G, let's

   say they are decreasingly sorted), 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.

   --
   Harshal Choudhary,
   III Year B.Tech Undergraduate,
   Computer Engineering Department,
   National Institute of Technology Surathkal, Karnataka
   India.

    --
   You received this message because you are subscribed to the Google Groups
   Algorithm Geeks group.
   To post to this group, send email to algoge...@googlegroups.com.
   To unsubscribe from this group, send email to
   algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from 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: Duplicate in an array

[ligerdave]

@Mukesh what's not known? in the problem, it stated an array of
positive numbers

On Oct 6, 11:47 am, Mukesh Gupta mukeshgupta.2...@gmail.com wrote:
 @Ankit: Insertion in hashmap in O(n) in worst case. As long as range of the
 numbers is not known we cannot predict whether the algo will run in linear
 time.
 Any other idea for O(n)??

 Mukesh Gupta
 Delhi College of Engineering



 On Wed, Oct 6, 2010 at 4:32 PM, sourav souravs...@gmail.com wrote:
  @Mukesh

  Thanks for your attempt. But the question asks for liner or sublinear
  solution.

  Sourav

  On Oct 6, 3:50 pm, Mukesh Gupta mukeshgupta.2...@gmail.com wrote:
   Keep inserting elements in a binary search tree and break once you get
   the find the element in the tree.
   Complexity=O(n log n)

   On 10/5/10, sourav souravs...@gmail.com wrote:

You are given an array of positive numbers in which one number is
repeated. Rest all are present only once. Find the duplicate number in
linear or sub linear time.

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

   --

   Mukesh Gupta
   Delhi College of Engineering

  --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algoge...@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from 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: Duplicate in an array

[ligerdave]

@nishaanth

hashing=O(n^2)? what kinda of hashing are we talking about?

array w/ range of the numbers? you meant smallest and the biggest?
so you have to scan through the given numbers first to find the range.
if you scanned, why not find the duplication in the first place?

okay, lets say you are given the smallest and the biggest. 4 and 44,
you would have an array size that's more than the size of given
numbers. what if the given set is 1, 100, 1?


On Oct 15, 12:53 pm, nishaanth nishaant...@gmail.com wrote:
 @ankit and lingerdave How does hashing help here ?? i say we have to
 create an array size which is there
 range of the numbers...else it cant be solved in O(n)

 Hashing is not helpful here in worst case hashing may lead to a O(n2)
 solution as all the keys may hash into the same place

 eg.. 4,14,24,34,44,4

 if h(n)= n mod 100

 On Sun, Oct 10, 2010 at 5:51 PM, Mridul Malpani 
 malpanimri...@gmail.comwrote:





  can this problem be solved in O(n) time and in O(1) space?

  On Oct 6, 10:41 pm, ligerdave david.c...@gmail.com wrote:
   @mukesh, nope, you do not need to know the range. are you thinking
   about array? ankit's solution is the implementation of bucket
   logic.

   On Oct 6, 11:47 am, Mukesh Gupta mukeshgupta.2...@gmail.com wrote:

@Ankit: Insertion in hashmap in O(n) in worst case. As long as range of
  the
numbers is not known we cannot predict whether the algo will run in
  linear
time.
Any other idea for O(n)??

Mukesh Gupta
Delhi College of Engineering

On Wed, Oct 6, 2010 at 4:32 PM, sourav souravs...@gmail.com wrote:
 @Mukesh

 Thanks for your attempt. But the question asks for liner or sublinear
 solution.

 Sourav

 On Oct 6, 3:50 pm, Mukesh Gupta mukeshgupta.2...@gmail.com wrote:
  Keep inserting elements in a binary search tree and break once you
  get
  the find the element in the tree.
  Complexity=O(n log n)

  On 10/5/10, sourav souravs...@gmail.com wrote:

   You are given an array of positive numbers in which one number is
   repeated. Rest all are present only once. Find the duplicate
  number in
   linear or sub linear time.

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

  --

  Mukesh Gupta
  Delhi College of Engineering

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

 --
 S.Nishaanth,
 Computer Science and engineering,
 IIT Madras.

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

[algogeeks] Re: missing 2 nums in an array

[ligerdave]

i think you need to define whether the array is in a sorted order or
not.

some solutions work on both, but if you want the optimized solution,
more information is needed


On Oct 11, 2:59 pm, Asquare anshika.sp...@gmail.com wrote:
 Given an array of size n. It contains numbers in the range 1 to n.
 Each number is present at least once except for 2 numbers.
 Find the missing numbers.

 I know of a solution using another array to store frequency of each
 number..
 But this holds for than 2 nums also..
 So Is there any other solution apart from this specific for 2 nums and
 of lesser complexity..??

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from 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: wiki issue on dijkstra's algorithm

[ligerdave]

@krunal that's just different representation

On Oct 11, 9:26 am, Krunal Modi krunalam...@gmail.com wrote:
 Each edge will have a cost not the nodes(vertices).
 Upload an image 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 algoge...@googlegroups.com.
To unsubscribe from 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: wiki issue on dijkstra's algorithm

[ligerdave]

@Ercan exactly. so do you also find the wiki somewhat misleading?
especially the animation? looks to me when it finds the min, it stops
and reset the start node to be the min and start over again.

or,

if you have more vertices between nodes in my example above, you are
able to find the shortest path by following wiki steps.

On Oct 12, 2:05 am, Gönenç Ercan gon...@gmail.com wrote:
 Dijkstra's algorithm is a dynamic programming algorithm. no matter
 which path is first discovered, the relax operation (if the new path
 is shorter update the path to the node, step 3) will find the correct
 answer in the end. The smallest distance criteria, which selects the
 next current node (step 5) ensures that an already visited node can
 not be relaxed (no shorter path to there). One big mistake is,
 terminating the algorithm when the destination node is reached. The
 first path discovered is not necessarily the correct solution. Your
 problem in particular is that, you are choosing the smallest distance
 node only from the path you are discovering. So lets trace this
 algorithm.

 Assume that vertices are letters from bottom to up, left to right; A,
 B, C, D, E, F

 A - B,C (discovered costs 7, 4) A is marked as visited
 C - E (discovered cost is 13) C is marked as visited
 Remember that we choose the smallest distance to initial node. one of
 the nodes B or E (costs: 7 or 13)
 B - D (discovered, cost 9)  B is marked as visited
 D- F (discovered, cost 10) D is marked as visited
  We should nt stop here, we still have unvisited node E. In
 this example E does not relax the path to F, but it should be checked
 in general or the solution may not be minimal.
 E - F (already discovered, its current cost is 10, since 14 is not
 smaller, no relax operation)

 All nodes are visited, we are done. Output the path A - B - D - F

 On Oct 6, 5:47 pm, ligerdave david.c...@gmail.com wrote:



  so i was reading a href=http://en.wikipedia.org/wiki/
  Dijkstra's_algorithmwiki/a on dijkstra's algorithm for finding
  shortest path. i dont think article specifically define the
  requirements of the graph in order to make the algorithm working
  properly.(unless i missed something?)

  for instance, in the graph below, the shortest path from 1to1 should
  be 1721. however, by following dijkstra's, you would get 1491
  because compared to 7, 4 is smallest among all direct vertices.

      1
    /   \
  2      9
  |        |
  7      4
    \   /
      1

  anyone knows the requirements, especially the ration of #of edges to
  #of vertices?

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from 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: Least fare for a return trip Algorithm

[ligerdave]

sorting is absolutely required. w/o the sorting, how are you going to
find the min? comparison is also a sorting algorithm.
it also depends on how many suggestions you wanna have. if it's just
the best deal, you can complete this in O(n+m) where n is the number
of different fares of trip to and m is the trip back

On Oct 12, 9:06 am, Amod gam...@gmail.com wrote:
 Suppose there are 100 flights from A to B and 1000 flights from B to
 A.
 Now a user selects the round trip from A to B and back to A, the site
 presents suggestions based on the least fare of the return journey.
 Could someone please help me to device and algorithm where based on
 number of suggestions   the results are displayed.
 ex
        A-B         B-A
 A1     1        B1    1
 A2     2        B2    3
 A3     4        B3    5
 A4     6        B4    8

 So if i want four suggestions then A1+B1, A2+B1, A1+B2, A2+B2

 Please also suggest whether sorting based on fares is required or not

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from 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 Question: Find kth largest of sum of elements in 2 array

[ligerdave]

@sourav


I think the best way to explain my logic is to draw a 2D matrix

   5  4  2  1
6
5
4
2

then you would find the patten. i have something draw on the paper. if
you need, i guess i can scan and send it out


On Oct 7, 10:05 am, sourav souravs...@gmail.com wrote:
 @lingerdave

 If you get the larget element from the 2 arrays
 A - 5, 4, 2, 1
 B - 6, 5, 4, 2,

 say 6, do not underestimate the next element in A. The difference
 between the first two elements in A may be less and 2nd element in A
 may be string enough to make itself plus an element in B greater than
 first element in A plus kth element in B. More so if elements in B are
 very small after first few. for example see example

 A- 100, 99,
 B- 50,9,2,1,1

 Here A[i] + B[1} is largest but A[2]+B[1] is much larger than
 A[2]+B[2].

 Sourav

 On Oct 7, 6:22 pm, ligerdave david.c...@gmail.com wrote:



  @ Ercan,

  yes, you were right. i forgot about that.
  anyway, that's the idea. you would need to move pointers on both,
  depends on which is bigger. for loop w/ i=k, when the loop stops, you
  have the pointers pointing at the numbers you wanted

  On Oct 6, 7:16 pm, Gönenç Ercan gon...@gmail.com wrote:

   A - 5, 4, 2, 1
   B - 6, 5, 4, 2, 1

   k = 3,

   ignoring duplicates, the answer is 9 (a=5, b=4) but doesn't the
   algorithm below give 8 (a=2, b=6)?

   On Oct 6, 9:06 pm, ligerdave david.c...@gmail.com wrote:

use pointers and lengths of two arrays. depends on what K is, if K
m*n/2, you reverse the pointers. therefore, the worst case is either
O(m) when length of m is shorter or O(n) when length of n is
shorter,

make the pointers pointing to the first elements in both arrays.

A)
4,3,2,2,1
^

B)
5,3,2,1
^

compare them to find out which one is larger, here 5 is larger than 4.
by definition, you know 5 would be bigger than any elements in array
A, and sum of 5 with kth element of array A (here, kth = A.length)
will be the one(kth largest sum(a+b) overall) you are looking for.

if kA.length, shift the pointer of B one number to the right and
repeat the same process.

like i said, if the k m*n/2, start from small

On Oct 6, 6:34 am, sourav souravs...@gmail.com wrote:

 you are given 2 arrays sorted in decreasing order of size m and n
 respectively.

 Input: a number k = m*n and = 1

 Output: the kth largest sum(a+b) possible. where
 a (any element from array 1)
 b (any element from array 2)

 The Brute force approach will take O(n*n). can anyone find a better
 logic. thnkx in advance.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from 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 Question: Find kth largest of sum of elements in 2 array

[ligerdave]

@ Ercan,

yes, you were right. i forgot about that.
anyway, that's the idea. you would need to move pointers on both,
depends on which is bigger. for loop w/ i=k, when the loop stops, you
have the pointers pointing at the numbers you wanted

On Oct 6, 7:16 pm, Gönenç Ercan gon...@gmail.com wrote:
 A - 5, 4, 2, 1
 B - 6, 5, 4, 2, 1

 k = 3,

 ignoring duplicates, the answer is 9 (a=5, b=4) but doesn't the
 algorithm below give 8 (a=2, b=6)?

 On Oct 6, 9:06 pm, ligerdave david.c...@gmail.com wrote:



  use pointers and lengths of two arrays. depends on what K is, if K
  m*n/2, you reverse the pointers. therefore, the worst case is either
  O(m) when length of m is shorter or O(n) when length of n is
  shorter,

  make the pointers pointing to the first elements in both arrays.

  A)
  4,3,2,2,1
  ^

  B)
  5,3,2,1
  ^

  compare them to find out which one is larger, here 5 is larger than 4.
  by definition, you know 5 would be bigger than any elements in array
  A, and sum of 5 with kth element of array A (here, kth = A.length)
  will be the one(kth largest sum(a+b) overall) you are looking for.

  if kA.length, shift the pointer of B one number to the right and
  repeat the same process.

  like i said, if the k m*n/2, start from small

  On Oct 6, 6:34 am, sourav souravs...@gmail.com wrote:

   you are given 2 arrays sorted in decreasing order of size m and n
   respectively.

   Input: a number k = m*n and = 1

   Output: the kth largest sum(a+b) possible. where
   a (any element from array 1)
   b (any element from array 2)

   The Brute force approach will take O(n*n). can anyone find a better
   logic. thnkx in advance.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from 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: wiki issue on dijkstra's algorithm

[ligerdave]

anyone here?

On Oct 6, 10:47 am, ligerdave david.c...@gmail.com wrote:
 so i was reading a href=http://en.wikipedia.org/wiki/
 Dijkstra's_algorithmwiki/a on dijkstra's algorithm for finding
 shortest path. i dont think article specifically define the
 requirements of the graph in order to make the algorithm working
 properly.(unless i missed something?)

 for instance, in the graph below, the shortest path from 1to1 should
 be 1721. however, by following dijkstra's, you would get 1491
 because compared to 7, 4 is smallest among all direct vertices.

     1
   /   \
 2      9
 |        |
 7      4
   \   /
     1

 anyone knows the requirements, especially the ration of #of edges to
 #of vertices?

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

[ligerdave]

use pointer. shift to left if one more leading char has been found.
any unmatched char resets the pointer to first char

once you went through the entire list(first one), the pointer on the
second list tells you where to concatenate

that gives you O(n) where n is the length of first list

On Oct 7, 3:52 am, snehal jain learner@gmail.com wrote:
 There are two linked list, both containing a character in each node.

 If one linked list contain characters  o x e n c and second contain
 characters e n c a r t a then the final linked list should contain o x
 e n c a r t a    i.e. if the end of one list is same as the start of
 second then those characters should come only once.

 can we do it in O(n+m) where n and m are the length of list. both are
 singly link list.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from 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] wiki issue on dijkstra's algorithm

[ligerdave]

so i was reading a href=http://en.wikipedia.org/wiki/
Dijkstra's_algorithmwiki/a on dijkstra's algorithm for finding
shortest path. i dont think article specifically define the
requirements of the graph in order to make the algorithm working
properly.(unless i missed something?)

for instance, in the graph below, the shortest path from 1to1 should
be 1721. however, by following dijkstra's, you would get 1491
because compared to 7, 4 is smallest among all direct vertices.


1
  /   \
2  9
||
7  4
  \   /
1


anyone knows the requirements, especially the ration of #of edges to
#of vertices?

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

[ligerdave]

yes, think about the logic working behind bucket sort.

we assume in this problem, memory space is inf

all you need to do is put all numbers in its own bucket

when a number was pushed into one bucket which had already been
occupied, you have the duplicated number there.

when you run to n-1 number, you know all the numbers so far are
unique(coz duplication hadn't happened). by definition of the problem,
you have only one duplicated number. therefore, the last number is
duplicated.

O(2(n-1))  O(n)


On Oct 5, 7:41 am, sourav souravs...@gmail.com wrote:
 You are given an array of positive numbers in which one number is
 repeated. Rest all are present only once. Find the duplicate number in
 linear or sub linear time.

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

[ligerdave]

yes, it can be done in O(n).

think about the logic working behind bucket sort.
we assume in this problem, memory space is inf
all you need to do is put all numbers in its own bucket
when a number was pushed into one bucket which had already been
occupied, you have the duplicated number there.
when you run to n-1 number, you know all the numbers so far are
unique(coz duplication hadn't happened). by definition of the
problem,
you have only one duplicated number. therefore, the last number is
duplicated.
O(2(n-1))  O(n)

On Oct 6, 7:08 am, tech rascal techrascal...@gmail.com wrote:
 can u do dis problem in linear time, o(n)??

 On Wed, Oct 6, 2010 at 4:20 PM, Mukesh Gupta 
 mukeshgupta.2...@gmail.comwrote:



  Keep inserting elements in a binary search tree and break once you get
  the find the element in the tree.
  Complexity=O(n log n)

  On 10/5/10, sourav souravs...@gmail.com wrote:
   You are given an array of positive numbers in which one number is
   repeated. Rest all are present only once. Find the duplicate number in
   linear or sub linear time.

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

  --

  Mukesh Gupta
  Delhi College of Engineering

  --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algoge...@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from 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: coin changing problem

[ligerdave]

use mod recursively.

total money(or reminder) mod denomination(big  small)



On Oct 5, 7:13 pm, pre lak pre.la...@gmail.com wrote:
 Hi all,

 Pls help me with the solution to the following problem related to the coin
 changing problem.

 suppose that the available coins a ein the denominations c^0, c^1 , c^2...
 c^k for some intgers  c1 and k=1. show tht the greedy algorithm always
 yeilds an optimal solution

 thanks in advance
 Preethi

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

[ligerdave]

@mukesh, nope, you do not need to know the range. are you thinking
about array? ankit's solution is the implementation of bucket
logic.


On Oct 6, 11:47 am, Mukesh Gupta mukeshgupta.2...@gmail.com wrote:
 @Ankit: Insertion in hashmap in O(n) in worst case. As long as range of the
 numbers is not known we cannot predict whether the algo will run in linear
 time.
 Any other idea for O(n)??

 Mukesh Gupta
 Delhi College of Engineering



 On Wed, Oct 6, 2010 at 4:32 PM, sourav souravs...@gmail.com wrote:
  @Mukesh

  Thanks for your attempt. But the question asks for liner or sublinear
  solution.

  Sourav

  On Oct 6, 3:50 pm, Mukesh Gupta mukeshgupta.2...@gmail.com wrote:
   Keep inserting elements in a binary search tree and break once you get
   the find the element in the tree.
   Complexity=O(n log n)

   On 10/5/10, sourav souravs...@gmail.com wrote:

You are given an array of positive numbers in which one number is
repeated. Rest all are present only once. Find the duplicate number in
linear or sub linear time.

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

   --

   Mukesh Gupta
   Delhi College of Engineering

  --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algoge...@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from 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 Question: Find kth largest of sum of elements in 2 array

[ligerdave]

use pointers and lengths of two arrays. depends on what K is, if K
m*n/2, you reverse the pointers. therefore, the worst case is either
O(m) when length of m is shorter or O(n) when length of n is
shorter,


make the pointers pointing to the first elements in both arrays.

A)
4,3,2,2,1
^

B)
5,3,2,1
^

compare them to find out which one is larger, here 5 is larger than 4.
by definition, you know 5 would be bigger than any elements in array
A, and sum of 5 with kth element of array A (here, kth = A.length)
will be the one(kth largest sum(a+b) overall) you are looking for.

if kA.length, shift the pointer of B one number to the right and
repeat the same process.

like i said, if the k m*n/2, start from small






On Oct 6, 6:34 am, sourav souravs...@gmail.com wrote:
 you are given 2 arrays sorted in decreasing order of size m and n
 respectively.

 Input: a number k = m*n and = 1

 Output: the kth largest sum(a+b) possible. where
 a (any element from array 1)
 b (any element from array 2)

 The Brute force approach will take O(n*n). can anyone find a better
 logic. thnkx in advance.

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

[ligerdave]

complete solution:

int change(stackint denominations, int total){

  int coin = denominations.pop();
  int reminder = total % coin;

  if(reminder == total) return 0; // in case you dont have a perfect
change

  int numberOfCoins = (total-reminder)/coin;

  if(reminder == 0) return numberOfCoins;
  else return numberOfCoins + change(denominations, reminder);

}

On Oct 6, 11:01 am, ligerdave david.c...@gmail.com wrote:
 use mod recursively.

 total money(or reminder) mod denomination(big  small)

 On Oct 5, 7:13 pm, pre lak pre.la...@gmail.com wrote:



  Hi all,

  Pls help me with the solution to the following problem related to the coin
  changing problem.

  suppose that the available coins a ein the denominations c^0, c^1 , c^2...
  c^k for some intgers  c1 and k=1. show tht the greedy algorithm always
  yeilds an optimal solution

  thanks in advance
  Preethi

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from 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: Sort in Linear time O(n)

[ligerdave]

with a data structure, you can definitely achieve O(N) where N != kN,
N is the length of the number.

On Oct 2, 1:02 pm, Harshal ..Bet oN iT!! hc4...@gmail.com wrote:
 you are given n integers in the range 0 to n3-1 ((n to the power 3) - 1) .
 how can u sort the numbers in O(n)?

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

[ligerdave]

First, if you have a set of unique usernames, those could be used to
be keys. How to generate hash is depends on your requirements. You can
add a few prefix chars or postfix

On Sep 30, 2:45 pm, amit amitjaspal...@gmail.com wrote:
 Design a hash table to store phone #s. Your job is to write a hash
 function that has a parameter username, and generate a key. Username
 is unique, length 5 and can be A-Z, 0-9, space. Write a hash function
 that generate keys without collisions and use minimum memory.

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

[ligerdave]

since this only allows you to go right or down, the easiest(easy to
understand) way is to draw a binary tree, then you will have a pretty
good view on what you have to do. basically recursion from top going
down(return the end node(bottom) and compare left and right

On Sep 30, 5:27 am, Christi Massey masseychri...@gmail.com wrote:
 A table composed of N*M cells,each having a certain quantity of apples, is
 given. you start from the upper-left corner. At each step you can go down or
 right one cell.Design an algorithm to find the maximum number of apples you
 can collect ,if you are moving from upper-left corner to bottom-right
 corner.

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

[ligerdave]

it depends on whether N strings are a subset of a finite set of
strings and the hash function.

collision happens when

# of keys  # of H(keys)

by following that, you dont even need an algorithm to find the
collision.

otherwise, there would always be up to N additional storage becoz you
need to generate the hash first unless you know how to hack the hash
function.
i think it's always speed vs. space

@saurabh i would love to know about the bit string solution



On Sep 27, 1:07 pm, AdrianW atw...@gmail.com wrote:
 Suppose you have N strings that can be generated on-the-fly, and you
 wanted to discover if a hash function generates any collisions.  Is
 there a way to do this without O(N) storage?

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

[ligerdave]

that will be

12 23 34 1 0 1c1

what's the some related problem?

only last char in the group represent the char, leading chars
represent the number of the repeated char. space(or whatever you like
it to be) is the separator of groups. when you see space, replace w/
'\t'.

On Sep 28, 2:58 am, umesh kewat umesh1...@gmail.com wrote:
 still there is some problem related to numbers encoding like..

 22333101 here how will u  going to
 encode it???





 On Tue, Sep 28, 2010 at 1:38 AM, ligerdave david.c...@gmail.com wrote:
  it's a compression problem. using hex instead of oct saves more space

  00aaa0ss  yyy = 50 2a 0 1s 3f 1\s ay

  On Sep 15, 8:21 am, bittu shashank7andr...@gmail.com wrote:
   A file is given with many 0s stored in continuous way , store it in
   another file such that when you store try saving the space by using
   minimum amount of space. When you want to create the original file ,
   you should be able to do so with the new file created

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

 --
 Thanks  Regards

 Umesh kewat

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

[ligerdave]

any type of replace would need at least one extra memory space.

recursion is the worst, depends how you implement recursion. one
iteration might depends on another, which depends one other, and so
on.. each iteration hold its own stack

On Sep 23, 1:59 pm, Albert alberttheb...@gmail.com wrote:
 How to reverse a String using recursion in C without using any extra
 memory?

 the question seems to be simple.

 char* strrev(char *)
 {
     ...
     ...
     ...

 }

 Try to give all the answers for this prototype.

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

[ligerdave]

it's a compression problem. using hex instead of oct saves more space

00aaa0ss  yyy = 50 2a 0 1s 3f 1\s ay

On Sep 15, 8:21 am, bittu shashank7andr...@gmail.com wrote:
 A file is given with many 0s stored in continuous way , store it in
 another file such that when you store try saving the space by using
 minimum amount of space. When you want to create the original file ,
 you should be able to do so with the new file created

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