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.7k215
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: 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 : 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

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 yesterday

vatsal1998's gravatar image

3★vatsal1998
1
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
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,221
×248
×43

question asked: 07 Apr, 15:39

question was seen: 1,216 times

last updated: yesterday