Amazon Interview Question for Software Engineers


Country: United States




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

Use combination of hashTable with hashNode pointing to MaxHeap Node
Key in hashTable: Price
Key in Heap : Total Quantity for that price

- sameer November 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

You don't need max heap here. Hash table is enough for this task. Just store current MSP in a variable and update it if necessary.

- Iuri Sitinschi November 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correct, you don't need max heap. That's because values cannot be deleted. If values could be deleted, then we'd need some structure like a heap.

- Anonymous November 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

possible c# implementation.

using System;
using System.Collections.Generic;
using System.Threading;

namespace MaxSoldPrice {

    class Program {

        private static void PrintPrices() {
            var hashTable = new Dictionary<double, int>();
            var msp = 0;
            string mspStr = null;

            foreach ( var rec in GenerateRecords() ) {
                
                int currMax;
                if ( hashTable.TryGetValue( rec.Price, out currMax ) ) {
                    hashTable[ rec.Price ] = currMax + rec.qty;
                } else {
                    hashTable.Add( rec.Price, rec.qty );
                }
                currMax = hashTable[ rec.Price ];
                if ( currMax > msp ) {
                    msp = currMax;
                    mspStr = $"{rec.Price}({currMax})";
                }

                Console.WriteLine($"{rec.Price}, {rec.qty}, {mspStr}");
            }
        }

        private static IEnumerable<PriceRecord> GenerateRecords() {
            Random rnd = new Random();
            while ( true ) {
                Thread.Sleep(1000);
                yield return new PriceRecord() { Price = rnd.Next( 1, 10 ), qty = rnd.Next( 1, 20) };
            }
        }

        public struct PriceRecord {
            public double Price { get; set; }
            public int qty { get; set; }
        }

        static void Main(string[] args) {
            PrintPrices();
        }
    }
}

- zr.roman November 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ solution with single hash table

#include <iostream>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<string> v{"11:01AM $10.01 100","11:03AM $11.01 200","11:04AM $12.81 150","11:06AM $10.01 210"};
    v.push_back("11:07AM $10.01 180");
    v.push_back("11:08AM $12.81 400");
    v.push_back("11:09AM $11.01 200");
    unordered_map<string,pair<int,double>> hash;
     
     
    for(int i=0;i<(int)v.size();++i){
        //input parsing
        stringstream ss;
        ss<<v[i];
        string times;
        double price;
        int quantity;
        ss>>times;
        string dv_s;
        ss>>dv_s;
        price=stod(dv_s.substr(1));
        ss>>quantity;
         
        //actual logic: store total quantity and price in a map hashed by dollar value of the item
        hash[dv_s].first+=quantity;
        hash[dv_s].second=price*hash[dv_s].first;
        
        double max_p=0;
        int res_quantity;
        string res_dv;
        
        //search the map for item with maximum total price so far and print dollar value and quantity
        for(auto it=hash.begin();it!=hash.end();++it){
            if(it->second.second>max_p){
                res_dv=it->first;
                res_quantity=it->second.first;
                max_p=it->second.second;
            }
        }
        cout<<res_dv<<"("<<res_quantity<<")"<<endl;
        //clear stream
        ss.clear();
   }
}

- jackdanielsparrow November 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Edd, so did the interviewer had in mind a distributed system design that handles very large number of updates, terrabytes of storage and very frequent queries, with lots of "players". And the system should be fault tolerant, etc?
Or is it just single machine algo/data structure question?

- blckembr November 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@blkembr: Upon his dissatisfaction, I asked him which direction he is expecting.
He told me think of a live system like eBay and they have a system for MSP.
How will they build this up ? Upon asking about distributed system he replied "If it helps then Why Not".

- Edd November 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How to build a distributed system for this particular case?

- Anonymous November 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how to build a distributed system for this particular case?

- PoWerOnOff November 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my submitted code during the interview. In search of a faster algorithm.

import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;

public class MostSoldPrice {
	
	private PriorityQueue<Pair> pQueue; 
	
	public MostSoldPrice()
	{
		PQsort pqs = new PQsort();
		pQueue = new PriorityQueue<Pair>(pqs);
	}
		
	public static void main(String[] args) {
			MostSoldPrice msp = new MostSoldPrice();
			msp.addEntry(10.01,100);
			System.out.println(msp.getMSPValue());
			msp.addEntry(11.01,200);
			System.out.println(msp.getMSPValue());
			msp.addEntry(12.81,150);
			System.out.println(msp.getMSPValue());
			msp.addEntry(10.01,210);
			System.out.println(msp.getMSPValue());
			msp.addEntry(10.01,180);
			System.out.println(msp.getMSPValue());
			msp.addEntry(12.81,400);
			System.out.println(msp.getMSPValue());
			msp.addEntry(11.01,200);

			System.out.println(msp.getMSPValue());
				
	}
	
	public void addEntry(double price, int quantity)
	{
		Iterator<Pair> it = pQueue.iterator();
		boolean recordFound=false;
		while (it.hasNext())
		{	
			Pair currentPair = it.next();
			if(currentPair.getPrice()==price){
				int oldQuantity = currentPair.getQuantity();
				pQueue.remove(currentPair);
				pQueue.add(new Pair(price,oldQuantity+quantity));
				recordFound=true;
				break;
			}
		}
		
		if (!recordFound)
		{
			pQueue.add(new Pair(price,quantity));
		}
	}
	
