[algogeeks] Re: Hash Table Design
Use a trie, the memory needed will be less than having a list of strings and it will be faster than hashTable (array implementation of trie). Check Trie in Wikipedia. If the datastructure is going to be static, then using a Directed acyclic finite automata (dafsa) may be even better. On Sep 30, 9: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.
Re: Fwd: [algogeeks] Prim's algorithm using min heap
That's kind of a nice hint. Rather then asking: Where is the link!? On Oct 1, 7:10 pm, Soundar wrote: > i couldn't find any link here. -- 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.
Re: Fwd: [algogeeks] Prim's algorithm using min heap
i couldn't find any link here. -- 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: How will you find the subarray whose product is k in an array of negative and positive numbers
Well, instead of continuously storing the maximum product, you try to equate the product to k, if and when you do, you've found your sub array. To make it faster you can add another condition that when the product > k, stop and move to the next element (provided you've sorted the elements first) I can't see a way to do this in O(n). Anyone? On Sep 30, 4:57 pm, abhishek singh wrote: > @ Minotauraus > * > * > *but here we are not going to find maximum product subarray, we are finding > here the subarray whose product is k. > * > correct me if i am wrong > > > > > > > > > > On Thu, Sep 30, 2010 at 9:35 PM, Minotauraus wrote: > > I guess you could use Kadane's algo replacing addition with > > multiplication. > >http://en.wikipedia.org/wiki/Maximum_subarray_problem > > > On Sep 30, 8:08 am, Abhishek Kumar Singh > > wrote: > > > How will you find the subarray whose product is k in an array of > > > negative and positive numbers > > > > efficient algorithm is to be considered, it will be better if time > > > complexity is 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 > .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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Minimum ladders required
It is the maximum number of overlapping flights. Sort the all the times in a single array, increment a counter when a plane lands, decrement when it flies. The other algorithm I think can be by assigning the maximum number of flights to different ladders until all flights are assigned. To assign a ladder maximum number of flights, sort with respect to fly times (finish), assign the first compatible flight (not lands before last assigned flight flies). After processing all the flights if there are more unassigned flights, than you add a ladder and repeat the process. Both algorithms are linear, but if you also need a ladder assignment this might work for you. On Oct 1, 2:48 pm, Dave wrote: > You need to move from one arrival-or-departure-time to another in > order throughout the day. An arrival means that another ladder is put > into use, while a departure takes a ladder out of use. Here is an > efficient algorithm to do that: > > Form a min-heap of the arrival times. Include the departure time and a > flag in the heap as to whether the heap condition is based on the > arrival time or a departure time. (See below) > > Set number_of_ladders_in_use = 0, number_of_ladders_required = 0. > > Loop until the heap is empty: > Look at the top heap item. > If it is an arrival time: > Increment number_of_ladders_in_use. > number_of_ladders_required = max(number_of_ladders_required, > number_of_ladders_in_use). > Replace the arrival time by the departure time and set the > flag accordingly. > Restore the min-heap condition (see below). > Else // it is a departure time > Decrement number_of_ladders_in_use. > Delete the top entry in the min-heap. > Restore the min-heap condition (see below). > > When the heap is empty, number_of_ladders_required is the minimum > number of ladders required. > > Note: When restoring the min-heap condition, break ties between > identical arrival and departure times based on whether the ladder can > be moved instantly from one plane to another. E.g., if a plane departs > at noon and another arrives at noon, put the departure first in the > heap if the same ladder can be used for both, but put the arrival > first if it takes time to move the ladder from one plane to another, > in which case the same ladder cannot be used. > > Dave > > On Oct 1, 5:31 am, mac adobe wrote: > > > correcting ... Its minimum numbers of ladders required > > > Please suggest how you think for this problem > > Suppose you have many airplanes . Each plane needs a ladder so > > that people can board the plane easily . > > Now plane will land at time land_time and then fly away again at fly_time . > > During this time , people will continue to board the plane and the > > ladder should remain attached to the plane. So if plane lands at 3 am and > > fly at 3 pm , we need a ladder from 3 am to 3 pm dedicated for that plane. > > Given land_time and fly_time of multiple planes in a day , find the > > minimum > > number of ladders your require . > > > --mac > > > On Fri, Oct 1, 2010 at 3:56 PM, Yan Wang wrote: > > > I think your question should be to find the minimum number of ladders > > > required. > > > > This is a very classic Greedy-Algorithm solved problem. Please refer > > > to Chapter 4 of book "Algorithm Design". > > > > On Fri, Oct 1, 2010 at 2:32 AM, mac adobe wrote: > > > > Hi > > > > Please suggest how you think for this problem > > > > Suppose you have many airplanes . Each plane needs a ladder so > > > > that people can board the plane easily . > > > > Now plane will land at time land_time and then fly away again at > > > > fly_time > > > . > > > > During this time , people will continue to board the plane and the > > > > ladder should remain attached to the plane. So if plane lands at 3 am > > > > and > > > > fly at 3 pm , we need a ladder from 3 am to 3 pm dedicated for that > > > plane. > > > > Given land_time and fly_time of multiple planes in a day , find the > > > minimum > > > > number of ladders your require . > > > > > --mac > > > > > -- > > > > 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. > > > > -- > > > 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.-Hide quoted text - > > > - Show quoted text - -- You received this message because you are s
[algogeeks] Re: Minimum ladders required
You need to move from one arrival-or-departure-time to another in order throughout the day. An arrival means that another ladder is put into use, while a departure takes a ladder out of use. Here is an efficient algorithm to do that: Form a min-heap of the arrival times. Include the departure time and a flag in the heap as to whether the heap condition is based on the arrival time or a departure time. (See below) Set number_of_ladders_in_use = 0, number_of_ladders_required = 0. Loop until the heap is empty: Look at the top heap item. If it is an arrival time: Increment number_of_ladders_in_use. number_of_ladders_required = max(number_of_ladders_required, number_of_ladders_in_use). Replace the arrival time by the departure time and set the flag accordingly. Restore the min-heap condition (see below). Else // it is a departure time Decrement number_of_ladders_in_use. Delete the top entry in the min-heap. Restore the min-heap condition (see below). When the heap is empty, number_of_ladders_required is the minimum number of ladders required. Note: When restoring the min-heap condition, break ties between identical arrival and departure times based on whether the ladder can be moved instantly from one plane to another. E.g., if a plane departs at noon and another arrives at noon, put the departure first in the heap if the same ladder can be used for both, but put the arrival first if it takes time to move the ladder from one plane to another, in which case the same ladder cannot be used. Dave On Oct 1, 5:31 am, mac adobe wrote: > correcting ... Its minimum numbers of ladders required > > Please suggest how you think for this problem > Suppose you have many airplanes . Each plane needs a ladder so > that people can board the plane easily . > Now plane will land at time land_time and then fly away again at fly_time . > During this time , people will continue to board the plane and the > ladder should remain attached to the plane. So if plane lands at 3 am and > fly at 3 pm , we need a ladder from 3 am to 3 pm dedicated for that plane. > Given land_time and fly_time of multiple planes in a day , find the > minimum > number of ladders your require . > > --mac > > > > On Fri, Oct 1, 2010 at 3:56 PM, Yan Wang wrote: > > I think your question should be to find the minimum number of ladders > > required. > > > This is a very classic Greedy-Algorithm solved problem. Please refer > > to Chapter 4 of book "Algorithm Design". > > > On Fri, Oct 1, 2010 at 2:32 AM, mac adobe wrote: > > > Hi > > > Please suggest how you think for this problem > > > Suppose you have many airplanes . Each plane needs a ladder so > > > that people can board the plane easily . > > > Now plane will land at time land_time and then fly away again at fly_time > > . > > > During this time , people will continue to board the plane and the > > > ladder should remain attached to the plane. So if plane lands at 3 am and > > > fly at 3 pm , we need a ladder from 3 am to 3 pm dedicated for that > > plane. > > > Given land_time and fly_time of multiple planes in a day , find the > > minimum > > > number of ladders your require . > > > > --mac > > > > -- > > > 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. > > > -- > > 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.- 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: Minimum ladders required
You can use a sweep like algorithm for that. 1) you sort the land_time,fly_away time points increasingly in time 2) You initialize a counter representing the number of ladders you need at the current time of the sweep line. 3) You process the sorted time time points, when you encounter a "land_time" point you do counter++ and when it is a "fly_away" counter-- 4) The maximum value the counter has reached is the minimum ladder you need (at the peak time). Pierre On Oct 1, 12:32 pm, mac adobe wrote: > @ Yang .. can you please share book authors so that i can refer .. . > > Please share some insight also .. it will help me understand it. > > --mac > > > > On Fri, Oct 1, 2010 at 4:01 PM, mac adobe wrote: > > correcting ... Its minimum numbers of ladders required > > > Please suggest how you think for this problem > > Suppose you have many airplanes . Each plane needs a ladder so > > that people can board the plane easily . > > Now plane will land at time land_time and then fly away again at fly_time > > . > > During this time , people will continue to board the plane and the > > ladder should remain attached to the plane. So if plane lands at 3 am and > > fly at 3 pm , we need a ladder from 3 am to 3 pm dedicated for that plane. > > Given land_time and fly_time of multiple planes in a day , find the > > minimum > > number of ladders your require . > > > --mac > > > On Fri, Oct 1, 2010 at 3:56 PM, Yan Wang wrote: > > >> I think your question should be to find the minimum number of ladders > >> required. > > >> This is a very classic Greedy-Algorithm solved problem. Please refer > >> to Chapter 4 of book "Algorithm Design". > > >> On Fri, Oct 1, 2010 at 2:32 AM, mac adobe wrote: > >> > Hi > >> > Please suggest how you think for this problem > >> > Suppose you have many airplanes . Each plane needs a ladder so > >> > that people can board the plane easily . > >> > Now plane will land at time land_time and then fly away again at > >> fly_time . > >> > During this time , people will continue to board the plane and the > >> > ladder should remain attached to the plane. So if plane lands at 3 am > >> and > >> > fly at 3 pm , we need a ladder from 3 am to 3 pm dedicated for that > >> plane. > >> > Given land_time and fly_time of multiple planes in a day , find the > >> minimum > >> > number of ladders your require . > > >> > --mac > > >> > -- > >> > 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.
Re: [algogeeks] Minimum ladders required
@ Yang .. can you please share book authors so that i can refer .. . Please share some insight also .. it will help me understand it. --mac On Fri, Oct 1, 2010 at 4:01 PM, mac adobe wrote: > correcting ... Its minimum numbers of ladders required > > > Please suggest how you think for this problem > Suppose you have many airplanes . Each plane needs a ladder so > that people can board the plane easily . > Now plane will land at time land_time and then fly away again at fly_time > . > During this time , people will continue to board the plane and the > ladder should remain attached to the plane. So if plane lands at 3 am and > fly at 3 pm , we need a ladder from 3 am to 3 pm dedicated for that plane. > Given land_time and fly_time of multiple planes in a day , find the > minimum > number of ladders your require . > > > --mac > > > On Fri, Oct 1, 2010 at 3:56 PM, Yan Wang wrote: > >> I think your question should be to find the minimum number of ladders >> required. >> >> This is a very classic Greedy-Algorithm solved problem. Please refer >> to Chapter 4 of book "Algorithm Design". >> >> On Fri, Oct 1, 2010 at 2:32 AM, mac adobe wrote: >> > Hi >> > Please suggest how you think for this problem >> > Suppose you have many airplanes . Each plane needs a ladder so >> > that people can board the plane easily . >> > Now plane will land at time land_time and then fly away again at >> fly_time . >> > During this time , people will continue to board the plane and the >> > ladder should remain attached to the plane. So if plane lands at 3 am >> and >> > fly at 3 pm , we need a ladder from 3 am to 3 pm dedicated for that >> plane. >> > Given land_time and fly_time of multiple planes in a day , find the >> minimum >> > number of ladders your require . >> > >> > >> > --mac >> > >> > -- >> > 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. >> > >> >> -- >> 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. >> >> > -- 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.
Re: [algogeeks] Minimum ladders required
correcting ... Its minimum numbers of ladders required Please suggest how you think for this problem Suppose you have many airplanes . Each plane needs a ladder so that people can board the plane easily . Now plane will land at time land_time and then fly away again at fly_time . During this time , people will continue to board the plane and the ladder should remain attached to the plane. So if plane lands at 3 am and fly at 3 pm , we need a ladder from 3 am to 3 pm dedicated for that plane. Given land_time and fly_time of multiple planes in a day , find the minimum number of ladders your require . --mac On Fri, Oct 1, 2010 at 3:56 PM, Yan Wang wrote: > I think your question should be to find the minimum number of ladders > required. > > This is a very classic Greedy-Algorithm solved problem. Please refer > to Chapter 4 of book "Algorithm Design". > > On Fri, Oct 1, 2010 at 2:32 AM, mac adobe wrote: > > Hi > > Please suggest how you think for this problem > > Suppose you have many airplanes . Each plane needs a ladder so > > that people can board the plane easily . > > Now plane will land at time land_time and then fly away again at fly_time > . > > During this time , people will continue to board the plane and the > > ladder should remain attached to the plane. So if plane lands at 3 am and > > fly at 3 pm , we need a ladder from 3 am to 3 pm dedicated for that > plane. > > Given land_time and fly_time of multiple planes in a day , find the > minimum > > number of ladders your require . > > > > > > --mac > > > > -- > > 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. > > > > -- > 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. > > -- 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.
Re: [algogeeks] maximum ladders required
I think your question should be to find the minimum number of ladders required. This is a very classic Greedy-Algorithm solved problem. Please refer to Chapter 4 of book "Algorithm Design". On Fri, Oct 1, 2010 at 2:32 AM, mac adobe wrote: > Hi > Please suggest how you think for this problem > Suppose you have many airplanes . Each plane needs a ladder so > that people can board the plane easily . > Now plane will land at time land_time and then fly away again at fly_time . > During this time , people will continue to board the plane and the > ladder should remain attached to the plane. So if plane lands at 3 am and > fly at 3 pm , we need a ladder from 3 am to 3 pm dedicated for that plane. > Given land_time and fly_time of multiple planes in a day , find the maximum > number of ladders your require . > > > --mac > > -- > 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. > -- 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.
Re: Fwd: [algogeeks] Prim's algorithm using min heap
Where is the link?! On Oct 1, 9:31 am, Rashmi Shrivastava wrote: > @soundar,This link may help u... > > -- Forwarded message -- > From: soundar > Date: Thu, Sep 30, 2010 at 12:48 PM > Subject: [algogeeks] Prim's algorithm using min heap > To: Algorithm Geeks > > Please some one provide link or source code for " Prim's algorithm > using min heap" Am having trouble with the implementation > > -- > 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 > athttp://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] maximum ladders required
Hi Please suggest how you think for this problem Suppose you have many airplanes . Each plane needs a ladder so that people can board the plane easily . Now plane will land at time land_time and then fly away again at fly_time . During this time , people will continue to board the plane and the ladder should remain attached to the plane. So if plane lands at 3 am and fly at 3 pm , we need a ladder from 3 am to 3 pm dedicated for that plane. Given land_time and fly_time of multiple planes in a day , find the maximum number of ladders your require . --mac -- 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.
Fwd: [algogeeks] Prim's algorithm using min heap
@soundar,This link may help u... -- Forwarded message -- From: soundar Date: Thu, Sep 30, 2010 at 12:48 PM Subject: [algogeeks] Prim's algorithm using min heap To: Algorithm Geeks Please some one provide link or source code for " Prim's algorithm using min heap" Am having trouble with the implementation -- 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. -- 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.
