Given daily prices A[N], you start with one unit of the asset and may hold at most one at a time. You can sell whenever you hold one and rebuy whenever you don't. Compute the maximum income; return the last 9 digits (mod 10⁹).

Example: A = [1, 2, 3, 3, 2, 1, 5] → 7.

Constraints

• 1 ≤ N ≤ 200000
• 0 ≤ A[i] ≤ 10⁹

解法

把所有正的相邻差 max(0, A[i] - A[i-1]) 累加 —— 等价于每个局部峰卖出、每个局部谷买入的总收益。模 10⁹。复杂度 O(N)。

def max_historical_income(A):
    profit = sum(max(0, A[i] - A[i-1]) for i in range(1, len(A)))
    return profit % 10**9

class Solution {
    static long maxHistoricalIncome(int[] A) {
        long MOD = 1_000_000_000L;
        long profit = 0;
        for (int i = 1; i < A.length; i++)
            if (A[i] > A[i - 1]) profit += A[i] - A[i - 1];
        return profit % MOD;
    }
}

long long maxHistoricalIncome(vector<int>& A) {
 const long long MOD = 1'000'000'000LL;
 long long profit = 0;
 for (int i = 1; i < (int)A.size(); ++i)
 if (A[i] > A[i - 1]) profit += A[i] - A[i - 1];
 return profit % MOD;
}

A regex is built from uppercase letters and [...] bracket groups holding a non-repeating uppercase subset ([ABC] matches any of A, B, C); concatenation builds longer regexes. Given strings x, y, z of equal length n, find the longest regex that matches both x and y but not z. If multiple, output the lexicographically smallest one. If none exists, return "-1".

Constraints

• 1 ≤ n ≤ 10⁶

解法

每个位置 i 的括号组必须包含 x[i] 和 y[i]。要让答案对 z 失配：找一个 i* 使 z[i*] 与 x[i*] 和 y[i*] 都不同，仅在该组排除 z[i*]，其余组全用 26 个字母。字典序最小取最早的这种 i*；若不存在返回 "-1"。复杂度 O(n · 26)。

def amazon_regex(x, y, z):
    n = len(x)
    best_star, best_excl = -1, ''
    for i in range(n):
        if z[i] != x[i] and z[i] != y[i]:
            best_star, best_excl = i, z[i]
            break
    if best_star == -1: return "-1"
    parts = []
    for i in range(n):
        chars = ''.join(c for c in "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
                        if not (i == best_star and c == best_excl))
        parts.append(f"[{chars}]")
    return ''.join(parts)

class Solution {
    static String amazonRegex(String x, String y, String z) {
        int n = x.length();
        int bestStar = -1, bestExcl = -1;
        for (int i = 0; i < n; i++)
            if (z.charAt(i) != x.charAt(i) && z.charAt(i) != y.charAt(i)) { bestStar = i; bestExcl = z.charAt(i) - 'A'; break; }
        if (bestStar == -1) return "-1";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append('[');
            for (char c = 'A'; c <= 'Z'; c++) {
                if (i == bestStar && c == 'A' + bestExcl) continue;
                sb.append(c);
            }
            sb.append(']');
        }
        return sb.toString();
    }
}

string amazonRegex(string x, string y, string z) {
 int n = x.size();
 int bestStar = -1; char bestExcl = 0;
 for (int i = 0; i < n; ++i)
 if (z[i] != x[i] && z[i] != y[i]) { bestStar = i; bestExcl = z[i]; break; }
 if (bestStar == -1) return "-1";
 string out;
 for (int i = 0; i < n; ++i) {
 out += '[';
 for (char c = 'A'; c <= 'Z'; ++c) {
 if (i == bestStar && c == bestExcl) continue;
 out += c;
 }
 out += ']';
 }
 return out;
}

Given points[n], players alternate picking any remaining element (player 1 first). Both maximize their own score. Return score1 - score2 under optimal play.

Example: points = [4, 1, 2, 3] → 2.

解法

贪心最优：降序排序后，先手取偶数位 0, 2, 4, ...，后手取奇数位 1, 3, 5, ...。差值 = Σ (-1)^i · sorted[i]。复杂度 O(n log n)。

