## Ebay Interview Question

Software Engineer / Developersimport java.util.LinkedList;

/**

* Ebay has its own system that it uses to levy taxes on the sellers.

* The taxes are computed in a progressive manner.

* For eg. if the seller sells goods worth $25 then for the first

* 10 dollars tax=8% and on remaining 15 dollars tax = 7%.

* So total tax= 8% of 25 + 7% of 15.

The table that they use to compute the tax is as follows

$0 - $10 8%

$11 - $50 7%

$51 - $500 6%

$501 - $10000 5%

$10001 -$1000000 4% and so on.

Which data structure would you use to store this table and how

would you use that data structure to code a function

float computeTaxableAmount(float amount) {}

*

* @author Administrator

*

*/

public class EbayTaxProblem {

private LinkedList<TaxValueNode> taxValueNodes;

public EbayTaxProblem()

{

taxValueNodes = new LinkedList<EbayTaxProblem.TaxValueNode>();

populateTaxValueNode();

}

class TaxValueNode{

int value1;

int value2;

float taxValue;

}

/**

* Function to populate TaxValue Nodes

*/

public void populateTaxValueNode()

{

TaxValueNode node1 = new TaxValueNode();

/** Bracket 1 */

node1.value1 = 10;

node1.value2 = 10;

node1.taxValue = 8;

taxValueNodes.add(node1);

node1 = new TaxValueNode();

/** Bracket 2 */

node1.value1 = 11;

node1.value2 = 50;

node1.taxValue = 7;

taxValueNodes.add(node1);

node1 = new TaxValueNode();

/** Bracket 3 */

node1.value1 = 51;

node1.value2 = 500;

node1.taxValue = 6;

taxValueNodes.add(node1);

node1 = new TaxValueNode();

/** Bracket 4 */

node1.value1 = 501;

node1.value2 = 10000;

node1.taxValue = 5;

taxValueNodes.add(node1);

node1 = new TaxValueNode();

/** Bracket 5 */

node1.value1 = 10001;

node1.value2 = 1000000;

node1.taxValue = 4;

taxValueNodes.add(node1);

}

/**

* Method to compute the Taxable Income

*

* @param amount

* @return

*/

public float computeTaxableAmount(float amount)

{

int i=0;

float taxAmount = 0;

float diffAmount =0;

float prevHigh =0;

/*for (TaxValueNode taxValueNode : taxValueNodes) {

System.out.println(taxValueNode.taxValue);

}*/

//System.exit(0);

for (TaxValueNode taxValueNode : taxValueNodes) {

if(i==0)

{

taxAmount = amount*taxValueNode.taxValue/100;

prevHigh = taxValueNode.value2;

}

else if(amount>taxValueNode.value1 && i>0)

{

taxAmount = taxAmount +

(amount - prevHigh) * taxValueNode.taxValue/100;

prevHigh = taxValueNode.value2;

}

else

{

break;

}

i++;

}

System.out.println(taxAmount);

return taxAmount;

}

public static void main(String[] args)

{

EbayTaxProblem e1 = new EbayTaxProblem();

e1.computeTaxableAmount(150);

}

}

use an array of {max dollar amount, tax rate} sorted by max dollar amount.

For a given amount, do binary search of the array to find entry.

I will add one more column to array to make calculations faster. As I will assume this code to hit many many times.

Thrid column will have pre-computed Tax for upto last slab.

So if price is $20 then rate is in second row & this new column in second row will have value $.8 (10*8%) so that calculations to compute tax upto $10 are not required to be done again & again.

We can populate this column at the process start-up.

We can also use a simple Hash function here

0 - 10 = Bucket_1

11 - 50 = Bucket_2

thus for a given value we could compute a hash-value.

Hence a simple HashTable(K,V) with the Bucket number gives the key (K) and the % is the Value (V)

thus by looking into the HashTable, we can get the interest percent and compute the actual value!

We can also use a simple Hash function here

0 - 10 = Bucket_1

11 - 50 = Bucket_2

thus for a given value we could compute a hash-value.

Hence a simple HashTable(K,V) with the Bucket number gives the key (K) and the % is the Value (V)

thus by looking into the HashTable, we can get the interest percent and compute the actual value!

I would use a navigablemap. Benefits?? Easy to get headmap for any given $ amount, easily changeable at runtime, and ofcourse looks sophisticated. :D Once you have the headmap, just iterate over each key-value pair, calculate taxes, decrease high limit from given $ amount.

If it was a design pattern, I would have used decorator pattern combined with chain of responsibility. Lots of good stuff.

I liked the use of enums but it requires code change everytime tax brackets change. Something to think about.

public static float[] maxArray = {10,50,500,10000,1000000};

public static float[] taxValue = {8,7,6,5,4};

public float computeTexableAmount( float amount){

int index = indArrange(maxArray, 0, maxArray.length, amount);

foat tax = taxVlaue[index]/100;

float money = amount;

float taxMoney = 0.0;

for( int i = 0; i <= index; i++){

taxMoney += money * taxVale[index]/100;

money -= maxArray[i];

}

return taxMoney;

}

public int indArrange(float[] arr, int low, int high, float m){

if( low > high){

return low;

}

int midInd = (low+high)/2;

float middle = arr[(midInd];

if( middle == m){

return midInd;

}

if(m > middle){

return indArrang(arr,midInd+1, high, m);

}else{

return indArrang(arr,low, midInd-1,m);

}

}

```
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package carcup;
import java.util.Set;
import java.util.TreeMap;
import java.util.Map;
/**
*
* @author rrrajesh
*/
public class ETaxes {
TreeMap<Integer,Double> taxInfo = new TreeMap<Integer,Double>();
public void setupTaxes(){
taxInfo.put(10, 0.08);
taxInfo.put(50, 0.07);
taxInfo.put(500, 0.06);
taxInfo.put(1000, 0.05);
taxInfo.put(10000, 0.04);
}
public double calculateTaxes(int amount){
int limit;
double tax,progressiveTax = 0.0;
for(Map.Entry<Integer,Double> entry : taxInfo.entrySet()){
limit = entry.getKey();
tax = entry.getValue();
System.out.println(limit+" "+tax);
if(amount <= limit){
progressiveTax += amount*tax;
break;
}else{
amount -= limit;
progressiveTax += amount*tax;
}
}
return progressiveTax;
}
public static void main(String args[]){
ETaxes et = new ETaxes();
et.setupTaxes();
System.out.println(et.calculateTaxes(25));
}
}
```

Because the value ranges are contiguous, simply use Enum to store each range as a single value. Then use Enum.values() to iterate and compare.

e.g.,

- Larry March 18, 2012