Atlassian New Grad OA

4 questions to do, given 90 minutes. Must complete at least 2 (but recommended to do as many as you can, if you only meet the minimum you might get wait listed)

Question 1:

  • Simple max difference: Given an array return the max difference nums[j] - nums[i] for pairs nums[i] <= nums[j] where i < j. (I wasted a lot of time on this problem for some dumb incorrect if statement, think through your solution before solving this should be a quick 10 min problem)
  • Ex. 7,2,3,10,1 the return value would be 10-2 and not 10-1 because 1 comes after the 10.

Question 2:

  • Return number of subarrays that statisfy the condition given a number n where n is the amount of even numbers that may exist in the subarray and subarrays cannot end or start with same values (I skipped this one). Ex. 1,2,3,4,5 and n=2 you would return 4: [1,2,3], [1,2,3,4] [2,3,4,5] [3,4,5]

Question 3:

  • Problem can be solved using Union find. Given array of edges calculate size of each tree take their square root if their size > 1 and add them up, if their size is 1 then just add 1. Return the sum.

Questiton 4:

A beautiful subarray is defined as an array of length having a specific number of odd elements. Given an array of integers and a number of odd elements that constitutes beauty, create as many distinct beautiful subarrays as possible. Distinct means the arrys dont share identical starting and ending indices, though they may share one of the two.
For example, given the array [1,2,3,4,5] and a beautiful number 2, the following beautiful subarrays can be formed.
output: 4

More Example
[2,5,4,9] , 2