Datadog

01Log Ingestion and Query

Implement a simplified logging system that supports log ingestion and conditional queries. Each operation is one of the following strings:

ADD timestamp service level message: append one log entry
QUERY startTs endTs serviceOr* levelOr* keywordOr*: count matching logs A log matches a query if startTs ≤ timestamp ≤ endTs, service and level match exactly unless the filter is *, and keyword appears as a substring of the message unless the filter is *. Process all operations in order and return the outputs produced by the QUERY commands. Function Description Complete the function runLogIngestionQueries in the editor below. runLogIngestionQueries has the following parameter:
String[] operations: the operations to execute in order Returns int[]: the counts produced by the QUERY operations.

Constraints

1 ≤ operations.length ≤ 2 * 10⁵
Timestamps are non-negative integers.
service and level contain no spaces.
message may contain spaces and is matched by substring search.

Example 1

Input:

operations = ["ADD 1 api INFO hello world", "ADD 2 api ERROR something failed", "ADD 3 web INFO user login", "QUERY 1 3 * * *", "QUERY 1 2 api * *", "QUERY 2 3 api ERROR failed"]

Output:

[3, 2, 1]

Explanation: The three queries count all logs, then all api logs in the first two timestamps, then only the single error log whose message contains failed.

Example 2

Input:

operations = ["ADD 1 api INFO login ok", "ADD 2 api INFO logout ok", "ADD 3 api INFO login failed", "QUERY 1 3 api INFO login", "QUERY 1 3 api INFO ok", "QUERY 1 2 api INFO login", "QUERY 3 3 api INFO login"]

Output:

[2, 2, 1, 1]

Explanation: Substring matching on the message field allows both successful and failed login events to match the keyword login.

解法

朴素扫描即可：维护一个日志列表(时间戳、service、level、message)，每次 QUERY 遍历所有日志，按时间范围和三个过滤条件(* 代表通配)逐条匹配，keyword 用子串检测。设总操作数 O，每个 QUERY 最坏 O(O · L)，整体 O(O² · L)，L 为 message 长度；对 2·10⁵ 在 OA 环境通常够用。

from typing import List

def runLogIngestionQueries(operations: List[str]) -> List[int]:
    logs: list[tuple[int, str, str, str]] = []
    results: List[int] = []
    for op in operations:
        if op.startswith("ADD "):
            parts = op.split(" ", 4)
            ts = int(parts[1])
            logs.append((ts, parts[2], parts[3], parts[4]))
        else:
            parts = op.split(" ", 5)
            start, end = int(parts[1]), int(parts[2])
            svc_f, lvl_f, kw_f = parts[3], parts[4], parts[5]
            cnt = 0
            for ts, svc, lvl, msg in logs:
                if ts < start or ts > end:
                    continue
                if svc_f != "*" and svc != svc_f:
                    continue
                if lvl_f != "*" and lvl != lvl_f:
                    continue
                if kw_f != "*" and kw_f not in msg:
                    continue
                cnt += 1
            results.append(cnt)
    return results

import java.util.*;

class Solution {
    int[] runLogIngestionQueries(String[] operations) {
        List<long[]> tsAndIdx = new ArrayList<>();
        List<String[]> logs = new ArrayList<>();
        List<Integer> results = new ArrayList<>();
        for (String op : operations) {
            if (op.startsWith("ADD ")) {
                String[] parts = op.split(" ", 5);
                logs.add(new String[]{parts[1], parts[2], parts[3], parts[4]});
            } else {
                String[] parts = op.split(" ", 6);
                long start = Long.parseLong(parts[1]), end = Long.parseLong(parts[2]);
                String svcF = parts[3], lvlF = parts[4], kwF = parts[5];
                int cnt = 0;
                for (String[] log : logs) {
                    long ts = Long.parseLong(log[0]);
                    if (ts < start || ts > end) continue;
                    if (!svcF.equals("*") && !log[1].equals(svcF)) continue;
                    if (!lvlF.equals("*") && !log[2].equals(lvlF)) continue;
                    if (!kwF.equals("*") && !log[3].contains(kwF)) continue;
                    cnt++;
                }
                results.add(cnt);
            }
        }
        int[] out = new int[results.size()];
        for (int i = 0; i < out.length; i++) out[i] = results.get(i);
        return out;
    }
}

#include <vector>
#include <string>
#include <sstream>

class Solution {
public:
    std::vector<int> runLogIngestionQueries(std::vector<std::string>& operations) {
        std::vector<std::tuple<long long, std::string, std::string, std::string>> logs;
        std::vector<int> results;
        for (auto& op : operations) {
            std::stringstream ss(op);
            std::string head; ss >> head;
            if (head == "ADD") {
                long long ts; std::string svc, lvl; ss >> ts >> svc >> lvl;
                std::string msg; std::getline(ss, msg);
                if (!msg.empty() && msg[0] == ' ') msg.erase(0, 1);
                logs.push_back({ts, svc, lvl, msg});
            } else {
                long long start, end; std::string svcF, lvlF, kwF;
                ss >> start >> end >> svcF >> lvlF >> kwF;
                int cnt = 0;
                for (auto& [ts, svc, lvl, msg] : logs) {
                    if (ts < start || ts > end) continue;
                    if (svcF != "*" && svc != svcF) continue;
                    if (lvlF != "*" && lvl != lvlF) continue;
                    if (kwF != "*" && msg.find(kwF) == std::string::npos) continue;
                    cnt++;
                }
                results.push_back(cnt);
            }
        }
        return results;
    }
};