Katkat
Back

Solve string and hashmap coding tasks

Goldman SachsSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate strings, utilize hash maps for grouping data, and perform iterative simulations based on sequential command logs.

Problem Statement

You are building a logging system for a distributed task processor. The system receives a sequence of log entries, each formatted as "TASK_ID:COMMAND".

Your task is to process these entries and return a map where each key is a TASK_ID and the value is a list of commands that were executed for that task, but only if the task contains at least one "COMPLETED" command.

Additionally, after filtering, you must calculate the "Execution Score" for each valid task. The score is calculated as follows:

  • Each "START" command is worth 1 point.
  • Each "RETRY" command is worth 2 points.
  • Each "COMPLETED" command is worth 5 points.
  • Ignore any other command types.

Function Signature

def process_logs(logs: list[str]) -> dict[str, int]:

Constraints

  • logs list length: 0 to 10,000.
  • TASK_ID is a non-empty string of alphanumeric characters.
  • COMMAND can be any string, but only START, RETRY, and COMPLETED affect the score.

Example 1

Input:

logs = ["task1:START", "task1:RETRY", "task1:COMPLETED", "task2:START", "task2:PENDING"]

Output:

{"task1": 8}

Explanation: task1 contains COMPLETED, so it is processed: 1 (START) + 2 (RETRY) + 5 (COMPLETED) = 8. task2 is ignored because it lacks a COMPLETED command.

Edge Cases

  • Empty logs list.
  • Tasks with no valid commands.
  • Tasks that appear multiple times or in non-sequential order.
  • Tasks containing multiple COMPLETED commands.

Hints

Hint 1

Use a hash map (dictionary) to group commands by TASK_ID first, then iterate through the map to check for the 'COMPLETED' condition.

Hint 2

Consider using a second pass or a temporary storage structure to track which tasks have encountered the 'COMPLETED' keyword while parsing the input.

Hint 3

Ensure you handle the string splitting efficiently using the colon separator to isolate the ID from the command.

Follow-up questions

  • How would you modify your solution to return the tasks sorted by their execution score in descending order?
  • If the input log size were in the billions and could not fit in memory, what architectural approach would you take to process this?
  • What is the time and space complexity of your current solution in terms of total logs N and unique tasks K?