Round 1
Questions:
Question 1:
For two positive integers, lo and hi, and a limit k, find two integers, a and b, satisfying the following criteria. Return the value of a⊕b. The ⊕ symbol denotes the bitwise XOR operator.
- lo <= a <= b <= hi
- The value of a⊕b is maximal for a⊕b <= k.
Example:
a b a⊕b 3 4 7 4 5 1
lo = 3
hi = 5
k = 6
The maximal usable XORed value is 6 because it is the maximal value that is less than or equal to the limit k = 6.
Function Description:
Complete the function maxXor in the editor. The function must return an integer denoting the maximum possible value of a⊕b for all a⊕b <= k.
maxXor has the following parameter(s):
- int lo: an integer
- int hi: an integer
- k: an integer
Constraints:
- 1 <= lo <= hi <= 10^4
- 1 <= k <= 10^4
Input Format for custom testing:
- Input from stdin will be processed as follows and passes to the function.
- The first line contains an integer, lo, the lower range limit.
- The second line contains an integer, hi, the upper range limit.
- The third line contains an integer, k, the maximal limit.
Sample Case 0:
STDIN Function ---------- ------------ 1 -> lo = 1 2 -> hi = 3 3 -> k = 3
Sample output:
3
The Following are the possible values of a and b satisfying lo <= a <= b <= hi:
- a = 1, b = 2 => a⊕b = 3
- a = 1, b = 3 => a⊕b = 2
- a = 2, b = 3 => a⊕b = 1 The maximum possible value of a⊕b <= 3 is 3.
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.
Question 2:
An array of integers is defined as being in meandering order when the first two elements are the respective largest and smallest elements alternate between its next largest and smallest elements. In other words, the elements are in order of [first_largest, first_smallest, second_largest, second_smallest, …].
Example: The array [-1, 1, 2, 3, -5] sorted normally is [-5, -1, 1, 2, 3]. Sorted in meandering order, it becomes [3, -5, 2, -1, 1].
Function Description:
Complete the function meanderingArray in the editor.
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.
Question 3:
The owner of
. A row of items is organized if the parity (even or odd) is different for each adjacent stack of items. To organize the row, half of the items in any stack can be removed. This can happen as many times and on as many stacks as is required. Determine the minimum number of operations needed to organize a row.
More formally, given an array items[] of integer of length n, the array is organized if for each x less than n -1, items[x] mod 2 != items[x + 1] mod 2.
A mod B is the remainder of A divided by B. In one operation, the owner can choose an element and divide it by 2. That is, if one chooses index x then do items[x] = floor(items[x] / 2). The goal is to return the minimum number of operations that one needs to perform to organize the array.
Example:
Items = [4, 10, 10, 6, 2]
The array is not organized since, for example, items[2] mod 2 = items[3] mod 2.
One way to organize the array is shown using 1-based indexing.
- Choose the 2nd index and divide it by 2: the new array is [4, 5, 10, 3, 2].
- Choose the 4th index and divide it by 2: the new array is [4, 5, 10, 3, 2].
[4, 5, 10, 3, 2] is an organized array so return the number of operations, 2.
Function Description:
Complete the function getMinimumOperation has the following parameters:
- int items[n]: a row of stack of items
Returns:
- int: the minimum number of operations needed to organize the array
Constraints:
- 1 <= n <= 10^5
- 1 <= items[i] < 2^30
Input format for custom testing:
- The first line contains an integer, n, size of the array items.
- Each of the next n lines contains an integer items[i].
Sample Case 0: Sample input 0:
STDIN FUNCTION --------- ------------------ 5 -> n = 5 6 -> items = [6, 5, 9, 7, 3] 5 9 7 3
Sample output:
3
Explanation:
The array is not organized since, for example, items[2] mod 2 = items[3] mod 2.
Here is the way to organize items in 3 moves.
- Choose the 3rd index and divide it by 2; the new is [6, 5, 4, 7, 3].
- Choose the 5th index and divide it by 2; items = [6, 5, 4, 7, 1].
- Choose the 5th index and divide it by 2; items = [6, 5, 4, 7, 0].
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.