Re: [algogeeks] Re: Hash Table
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: Hash Table
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.
[algogeeks] Re: Find all possible combination of integers for a given sum
@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 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
Sorry, but this isn't a mysql group. all discussions need to be algorithm related. On Apr 28, 3:04 pm, Aniket 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
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 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 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
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: generate ques set
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 wrote:
> m*k>N . 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 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 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: Application of Prime Number . An Interesting For Geeks
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 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 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..
@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 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 > wrote: > >http://flexaired.blogspot.com/2011/03/big-file-containing-billions-of... > > > On Mon, Mar 21, 2011 at 4:05 AM, Natansh Verma > > 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 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 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 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
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 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
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 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: Design friend of friend function for FB
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 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: Link list Problem
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 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
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 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
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 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
@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 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 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.com > .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: Yahoo coding round question
@ravindra
agree!
On Oct 24, 2:20 pm, ravindra patel 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 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 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 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
> >> 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 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
[algogeeks] Re: Yahoo coding round question
@Kishen
i think parallel computation means when you have two tasks, instead
having only one person working on both, you have two persons working
simultaneously. however, that doesnt mean you dont have to do the job
right? the problem isn't in the inner loop.
when you have one loop inside of another loop, you general would have
n^2. again, we are talking about bigO, which means the worst time
On Oct 21, 10:47 pm, Kishen Das 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 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 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 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 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.com > > > > >> .com>
> >
> > > >
> > > > > >>
[algogeeks] Re: 10 most repeating words
@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 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 wrote: > > > > > > > > > for a large file, you probably would want to use external sort. kinda > > like a map-reduce concept. it's actually how sort&uniq 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..." 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: 10 most repeating words
for a large file, you probably would want to use external sort. kinda like a map-reduce concept. it's actually how sort&uniq 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..." 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: linked lists
@asquare basically i just added a flag to enable the "window slide". good catch btw! On Oct 20, 7:55 am, Asquare 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
@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 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
@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 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 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 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 > >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.com > > >> .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.com > > > .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 > .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
what if two elements are not next to each other. would it work? On Oct 20, 8:19 am, "juver++" 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 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: Yahoo coding round question
@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 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
> 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.com >> .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.com > .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: Yahoo coding round question
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 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: Duplicate in an array
@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 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 > wrote: > > > > > > > can this problem be solved in O(n) time and in O(1) space? > > > On Oct 6, 10:41 pm, ligerdave 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 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 wrote: > > > > > @Mukesh > > > > > > Thanks for your attempt. But the question asks for liner or sublinear > > > > > solution. > > > > > > Sourav > > > > > > On Oct 6, 3:50 pm, Mukesh Gupta 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 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 > > > > > > .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.com > > > > .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 > .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: Duplicate in an array
@Mukesh what's not known? in the problem, it stated "an array of positive numbers" On Oct 6, 11:47 am, Mukesh Gupta 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 wrote: > > @Mukesh > > > Thanks for your attempt. But the question asks for liner or sublinear > > solution. > > > Sourav > > > On Oct 6, 3:50 pm, Mukesh Gupta 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 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 > > > .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.com > .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
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 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 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.
>
> > #include
> > #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;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;i%3d ", s[i].a, s[i].b,
> > s[i].value);
>
> > return 0;
>
> > }
>
> > -Arun
>
> > On Thu, Oct 14, 2010 at 1:25 PM, Harshal 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.com > > .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: Least fare for a return trip Algorithm
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 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: wiki issue on dijkstra's algorithm
@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 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 wrote: > > > > > so i was reading http://en.wikipedia.org/wiki/ > > Dijkstra's_algorithm">wiki 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 1>7>2>1. however, by following dijkstra's, you would get 1>4>9>1 > > 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: wiki issue on dijkstra's algorithm
@krunal that's just different representation On Oct 11, 9:26 am, Krunal Modi 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: missing 2 nums in an array
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 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: Google Question: Find kth largest of sum of elements in 2 array
@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 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 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 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 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 k>A.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 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: linked lists
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 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] Re: wiki issue on dijkstra's algorithm
anyone here? On Oct 6, 10:47 am, ligerdave wrote: > so i was reading http://en.wikipedia.org/wiki/ > Dijkstra's_algorithm">wiki 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 1>7>2>1. however, by following dijkstra's, you would get 1>4>9>1 > 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: Google Question: Find kth largest of sum of elements in 2 array
@ 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 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 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 k>A.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 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
complete solution:
int change(stack 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 wrote:
> use mod recursively.
>
> total money(or reminder) mod denomination(big > small)
>
> On Oct 5, 7:13 pm, pre lak 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 c>1 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: Google Question: Find kth largest of sum of elements in 2 array
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 k>A.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 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: Duplicate in an array
@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 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 wrote: > > @Mukesh > > > Thanks for your attempt. But the question asks for liner or sublinear > > solution. > > > Sourav > > > On Oct 6, 3:50 pm, Mukesh Gupta 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 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 > > > .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.com > .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
use mod recursively. total money(or reminder) mod denomination(big > small) On Oct 5, 7:13 pm, pre lak 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 c>1 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
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 wrote: > can u do dis problem in linear time, o(n)?? > > On Wed, Oct 6, 2010 at 4:20 PM, Mukesh Gupta > 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 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 > > .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.com > .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
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 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] wiki issue on dijkstra's algorithm
so i was reading http://en.wikipedia.org/wiki/ Dijkstra's_algorithm">wiki 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 1>7>2>1. however, by following dijkstra's, you would get 1>4>9>1 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: Sort in Linear time O(n)
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!!" 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
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 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
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 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
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 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
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 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 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 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 > .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: Amazon Interview
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 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.
[algogeeks] Re: ReVerse a string using recursion
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 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.