def pick_difference(points):
    a = sorted(points, reverse=True)
    return sum(a[i] if i % 2 == 0 else -a[i] for i in range(len(a)))

class Solution {
    static long pickDifference(int[] points) {
        Integer[] a = new Integer[points.length];
        for (int i = 0; i < points.length; i++) a[i] = points[i];
        Arrays.sort(a, Collections.reverseOrder());
        long diff = 0;
        for (int i = 0; i < a.length; i++) diff += (i % 2 == 0 ? a[i] : -a[i]);
        return diff;
    }
}

long long pickDifference(vector<int>& points) {
 vector<int> a = points;
 sort(a.begin(), a.end(), greater<int>());
 long long diff = 0;
 for (int i = 0; i < (int)a.size(); ++i) diff += (i % 2 == 0 ? a[i] : -a[i]);
 return diff;
}

Find all values appearing exactly twice in values[]. Output the doubled values, separated by spaces, in ascending sorted order.

Score for a positive integer n is the sum of four independent components evaluated on the decimal representation:

• +2 per digit '5'.
• +4 for each consecutive pair of '3's — a run of N consecutive '3's contributes +4 · (N-1).
• +N² for each maximal run of length N (N ≥ 1) where every digit is prev + 1.
• +6 if n is divisible by 5.
• +1 per odd digit.

A digit can contribute to multiple components.

Events look like "ACQUIRE X" or "RELEASE X". A correct log: locks must release in reverse order of acquire; a lock can't be released without being held; a held lock can't be re-acquired. Return:

• 0 if there are no violations and no dangling locks.
• N + 1 if dangling locks remain after the last event (but no in-stream violation).
• K (1-based) on the first violating event.

Given a lowercase string s, count all (i, j) pairs with i ≤ j such that s[i..j] is a palindrome. Identical substrings at different positions count separately.

Example: s = "hellolle" → 13; s = "wowyouwin" → 14.

Bob wrote the binary search below and claims it returns the index of target in a sorted array, or -1 if not present. Either prove it correct or produce a counterexample sorted array + target where it returns the wrong answer.

int sorted_search(int* elements, int size, int target) {
 if (size <= 0 || !elements) return -1;
 int left = 0, right = size - 1;
 while (left < right) {
 int middle = (left + right + 1) / 2;
 if (elements[middle] > target) right = middle - 1;
 else left = middle + 1;
 }
 if (elements[right] == target) return right;
 return -1;
}

Q1: One million sorted integers — array vs doubly linked list lookup

We want to store one million "interesting" 64-bit unsigned integers, inserted in sorted order, and query whether a random 64-bit value is interesting. Each element probe takes 5 ns. Average-case lookup time?

• (A) 100 ns array / 2.5M ns linked list
• (B) 100 ns array / 5M ns linked list
• (C) 2.5M ns array / 2.5M ns linked list
• (D) 2.5M ns array / 5M ns linked list
• (E) 2.5M ns array / 100 ns linked list
• (F) 5M ns array / 100 ns linked list

Answer: A. Random-access array supports binary search in log2(10⁶) ≈ 20 probes → ≈ 100 ns. Linked list has no random access, so binary search degrades; average half-list scan is 5·10⁵ probes → ≈ 2.5M ns.

Q2: Alphabetic comparator bug

The instructor's comparator increments letter_index before reading characters, skipping index 0; for inputs ["aaa", "ccc"] it ends up comparing position 1 vs 1 ('a' vs 'c'), returns False, and the sort tries to swap — but the same buggy compare reverses on the swapped order too, leading to undefined behavior or an infinite loop in some sort frameworks.

• (A) ["ccc", "aaa"]
• (B) ["ccc", "ccc"]
• (C) ["aaa", "aaa"]
• (D) ["aaa", "ccc"]
• (E) Program will crash, throw an error, or exhibit undefined behavior.

Answer: E. The off-by-one (letter_index += 1 before reading) and the "return True even on equal" tail mean the comparator is not a strict weak ordering — most standard sorts will exhibit undefined behavior.

Q3: Extract a Field (bit ops on byte 6)

