Quick Overview

Aggregate completed HTTP request logs across files to find the top five client IPv4 addresses, excluding auxiliary messages and applying deterministic count ties.

Find the Five Busiest Client IPs in Request Logs

Company: Render

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

During an API traffic incident, find the five client IP addresses with the most completed request-log entries across several files. Ignore background-service messages and auxiliary messages that mention an IP without recording a request. Implement `top_request_ips(files: string[][]) -> string[][]`. Each inner input array contains the lines of one file. Return rows `[ip,count]`, ordered by descending numeric count and then by ascending numeric IPv4 address. Return fewer than five rows if fewer than five distinct client addresses occur. ### Constraints & Assumptions The source provides file logs with HTTP request lines, background messages, and a separate `Client IP=` redirect diagnostic. Passing file contents directly and the deterministic tie order are explicit practice choices. - At most 20 files and 200000 lines in total; total input length is at most 20000000 characters. - A counted line contains a request portion of the form `METHOD URL HTTP/version`, followed later on that same line by ` from A.B.C.D:port - status`. METHOD is one of GET, POST, PUT, PATCH, DELETE, HEAD, OPTIONS. Version is 1.0, 1.1, or 2.0. Status is exactly three decimal digits. - Request-line quote characters may be escaped with backslashes, as in the reported logs. Match the request and client-address fields, not an assumed fixed quote position. - Counted lines have exactly one such request/client pair. Other lines have no complete pair, even if they contain `Client IP=` or an isolated `from` substring. - IPv4 octets are decimal integers from 0 to 255 with no leading zeroes except `0`; ports are decimal integers from 1 to 65535. IPv6, forwarded-header interpretation, multiline records, and malformed request fields are outside this practice contract. - Count every completed request line once, including non-2xx statuses, repeated request IDs if any, private IPs, and lines in different files. Ignore the port when grouping. No file-overlap deduplication is implied. - Return counts as ordinary decimal strings. Numeric IPv4 tie order compares the four integer octets left to right, not the textual address strings. ### Example ```text files = [[ 'time="t" msg="GET https://api.example/a HTTP/2.0 from 10.0.0.2:12 - 200 4B"', 'time="t" msg="redirecting" Client IP="10.0.0.9:15"', 'time="t" msg="POST https://api.example/b HTTP/1.1 from 10.0.0.2:13 - 500 0B"' ], [ 'time="t" msg="GET https://api.example/c HTTP/1.1 from 10.0.0.10:14 - 200 4B"', 'time="t" msg="no pending executions"' ]] result = [["10.0.0.2","2"],["10.0.0.10","1"]] ``` Explain how you would read an actual archive incrementally without loading all files into memory. Distinguish a high request count from proof that an address is malicious. ```hint Count the event, not every address mention First identify a completed HTTP request record. Its `from` field supplies the client address; a separate diagnostic for the same request is not another request. ```

Overview: Aggregate completed HTTP request logs across files to find the top five client IPv4 addresses, excluding auxiliary messages and applying deterministic count ties.

Read the full Render Software Engineer interview experience this question came from

During an API traffic incident, find the five client IP addresses with the most completed request-log entries across several files. Ignore background-service messages and auxiliary messages that mention an IP without recording a request. Implement `top_request_ips(files: string[][]) -> string[][]`. Each inner input array contains the lines of one file. Return rows `[ip,count]`, ordered by descending numeric count and then by ascending numeric IPv4 address. Return fewer than five rows if fewer than five distinct client addresses occur. ### Constraints & Assumptions The source provides file logs with HTTP request lines, background messages, and a separate `Client IP=` redirect diagnostic. Passing file contents directly and the deterministic tie order are explicit practice choices. - At most 20 files and 200000 lines in total; total input length is at most 20000000 characters. - A counted line contains a request portion of the form `METHOD URL HTTP/version`, followed later on that same line by ` from A.B.C.D:port - status`. METHOD is one of GET, POST, PUT, PATCH, DELETE, HEAD, OPTIONS. Version is 1.0, 1.1, or 2.0. Status is exactly three decimal digits. - Request-line quote characters may be escaped with backslashes, as in the reported logs. Match the request and client-address fields, not an assumed fixed quote position. - Counted lines have exactly one such request/client pair. Other lines have no complete pair, even if they contain `Client IP=` or an isolated `from` substring. - IPv4 octets are decimal integers from 0 to 255 with no leading zeroes except `0`; ports are decimal integers from 1 to 65535. IPv6, forwarded-header interpretation, multiline records, and malformed request fields are outside this practice contract. - Count every completed request line once, including non-2xx statuses, repeated request IDs if any, private IPs, and lines in different files. Ignore the port when grouping. No file-overlap deduplication is implied. - Return counts as ordinary decimal strings. Numeric IPv4 tie order compares the four integer octets left to right, not the textual address strings. ### Example ```text files = [[ 'time="t" msg="GET https://api.example/a HTTP/2.0 from 10.0.0.2:12 - 200 4B"', 'time="t" msg="redirecting" Client IP="10.0.0.9:15"', 'time="t" msg="POST https://api.example/b HTTP/1.1 from 10.0.0.2:13 - 500 0B"' ], [ 'time="t" msg="GET https://api.example/c HTTP/1.1 from 10.0.0.10:14 - 200 4B"', 'time="t" msg="no pending executions"' ]] result = [["10.0.0.2","2"],["10.0.0.10","1"]] ``` Explain how you would read an actual archive incrementally without loading all files into memory. Distinguish a high request count from proof that an address is malicious. ```hint Count the event, not every address mention First identify a completed HTTP request record. Its `from` field supplies the client address; a separate diagnostic for the same request is not another request. ```

