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.