Records pack data-routing, pri, flag, r and destination-id into bytes 4-7. The flag field occupies bits 6..4 of byte 6 (3-bit field). Which expression extracts flag?

• (A) (record[2] & 0xF0) >> 4
• (B) (record[6] | 0xF) >> 4
• (C) (record[2] >> 4) & 0x7
• (D) (record[2] & 0x7) << 1
• (E) (record[6] & 0x70) >> 4

Answer: E. Mask 0x70 = 0111_0000 keeps exactly bits 6..4 of record[6], then shift right by 4 to align.

Q4: Stack size trace

list = [3, 3, 4, 2, 5, 4]
for element in list:
 if element is odd: push element
 else: old = pop; if old > element: push element

What is the maximum stack size?

• (A) 1
• (B) 2
• (C) 3
• (D) 4
• (E) 5

Answer: B (2). Trace: push 3 (size 1) → push 3 (size 2) → pop, 3<4, no push (size 1) → pop, 3>2, push 2 (size 1) → push 5 (size 2) → pop, 5>4, push 4 (size 1). Peak = 2.

Q5: Singly linked list operations dependent on length

Singly linked list with head pointer F and tail pointer L. Which operations take time proportional to list length?

• (A) Split the list into two equal-length lists
• (B) Add an element after the last element
• (C) Add an element before the last element
• (D) Add an element after the first element
• (E) Interchange first and last elements

Answer: A, C, E. Splitting requires walking to the midpoint (O(n)); inserting before tail needs the second-to-last node, which requires a full scan (O(n)); interchanging first and last requires the second-to-last node to relink (O(n)). Appending after L and inserting after F are both O(1) since we have those pointers directly.

Q6: Loop invariant of p = (k-1)!

p = 1; k = 1;
while (k < n) { p = p * k; k = k + 1; }

Which is a loop invariant (true at every loop-head and at exit)?

• (A) p = n^k
• (B) p = (k - 1)!
• (C) p = k!
• (D) p = (n-1)!
• (E) p = 2^(k-1)

Answer: B. Initially k = 1, p = 1 = 0! = (k-1)!. After each iteration k becomes k+1 and p is multiplied by the old k, preserving p = (k_new - 1)!.

Q7: Random number guessing in [1, 200]

Mary plays yes/no 20-questions on a number from 1 to 200, adversary always tells the truth. Worst-case optimal number of questions?

• (A) 199
• (B) 99
• (C) 32
• (D) 16
• (E) 8

Answer: E (8). Binary search the range: ceil(log2(200)) = 8.

Q8: BNF grammar derivations

Given the grammar (word starts with a letter, then optional pairlet of pairs of letters OR pairdg of pairs of digits), which strings can be derived?

• (A) pairlet — derivable: p + airlet (6 letters = 3 pairs). Yes.
• (B) pairlets — 8 letters: p + 7 letters. 7 is odd, can't form pairlet. No.
• (C) 70words — starts with a digit. word must start with a letter. No.
• (D) w70 — w + 2 digits = letter + pairdg. Yes.
• (E) words70 — w + ords (4 letters, 2 pairs) but then 70 (2 digits) follows. The grammar allows letter pairlet OR letter pairdg, NOT mixed. ords70 is not a valid suffix. No.

Answer: A, D. (Some OA versions also accept E if the grammar is interpreted with concatenation; the conservative answer is A, D.)

Q9: Stack initialization

Push: i := i + 1; S[i] := x
Pop: x := S[i]; i := i - 1

Stack array S[1..N]. Which initializes i correctly?

• (A) i := N
• (B) i := N - 1
• (C) i := N + 1
• (D) i := 0
• (E) i := 1

Answer: D. Push increments i before writing, so the first push lands at S[1]. That requires i = 0 initially.

Q10: Concurrency with atomic statements

Task 0: Task 1:
 x = 1 y = 1
 a = x + y b = x - y

Each statement is atomic. x = y = 0 initially. Which must hold?

• (A) (a == 2) ⇒ (b == 0)
• (B) (a == 1) ⇒ (b == 0)
• (C) (b == -1) ⇒ (a == 2)
• (D) (b == 0) ⇒ (a == 2)
• (E) None of the above