	public String getMSPValue()
	{
		Pair front = pQueue.peek();		
		return front.getPrice()+"["+front.getQuantity()+"]";
	}
	
	static class PQsort implements Comparator<Pair> {
		 
		public int compare(Pair one, Pair two) {
			return two.getQuantity() - one.getQuantity();
		}
	}	
	
}
	

class Pair
{
	double price;
	int quantity;
	
	public Pair(double price, int quantity)
	{
		this.price=price;
		this.quantity=quantity;
	}
	
	public double getPrice()
	{
		return price; 
	}
	
	public int getQuantity()
	{
		return quantity;
	}
	
	
}

- Edd November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I was asked a similar question in an interview. The premise of this question is that all the logs are static, like records saved during last week. They are not dynamic and on-going. Compared to using a priority queue, which is suitable for on-going stream information, it is better to pre-process the logs, push quantity-price pairs to an array, and sort the array based on quantity.

Then segregate the huge array to small segments, and distribute the segments to different computers. Use merge sort or quick sort or other sorting algorithms to sort those segments. Eventually combine the result and obtain a large sorted array.

I guess the interviewer wanted an answer like this.

- PoWerOnOff November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Retrieve the current max quantity sold and compare it with current quantity. If it is greater than current max then it current max and the price associated with it is current MSP,print those two values. If current max quantity is not there, then initialize to current quantity and MSP to current MSP.

I hope this should work!

- rjk422@nyu.edu February 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Yep this sounds more like distributed system solution. The data you are recieving is streaming data and would require stream processing. Kafka/Kinesis --> Storm/SparkStreaming --> Redsift.

Kafka would handle large amount of stream data, you could process it with either Kinesis KCL app or Storm/Spark Streaming and store it in the Redshift.

This is how I would have answered, not really sure it would be right or wrong.

- utrivedi May 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package test;

public class AmazonMostSolidPrice {
	
	Data [] bucketsData = new Data[5000];
	int[] numbers= new int[5000];
	int number;

	public static void main(String[] args) {
		
		AmazonMostSolidPrice amazonMostSolidPrice = new AmazonMostSolidPrice();
		
		amazonMostSolidPrice.addData(10.01d, 100);
		amazonMostSolidPrice.addData(11.01d, 200);
		amazonMostSolidPrice.addData(10.01d, 210);
		
		amazonMostSolidPrice.show();

	}
	
	private void show (){
		
		for (int i=0;i<number;i++){
			  System.out.println(bucketsData[numbers[i]].price + ":"+bucketsData[numbers[i]].quantity);
		}
		
	}
	
	
	public class Data {
		
		double price;
		int quantity;
		
		Data(double priceRec, int qty){
			price = priceRec;
			quantity = qty;			
		}
		
	}
	
	private  void addData(double priceRec, int qty){
		
		Data newData = new Data(priceRec, qty);
		int indexData = hash(priceRec);
		Data data = bucketsData[indexData];
		
		if (data!=null){
			newData.quantity = newData.quantity + data.quantity;
			bucketsData[indexData] = newData;
			
		}else{
			bucketsData[indexData] = newData;
			numbers[number]=indexData;
			number++;
		}
		
	}
	
	private int hash(double key){
		
		StringBuilder sb = new StringBuilder();
		
		for (String str: String.valueOf(key).split("\\.")){
			sb.append(str);
		}
		
		return Integer.valueOf(sb.toString()) ;
		
	}

}

- israAzul June 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package test;

public class AmazonMostSolidPrice {
	
	Data [] bucketsData = new Data[10];
	int number = 1;

	public static void main(String[] args) {
		
		AmazonMostSolidPrice amazonMostSolidPrice = new AmazonMostSolidPrice();
		
		amazonMostSolidPrice.addData(10.01d, 100);
		amazonMostSolidPrice.addData(11.01d, 200);
		amazonMostSolidPrice.addData(10.01d, 210);
		
		amazonMostSolidPrice.dump();

	}
	
	void dump() {
     System.out.println();
     for (int i = 0; i < number; i++) {
        System.out.print(i + ":");
        Data list = bucketsData[i];
        while (list != null) {
           System.out.print("  (" + list.price + "," + list.quantity + ")");
           list = list.next;
        }
        System.out.println();
     }
  }
	
	
	public class Data {
		
		double price;
		int quantity;
		Data next = null;
		
		Data(double priceRec, int qty){
			price = priceRec;
			quantity = qty;			
		}
		
		public boolean equals(Object object){
			
			if (object instanceof Data){
				
				return price == ( ((Data) object).price);
				
			}
			
			return false;		
			
		}
		
	}
	
	private  void addData(double priceRec, int qty){
		
		Data newData = new Data(priceRec, qty);
		int indexData = 0;
		Data data = bucketsData[indexData];
		
		if (data!=null){
			
			while (data !=null ){
				
				if(newData.equals(data)){
					
					newData.quantity = newData.quantity + data.quantity;					
					data.quantity = newData.quantity;					
					return;
				}
					
				else
					data = data.next;
			}
			
			newData.next= bucketsData[indexData] ;
			bucketsData[indexData] = newData;
			
		}else{
			
			bucketsData[indexData] = newData;
			
		}
		
	}

}

- israAzul June 23, 2016 | Flag Reply


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