[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 dave_and_da...@juno.com 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 macatad...@gmail.com 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 wangyanadam1...@gmail.com 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 macatad...@gmail.com 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group.
[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 iiita2007...@gmail.com 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 anike...@gmail.com 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 iiita2007...@gmail.com 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.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ABHISHEK KUMAR SINGH BTECH (INFORMATION TECHNOLOGY) IIIT ALLAHABAD 9956640538 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.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 amitjaspal...@gmail.com wrote: Design a hash table to store phone #s. Your job is to write a hash function that has a parameter username, and generate a key. Username is unique, length 5 and can be A-Z, 0-9, space. Write a hash function that generate keys without collisions and use minimum memory. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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.
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 soundha...@gmail.com 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.
[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 amitjaspal...@gmail.com wrote: Design a hash table to store phone #s. Your job is to write a hash function that has a parameter username, and generate a key. Username is unique, length 5 and can be A-Z, 0-9, space. Write a hash function that generate keys without collisions and use minimum memory. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
