कठिन 1 हल किया गया 100.0% स्वीकृति

Scaled Dot-Product Attention

Implement the attention operation at the heart of Transformers and large language models.

आप क्या सीखेंगे

  • Score queries against keys
  • Apply softmax to get attention weights
  • Mix values with those weights

समस्या

अनुवाद दिखाएँ

Attention lets each position in a sequence look at every other position and mix their information. It is the core of the Transformer architecture used by large language models:

Attention(Q, K, V) = softmax(Q × Kᵀ / √d) × V

For each query row q:

  1. Score every key row k: score = (q · k) / √d, where d is the number of columns of K.
  2. Turn the scores into weights with softmax (subtract the largest score before taking e^x).
  3. The output row is the weighted sum of the value rows: Σ weight_j × values[j].

Implement attention(queries, keys, values).

Input

queries: n rows, each with d numbers.

keys: m rows, each with d numbers.

values: m rows (one per key), each with v numbers.

Output

Return the n × v output matrix.

सीमाएँ

1 ≤ n, m ≤ 50, 1 ≤ d, v ≤ 32

-10 ≤ each value ≤ 10

उदाहरण

उदाहरण 1
इनपुट:
queries = [
    [1.0, 0.0]
]
keys = [
    [1.0, 0.0],
    [1.0, 0.0]
]
values = [
    [2.0, 4.0],
    [6.0, 8.0]
]

अपेक्षित आउटपुट:
expected = [
    [4.0, 6.0]
]
इनपुट:
std::vector<std::vector<double>> queries = {
    {1.0, 0.0}
};
std::vector<std::vector<double>> keys = {
    {1.0, 0.0},
    {1.0, 0.0}
};
std::vector<std::vector<double>> values = {
    {2.0, 4.0},
    {6.0, 8.0}
};

अपेक्षित आउटपुट:
std::vector<std::vector<double>> expected = {
    {4.0, 6.0}
};
इनपुट:
double[][] queries = new double[][] {
    new double[] {1.0, 0.0}
};
double[][] keys = new double[][] {
    new double[] {1.0, 0.0},
    new double[] {1.0, 0.0}
};
double[][] values = new double[][] {
    new double[] {2.0, 4.0},
    new double[] {6.0, 8.0}
};

अपेक्षित आउटपुट:
double[][] expected = new double[][] {
    new double[] {4.0, 6.0}
};

व्याख्या

Both keys give the same score, so the softmax weights are 0.5 and 0.5. The output is the average of the value rows: [(2 + 6) / 2, (4 + 8) / 2] = [4, 6].

उदाहरण 2
इनपुट:
queries = [
    [0.0, 0.0]
]
keys = [
    [3.0, 1.0],
    [-2.0, 5.0],
    [7.0, 7.0]
]
values = [
    [1.0],
    [2.0],
    [6.0]
]

अपेक्षित आउटपुट:
expected = [
    [3.0]
]
इनपुट:
std::vector<std::vector<double>> queries = {
    {0.0, 0.0}
};
std::vector<std::vector<double>> keys = {
    {3.0, 1.0},
    {-2.0, 5.0},
    {7.0, 7.0}
};
std::vector<std::vector<double>> values = {
    {1.0},
    {2.0},
    {6.0}
};

अपेक्षित आउटपुट:
std::vector<std::vector<double>> expected = {
    {3.0}
};
इनपुट:
double[][] queries = new double[][] {
    new double[] {0.0, 0.0}
};
double[][] keys = new double[][] {
    new double[] {3.0, 1.0},
    new double[] {-2.0, 5.0},
    new double[] {7.0, 7.0}
};
double[][] values = new double[][] {
    new double[] {1.0},
    new double[] {2.0},
    new double[] {6.0}
};

अपेक्षित आउटपुट:
double[][] expected = new double[][] {
    new double[] {3.0}
};

व्याख्या

A zero query scores 0 against every key, so attention is spread evenly: (1 + 2 + 6) / 3 = 3.

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

For each query, compare it with every key using a dot product scaled by the square root of the key dimension.

संकेत 2

Convert the scores into weights with a numerically stable softmax, then blend the value rows using those weights.

संकेत 3

Each query produces one output row, and the value vectors determine the output width rather than the queries or keys.

अपेक्षित जटिलता

O(n m (d + v)) time, O(m) extra space

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

# कोडर भाषा समय मेमोरी AI रिव्यू समाधान
1 ННикита Python 833 ms - 5/5 कोड देखें

दूसरों से सीखें

समुदाय समाधान

स्पॉइलर अलर्ट: नीचे 1 पूरा समाधान पहले खुद हल करने की कोशिश करें। आप फिर भी अन्य डेवलपर्स का कोड और AI समीक्षा देख सकते हैं। चर्चा में शामिल होने के लिए साइन इन करें और चुनौती हल करें।