Answer: B, C.

• B: a == 1 means Task 0 saw x + y = 1. Since Task 0 just wrote x = 1, that requires y = 0 at the read, so Task 1 had not yet executed y = 1. Task 1 will then later read x = 1, y = 1, giving b = 0.
• C: b == -1 means Task 1 read x = 0, y = 1, so it executed both statements before Task 0's x = 1. Task 0 then reads x = 1, y = 1, so a = 2.
• A is false: a == 2 is consistent with Task 1 running y = 1 before Task 0's read and x = 1 after; b could equal -1.
• D is false: b == 0 is consistent with a == 1 from rule B above.

Q11: Adjacent pixels gray-level pairs

A 10-level (0..9) gray pixel pair (p, q) is legal if |p - q| ≤ 2. How many of the 100 ordered pairs are legal?

• (A) 10
• (B) 20
• (C) 34
• (D) 44
• (E) 90

Answer: D (44). For each p, the count of legal q values within ±2 is:

• p = 0 or 9: 3 choices
• p = 1 or 8: 4 choices
• p = 2..7 (six values): 5 choices each Total = 2·3 + 2·4 + 6·5 = 6 + 8 + 30 = 44.

Q12: Binary tree of height 6 — failure success probability

A full binary search tree of height 6 has 2⁷ - 1 = 127 nodes. Exactly one node fails (and all its descendants become unreachable); you randomly pick a target node. Probability that the failed node is not on the root→target path?

The probability of failure equals the average depth of a target node divided by 127. Sum of depths in a full tree of height 6 is Σ_{d=0}^{6} d · 2^d = 502. Expected probability of failure given uniform target = (1/127) · (502/127) ≈ 0.0312. Success ≈ 96.9%.

• (A) 90-100% — correct
• (B) 80-89.99%
• (C) 70-79.99%
• (D) 60-69.99%
• (E) 50-59.99%
• (F) less than 50%

Answer: A. ≈ 96.9% success.

Q13: Concurrent container thread safety

The concurrent_container shown uses one mutex around get, set, resize, but never destroy. Issues present?

• (A) Deadlock possible — No (single mutex).
• (B) Resource leak — No (destroy frees data).
• (C) Doesn't prevent multiple threads from accessing data — No (every method takes the lock).
• (D) Memory corruption — Yes: malloc(size) should be malloc(size * sizeof(int)); the buffer is size bytes but stores size ints.
• (E) Unaligned memory access — possible consequence of (D) on some platforms.
• (F) Doesn't handle invalid input — Yes: get returns -INT_MAX on out-of-range but only after entering the critical section and leaks the lock on the early return (no release before returning).
• (G) Integer overflow not protected — Yes: int N and size * sizeof(int) can overflow.
• (H) Correct and thread-safe — No.

Answer: D, F, G.

Q14: Timestamp-sorted container design

Insertion-only container of up to 10⁹ 32-bit-timestamped objects; iterate in sorted order occasionally; single-threaded. Acceptable worst-case designs?

• (A) Array, append + quicksort before iterate — quicksort is O(n log n) per iterate, append O(1). Acceptable.
• (B) Array, append + in-place merge sort after each insertion — O(n log n) per insert → totally O(n² log n). Not acceptable.
• (C) Array, keep sorted by inserting at correct position — O(n) per insert → O(n²) total. Not acceptable at 10⁹.
• (D) Balanced tree by timestamp — O(log n) per insert + O(n) iterate. Acceptable.
• (E) Linked list + merge sort before iterate — O(n log n) per iterate, O(1) insert. Acceptable.
• (F) Hashmap keyed by timestamp — iteration is not sorted unless re-sorted. Acceptable if you also sort on iterate (O(n log n) per iterate).
• (G) Preallocate array indexed by timestamp value (32-bit range = 4·10⁹ slots) — memory blowout for 10⁹ objects in 4·10⁹ slots is feasible (~16 GB), but worst-case iterate is O(2³²). Not acceptable.

Answer: A, D, E (F is borderline-acceptable).

Q15: Memory page record minimum bytes

