Microsoft Online Assessment (OA) - Particle Velocity
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 is2
)7, 7, 7, 7
is stable (particle stays in place)3, -1, -5, -9
is stable (velocity is4
)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:
1public 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 |
Try it yourself
Implementation
1from typing import List
2
3def particle_velocity(particles: List[int]) -> int:
4 num_stable = 0
5 if len(particles) < 3:
6 return 0
7 for i in range(len(particles) - 2):
8 for j in range(i + 1, len(particles) - 1):
9 if particles[j + 1] - particles[j] == particles[i + 1] - particles[i]:
10 num_stable += 1
11 else:
12 break
13 return num_stable if num_stable < 1000000000 else -1
14
15if __name__ == "__main__":
16 particles = [int(x) for x in input().split()]
17 res = particle_velocity(particles)
18 print(res)
19
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4import java.util.PriorityQueue;
5import java.util.Scanner;
6import java.util.stream.Collectors;
7
8class Solution {
9 public static int particleVelocity(List<Integer> particles) {
10 int totalPeriods = 0;
11 int particleSize = particles.size();
12 for (int i = 0; i < particleSize; i++) {
13 for (
14 int count = 0;
15 i + 2 < particleSize && particles.get(i + 1) - particles.get(i) == particles.get(i + 2) - particles.get(i + 1);
16 i++) {
17 count++;
18 totalPeriods += count;
19 }
20 }
21 return totalPeriods < 1000000000 ? totalPeriods : -1;
22 }
23
24 public static List<String> splitWords(String s) {
25 return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
26 }
27
28 public static void main(String[] args) {
29 Scanner scanner = new Scanner(System.in);
30 List<Integer> particles = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
31 scanner.close();
32 int res = particleVelocity(particles);
33 System.out.println(res);
34 }
35}
36
1"use strict";
2
3function particleVelocity(particles) {
4 let totalPeriods = 0;
5 const particleSize = particles.length;
6
7 for (let i = 0; i < particleSize; i++) {
8 for (
9 let count = 0;
10 i + 2 < particleSize && particles[i + 1] - particles[i] === particles[i + 2] - particles[i + 1];
11 i++
12 ) {
13 count++;
14 totalPeriods += count;
15 }
16 }
17 return totalPeriods < 1000000000 ? totalPeriods : -1;
18}
19
20function splitWords(s) {
21 return s === "" ? [] : s.split(" ");
22}
23
24function* main() {
25 const particles = splitWords(yield).map((v) => parseInt(v));
26 const res = particleVelocity(particles);
27 console.log(res);
28}
29
30class EOFError extends Error {}
31{
32 const gen = main();
33 const next = (line) => gen.next(line).done && process.exit();
34 let buf = "";
35 next();
36 process.stdin.setEncoding("utf8");
37 process.stdin.on("data", (data) => {
38 const lines = (buf + data).split("\n");
39 buf = lines.pop();
40 lines.forEach(next);
41 });
42 process.stdin.on("end", () => {
43 buf && next(buf);
44 gen.throw(new EOFError());
45 });
46}
47