Edit Question - KnowledgeHub

Title Body

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

Tags (comma-separated) Cancel