Altimetrik

Role: Not Specified (Software Engineer - Screening Round)

College: Not Specified

Interview Date: August 30, 2024

Interview Type: Online Interview / Assessment (HackerRank Test)

Result: Rejected

Difficulty: Hard

Rounds: 1 (Screening Round)

Topics Asked: Algorithms (Longest subsequence with even sum of adjacent differences)

Experience:

This experience details an Altimetrik screening round conducted on HackerRank on August 30, 2024. The candidate failed the test because they couldn't solve the problem with an O(n) time complexity.

Coding Question: Given an array of integers, return the length of the longest subsequence such that when the subsequence is sorted in non-decreasing order, the sum of the differences between adjacent elements is even. A subsequence is defined as a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

Example 1: Input: `[7, 1, 3, 4, 6, 2, 4]` Output: `7`. Explanation: The entire array can be taken as the subsequence. When sorted, it becomes `[1, 2, 3, 4, 4, 6, 7]`. The sum of the differences between adjacent elements is `1 + 1 + 1 + 0 + 2 + 1 = 6`, which is even.

Example 2: Input: `[7, 3, 4, 6, 2, 4]` Output: `5`. Explanation: The longest subsequence that satisfies the condition has a length of 5.

Constraints mentioned were: array length between 1 and 10^5, and array elements between -10^9 and 10^9.