Concurrent Web Crawler Simulation
Updated
Problem statement
You are writing a web crawler that fetches many pages at once. To keep it testable, the web is given to you as data, and time is simulated.
Fetching page urls[i] takes fetchTimes[i] time units. When the fetch finishes, you learn the page's links, links[i], in order. The host of a URL is the part between "http://" and the next "/", or the end of the URL. For example, the host of "http://a.com/x" is "a.com".
Which pages to crawl
- At time
0,startUrlis the only accepted page. It counts toward its host's page total. - When a fetch finishes, go through its links in order. Skip a link whose page was already accepted, so cycles and repeated links are fetched only once. Also skip a link whose host already has
maxPagesPerHostaccepted pages, so a host that keeps producing new pages cannot trap the crawler. Otherwise, accept the page and add it to the end of the waiting line.
When fetches run
- At most
workersfetches run at the same time, and at most one fetch per host runs at a time. - To start fetches, go through the waiting line from the front. Start each page whose host has no running fetch, until no worker is free. A page whose host is busy keeps its place in the line. A fetch that starts at time
sfinishes at times + fetchTimes[i]. - Start fetches at time
0, and again after each moment when fetches finish. When several fetches finish at the same time, handle all of them first, in the order they started, and only then start new fetches.
Return the accepted pages in the order their fetches finish. Every accepted page is fetched exactly once.
Function
crawl(startUrl: String, urls: String[], fetchTimes: int[], links: String[][], workers: int, maxPagesPerHost: int) → List<String>Examples
Example 1
startUrl = "http://a.com"urls = ["http://a.com","http://a.com/x","http://b.com","http://a.com/y"]fetchTimes = [1,1,1,1]links = [["http://a.com/x","http://b.com","http://a.com/x"],["http://a.com"],["http://a.com/y"],[]]workers = 1maxPagesPerHost = 10return = ["http://a.com","http://a.com/x","http://b.com","http://a.com/y"]With one worker, pages are fetched one at a time in the order they were found.
http://a.comfinishes at time 1. Its links addhttp://a.com/xandhttp://b.com. The second copy ofhttp://a.com/xis already known, so it is skipped.http://a.com/xfinishes at time 2. Its only link goes back tohttp://a.com, which is already known.http://b.comfinishes at time 3 and addshttp://a.com/y, which finishes at time 4.
Example 2
startUrl = "http://s.io"urls = ["http://s.io","http://s.io/a","http://s.io/b","http://t.io"]fetchTimes = [1,3,1,2]links = [["http://s.io/a","http://s.io/b","http://t.io"],[],[],[]]workers = 2maxPagesPerHost = 10return = ["http://s.io","http://t.io","http://s.io/a","http://s.io/b"]Two workers, but only one fetch per host at a time.
- At time 1,
http://s.iofinishes and adds/a,/bandhttp://t.io.http://s.io/astarts (ends at 4).http://s.io/bmust wait because hosts.iois busy, sohttp://t.iotakes the second worker (ends at 3). - At time 3,
http://t.iofinishes. A worker is free, but the only waiting page is on the busy hosts.io. - At time 4,
http://s.io/afinishes andhttp://s.io/bstarts, ending at 5.
Example 3
startUrl = "http://trap.net/1"urls = ["http://trap.net/1","http://trap.net/2","http://trap.net/3","http://trap.net/4","http://ok.org"]fetchTimes = [1,1,1,1,1]links = [["http://trap.net/2","http://ok.org"],["http://trap.net/3"],["http://trap.net/4"],[],[]]workers = 2maxPagesPerHost = 2return = ["http://trap.net/1","http://trap.net/2","http://ok.org"]Each host may have at most 2 accepted pages. http://trap.net/1 is the first.
- At time 1 it finishes.
http://trap.net/2is accepted (the secondtrap.netpage) and so ishttp://ok.org. Both start on the two workers and end at time 2. - At time 2 both finish.
http://trap.net/2started first, so it is listed first. Its linkhttp://trap.net/3is dropped becausetrap.netalready has 2 pages.
Nothing is left to fetch, so the crawl ends after 3 pages.
Constraints
1 <= urls.length <= 1000fetchTimes.length == urls.lengthandlinks.length == urls.length- The values in
urlsare distinct. Each one is"http://", then a host made of lowercase English words joined by dots, then zero or more parts that are each"/"followed by zero or more lowercase English letters or digits. - Every URL, including
startUrland every link, has at most30characters. startUrlis one of the values inurls.1 <= fetchTimes[i] <= 10000 <= links[i].length <= 10- Every
links[i][j]is one of the values inurls. 1 <= workers <= 1001 <= maxPagesPerHost <= 1000
More OpenAI Onsite Interview questions
- Sparse Plant Infection SimulationPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Rectangle Point Coverage CountsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Message Event AggregationPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- 15-Minute Chat Session TrackerPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Segmented Durable Key-Value StorePHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Durable Work Queue OperationsPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Versioned Social NetworkPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Budgeted API Inference with Out-of-Order FeedbackONSITE INTERVIEW · Seen Oct 2026
- Plant Infection Simulation, Part 4: Death CountdownPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Count Friend CirclesPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Keyed Bounded Executor ScheduleMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Detect a Deadlock from Lock LogsHelm.ai · PHONE SCREEN
- Thread-Safe Task Storage and Worker DispatchNuro · ONSITE INTERVIEWNuro interview questions
- Satellite Network Message PropagationOptiver · OAOptiver interview questions
- Bus RoutesUiPath · PHONE SCREEN
- Split Tender Part 4 - RefundsStripe · OA · PHONE SCREENStripe interview questions
- Fuel Route with Fewest Station VisitsGoogle · ONSITE INTERVIEWGoogle interview questions
- Minimum Bus Routes to a DestinationPinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
- Jump Game IVZomato / Eternal · ONSITE INTERVIEWZomato / Eternal interview questions
- LRU Cache with TTLAutodesk · ONSITE INTERVIEWAutodesk interview questions