@Gene : nice way of thinking toward the given problem , and now i see similarity b/w this question and m/m allocation example as you have mentioned.i didnt think in this way. :) :)
On Mon, Mar 12, 2012 at 6:35 PM, Gene <gene.ress...@gmail.com> wrote: > This is nearly what malloc() and similar memory allocators do. If you > look at an operating system book or web search you'll get lots of > approaches. The overall problem of finding the best allocation is NP > hard, so you must use some kind of heuristic. The most common ones > are called "First fit" and "Best fit". First fit just keeps a > persistent pointer into the list of trucks with free space. When a > new requirement comes in, the pointer is advanced (with wrapping at > the end of the list) until the first free block (truck with enough > space) is found that is bigger than the requirement. In best fit, the > smallest free block that is no smaller than the requirement is always > selected. In this case you'd normally need a tree or some other > efficient search structure. You might think that best fit would get > better results than first fit, but this often isn't true. This is > because best fit tends to leave many free blocks so small that > requirements can't use them. For this reason in some cases people > even use _worst_ fit. In this case that would be equal to always > selecting the emptiest truck. Since he told you there are many > trucks, this may be the "best" answer. It's a fast strategy. Keeping > track of the trucks by emptiness might be done by maintaining K lists > of trucks where list i holds trucks with ceiling(100i/K) space > remaining. > > This is a good question because there is no "correct" answer. The > interviewer is probably trying to see how you think and approach > difficult problems. If you have the opportunity you should ask lots > of questions: how requests are distributed, whether you can move load > from one truck to another as a last resort to make free space, etc. > > > On Mar 10, 11:32 am, shruthi sharma <shruthi.shar...@gmail.com> wrote: > > Hi, > > > > Im new to algorithms, so this might be a simple question for most of you > > > > Lets say there are 5 trucks, each of which can take 100kg load. And they > > are filled to some extent randomly. > > Let the free quantity be 40kg, 30kg, 20kg, 80kg, 60kg respectively. At > any > > given time only single load comes. > > Lets say a load of 25kg comes, we have to select the truck where it fits > > leaving less free space, here 30kg > > Now the free quantities are 40, 5, 20, 80 and 60. Next if a load of 10kg > > comes, we have to select the truck with 20kg free space. > > and go on... > > > > Write a java code for selecting a truck for the above situation when the > > number of trucks is very large. > > It should be with least time and space complexity with minimum number of > > iterations in the loop > > (interviewer said its part of a very large application which takes huge > > system resources, so this part of the code should be very efficient) > > -- > 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.
