FastPrepPrice at Query Timestamps
Problems/Price at Query Timestamps

Price at Query Timestamps

Google logoGoogle● EasyFULLTIMEPHONE SCREEN
QuestionExamples

Problem statement

Source note: In a Google technical phone screen, the candidate received a list of price records, each a time with the price that starts then, plus a list of query times, and had to give the price in effect at each query time, with no price before the first record. The interviewer first allowed the queries to arrive sorted and then asked how to handle them unsorted. The report includes one worked example.

The report gives no limits and leaves the input shape open. Practice choices here: the records come as two parallel arrays with strictly increasing times, a record applies from its own time on, the queries may be in any order and the answers keep the query order, the empty string stands for no price, and the limits and other examples are ours.

The judged task matches the report at about 90%.

A price history is given as two arrays of the same length: from time times[i] on, the price is prices[i], until the next record takes over. The record times are strictly increasing.

You are also given an array queries of times, in any order. For each query time q, find the record with the largest time that is at most q and report its price. A record whose time equals q already applies at q. If q is earlier than every record time, no price is known yet; report the empty string "".

The problem statement continues
Pro

Examples

Example 1

times = [0,50,500]prices = ["Price A","Price B","Price C"]queries = [-10,20,50,499,600]return = ["","Price A","Price B","Price B","Price C"]
  • Time -10 is before the first record at time 0, so no price is known yet: "".
  • Time 20: the latest record at or before it is time 0, so "Price A".
  • Time 50 matches a record exactly, so that record's "Price B" applies.
  • Time 499: the next record starts at 500, so "Price B" still applies.
  • Time 600: the latest record is time 500, so "Price C".
02 · Example 2
FastPrep Pro
Reported in 1 Google interview this week

Unlock this recently reported problem

FastPrep Pro gives you full access to interview problems reported within the last week.

  • Full problem statement and constraints
  • 2 more worked examples, explained
  • Guided hints and editorial
  • Run your code on real test cases
$8.25/month

$99 billed yearly — or $19 month-to-month. Cancel anytime.

Free plan — 2 of 2 free unlocks used this week
All Google interview questionsSee Google hiring insights
CodePython 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import heapq
from collections import defaultdict
 
class Solution:
def solve(self, values, queries):
# Build the adjacency structure
n = len(values)
graph = defaultdict(list)
for u, v in queries:
graph[u].append(v)
 
best = [float("inf")] * n
heap = [(0, 0)]
while heap:
cost, node = heapq.heappop(heap)
if cost > best[node]:
continue
Run and Submit unlock with Pro
FastPrep Pro
Reported in 1 Google interview this week

Unlock this recently reported problem

FastPrep Pro gives you full access to interview problems reported within the last week.

  • Full problem statement and constraints
  • 2 more worked examples, explained
  • Guided hints and editorial
  • Run your code on real test cases
$8.25/month

$99 billed yearly — or $19 month-to-month. Cancel anytime.

Free plan — 2 of 2 free unlocks used this week