Google Online Assessment | Failed
Anonymous User
316

Got the following question in google online assesment, can anyone solve this and explain the solution

The problem statement in the image describes a task related to analyzing and optimizing a log file. Here's a summary of the problem:A log file contains a series of entries represented by a permutation of length n integers. To analyze the log efficiently, n operations, indexed from 0 to n-1, are available. Each operation involves swapping two entries in the log.The goal is to select some of these n operations and apply them in any order to the log entries to produce the lexicographically smallest permutation, facilitating a more streamlined log analysis.The task is to return this lexicographically smallest permutation of entries.Additional notes provided in the problem statement include:
• Each operation can be used at most once.
• 0-based indexing is considered.
• A permutation is an array consisting of distinct integers from 1 to n in arbitrary order.
• The permutation p of length n is lexicographically less than the permutation q of length n if there is an index i such that for all j from 0 to i-2, the condition p[j] = q[j] is satisfied, and p[i] < q[i].
The problem also includes an example demonstrating the application of operations to achieve the optimal (lexicographically smallest) permutation for a given set of entries.

Example

entries [5, 4, 1, 3, 2]

Apply operation 2 to swap entries [1] and entries[2] to get entries [5, 1, 4, 3, 2].

Apply operation 1 to swap entries(0) and entries[1] to get entries [1, 5,4,3,2].

Apply operation 4 to swap entries (3) and entries[4] to get entries [1, 5, 4.23].

Apply operation 3 to swap entries[2] and entries[3] to get entries [1,5,2,4,3,]

Hence, the answer is [1, 5, 2, 4, 3].

Example 2
Input -> entries [4, 3, 2, 1]
Output -> [1,4,3,2]

Apply operation 3 to swap entries [2] (considering 0-based indexing) and entries [3] to get entries = [4, 3, 1, 2].

Apply operation 2 to swap entries [1] and entries[2] to get entries=[4, 1, 3, 2]

Apply operation to swap entries[0] to get entries = [1,4,3,2]
Constraints

• 1 <n<2* 10^5

1 ≤ entries[i] < n

It is guaranteed that the array entries is a permutation of length n.

Comments (2)