## Amazon Yahoo Interview Question for Software Engineer / Developers

• 0
of 2 votes

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

Greedy / Knapsack 0/1 ?

Comment hidden because of low score. Click to expand.
0
of 0 votes

neither. just similar to knapsack

Comment hidden because of low score. Click to expand.
1
of 1 vote

Its a knapsack problem where we have to minimize value instead of maximizing it.

0-1 knapsack problem - If it is mandatory to pick all books of given price.

Fractional knapsack problem - If it is allowed to pick any quantity of books of given price.

This is very good point to discuss with your interviewer.

Comment hidden because of low score. Click to expand.
0
of 0 votes

Not quite it is also different from the classic knapsack problem in that you have different Classes of objects instead of just a discreet list, still seems to face the same problems with using a naive greedy solution though, such a solution could probably be made reasonably good in most circumstances with the right heuristics

Comment hidden because of low score. Click to expand.
0
of 2 vote

Simplex method....

Comment hidden because of low score. Click to expand.
0
of 0 votes

can you explain

Comment hidden because of low score. Click to expand.
0
of 0 votes

1. Greedy algorithm question.
2. sort the books by price in increasing order.
3. Now choose the books by price till Q books are not selected.

Comment hidden because of low score. Click to expand.
0
of 0 votes

@googlybhai ..one quantity of books can be taken multiple times
like 500 quantity
a)25*20
b)10*50
c)25*19+ 15*1+10*1 etc
u have give the least price among all these poosible quantity list which add upto 500

Comment hidden because of low score. Click to expand.
0
of 0 votes

If i got the question right:-
"user wants to purchase 500 quantity of books.come up with minimum price"

if user want 500 quantity of books, with minimun prices, so not get the 500 copies of book which has minimum price.

or may be i got the question wrong...

Comment hidden because of low score. Click to expand.
0
of 0 votes

@ravisingh:

This is a knapsack problem with repititions allowed. The solution would look something like below (simple and stupid pseduo-code):

``````knapsack(w)
knapack(0) = 0
for each wi = 1 to W:
knapsack(wi) = max{K(w - wi) + vi : wi <= w}
return knapsack(W)``````

where W = 500
wi is the individual prices of the books per bundle
w is the current quantity (multiples of quantities per bundle).

I am not sure if I have made any honest attempt to think about the right solution to the problem, but the problem looks like knapsack problem with repititions as described in algorithms book by Vazirani, Papadimitrou & Dasgupta.

Please validate my assumptions and answer if anything is misleading or wrong.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I suppose, dynamic programming can help to solve this in O(n^2).
Code below:

