Contents
Particle Velocity Solution Microsoft OA
You are a programmer in a scientific team doing research into particles. As an experiment, you have measured the position of a single particle in N equally distributed moments of time. The measurement made in moment K is recorded in an array particles as particles[K]. Now, your job is to count all the periods of time when the movement of the particle was stable. Those are the periods during which the particle doesn’t change its velocity: i.e. the difference between any two consecutive position measurements remains the same. Note that you need at least three measurements to be sure that the particle didn’t change its velocity.
For Example
- 1, 3, 5, 7, 9 is stable (velocity is 2)
- 7, 7, 7, 7 is stable (particle stays in place)
- 3, -1, -5, -9 is stable (velocity is 4)
- 0, 1 is not stable (you need at least three measurements)
- 1, 1, 2, 5, 7 is not stable (velocity changes between measurements)
More formally, your task is to find all the periods of time particles[P], particles[P+1], ….particles[Q] (of length at least 3) during which the movement of the particle is stable. Note that some periods of time might be contained in others (see below example).
Example:
Input: [-1, 1, 3, 3, 3, 2, 3, 2, 1, 0]
Output: 5
Explanation:
Possible periods of time for which velocity is stable are:
values | location(from, to) | Velocity |
---|---|---|
[-1, 1, 3] | (0,2) | 2 |
[3, 3, 3] | (2,4) | 0 |
[3, 2, 1, 0] | (6,9) | -1 |
[3, 2, 1] | (6,8) | -1 |
[2, 1, 0] | (7,9) | -1 |
Note: Last two periods are contained by (6,9)
Write a function:
public static int particleVelocity(int[] particles)
that given array particles
consisting of N
integers representing the results of the measurements, returns the number of periods of time when the movement of the particle was stable. The function should return -1
if the result exceeds 10^9
.
More examples:
Example 1:
Input: [1, 3, 5, 7, 9]
Output: 6
Explanation:
Possible periods of time for which velocity is stable are:
values | location(from, to) | Velocity |
---|---|---|
[1, 3, 5] | (0,2) | 2 |
[3, 5, 7] | (1,3) | 2 |
[5, 7, 9] | (2,4) | 2 |
[1, 3, 5, 7, 9] | (0,4) | 2 |
[1, 3, 5, 7] | (0,3) | 2 |
[3, 5, 7, 9] | (1,4) | 2 |
Example 2:
Input: [7, 7, 7, 7]
Output: 3
Explanation:
Possible periods of time for which velocity is stable are:
values | location(from, to) | Velocity |
---|---|---|
[7, 7, 7, 7] | (0,3) | 0 |
[7, 7, 7] | (1,3) | 0 |
[7, 7, 7] | (0,2) | 0 |
Also See: Amazon OA Online Assessment 2023 Questions and Answers
SOLUTION
Program: Particle Velocity Solution in C++
Explanation:
The simple formula : ans = ans + (streak * (streak + 1) / 2) – (2 * streak – 1) is nothing but the count of all subarrays for the given streak minus the count of subarrays of length 1 and 2.
Suppose we have an array of size n.
Total number of subarrays of the array : n * (n + 1) / 2
Count of subarrays of length 1 : n
Count of subarrays of length 2 : n – 1
Therefore, count of subarray of length ≥ 3 : (n * (n + 1) / 2) – (n – n – 1) = (n * (n + 1) / 2) – (2 * n – 1)
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums)
{
int ans = 0;
for(int i = 0 ; i < nums.size() ; )
{
int streak = 0, cd = INT_MAX;
if(i < nums.size() - 1)
{
streak = 2;
cd = nums[i] - nums[i + 1];
}
i++;
while(i < nums.size() - 1 and nums[i] - nums[i + 1] == cd)
{
streak++;
i++;
}
if(streak >= 3)
ans = ans + (streak * (streak + 1) / 2) - (2 * streak - 1);
}
return ans;
}
};
Program: Particle Velocity Solution in Python
Explanation:
nums = [1, 3, 5, 7, 9, 13]
differ = [2, 2, 2, 2, 4]
In order to match the condition – at least three elements, there are must have more than 2 continuous and same value elements in the differ for calculate arithmetic slices.
This problem is converted to calculate the number of combinations in differ’s sublist [2, 2, 2, 2] and [4]. (see function def arithmetic)
[2, 2, 2, 2] -> n_same = 4
kernal = 2, (include 3 elements)
num(n_same, k=2) = 3 ((0,1), (1, 2), (2, 3))
kernal = 3,
num(n_same, k=3) = 2 ((0,2), (1, 3))
kernal = 4,
num(n_same, k=4) = 1 ((0,3))
Total = 6
class Solution:
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
if len(nums) <= 2:
return 0
# n_same is number of continuous elements with same value
# (in difference space)
result, n_same = 0, 1
for i in range(1, len(nums)-1):
diff_1 = nums[i] - nums[i-1]
diff_2 = nums[i+1] - nums[i]
if diff_1 == diff_2:
n_same += 1
else:
result += self.arithmetic(n_same)
n_same = 1
result += self.arithmetic(n_same)
return result
def arithmetic(self, n):
"""
Sum(
num(n, k=2), num(n, k=3), ...,num(n, k=n)
)
if n = [1, 1, 1],
num(n, k=2) = 2 ((0, 1) and (1, 2));
num(n, k=3) = 1 ((0, 2)).
"""
# Set kernal = 2 to match the condition: at least three elements
kernal = 2
if n < kernal:
return 0
# Trapezoidal rule
return int(((n - kernal + 1) + (1)) * (n - kernal + 1) / 2)
### Same as:
# num_arith = 0
# while kernal <= n:
# num_arith += (n - kernal + 1)
# kernal += 1
# return num_arith
Program: Particle Velocity Solution in Java
class Solution {
/**
* count length of the maximum size Arithmetic progression that can be made from given index.
* nums = [1,2,3,4,5,8,11]
* ap = [5,4,3,2,3,2,1]
* because the array need to continuous , so starting from given number iterate over all the next number, the number would be either included in AP or not.
* If number is not included then it mark the end of the AP.
* In this way calculate the length of the AP foe each index.
* So given a AP of size 5 like 1,2,3,4,5 we can make ap[i] - 2 sub arrays of length greater than 3. AP size should be equal to and greater than 3
* Do the sum for all the number to get all possible sub arrays
* Time Complextiy : O(N^2)
*/
public int numberOfArithmeticSlices(int[] nums) {
int n = nums.length;
int[] ap = new int[n];
int last;
int d = Integer.MIN_VALUE;
boolean init;
for (int i = 0; i < n; i++) {
int count = 1;
init = false;
for (int j = i + 1; j < n; j++) {
if (!init) {
d = nums[j] - nums[j - 1];
init = true;
count++;
} else if (nums[j] - nums[j - 1] == d) {
count++;
} else {
break;
}
}
ap[i] = count;
}
int sum = 0;
for (int i = 0; i < n; i++) {
if (ap[i] >= 3) {
sum = sum + (ap[i] - 2);
}
}
return sum;
}
}
Microsoft Online Assessment 2023 Questions List
- Maximal Network Rank Solution
- Min Deletions To Obtain String in Right Format
- Day of week that is K days later Solution
- Minimum Adjacent Swaps to Make Palindrome Solution
- Lexicographically Smallest String
- Longest Substring Without Two Contiguous Occurrences of Letter
- String Without 3 Identical Consecutive Letters
- Microsoft OA Longest Semi-Alternating Substring
- Microsoft OA Min Steps to Make Piles Equal Height
- Max Inserts to Obtain String Without 3 Consecutive ‘a’
- Concatenated String Length with unique Characters
- Largest K such that both K and -K exist in array
- Microsoft OA Min Adj Swaps to Group Red Balls
- Maximum Length of a Concatenated String with Unique Characters
- Microsoft OA Unique Integers That Sum Up To 0
- Find N Unique Integers Sum up to Zero
- Microsoft OA Particle Velocity Solution
- Microsoft OA Arithmetic Slices Solution
- Microsoft OA Widest Path Without Trees Solution
- Microsoft OA Jump Game Solution
- Microsoft OA Fair Indexes Solution