Hi everyone, I encountered this problem during my Google Virtual Onsite Interview and still I could not figure out the Solution.

Given a Doubly Linked list, find a minimum number of API calls ( move()) to sort the given Linked List. we can only use the move() method to move the node value. We can iterate over the LinkedList elements as many times as we want but the task is to minimize the move() calls and sort the LinkedList.

Example LinkedList 5 -> 2 -> 4 -> 3 -> 1 -> 6

move() - function takes node_val that you want to move and the position of where you want to place the node at. For example, if you want to pick node_val 5 and place it between 1 and 6 you can use move(5,1,6). The interviewer mentioned the move function is flexible and we can use an index as well to move the node. The way the function works is It would delete the node_val 5 and place it between 1 and 6 like this 2->4->3->1->5->6. This is defined as a 1 move() call.

Our task is to minimize the move() call to sort the given LinkedList. For this linkedList 5 -> 2 -> 4 -> 3 -> 1 -> 6, minimum move() calll is 3 to sort the list.

2->4->3->1->5->6 <-- move 1
1->2->4->3->5->6 <-- move 2
1->2->3->4->5->6 <-- move 3

I could not come up with a solution for the above problem. Please let me know if you could build intuition. Also, this is my 1st post forgive me for any mistakes or I missed adding details.