Amazon Interview Question
Software EngineersCountry: United States
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.
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();
}
}
}
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();
}
}
@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?
@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".
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;
}
}
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.
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!
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.
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()) ;
}
}
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;
}
}
}
Use combination of hashTable with hashNode pointing to MaxHeap Node
- sameer November 25, 2015Key in hashTable: Price
Key in Heap : Total Quantity for that price