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回の判定が速くなります。