Microsoft Online Assessment Questions
15. Microsoft OA Unique Integers That Sum Up To 0
Given an integer n, return any array containing n unique integers such that they add up to 0.
Example 1:
Input:5
Output: [-4,-2,0,2,4]
Example 2:
Input:3
Output: [-2, 0, 2]
Example 3:
Input:1
Output: [0]
Solution:
Program Python:
from typing import List
def numsum(n):
res = []
for i in range(n):
res.append(i * 2 - n + 1)
return res
n = int(input())
res = numsum(n)
print(' '.join(map(str, res)))Program Java:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
class Solution {
public static List<Integer> uniqueSum(int n) {
ArrayList<Integer> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
res.add(i * 2 - n + 1);
}
return res;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = Integer.parseInt(scanner.nextLine());
scanner.close();
List<Integer> res = uniqueSum(n);
System.out.println(res.stream().map(String::valueOf).collect(Collectors.joining(" ")));
}
}16. Find N Unique Integers Sum up to Zero
Find N Unique Integers Sum up to Zero
Given an integer n, return any array containing n unique integers such that they add up to 0.
Example 1:
Input: n = 5
Output: [-7,-1,1,3,4]
Explanation: These arrays also are accepted [-5,-1,1,2,3], [-3,-1,2,-2,4].
Example 2:
Input: n = 3
Output: [-1,0,1]
Example 3:
Input: n = 1
Output: [0]
Constraints:
1 <= n <= 1000
Solution:
This task is very simple. We don’t need to play with a random number generator. We just need to make an array of different numbers. For example sequence 012345 contains different and unique numbers. So we just generate two the same sequences of numbers and make one of them negative.
For example: [-3, -2,-1,0,1,2,3]
All numbers of this sequence are unique and sum of them = 0. This is exactly what we need. The only thing we need to check is check if the given n is odd or even. In case n is odd we will add zero to our sequence, if n is even we will not do it.
Program C++:
#include <iostream>
#include <vector>
using namespace std;
/*
Simple idea
n = 1, [0]
n = 2, [-1, 1]
Now write more based on this
n = 3, [-2, 0, 2]
n = 4, [-3, -1, 1, 3]
n = 5, [-4, -2, 0, 2, 4]
*/
vector<int> sumZero1(int n) {
vector<int> v;
v.reserve(n);
int until = n/2;
// if n is odd
if (n & 1) { v.push_back(0); }
for (int i = 1; i <= until; ++i) { v.push_back(i); v.push_back(-i); }
return v;
}
/*
Another idea based on properties of the sequence
Find the rule
A[i] = i * 2 - n + 1
Math Observation
Actually, this rule could be derived from constructing an arithmetic sequence.
(Note that any arithmetic sequence must have unique values if the common delta is non-zero)
We need the sequence sum, so that
(a[0] + a[n-1]) * n / 2 = 0, which means a[0] + a[n-1] = 0.
Note that a[n-1] - a[0] = (n-1) * delta, which is -2 * a[0],
so we simply set delta = 2, a[0] = 1 - n
*/
vector<int> sumZero2(int n) {
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = i * 2 - n + 1;
}
return v;
}
int main() {
cout << "" << endl;
return 0;
}Another idea based on properties of the sequence. You can note that each item of the required sequence following the rule A[i] = i * 2 — n + 1
Math Observation
Actually, this rule could be derived from constructing an arithmetic sequence.
(Note that any arithmetic sequence must have unique values if the common delta is non-zero)
We need the sequence sum, so that
(a[0] + a[n-1]) * n / 2 = 0, which means a[0] + a[n-1] = 0.
Note that a[n-1] — a[0] = (n-1) * delta, which is -2 * a[0],
so we simply set delta = 2, a[0] = 1 — n
The solution code will looks like:
vector<int> solution2(int n) {
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = i * 2 - n + 1;
}
return v;
}It’s better to remember the first approach, as it’s easier to understand.
Program Python:
Using the Gauss Sum formula (n * (n + 1)) / 2 you can easily sum up all the values from 1 to n.
Concatenate the negation of the Gauss Sum for n – 1 with the range of numbers from 1 to n – 1 and you get the result.
class Solution:
def sumZero(self, n: int) -> List[int]:
return [- (n * (n - 1)) // 2] + list(range(1, n))Program Java:
class Solution {
public int[] sumZero(int n) {
int[] ans = new int[n];
int num = n/2;
int index = 0;
while(num>0)
{
ans[index++] = num;
ans[index++] = num*-1;
num--;
}
if(n%2 == 1)
ans[index++] = 0;
return ans;
}
}17. Microsoft OA Particle Velocity Solution
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
Solution:
Program C++: Particle Velocity in C++
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 Python: Particle Velocity in Python
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_arithProgram 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;
}
}18. Microsoft OA Arithmetic Slices Solution
An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences.
Given an integer array nums, return the number of arithmetic subarrays of nums.
A subarray is a contiguous subsequence of the array.
Example 1:
Input: nums = [1,2,3,4]
Output: 3
Explanation: We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself.
Example 2:
Input: nums = [1]
Output: 0
Constraints:
1 <= nums.length <= 5000
-1000 <= nums[i] <= 1000
Solution:
Program C++:
Key points:
Just keep looking for continuous sequence and get its length.
For a sequence of n gaps, it generates n-1 3-item combo, n-2 4-item combo, n-3 5-item combo and go on till 1 combo with all items in sequence. The total combination count is simply n*(n-1)/2.
Once a sequence is over, add up the slice count and keep going.
Remember to add when last item is scanned.
You can use item count start from 2 instead of gap count start from 1, same result for sure.
int numberOfArithmeticSlices(const vector<int>& A) {
int len = A.size();
if (len < 3)
return 0;
int ret = 0;
int prevDiff = A[1]-A[0];
int seqLen = 1;
for (int i=2; i<len; ++i) {
if (A[i] - A[i-1] == prevDiff)
++seqLen;
else {
ret += (seqLen-1)*seqLen/2;
seqLen = 1;
prevDiff = A[i] - A[i-1];
}
}
ret += (seqLen-1)*seqLen/2;
return ret;
}Program Python:
Create an array of size le (le=len(A))
As given ”A sequence of numbers is called arithmetic if it consists of at least three elements”, start for loop from 2 to le.(because first two elements(index 0 and 1) will never from a sequence as minimum length of a sequence is 3)
It is also given that ”A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.”
here i is current element ,if A[i]-A[i-1] == A[i-1]-A[i-2] then sequence length for current element i.e l[i] will be 1+sequence length of previous element(l[i-1)
To return the total number of arithmetic slices in the array A return Caluculated Sum of array l.
class Solution:
def numberOfArithmeticSlices(self, A: List[int]) -> int:
le=len(A)
l=[0]*(le)
for i in range(2,le):
if A[i]-A[i-1] == A[i-1]-A[i-2]:
l[i]=1+l[i-1]
return sum(l)Program Java:
Explanation:
We need to find the consecutive subarray, if its length is len, then it could contribute (len – 1) * (len – 2) / 2 slices,
then start from the end of last consecutive +1, and go ahead to find the next consecutive util the end of array.
// AC: Runtime: 0 ms, faster than 100.00% of Java online submissions for Arithmetic Slices.
// Memory Usage: 36.7 MB, less than 80.00% of Java online submissions for Arithmetic Slices.
// thoughts: find the consecutive subarray, then it could contribute (len - 1) * (len - 2) / 2 slices,
// then start from the end of last consecutive +1, and go ahead to find the next consecutive.
// T:O(n), S:O(1)
//
class Solution {
public int numberOfArithmeticSlices(int[] nums) {
int size = nums.length, ret = 0;
if (size >= 3) {
for (int i = 0; i < size - 2;) {
int diff1 = nums[i + 1] - nums[i], diff2 = nums[i + 2] - nums[i + 1];
if (diff1 == diff2) {
int end = i + 2;
while (end < size && nums[end] - nums[end - 1] == diff1) {
end++;
}
// length of the consecutive subarray that has same adjacent diff.
int len = end - i;
// may produce such amount amount of `arithmetic slices`.
ret += (len - 1) * (len - 2) / 2;
// forwarding to the sequence's end + 1
i = end - 2;
} else {
i++;
}
}
}
return ret;
}
}19. Microsoft OA Widest Path Without Trees Solution
There are N trees in the forest (numbered from 0 to N-1). The Kth tree is located at coordinates (X[k], Y[k]).
We want to build the largest possible vertical path so that there is no tree. The path must be established somewhere between the leftmost tree and the rightmost tree, which means that the width of the path is not infinite.
Write a function:
public static Integer solution(int[] X, int[] Y), given the N integers to form the X and Y of the array, they indicate the position of the tree, then return the most constructable The width of the wide path.
Example
Given X=[1,8,7,3,4,1,8] , Y=[6,4,1,8,5,1,7] , the function should return 3.
Solution:
Program Java: Widest Path Without Trees in Java
public static void main(String[] args) {
int[] M = {1, 8, 7, 3, 4, 1, 8};
int[] N = {6, 4, 1, 8, 5, 1, 7};
System.out.println(solution2(M, N));
int[] M1 = {5, 5, 5, 7, 7, 7};
int[] N1 = {3, 4, 5, 1, 3, 4};
System.out.println(solution2(M1, N1));
int[] M2 = {6, 10, 1, 4, 4};
int[] N2 = {2, 5, 3, 1, 6};
System.out.println(solution2(M2, N2));
int[] M3 = {4, 1, 5, 4};
int[] N3 = {4, 5, 1, 3};
System.out.println(solution2(M3, N3));
}
public static Integer solution2(int[] X, int[] Y) {
int maxX = 0;
int maxY = 0;
ArrayList<Integer> X = new ArrayList<>();
ArrayList<Integer> Y = new ArrayList<>();
for (int i : X) {
X.add(i);
}
for (int i : Y) {
Y.add(i);
}
Collections.sort(X);
Collections.sort(Y);
for (int i = 1; i < X.size(); i++) {
int j = X.get(i) - X.get(i - 1);
maxX = j >= maxX ? j : maxX;
}
for (int i = 1; i < Y.size(); i++) {
int j = Y.get(i) - Y.get(i - 1);
maxY = j >= maxY ? j : maxY;
}
return maxX >= maxY ? maxX : maxY;
}20. Microsoft OA Jump Game Solution
Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.
Notice that you can not jump outside of the array at any time.
Example 1:
Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation: All possible ways to reach at index 3 with value 0 are:
index 5 -> index 4 -> index 1 -> index 3
index 5 -> index 6 -> index 4 -> index 1 -> index 3
Example 2:
Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true
Explanation: One possible way to reach at index 3 with value 0 is:
index 0 -> index 4 -> index 1 -> index 3
Example 3:
Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.
Constraints:
1 <= arr.length <= 5 * 104
0 <= arr[i] < arr.length
0 <= start < arr.length
Solution:
Program Python: Jump Game in Python BFS Solution, Time Complexity: O(n)
class Solution:
def canReach(self, arr: List[int], start: int) -> bool:
import collections
queue=collections.deque()
queue.append(start)
s=set()
while len(queue):
curr = queue.popleft()
if arr[curr]==0:
return True
if curr not in s:
s.add(curr)
if curr + arr[curr] < len(arr):
queue.append(curr + arr[curr])
if curr - arr[curr] > -1:
queue.append(curr - arr[curr])
return False
class Solution:
def canReach(self, arr: List[int], start: int) -> bool:
seen, temp = set(), [start]
while temp:
i = temp.pop()
if arr[i] == 0: return True
else: seen.add(i)
if 0 <= i - arr[i] < len(arr) and i - arr[i] not in seen:
temp.append(i - arr[i])
if 0 <= i + arr[i] < len(arr) and i + arr[i] not in seen:
temp.append(i + arr[i])
return FalseProgram Java: Jump Game in Java DFS Solution
/*
Classic DFS question.
For DFS loops, modify the arr value to go beyound valid as "visited".
*/
class Solution {
public boolean canReach(int[] arr, int start) {
if (start < 0 || start >= arr.length || arr[start] >= arr.length) {
return false;
}
if (arr[start] == 0) {
return true;
}
int move = arr[start];
arr[start] = arr.length;
return canReach(arr, start - move) || canReach(arr, start + move);
}
}Program C++: Jump Game in C++ DFS Solution
class Solution {
public:
int solve(vector<int>& arr, int idx){
if(idx<0 || idx>arr.size()-1 || arr[idx]==-100) return 0;
if(arr[idx]==0) return 1;
int temp = arr[idx];
arr[idx]=-100;
bool right = solve(arr,idx+temp);
bool left = solve(arr,idx-temp);
arr[idx]=temp;
return (right || left) ? 1 : 0;
}
bool canReach(vector<int>& arr, int start) {
return solve(arr, start)==1 ? true : false;
}
};21. Microsoft OA Fair Indexes Solution
You are given two arrays A and B consisting of N integers each.
Index K is named fair if the four sums(A[0]+…A[K-1]),(A[K]+…+A[N-1]),(B[0]+…+B[K-1]) and (B[K]+…+B[N-1]) are all equal, In other words, K is the index where the two arrays, A and B, can be split (into two non-empty arrays each) in such a way that the sums of the resulting arrays’ elements are equal.
For example, given arrays A = [4,-1, 0, 3] and B = [-2, 5, 0, 3], index K = 2 is fair. The sums of the subarrays are all equal: 4+(-1) = 3; 0+3 = 3; -2 + 5 = 3 and 0 + 3 = 3.
Example
Example 1:
Input: [4,-1,0,3] [-2,5,0,3]
Output: 2
Example 2:
Input: [2,-2,-3,3] [0,0,4,-4]
Output: 1
Example 3:
Input: [4,-1,0,3] [-2,6,0,4]
Output: 0
Example 4:
Input: [1,4,2,-2,5] [7,-2,-2,2,5]
Output: 2
Solution:
Program Python: Fair Indexes in Python
Solution: prefix sum
Algorithm: Prefix and
Problem-solving ideas
First judge whether the sum of the two arrays are equal, if they are not equal, return 0 directly; then scan the array and use pre_a and pre_b to record the prefix sum of the two arrays respectively. When the prefix sum is equal and equal to the remaining part, ans++ is fine . It should be noted that the value of the number in the array is in the range of -1e9, 1e9, and the length of the array is 0, 1e5, so the middle sum will exceed the int range, and long is required; and the two divided arrays cannot be empty, so the prefix And p0 and pn-1 are not considered;
Complexity analysis
Time complexity: O(n)
Need to traverse the array twice.
Space complexity: O(1)
There is no need to open up additional data space, only a few variables are needed to record the values.
class Solution:
"""
@param A: an array of integers
@param B: an array of integers
@return: return a integer indicating the number of fair indexes.
"""
def CountIndexes(self, A, B):
if (sum(A) != sum(B)) :
return 0
pre_a = 0
pre_b = 0
sum_a = sum(A)
answer = 0
for i in range(len(A) - 1):
pre_a = pre_a + A[i]
pre_b = pre_b + B[i]
if pre_a == pre_b and pre_a == sum_a - pre_a:
answer += 1
return answerProgram Java: Fair Indexes in Java
public class Solution {
/**
* @param A: an array of integers
* @param B: an array of integers
* @return: return a integer indicating the number of fair indexes.
*/
public int CountIndexes(List<Integer> A, List<Integer> B) {
int length = A.size();
long sumA = 0;
long sumB = 0;
for (int i = 0; i < length; i++) {
sumA += A.get(i);
sumB += B.get(i);
}
if (sumA != sumB) {
return 0;
}
long preA = 0, preB = 0;
int answer = 0;
for (int i = 0; i < length - 1; i++) {
preA += A.get(i);
preB += B.get(i);
if (preA == preB && sumA - preA == preA) {
answer += 1;
}
}
return answer;
}
}Program C++: Fair Indexes in C++
class Solution {
public:
/**
* @param A: an array of integers
* @param B: an array of integers
* @return: return a integer indicating the number of fair indexes.
*/
int CountIndexes(vector<int> &A, vector<int> &B) {
int length = A.size();
long sumA = 0;
long sumB = 0;
for (int i = 0; i < length; i++) {
sumA += A[i];
sumB += B[i];
}
if (sumA != sumB) {
return 0;
}
long preA = 0, preB = 0;
int answer = 0;
for (int i = 0; i < length - 1; i++) {
preA += A[i];
preB += B[i];
if (preA == preB && sumA - preA == preA) {
answer += 1;
}
}
return answer;
}
};Part 1 : https://leetcode.com/discuss/interview-question/2209187/microsoft-online-assessment-1/
Part 2 : https://leetcode.com/discuss/interview-question/2209192/Microsoft-Online-Assessment-Questions-2
Part 3 : https://leetcode.com/discuss/interview-question/2209201/Microsoft-Online-Assessment-Questions-3
Part 4 : https://leetcode.com/discuss/interview-question/2209220/Microsoft-Online-Assessment-Questions-4