Katkat
Back

Solve substring and access-log problems

SumologicSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to process log data and perform string manipulation by identifying users who visited a specific URL across multiple days and determining the longest common substring between two modified strings.

Part 1: Cross-Day URL Consistency

Given a list of log entries represented as tuples (user_id, url, day), find all users who visited the same URL on both day_i and day_i + 1 for any given day. Return a list of unique user_ids who satisfy this condition.

Example: Logs: [(1, "/home", 1), (2, "/login", 1), (1, "/home", 2), (2, "/settings", 2)] Output: [1] (User 1 visited "/home" on both day 1 and 2).

Part 2: Substring Edit Similarity

Given two strings s1 and s2, you are allowed to perform at most one operation on s1: deleting any single character. After this operation (or choosing to perform none), find the length of the longest substring of the modified s1 that is also a substring of s2.

Function Signature: def max_modified_substring(s1: str, s2: str) -> int:

Constraints:

  • len(s1), len(s2) <= 1000
  • Time complexity should be better than O(N^3).

Example: Input: s1 = "abcde", s2 = "abce" Output: 4 (Delete 'd' from s1 to get "abce", which is a substring of s2).

Hints

Hint 1

For the logs, use a dictionary to group URLs by user and day, then intersect sets of URLs for consecutive days.

Hint 2

For the substring problem, note that deleting a character creates a new string `s1[:i] + s1[i+1:]` for all `i` from 0 to `len(s1)`.

Hint 3

Since checking all possible deletions is `O(N^2)`, you can use a Suffix Tree or Longest Common Substring dynamic programming approach to optimize each check.

Follow-up questions

  • How would you optimize the log processing if the number of entries is in the billions and must be processed in a distributed environment?
  • If the edit operation was instead a 'replacement' of one character, how would the complexity of the substring problem change?
  • How would you handle a scenario where logs arrive out of chronological order?