FastPrepConcurrent Web Crawler Simulation
Problems/Concurrent Web Crawler Simulation

Concurrent Web Crawler Simulation

OpenAI logoOpenAI● HardFULLTIMEPHONE SCREENONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reports from April 2020 to August 2021 describe a coding round at an OpenAI onsite where you build a web crawler. You visit the pages you can reach from a start page, first one page at a time and then with several workers running at once.

None of them gives the fetch interface, the timing or what to return. Here the web is given as data and fetch time is simulated. At most workers fetches run at once, and you return pages in the order their fetches finish. Running only one fetch per host at a time, and keeping at most maxPagesPerHost pages per host, are our own rules. Real threads are covered in the editorial and are not tested. The examples are our own.

Our version is about 55% the same as the reported questions.

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, startUrl is 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 maxPagesPerHost accepted 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 workers fetches 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 s finishes at time s + 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.com finishes at time 1. Its links add http://a.com/x and http://b.com. The second copy of http://a.com/x is already known, so it is skipped.
  • http://a.com/x finishes at time 2. Its only link goes back to http://a.com, which is already known.
  • http://b.com finishes at time 3 and adds http://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.io finishes and adds /a, /b and http://t.io. http://s.io/a starts (ends at 4). http://s.io/b must wait because host s.io is busy, so http://t.io takes the second worker (ends at 3).
  • At time 3, http://t.io finishes. A worker is free, but the only waiting page is on the busy host s.io.
  • At time 4, http://s.io/a finishes and http://s.io/b starts, 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/2 is accepted (the second trap.net page) and so is http://ok.org. Both start on the two workers and end at time 2.
  • At time 2 both finish. http://trap.net/2 started first, so it is listed first. Its link http://trap.net/3 is dropped because trap.net already has 2 pages.

Nothing is left to fetch, so the crawl ends after 3 pages.

Constraints

  • 1 <= urls.length <= 1000
  • fetchTimes.length == urls.length and links.length == urls.length
  • The values in urls are 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 startUrl and every link, has at most 30 characters.
  • startUrl is one of the values in urls.
  • 1 <= fetchTimes[i] <= 1000
  • 0 <= links[i].length <= 10
  • Every links[i][j] is one of the values in urls.
  • 1 <= workers <= 100
  • 1 <= 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
All OpenAI interview questionsSee OpenAI hiring insights
Saved
class Solution {
    public List<String> crawl(String startUrl, String[] urls, int[] fetchTimes, String[][] links, int workers, int maxPagesPerHost) {
        // Write your code here.
    }
}
Checking account…