Question

Microsoft | OA Coding Questions and Solutions | Set - 60 | 2022

Answer 1

1st question:
https://leetcode.com/problems/find-n-unique-integers-sum-up-to-zero/

 

2nd question:

Answer 2

2nd question:
https://leetcode.com/problems/longest-arithmetic-subsequence/description/

Answer 3

Q1 is pretty trival, just pair the neg and pos from 1..n/2.

 

Q2: O(biggestDiff * n + nlogn)

 

public int longestArithSeqLength(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length;
    int biggestDiff = nums[n-1] - nums[0];
    Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
    int ans = 0;
    for(int num : nums) {
        for(int i=0; i<=biggestDiff; i++) {
            if(map.containsKey(num-i)) {
                int seqCnt = map.get(num-i).get(i);
                ans = Math.max(ans, seqCnt+1);
                map.computeIfAbsent(num, x->new HashMap<>()).put(i, seqCnt+1);
            } else {
                map.computeIfAbsent(num, x->new HashMap<>()).put(i, 1);
            }
        }
    }
    return ans;
}