OA Question

Round 1

Questions: The developers at xyz are working on optimizing the message queue algorithm. There are n events to be sent through a queue, and the size of the ih event payload is denoted by payload. The queue performs more efficiently if a subset of the events can be selected and rearranged into a new array called optimizedPayload, which satisfies the following conditions, regardless of the original order of the elements:

1. The first part of optimizedPayload forms an increasing sequence: optimizedPayload[1] < optimizedPayload[2] < ... < optimizedPayload[i - 1] < optimizedPayload[i]

2. The second part of optimizedPayload forms a decreasing sequence: optimizedPayload[i] > optimizedPayload[i + 1] > ... > optimizedPayload[j]

3. The third part of optimizedPayload forms an increasing sequence: optimizedPayload[j] < optimizedPayload[j + 1] < ... < optimizedPayload[n]

The order of elements in optimizedPayload can be rearranged to meet these conditions, meaning the original order of the payload array does not matter when forming the subset. The task is to determine the maximum number of events that can be selected and rearranged to form optimizedPayload that satisfies the increasing-decreasing-increasing configuration.

Example 1:

• n = 9
• payload = [1, 3, 5, 4, 2, 6, 8, 7, 9]
• Consider the subset optimizedPayload = [1, 3, 5, 4, 2, 6, 7, 8, 9]. This satisfies the conditions as follows:
  1. Increasing part (1 to i): (1, 3, 5), with i = 3.
  2. Decreasing part (i to j): [5, 4, 2], with j = 5.
  3. Increasing part (j to end): [2, 6, 7, 8, 9].

All conditions are met, and the maximum number of events selected is 9. Hence, the answer is 9.

Example 2:

• n = 5
• payload = [5, 5, 2, 1, 3, 4, 5]
• Consider the subset optimizedPayload = [1, 3, 5, 4, 2, 5]. This satisfies the conditions as follows:
  1. Increasing part (1 to i): [1, 3, 5], with i = 3.
  2. Decreasing part (i to j): [5, 4, 2], with j = 5.
  3. Increasing part (j to end): [2, 5].

All conditions are met, and the maximum number of events selected is 6. Hence, the answer is 6.