I recently went through an interview and was asked this question. Let me explain the question properly:

Given a number M (N-digit integer) and K number of swap operations(a swap operation can swap 2 digits), devise an algorithm to get the maximum possible integer?
Examples:
M = 132 K = 1 output = 312
M = 132 K = 2 output = 321
M = 7899 k = 2 output = 9987

My solution ( algorithm in pseudo-code). I used a max-heap to get the maximum digit out of N-digits in each of the K-operations and then suitably swapping it. 

for(int i = 0; i<K; i++)
{
    int max_digit_currently = GetMaxFromHeap();
    // The above function GetMaxFromHeap() pops out the maximum currently and deletes it from heap

    int index_to_swap_with = GetRightMostOccurenceOfTheDigitObtainedAbove();
    // This returns me the index of the digit obtained in the previous function  
    // .e.g If I have 436659 and K=2 given,   
    // then after K=1 I'll have 936654 and after K=2, I should have 966354 and not 963654.

    // Now, the swap part comes. Here the gotcha is, say with the same above example, I have K=3.
    // If I do GetMaxFromHeap() I'll get 6 when K=3, but I should not swap it, 
    // rather I should continue for next iteration and 
    // get GetMaxFromHeap() to give me 5 and then get 966534 from 966354.

    if (Value_at_index_to_swap == max_digit_currently)
        continue;
    else
        DoSwap();
}

Time complexity: O(K*( N + log_2(N) ))
// K-times [log_2(N) for popping out number from heap & N to get the rightmost index to swap with]

The above strategy fails in this example:
M = 8799 and K = 2
Following my strategy, I'll get M = 9798 after K=1 and M = 9978 after K=2. However, the maximum I can get is M = 9987 after K=2.

What did I miss?
Also suggest other ways to solve the problem & ways to optimi

algorithm
Edit
Report