We all love algorithms. In real life, the problems do not pose themselves as textbooks problems under a particular chapter so that we know what algorithm to apply. The problems are camouflaged. The challenge lies not in implementing the algorithms but identifying the problem in its abstract form and finding out the appropriate algorithm to apply.
I have had a few chances at my work where I’ve had this Aha! feeling along with my colleagues where we talked about the problem, reformulated it and then discovered that the problem is a likely candidate for applying some algorithm X. This is the first part of this series.
To boost the sales of our product, we had come up with certain promotions. Some were simple flat rate discount, some were % discounts. Then we embarked on this idea of buy-one-and-get-one-free. Here the user chooses products of different prices and pays for approximately half the price. It is similar to buy-one-shirt-and-get-one-free (where you pay for the costlier one). Just that here it is bundle of products.
Let me explain with an example.
1. Suppose a customer buys products each worth $10, $30 & $100. Then the customer would pay $100 and get $40 (=10 +30) worth products free. So this ain’t a simple buy-one-get-one free.
2. If customer buys two products each worth $100, then she pays $100 and gets the other one free.
3. If the purchases are $10, $100, $45, $40, $10 then customer pays $105 (= 10+45+40+10) and gets the $00 product free.
This should give a fair idea of what we want to achieve. A little thought would suggest such a reformulation of the problem above.
“Given a set of numbers, split it into two parts such that the difference between their sums is the least.”
This is quite straight forward to solve. The plan is given below.
1. sort the numbers in descending order.
2. have two buckets call them L & R.
3. put the first one into L (l1). put the second one into R (r1).
4. take the third one x3.
if r1+x3 > l1 then put x3 in L1
else put x3 in L2
Now it is a matter of policy whether the customer is charged the higher one or the lower (in cases where the split is unequal)
If you like this you might probably like this as well.
August 11, 2008 at 5:41 am |
Yeah you are right if the array of numbers is streaming from some source.But actually we have got a fixed array of numbers. we are going to divide this array into 2 arrays of least difference in their sums.To put in other words we are going to divide this array into 2 arrays such that the sum of each array is close to the (sum of the original array /2).So the algorithm would be o(n) instead of o(nlogn) as in your case.
t-total sum of original array
s-0
for each element in array
{
if((s+element)<t/2)
{
s=s+element
put element in L array
}
else
put element in R array
}
Correct me if I am wrong ….
August 11, 2008 at 2:30 pm |
Hi Dante
Thanks for your pointers. Your approach is quite simple and elegant.
I guess in my approach, the precondition that the array be sorted is of significance. Even if the source is streaming, the numbers should arrive in the sorted (descending) order.
If the incoming numbers are inserted into a priority queue, and then read back from it, the output would be in the descending order of the numbers.
The complexity for insert and remove for Priority queue is N log N, which is what you have pointed out.
In the context where I used this, the numbers were already in the sorted order and dint incur the N Log N expense. But in the generic case, I would do as you have suggested.
August 15, 2008 at 5:41 pm |
[...] algorithms @ work – part 2 In this edition, I take up a slightly more complex case than the previous one. [...]