Namaran

Code daily. Without assist.

2026-10-06

idempotency.c

struct seen {
    int len;
    unsigned keys[64];
};

bool first_time(struct seen *s, unsigned key) {
}

再送された要求を二重に処理しないよう、処理済みの冪等性キーを struct seen に記録しておきます。key が初めて届いたキーなら s に記録して true を、記録済みなら s を変えずに false を返す first_time を書いてください。s->keys のうち使っているのは先頭の s->len 個で、記録するキーは64個を超えないものとします。入出力例は、struct seen s = {0}; で作った空の表に対して順に呼んだときの戻り値です。

入力例 1

first_time(&s, 7); first_time(&s, 9); first_time(&s, 7);

出力例 1

true, true, false

入力例 2

first_time(&s, 0);

出力例 2

true

入力例 3

first_time(&s, 5); first_time(&s, 5); first_time(&s, 5);

出力例 3

true, false, false
Reference
struct seen {
    int len;
    unsigned keys[64];
};

bool first_time(struct seen *s, unsigned key) {
    for (int i = 0; i < s->len; i++)
        if (s->keys[i] == key) return false;
    s->keys[s->len++] = key;
    return true;
}

参考実装は、記録済みの先頭 s->len 個だけを順に調べ、見つからなければ末尾に足します。調べる範囲を64個全部にしないのは、{0} で初期化した表の残りの要素が0で埋まっているからです。全部を調べると、入力例2の 0 が未使用の要素と一致し、初めてのキーなのに false が返ります。

掲載したのは参考実装で、唯一の正解ではありません。キーが多いなら、ハッシュ表や、ソート済みの配列に対する二分探索を使うと、1回の判定が速くなります。