FastPrep
Problem · Array

Optimize Log File

Learn this problem
● HardGoogleOA
See Google hiring insights

Problem statement

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:

  • 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].

    • Function

    optimizeLogFile(entries: int[]) → int[]

    Examples

    Example 1

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

    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, 2, 3].

    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

    entries = [4, 3, 2, 1]return = [1, 4, 3, 2]

    Apply operation 3 to swap entries[2] 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 1 to swap entries[0] and entries[1] 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.

    More Google problems

    drafts saved locally
    public int[] optimizeLogFile(int[] entries) {
  // write your code here
}
    entries[5, 4, 1, 3, 2]
    expected[1, 5, 2, 4, 3]
    checking account