You are not logged in. Please login at to post your questions!


Lazy Bartender: Amazon Interview Question | Help


Can someone tell me how to solve this(Lazy Bartender) problem ?

asked 07 Apr, 15:39

bansal1232's gravatar image

accept rate: 16%

edited 08 Apr, 22:35

Depends on constraints. You can solve it easily if either N or C is small. If N is small, then you can just brute force. If 'C' is small, you can use bitmask dp, DP[i][mask] = minimum number of drinks from the first 'i' drinks for all customers represented by 'mask'. I don't think there are better solutions because this problem seems to be similar to the Set Cover problem, which is NP-Hard.


answered 10 Apr, 22:41

hemanth_1's gravatar image

accept rate: 25%

So what would be the expected time complexity of Brute Force?

(11 Apr, 13:21) bansal12325★

O(C*2^N). The other solution has complexity O(N*2^C).

(11 Apr, 16:00) hemanth_16★

But in original question $N$ and $C$ was given to me as,

$1 < N < 1000$

$1 < C < 10000$

(11 Apr, 23:03) bansal12325★

Take a look at this : , its easy to see that every instance of this problem can be reduced to Lazy Bartender. So, I don't think there is a polynomial time solution.

(11 Apr, 23:25) hemanth_16★

You can see the original question here(

(11 Apr, 23:29) bansal12325★

I don't think it can be solved.

(11 Apr, 23:48) hemanth_16★

Is that not possible to pick the bars greedy, I mean first sort all the cocktails in ascending order and then pick one by one?

(12 Apr, 11:13) bansal12325★

What do you mean by ascending order ? ascending based on what ?

(13 Apr, 22:39) hemanth_16★
showing 5 of 8 show all

You can do this... Use hashing or a frequency array for drinks (n1,n2...) Then count the frequency of all the drinks that can be supplied i.e.lets say customer 1 =n1,n2,n3 customer 2 =n1,n4,n3 customer 3 =n1 Now frequency array will be 3 1 2 1 for all the drinks respectively. Now sort the frequency array and provide drinks to the customer in decreasing order of frequency. Continue this process till all the customers are satisfied. So the time complexity will become O(c*n +nlogn).


answered yesterday

vatsal1998's gravatar image

accept rate: 0%

This has no guarantees on optimality. A simple counterexample, consider c1 = {n1,n2}, c2 = {n1,n2}, c3 = {n3}. Your algo serves using 3 when the optimal is 2. In this case there are duplicates, but it's easy to construct harder cases.

(yesterday) algmyr6★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 07 Apr, 15:39

question was seen: 1,216 times

last updated: yesterday