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

×

Lazy Bartender: Amazon Interview Question | Help

3
2

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

asked 07 Apr, 15:39

bansal1232's gravatar image

5★bansal1232
2.8k316
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.

link

answered 10 Apr, 22:41

hemanth_1's gravatar image

6★hemanth_1
1.3k9
accept rate: 26%

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 : https://en.wikipedia.org/wiki/Set_cover_problem , 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(https://goo.gl/Mgnqc4)

(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★
1

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

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

If I haven't missed something it can be reduced to https://en.wikipedia.org/wiki/Vertex_cover. That problem is NP-hard. So, the best solution I can go has complexity O(2^(number of drinks)). If you precalculate for every drink the mask of customers which has this drink as favorite: you just need to calculate for every subset of drinks BITWISE OR of all masks of customers for every element in that subset, it can be done in O(2^(number of drinks) * number of drinks) in a naive way. But you can make an observation that if you know all masks of customers for smaller subsets, you can erase the lowest bit and recalculate the answer F[mask] = F[mask xor (lowest bit)] OR (mask of customers for (lowest bit)). Overall O(2^(number of drinks) + (number of drinks) * (number of customers)). In the end, you just need iterate over all subsets of drinks and check if the value of BITWISE OR is equal to (2^(number of customers)-1). Of course, you can add some hacks and optimizations to achieve very fast practical solution, but the main idea is given above.

link

answered 09 Apr, 20:05

mgch's gravatar image

6★mgch
3001021
accept rate: 21%

edited 09 Apr, 20:10

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).

link

answered 18 Apr, 20:54

vatsal1998's gravatar image

4★vatsal1998
112
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) algmyr6★

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★
1

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) algmyr6★
toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×2,398
×303
×53

question asked: 07 Apr, 15:39

question was seen: 1,773 times

last updated: 21 Apr, 23:29