Constraints

  • At most 20 files, 200000 lines and 20000000 total characters.
  • Count complete same-line METHOD URL HTTP/version portions followed later by from IPv4:port - exactly-three-digit-status.
  • Method is GET, POST, PUT, PATCH, DELETE, HEAD or OPTIONS; version is 1.0, 1.1 or 2.0; quotes may be backslash-escaped.
  • IPv4 octets are 0 through 255 with no leading zeroes except 0; ports are decimal integers 1 through 65535. Malformed request fields, IPv6 and multiline interpretation are outside the contract.
  • Count every completed line once across files regardless of status, private IP or repeated IDs; ignore ports and auxiliary IP mentions.
  • Return at most five [ip,count] rows, descending by count then ascending numeric IPv4, with decimal-string counts.

Examples

Input: ([['time=t msg="GET /resource HTTP/2.0 from 10.0.0.2:12 - 200 4B"', 'time=t msg="redirecting" Client IP="10.0.0.9:15"', 'time=t msg="POST /resource HTTP/1.1 from 10.0.0.2:13 - 500 4B"'], ['time=t msg="GET /resource HTTP/1.1 from 10.0.0.10:14 - 200 4B"', 'time=t msg="no pending executions"']],)

Expected Output: [['10.0.0.2', '2'], ['10.0.0.10', '1']]

Explanation: The source scenario counts completed requests across files but not diagnostics.

Input: ([['time=t msg="GET /resource HTTP/1.1 from 1.0.0.10:80 - 200 4B"', 'time=t msg="GET /resource HTTP/1.1 from 1.0.0.2:80 - 200 4B"', 'time=t msg="GET /resource HTTP/1.1 from 255.255.255.255:80 - 200 4B"', 'time=t msg="GET /resource HTTP/1.1 from 0.0.0.0:80 - 200 4B"', 'time=t msg="GET /resource HTTP/1.1 from 10.0.0.1:80 - 200 4B"', 'time=t msg="GET /resource HTTP/1.1 from 2.0.0.0:80 - 200 4B"', 'time=t msg="GET /resource HTTP/1.1 from 1.0.0.1:80 - 200 4B"']],)

Expected Output: [['0.0.0.0', '1'], ['1.0.0.1', '1'], ['1.0.0.2', '1'], ['1.0.0.10', '1'], ['2.0.0.0', '1']]

Explanation: Numeric octet order resolves a tie at the top-five boundary.

Loading coding console...

Show the approach

Approach

Locate a supported METHOD URL HTTP/version request portion without assuming where quote characters occur. Then look only later in the same line for its complete from IPv4:port - three-digit-status field. The implementations use separate request/client recognizers; C++ scans those fields directly to avoid recursive regular-expression processing of long URL tokens. Validate canonical IPv4 octets and the port range, count one complete pair per line, and ignore status class when incrementing. Auxiliary Client IP diagnostics and standalone fields lack the required ordered pair. Encode four octets into a nonnegative 32-bit numeric key, then rank distinct keys by descending counts and ascending keys; this is the required octet-by-octet numeric tie order. Reconstruct canonical dotted addresses and return up to five counts. Ports, file identity and repeated request IDs do not partition or deduplicate counts. With C input characters and D distinct clients, field processing scans the records and ranking adds O(D log D); memory is O(D) counting/ranking state plus parsing space for the current line. When reading a real archive, iterate files and lines through bounded decompression buffers and update this same map, rather than materializing every file; protect resource limits for very large archives. A high count identifies traffic volume, not malicious intent: proxies, legitimate bulk clients and retry behavior require separate evidence.

Time complexity:
Field scanning over C input characters plus O(D log D) ranking
Space complexity:
O(D) count/ranking state plus current-line parsing space and output