``````public static int optimalPrice(int amount) {
if (amount == 0) return 0;

if (cache.containsKey(amount)) return cache.get(amount);

int result = 100000;
for (int i = 0; i < quantities.length; i++) {
int q = quantities[i];
int p = prices[i];

if (amount >= q) {
int t = optimalPrice(amount - q) + p;
if (t < result) result = t;
}
}

cache.put(amount, result);
return result;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

below is the typical dp. and time complexity should be O(n*amount)
int tmp;
int dp[]=new int[amount+1];
for(int s=0;s<amount+1;s++)
for(int i=0;i<quantities.length;i++){
if(s>=quantities[i]) tmp=dp[s-quantities[i]]+price[i];
if(i==0) dp[s]=tmp;
else dp[s]=Math.min(tmp,dp[s]);
}
return dp[amount];

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class PurchaseQBooksWithMinPrice {

public static void main(String[] args){
int arr[]= {100,200,120,130,165};
int quanity[] = {10,20,30,15,25};
for(int i = 0; i < arr.length; i++){
System.out.println(arr[i]+" "+quanity[i]);
}
System.out.println();

quickSort(arr,quanity, arr.length);
for(int i = 0; i < arr.length; i++){
System.out.println(arr[i]+" "+quanity[i]);
}

System.out.println(getPrice(arr,quanity,50));
}

private static int getPrice(int[] arr, int[] quanity,int totalQ) {
int tq=0;
int price = 0;
for(int i = 0; i<arr.length;i++){
if(tq == totalQ){
return price;
}
if(tq + quanity[i] < totalQ){
price += arr[i]*quanity[i];
tq = tq + quanity[i];
}else if(tq + quanity[i] > totalQ){
price += (totalQ-tq)*arr[i];
tq = totalQ;
}
}
if(tq == totalQ){
return price;
}else{
return -1; //Incase the total quantity is less than quantity given as input
}
}

private static void quickSort(int[] arr, int[] quantity, int length) {
recQuickSort(arr,quantity, 0, length - 1);
}

private static void recQuickSort(int[] arr,int []quantity, int left, int right) {
if(right - left <= 0)
return;
else{
int pivot = arr[right];
int partition = partitionIt(arr,quantity,left, right, pivot);
recQuickSort(arr,quantity, left, partition-1);
recQuickSort(arr,quantity, partition+1, right);
}

}

private static int partitionIt(int[] arr,int[] quantity, int left, int right, int pivot) {
int leftPtr = left - 1;
int rightPtr = right;
int temp;
while(true){
while(arr[++leftPtr]<pivot);
while(rightPtr > 0 && arr[--rightPtr]>pivot);
if(leftPtr >= rightPtr)
break;
else{
temp = arr[leftPtr];
arr[leftPtr]= arr[rightPtr];
arr[rightPtr]= temp;

temp = quantity[leftPtr];
quantity[leftPtr]= quantity[rightPtr];
quantity[rightPtr]= temp;
}
}
temp = arr[leftPtr];
arr[leftPtr]= arr[right];
arr[right] = temp;

temp = quantity[leftPtr];
quantity[leftPtr]= quantity[right];
quantity[right] = temp;
return leftPtr;

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class BuyBooks {

int[] bundle={10, 20, 30, 15, 25};
int[] price ={100, 200, 120, 130, 165};
BookOffer[] offers;

public BuyBooks() {
super();
}

private  void loadValues() {
offers=new BookOffer[bundle.length];
for(int i=0;i<bundle.length;i++){
offers[i]=new BookOffer(bundle[i], price[i]);
}
qsort();
}

private void qsort(){

quicksort(0,offers.length-1);

}

private BookOffer[] quicksort( int low,int high) {

//    System.out.println("Quick sorting"+low +" "+high);
int i = low, j = high;
// Get the pivot element from the middle of the list
BookOffer pivot = offers[low + (high-low)/2];

// Divide into two lists
while (i <= j) {
// If the current value from the left list is smaller then the pivot
// element then get the next element from the left list
while (offers[i].costfactor < pivot.costfactor) {
i++;
}
// If the current value from the right list is larger then the pivot
// element then get the next element from the right list
while (offers[j].costfactor > pivot.costfactor) {
j--;
}

// If we have found a values in the left list which is larger then
// the pivot element and if we have found a value in the right list
// which is smaller then the pivot element then we exchange the
// values.
// As we are done we can increase i and j
if (i <= j) {
exchange(i, j);
i++;
j--;
}
}
// Recursion
if (low < j)
quicksort(low, j);
if (i < high)
quicksort(i, high);

return offers;
}

private void exchange(int i, int j) {
BookOffer temp = offers[i];
offers[i] = offers[j];
offers[j] = temp;
}

public static void main(String[] args) {
BuyBooks buyBooks = new BuyBooks();
buyBooks.loadValues();
for(BookOffer b: buyBooks.offers){
//        System.out.println(b);
}

buyBooks.bestBuy(100);

}

private  void bestBuy(int cnt) {
int fchoice,schoice,thirdchoice;
int div;
for(int i=0;i<this.offers.length;i++){
System.out.println(this.offers[i]);
if((div=cnt/offers[i].bundle)>=1){
System.out.println("Buy"+(div*offers[i].bundle)+"@"+(div*offers[i].price));
cnt-=div*offers[i].bundle;
}
}

}
}

class BookOffer{
int bundle;
int price;
double costfactor;

BookOffer(int bundle,int price){
this.bundle=bundle;
this.price=price;
this.costfactor=price/bundle;
}

public String toString(){
return this.bundle+"books of bundle costs"+this.price+" at cost"+this.costfactor;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

short by price
the use divide and concur to find @t what point quantity limit is reached or more

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is very similar to the rod-cutting example provided in Introduction to algorithms CLRS book under section dynamic programming isn't it?

Comment hidden because of low score. Click to expand.
0
of 0 votes

Well it could be a knapsack problem as well solvable using DP technique. Trying to come up with a code!

Comment hidden because of low score. Click to expand.
0
of 0 vote

If i got the question right:-
"user wants to purchase 500 quantity of books.come up with minimum price"

if user want 500 quantity of books, with minimun prices, so not get the 500 copies of book which has minimum price.

or may be i got the question wrong...

Comment hidden because of low score. Click to expand.
0
of 0 vote

HashTable<P,Q> hashtable; //Store all the Price and Quantity in hash

HashSet set = hashtable.getKeys();
hashSet sortedSet = Collection.Sort(set);

iterator i = sortedSet.iterator();

int total_p =0. total_q=0;
While(i.hasNext())
{
int p=i.next();
int q= hastable.getValue(p);
if(target-total_q <=q){
total_q+=q;
total_p+=p*q;
}
else{
int rem = target-total_q;
total_q+=rem;
total_p+=rem*p;
return total_p;
}
}

return -1;

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
int max(int a, int b) { return (a > b)? a : b; }
int knapSack(int W, int wt[], int val[], int n)
{
if (n == 0 || W == 0)
return 0;

if (wt[n-1] > W)
return knapSack(W, wt, val, n-1);

// Return the maximum of two cases: (1) nth item included (2) not included
else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
knapSack(W, wt, val, n-1)
);
}

// Driver program to test above function
int main()
{
int val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int W = 50;
int n = sizeof(val)/sizeof(val);
printf("%d", knapSack(W, wt, val, n));
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Dynamic Programming based implementation.

``````#include<stdio.h>

// A utility function that returns maximum of two integers
int max(int a, int b) { return (a > b)? a : b; }

// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
int i, w;
int K[n+1][W+1];

// Build table K[][] in bottom up manner
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i==0 || w==0)
K[i][w] = 0;
else if (wt[i-1] <= w)
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}

return K[n][W];
}

int main()
{
int val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int  W = 50;
int n = sizeof(val)/sizeof(val);
printf("%d", knapSack(W, wt, val, n));
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursion, test it simply copy and paste this in your console!

``````function knapack(require_amount){

var a = {
quantity: 10,
price: 100
}

var b = {
quantity: 20,
price: 200
}

var c = {
quantity: 30,
price: 120
}

var d = {
quantity:15,
price: 130
}

var e = {
quantity: 25,
price: 165
}

var arr = [a,b,c,d,e];

return min_price(arr, require_amount, 0);
}

function min_price(arr, require_amount, price){
if(require_amount === 0) return price;
if(require_amount < 0) return Infinity;

var result_arr = [];
for(var i = 0; i < arr.length; i++){
var item = min_price(arr, require_amount - arr[i].quantity, price + arr[i].price);
result_arr.push(item);
}

return Math.min.apply(null, result_arr);
}

knapack(100);``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

1 calculate the avg price of per quality for each books
2 choose the lowest one and pick as many as we can
3 do the same procedure if any quality left

i guess that would get the job done

Comment hidden because of low score. Click to expand.
0
of 0 votes

It fails with
Quantity 1, 5, 8
Price 2, 4, 6
and you want to buy 10 books. The best solution is to buy 5 books twice, but your algorithm will buy 8+1+1 books with 6+2+2 = \$10

Comment hidden because of low score. Click to expand.
0
of 0 votes

isnt 8/6 > 5/4 and hence the above example will pick 5 and not 8.

Comment hidden because of low score. Click to expand.
0
of 0 votes

No. It's the other way. If you want to buy 40 books, you want to buy 8 books at a time and pay 6*5 = \$30. Buying 5 books at a time needs 4*32 = \$32.

Comment hidden because of low score. Click to expand.
0
of 0 votes

A solution to bobs problem would be to perform such a greedy from oohjt for each class of books treating each class of books in it's order as cheapest on average (could be done quite effiecently with the right math) and keeping track of which one is best could even terminate early under the right circumstances

Comment hidden because of low score. Click to expand.
-1
of 1 vote

what if we sort books by prices, and take all available books from chipper to expensive until we reach the quantity. Complexity is O(N log N)

Comment hidden because of low score. Click to expand.
0
of 0 votes

What's the difference between this answer and oohtj's answer?

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More