Hi Amal, Unless one needs to compare array A with many arrays(in this example it is just one), it is not a good idea to spend on constructing aTRIE for A...do you agree?
Siva Amal wrote: > Hey Guys , > I think using a Data structure like TRIE could also be Good solution for > the question . > > Just put the strings of one array into a TRIE and then search for the > strings of the other array. > > The Order will be 2 * O(n * d) approx > where d is the average length of all the strings in an array. > > Amal. > > > On 7/20/06, Bruno Avila <[EMAIL PROTECTED]> wrote: > > > > To sort an array A you could use Radix Sort, which complexity is O(d*n), > > where d = log2(max(A)). So, > > > > sort the first array -> O(d*n) > > sort the second array -> O(e*n) > > > > compare the two arrays -> O(n) > > the solution : (d+e+1)*O(n) = O(n) > > > > Use it only if (d+e+1) is smaller than the hash constant. > > > > Bruno Avila > > > > 2006/7/19, ridvansg <[EMAIL PROTECTED]>: > > > > > > > > L7, > > > from the first array make a hash table H-> O(n) > > > > > > go through the second array and test if the element is present in H1 > > > ->O(n) > > > > > > so the solution is 2*O(n)=O(n) > > > > > > Your solution: > > > sort the first array -> O(n log n) > > > > > > sort the second array -> O( n log n) > > > > > > compare the two arrays -> O(n) > > > > > > the solution : 2*O(n log n) + O(n) = O( n log n) > > > > > > > > > Siva how will you use the B-tree, so you can make one node to > > > correspond to one block in the disk but how will you contro the writing > > > the each node to the disk. This is a issue of low level programing for > > > me. Siva please explain? > > > > > > > > > > > > > > > > > > > ------=_Part_3156_26693476.1153372747917 > Content-Type: text/html; charset=ISO-8859-1 > X-Google-AttachSize: 2191 > > <br> > Hey Guys ,<br> > I think using a Data structure like TRIE could also be Good solution > for the question .<br> > <br> > Just put the strings of one array into a TRIE and then search for the strings > of the other array.<br> > <br> > The Order will be 2 * O(n * d) approx<br> > where d is the average length of all the strings in an array.<br> > <br> > Amal.<br> > <br><br><div><span class="gmail_quote">On 7/20/06, <b > class="gmail_sendername">Bruno Avila</b> <<a href="mailto:[EMAIL > PROTECTED]">[EMAIL PROTECTED]</a>> wrote:</span><blockquote > class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: > 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> > <div>To sort an array A you could use Radix Sort, which complexity is O(d*n), > where d = log2(max(A)). So,<br><br>sort the first array -> O(d*n)<br>sort > the second array -> O(e*n)</div><div><span class="q"><br>compare the two > arrays -> O(n) > <br></span></div><div>the solution : (d+e+1)*O(n) = O(n) > <br><br>Use it only if (d+e+1) is smaller than the hash > constant.<br><br>Bruno Avila<br><br><div><span class="gmail_quote">2006/7/19, > ridvansg <<a href="mailto:[EMAIL PROTECTED]" target="_blank" > onclick="return top.js.OpenExtLink(window,event,this)"> > [EMAIL PROTECTED]</a>>:</span></div><div><span class="e" > id="q_10c893cd49924801_3"><blockquote class="gmail_quote" style="border-left: > 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> > <br>L7,<br>from the first array make a hash table H-> O(n)<br><br>go > through the second array and test if the element is present in > H1<br>->O(n)<br><br>so the solution is 2*O(n)=O(n)<br><br>Your > solution:<br>sort the first array -> O(n log n) > <br><br>sort the second array -> O( n log n)<br><br>compare the two arrays > -> O(n)<br><br>the solution : 2*O(n log n) + O(n) = O( n log > n)<br><br><br>Siva how will you use the B-tree, so you can make one node > to<br> > > correspond to one block in the disk but how will you contro the > writing<br>the each node to the disk. This is a issue of low level programing > for<br>me. Siva please explain?<br><br><br><br> > <br> > <br> > </blockquote></span></div><div></div></div></blockquote></div><br> > > ------=_Part_3156_26693476.1153372747917-- --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
