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: 28%

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 18 Apr, 20:54

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.

(19 Apr, 09:05) algmyr7★

Ohh yeah!!! You are right. But i got a slight correction. We would also have to reduce frequency of all the drinks of that customer whom we are supplying a drink.This complexity remains cn(overall for all customers) .After that we have to sort it again. So at most we have to sort it c times. So net complexity is O(cn +cnlogn)=O(cnlogn). But i am not sure that it will run in the given time constraints. Please check!! But i think this will give an optimal solution. If anyone can improve this please comment!!!

(21 Apr, 11:35) vatsal19984★

c1 = {n1,n3}, c2 = {n1,n2}, c3 = {n1,n4}, c4 = {n4,n5}, c5 = {n3,n6}, c6 = {n2,n7}. The highest frequency doesn't always give the best solution. In the worst case you would have to check every subsequence in your sorted frequency array.

(21 Apr, 15:09) hemanth_16★

As @hemanth_1 mentioned in the comments in to their answer, set cover is reducible to lazy bartender, and set cover is NP-hard. So unless P=NP there is no polynomial algorithm for this problem. So either P=NP or your algorithm does not give the optimal answer. It's very much the latter.

(21 Apr, 23:29) algmyr7★
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: 2,900 times

last updated: 21 Apr, 23:29