MICROSOFT Coding Question – Solved

12 Live

A coding competition organized to recruit software developers includes a problem involving the bitwise-OR operation. The score of a sequence is defined as the result of the bitwise-OR operation on its elements. Given an array arr of length n, identify all possible distinct scores that can be obtained by selecting any strictly increasing subsequence from the array. Return the results sorted in ascending order. Note: A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without altering the order of the remaining elements. Example n = 4 arr = [4, 2, 4, 1] There are n = 4 elements in the array. The strictly increasing subsequences that can be chosen to have distinct score values are: - Empty subsequence; score = 0 - [1]; score = 1 - [2]; score = 2 - [4]; score = 4 - [2, 4]; score = 6 There are no other strictly increasing subsequences that yield a different score value. So, the answer is [0, 1, 2, 4, 6], which is sorted in ascending order. Function Description Complete the function getDistinctScoreValues in the editor with the following parameter: int arr[n]: an array of integers Returns int[]: all possible distinct score values, sorted ascending Constraints - 1 ≤ n ≤ 10⁴ - 1 ≤ arr[i] < 1024 Input Format For Custom Testing Sample Case 0 Sample Input For Custom Testing STDIN arr[] size, n = 4 arr = [3, 2, 4, 6] 4 Sample Output [0, 2, 3, 4, 6, 7] Explanation Some strictly increasing subsequences that have distinct score values are: - Empty subsequence; score = 0 - [2]; score = 2 - [3]; score = 3 - [4]; score = 4 - [2, 4]; score = 6 - [3, 4]; score = 7

Asked in: MICROSOFT

Image of the Question

All Testcases Passed ✔

Solution

def solve(arr):
    result = set()
    prev = dict()
    for num in arr:
// ... rest of solution available after purchase

🔒 Please login to view the solution

Explanation

```
To solve this problem, you need to identify all distinct scores obtained by performing a bitwise-OR on every strictly increasing subsequence of the given array, including the empty subsequence which contributes a score of 0. The main challenge lies in efficiently exploring subsequences and combining their bitwise-OR values without enumerating all subsequences explicitly, which would be computationally infeasible for larger arrays.

---

Step 1: Understanding the Problem and Key Concepts

- A strictly increasing subsequence is a sequence of elements taken from the array in order, where each element is strictly greater than the previous one.
- The score for any subsequence is the bitwise-OR of all elements in that subsequence.
- We want to find all distinct possible scores, including the score of the empty subsequence (0).
- The input array size can be up to 10^4, which makes naive enumeration of all subsequences impossible due to exponential complexity.
- Each element is less than 1024, so the numbers are at most 10 bits long, allowing bitwise operations to be done efficiently.

---

Step 2: Naive Approach and Its Limitations

The simplest but impractical approach would be:

- Generate all strictly increasing subsequences.
- For each subsequence, calculate the bitwise-OR of its elements.
- Collect these results into a set to get distinct scores.
- Finally, sort the set and return.

However, since the number of subsequences grows exponentially with n, this approach is not feasible for n=10,000.

---

Step 3: Identifying Opportunities for Optimization

- Notice that the problem can be broken down into dynamic programming where at each position you keep track of achievable scores.
- Instead of considering subsequences explicitly, think about the scores that can be formed ending at each element.
- Because the subsequence must be strictly increasing, you can only append the current element to subsequences that ended with a smaller element.
- The bitwise-OR operation is associative and monotonic in terms of bits being set; combining OR results can produce new scores without enumerating every subsequence.

---

Step 4: Developing a Dynamic Programming Approach

- Initialize a global set of scores that will eventually contain all possible distinct scores (start with {0} for the empty subsequence).
- Process the array from left to right.
- For each element at position i:
- Maintain a temporary set for new scores formed by appending the current element to subsequences ending at previous indices where arr[j] < arr[i].
- These new scores are formed by bitwise-OR of the current element with the scores achievable from previous elements smaller than it.
- Merge these new scores into the global set.
- To make this efficient:
- You can maintain, for each position, the set of achievable scores ending exactly at that position.
- For each position i, you try to extend subsequences ending at positions j < i where arr[j] < arr[i].
- Since n can be up to 10,000 and naive nested loops may still be costly, optimizations around data structures or bitmasks can be considered.

---

Step 5: Further Insights and Possible Optimizations

- Because arr[i] < 1024, scores can be represented using integers up to 10 bits.
- This allows using bitmasks and sets efficiently.
- Instead of keeping track of all sequences ending at each element, think of tracking all possible scores at each step globally.
- A possible approach is:
- Start with a set of scores = {0}.
- Iterate over the array.
- For each element, create a new set of scores by OR-ing the element with each existing score but only if the element can be appended to subsequences that respect the strictly increasing order.
- To enforce the strictly increasing condition, you can use a data structure or logic to ensure that scores only propagate from smaller elements to larger elements.
- One way to handle this is:
- At each step, maintain a mapping from values to the set of scores achievable with subsequences ending with that value.
- When you move to a new element arr[i], consider all smaller keys from this mapping and OR their scores with arr[i].
- This is akin to doing a form of DP where keys are the last element values of subsequences.

---

Step 6: Summary of Steps to Implement

1. Initialize a data structure (e.g., a dictionary or map) to hold, for each distinct value, the set of scores achievable by subsequences ending with that value. Initially empty.

2. Initialize a global set with the empty subsequence score: {0}.

3. Iterate through each element in the array in order.

4. For the current element:
- Find all entries in the map where the key (previous element) is less than the current element (to satisfy strictly increasing condition).
- For each such key, take the scores stored, OR each with the current element, and add the results to a temporary set representing new subsequence scores ending with the current element.
- Also consider the current element alone as a subsequence (score = current element).
- Update the map entry for the current element with the union of existing and new scores.
- Add all new scores to the global set.

5. After processing all elements, convert the global set to a sorted list.

6. Return the sorted list as the final answer.

---

Step 7: Handling the Empty Subsequence

- Remember to include 0 in the final set to represent the empty subsequence.
- This can be added at the start and carried along without modification.

---

Step 8: Time and Space Considerations

- The complexity depends on how many distinct scores are produced at each step and how many smaller keys exist.
- Since numbers are bounded by 1024, the map keys and scores are limited, reducing complexity.
- Using appropriate data structures like sorted maps or balanced trees may help quickly query keys less than the current element.

---

Step 9: Verification With Examples

- Use the provided examples to verify your reasoning:
- For arr = [4,2,4,1], verify that you get scores [0,1,2,4,6].
- For arr = [3,2,4,6], verify that you get scores [0,2,3,4,6,7].

This stepwise dynamic programming approach efficiently captures all distinct scores achievable by strictly increasing subsequences while avoiding exponential enumeration.
```