Particle Velocity Microsoft OA 2023

Contents

1 Particle Velocity Solution Microsoft OA
- 1.1 SOLUTION
2 Microsoft Online Assessment 2023 Questions List

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;
    }
}

Particle Velocity Solution Microsoft OA

SOLUTION

Microsoft Online Assessment 2023 Questions List

Leave a Comment Cancel reply