Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
function F (startDate, expirationDate, quantity) {
this.startDate = startDate
this.expirationDate = expirationDate
this.quantity = quantity
}
var Demand = F
var Supply = F
function fulfill(demand, supply) {
// First let's normalize all supply and demand objects
// to be of quantity 1
var tmp = demand
demand = []
for (var m = 0; m < tmp.length; ++m) {
var d = tmp[m]
for (var i = 0; i < d.quantity; ++i) {
demand.push(new Demand(d.startDate,
d.expirationDate, 1))
}
}
tmp = supply
supply = []
for (var n = 0; n < tmp.length; ++n) {
var s = tmp[n]
for (i = 0; i < s.quantity; ++i) {
supply.push(new Supply(s.startDate,
s.expirationDate, 1))
}
}
// Now each supply must have at least 3 days remaining
// lets assume that expirationDate and startDate are in
// milliseconds (ms)
for (n = 0; n < supply.length; ++n) {
supply[n].expirationDate -= 259200000
}
// I'm not entirely sure about `a demand is said to be
// fulfilled 24 hours after all demands have been mapped
// to correspondingly available supplies`
// I think it means that Demand.startDate => Demand.startDate
// + 24 hours.
for (m = 0; m < demand.length; ++m) {
demand[m].startDate += 86400000
}
// Now we should sort both supply and demand by expirationDate,
// ties are broken by a secondary key of `startDate`
function f (a, b) {
if (a.expirationDate < b.expirationDate) {
return -1
}
if (a.expirationDate > b.expirationDate) {
return 1
}
if (a.startDate < b.startDate) {
return -1
}
if (a.startDate > b.startDate) {
return 1
}
return 0
}
supply.sort(f)
demand.sort(f)
// Now all supply and demand is sorted so that
// it is in order of expirationDate and secondarily by
// startDate so that if a precedes b that means either:
// a.expirationDate < b.expirationDate ||
// a.expirationDate === b.expirationDate &&
// a.startDate < b.startDate
//
// Now for each demand we need to find the first supply that
// fulfills the demand conditions because at this point it
// is assured that if supply X fulfills demand Y then supply X-1
// to supply 0 do not.
// It is also guaranteed for either supply X or demand X that
// supply/demand X+1 either has a later startDate, a later
// expirationDate or both
var mapping = []
for (m = 0; m < demand.length; ++m) {
for (n = 0; n < supply.length; ++n) {
d = demand[m]
s = supply[n]
if (s.expirationDate >= d.expirationDate) {
if (s.startDate <= d.startDate) {
mapping.push([d, s])
break
}
}
}
}
return mapping
}
- NoOne October 30, 2016