Fields:

• Page status: 3 states → 2 bits.
• Page index: range [0, 364847] → log2(364848) = 19 bits.
• Access mode: 6 modes → 3 bits.
• Process ID: range [0, 37337] → log2(37338) = 16 bits.

Total = 2 + 19 + 3 + 16 = 40 bits = 5 bytes. With the "direct field access API as simple as possible" (byte-aligned fields, no bit-packing), each field rounds up to whole bytes: 1 + 3 + 1 + 2 = 7 bytes.

Answer: 7 bytes (under the byte-aligned interpretation; 5 bytes under bit-packed).

Q16: 7-drive RAID 0 fill-up time (Codility memory/throughput math)

Workload: 200000 writes/s; distribution 512B 20% / 1024B 30% / 4096B 40% / 16384B 10%. Average write size = 0.2·512 + 0.3·1024 + 0.4·4096 + 0.1·16384 = 102.4 + 307.2 + 1638.4 + 1638.4 = 3686.4 bytes. Aggregate write rate = 200000 · 3686.4 = 7.37 · 10⁸ bytes/s.

Total capacity = 7 · 513 GiB = 3591 GiB = 3855.5 · 10⁹ bytes. Target 86% = 3.315 · 10¹² bytes.

Time = 3.315e12 / 7.37e8 ≈ 4500 s ≈ 75 minutes.

Answer: ≈ 75 minutes.

Q17: DFS print order

dfs(node, target) prints node->value, marks visited = true, then recurses into right_child, parent, left_child (in that order, skipping visited or NULL nodes). Trace through the tree from dfs(node_11, target = 12).

Without the OCR'd diagram being fully legible, the print sequence depends on the exact tree shape. Typical Pure Storage answer pattern: nodes are visited in the order 11 → 5 (right child) → ... → 12, with the print list ending at 12.

Answer: depends on the exact tree; typical correct answer prints all ancestors then siblings before reaching 12.

Q18: Alice's two-tier memory (LRU vs random)

Type A: 10 GB, 1 ms per read. Type Z: 1 TB, 100 ms per read. All 2048 objects stored in Z (size 512 MB each), copies of up to 20 objects fit in A (10 GB / 512 MB = 20).

• Naive random fill, 10 random reads: P(hit) = 20/2048 ≈ 0.00977. Avg time per object = 0.00977·1 + 0.99023·100 ≈ 99.033 ms. For 10 reads = 990.33 ms.
• Naive random + workload (50% recent / 50% random): recent reads hit Z (since A is random and stale), random reads hit A with prob 20/2048. Avg = 0.5·100 + 0.5·(0.00977·1 + 0.99023·100) ≈ 0.5·100 + 0.5·99.033 ≈ 99.517 ms.
• LRU strategy, best case (every recent re-read is in A): recent reads cost 1 ms, random reads cost ≈ 100 ms (cold miss). Avg = 0.5·1 + 0.5·100 = 50.5 ms.
• LRU worst case (random reads evict useful recent entries): essentially same as naive ≈ 99 ms.

Answers:

• Naive random, 10 reads → ≈ 990.330 ms total.
• Naive random with workload → ≈ 99.517 ms average.
• LRU best case → ≈ 50.500 ms.
• LRU worst case → ≈ 99.517 ms.

Your program controls boxes of pastries coming out of a bakery. For each produced box, you are required to compare its contents to a list of expected items (its "template") and determine whether the box is correct or not. The contents of a box is described by a string such as "pcm" for 'p'ie, 'c'ookie, and 'm'uffin, or "ddp" for 'd'onut, 'd'onut, and 'p'ie. The template is described in the same manner. So given a list of (box, template) pairs, your program should indicate how many times it found a mismatch between a box and its template and return that total. A box contains no more than 10 items, and there are no more than 1000 boxes to check at a time. Items in a box can be repeated, so "cc" (cookie cookie) is not the same as "c" (cookie). Items are not ordered, so the box "cm" (cookie, muffin) matches the template "mc" (muffin, cookie). Function Description Complete the function countMismatchedBoxes in the editor. countMismatchedBoxes has the following parameters:

