Recently I appeared for the Autodesk OA round and I got stuck on two problems. I am sharing them here. If anyone has seen similar problems or knows the approach, please help me understand the intuition.
Problem 1
Imagine you are given a number line represented by [0, length - 1], and you are coloring the coordinates along the line. Specifically, you are given a list of queries that determines how to color coordinates along the line in the following format: [coord, color] — color the coordinate coord with color color. All existing colors are overwritten.
After processing each query, record the number of consecutive pairs of coordinates which currently have the same color on the number line. Your task is to return an array of length queries.length containing these records after processing all queries.
Example For length = 7 and queries = [[1, 2], [0, 2], [3, 5], [3, 2], [2, 2], [6, 1], [1, 3]], the output should be solution(length, queries) = [0, 1, 1, 1, 3, 3, 1]. Expand to see the example video. Note: If you are not able to see the video, use this link to access it.
Let's consider all queries: * [1, 2] — color the coordinate 1 with color 2. After this query, the number line becomes: [0, 2, 0, 0, 0, 0, 0]. There is just 1 colored coordinate on the line, so record 0. * [0, 2] — color the coordinate 0 with color 2. After this query, the number line becomes: [2, 2, 0, 0, 0, 0, 0]. There is one consecutive pair of coordinates with the same color 2: coordinates[0] and coordinates[1], so record 1. * [3, 5] — color the coordinate 3 with color 5. After this query, the number line becomes: [2, 2, 0, 5, 0, 0, 0]. There is still just one consecutive pair of coordinates with the same color 2, so record 1. * [3, 2] — color the coordinate 3 with color 2. After this query, the number line becomes: [2, 2, 0, 2, 0, 0, 0]. There is still just one consecutive pair of coordinates with the same color 2, so record 1. * [2, 2] — color the coordinate 2 with color 2. After this query, the number line becomes: [2, 2, 2, 2, 0, 0, 0]. There are 3 consecutive pairs of coordinates with the same color 2: coordinates[0] and coordinates[1], coordinates[1] and coordinates[2], coordinates[2] and coordinates[2]. So, record 3. * [6, 1] — color the coordinate 6 with color 1. After this query, the number line becomes: [2, 2, 2, 2, 0, 0, 1]. There are still 3 consecutive pairs of coordinates with the same color 2, so record 3. * [1, 3] — color the coordinate 1 with color 3. After this query, the number line becomes: [2, 3, 2, 2, 0, 0, 1]. Now, there is one consecutive pair of coordinates with the same color 2: coordinates[2] and coordinates[3], so record 1.
After processing all queries, the final output is [0, 1, 1, 1, 3, 3, 1].
Input/Output * [execution time limit] 0.5 seconds (cpp) * [input] integer length The length of the number line represented by [0, length - 1]. Guaranteed constraints: $$$1 \le \text{length} \le 10^9$$$. * [input] array.array.integer queries An array of queries. Guaranteed constraints: $$$1 \le \text{queries.length} \le 10^5$$$, $$$0 \le \text{queries}[i][0] \lt \text{length}$$$, $$$1 \le \text{queries}[i][1] \le 10^9$$$. * [output] array.integer Return an array of length queries.length, such that the $$$i$$$-th element contains the number of consecutive pairs of coordinates with the same color on the number line after the $$$i$$$-th query is processed.
[C++] Syntax Tips
// Prints help message to the console
// Returns a string
string helloWorld(string name) {
cout << "This prints to the console when you Run Tests" << endl;
return "Hello, " + name;
}
Problem 2
There are N centers, each with a fixed processing capacity. A log of events arrives: * "PACKAGE" -> send 1 package to the next open center (cyclic order). A center can handle only capacity[i] packages before needing a reset. * "CLOSURE j" -> center j becomes permanently closed.
Key rule: After attempting a full rotation (i.e., checking all centers without finding one with remaining capacity), -> reset all open centers to full capacity.
Return the index of the center that processed the most packages. If tied -> return the highest index.
Example
centerCapacities = [1, 2, 1, 2, 1]
dailyLog = [
"PACKAGE",
"PACKAGE",
"CLOSURE 2",
"PACKAGE",
"CLOSURE 3",
"PACKAGE",
"PACKAGE"
]
Output: 1
Comments (0)
