There are two stacks(S1 and S2) of books. Each book in stack has a weight. You are given a net weight(W) of books that can be picked. You have to maximize the number of books that can be picked. Note that each time you can either pick from S1 or S2 only.

eg: s1:5,1,1

s2:1,2,6 W=10

So answer:5(order:1,2 from s2,then all from s1)

I know this question can be done with a greedy approach by comparing top elements of both stacks, but can we solve it with the concept of trees?

Is there any other data structure that can be used to solve this problem?

  • $\begingroup$ The description is contradictory "You are given the maximum weight(W) of books that can be picked. You have to maximize the number of books that can be picked." Could you edit your question and write why do you want to use trees? What exactly is your problem? If this is question whether trees could be used, maybe try it? $\endgroup$ – Evil Oct 6 '17 at 16:15
  • $\begingroup$ This was an interview problem in which the answer was to use trees,but I can't figure out how?So that's why I asked here if there is any alternative solution as well? $\endgroup$ – Saurabh Oct 6 '17 at 16:28
  • $\begingroup$ Edited the question,the W can be any number,not the maximum value. $\endgroup$ – Saurabh Oct 6 '17 at 16:29
  • $\begingroup$ I don't know what "solve it with the concept of trees" would mean. Why would we want to, given that there already exists an efficient (linear-time) and simple solution for the problem? I suspect there's some additional context or requirements you haven't given us. There's always some other data structure: for instance, I could create a Froobazingus data structure and then never use it. $\endgroup$ – D.W. Oct 8 '17 at 1:18
  • $\begingroup$ No additional context,trees was just one way of solving it,please suggest if you have another solution for the question. $\endgroup$ – Saurabh Oct 9 '17 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.