• 1. String[] boxes: an array of strings representing the contents of each box
• 2. String[] templates: an array of strings representing the expected contents of each box Returns int: the number of boxes that do not match their templates

A string S is considered palindrome if it reads same way if spelled backwards, for example "nolemonnomelon", "ASANtaLivedAsAdeviLatNASA". Any non-empty string has substrings that are palindromes. For example, in the string S = "hellolle", there are many of such "subpalindromes": ellolle ll, ll - note that these are two distinct substrings that only happen to be equal. lol and lloll And each single letter can be considered a palindrome - 8 of them. Please write a function that, given a string S (only contains lowercase letters), returns number of different ways are there to pick a palindrome substring fro mS.

Example 1

Input:

s = "hellolle"

Output:

13

Explanation: Output 13.

Example 2

Input:

s = "wowpurerocks"

Output:

14

Explanation: each letter + "wow" + "rer"

Given a list of N integers, not necessarily unique, find all elements of the list for which there exists exactly one element of the list which is twice that number. The integers range from 0 to 1000. The list has no more than 100,000 elements. Your code should find the appropriate values and print them to STDOUT in sorted order.

Example 1

Input:

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 8]

Output:

[0, 1, 2, 3]

Explanation: 8 is 4*2, but 8 is present twice, 0 is its own double, so it's part of the result.

Example 2

Input:

numbers = [7, 17, 11, 1, 23]

Output:

[]

Explanation: Nothing is exactly twice another element.

Example 3

Input:

numbers = [1, 1, 2]

Output:

[1, 1]

Explanation: 1 and 1 both have their double 2 present, and 2 is present in the list only once.

You receive a short string short_s and a long string long_s, such that short_s can be found repeated a number of times in long_s. The goal is to compute the maximum number of consecutive repetitions of short_s within long_s, and return that number. If any of short_s or long_s are empty, then the answer is 0. Constraints

• 0 ≤ len(short_s) < 10
• 0 ≤ len(long_s) < 1,000,000

Example 1

Input:

short_s = "AB"
long_s = "ABBAC"

Output:

1

Explanation: "AB" is only found once in "ABBAC" so the answer is 1.

Example 2

Input:

short_s = "AB"
long_s = "ABCABCABAB"

Output:

2

Explanation: "AB" is found in long_s at index 0, 3, 6 and 8. Because it repeats twice consecutively at the end, the answer is 2.

Unfortunately, the database containing all this year's racing results has crashed. The only thing left is a backup of database records and results for each race. We urgently need to know who is the winner! Your program will receive input as a list of elements in the form of [race, racer_name, position], where all elements are integers: race is a database record number between 2001 and 2000+N where N is the total number of races in the championship. racer_name is a database record number between 1001 and 1000+R where R is the total number of racers participating. position is a value between 1 (won the race) and R (arrived last). Points are given according to the racers' position in a race: the 1st position is worth 10 points, 2nd is worth 6 points, 3rd is 4 points, 4th is 3 points, 5th is 2 points and 6th is worth 1 point. Positions further down earn no points. In case of an equal number of points at the end of the championship, the winner is the racer with the lowest record number. There are at most 100 racers, and at most 100 races in the championship. Your program is expected to output the record number of the winner, followed by how many points he or she got. Function Description Complete the function findWinner in the editor. findWinner has the following parameter:

• int[][] results: a 2D array of integers where each element is an array of the form [race, racer_name, position] Returns int[]: an array of two integers where the first element is the record number of the winner and the second element is the number of points they got

Example 1

Input:

results = [[2001, 1001, 3], [2001, 1002, 2], [2002, 1003, 1], [2002, 1001, 2], [2002, 1002, 3], [2001, 1003, 1]]

Output:

[1003, 20]

Explanation: The two races are coded 2001 and 2002. The racers with records 1001, 1002 and 1003 competed. Based on the raw results, they have the following points:

• Racer 1001: 4+6=10 (3rd and 2nd positions)
• Racer 1002: 6+4=10 (2nd and 3rd positions)
• Racer 1003: 10+10=20 (1st in both races) Your program is expected to output the following line in that case: 1003 20