Feature #6: Assign Transactions

Implement the "Assign Transactions" feature for our "Stocks" project.

Description

Stock transaction requests arrive and are inserted at the head of a singly linked list. The transactions need to be carried out by K brokers, such that each transaction is independent of all others. K is a positive integer and is less than or equal to the length of the linked list. There are a total of N transaction requests in the linked list. The first N/K\lfloor N/K \rfloor transactions need to be assigned to the first broker, the next N/K\lfloor N/K \rfloor transactions to the second broker, and so on. In the end, some transactions (<N/K)(< N/K) may still be left in the original linked list. A first-come-first-serve policy will not be guaranteed globally, but the subset of transactions assigned to a specific broker will need to be carried out in the same order in which they arrived.

We do not want to split the original linked list. We will just pass a pointer to the transaction at the beginning of each K-node, set to different brokers. However, since this is a singly linked list and the order of the transactions in the linked list is opposite to the order in which they need to be processed, we will require each set of N/K\lfloor N/K \rfloor transactions in the linked list to be reversed. For this problem, we can assume that we are given a linked list of stock transaction requests, where an integer value represents each transaction request. We want to reverse the transactions in the list N/K\lfloor N/K \rfloor at a time and return the modified list. We may not alter the values, and only the transaction, rather physically change the transactions in the linked list.

Note: N/K\lfloor N/K \rfloor is guaranteed to be a positive integer that is less than or equal to the length of the linked list. If the number of transactions is not a multiple of N/K\lfloor N/K \rfloor then the transaction left in the end should remain as it is.

We may not use any additional space for our solution and we may solve the problem in O(1)O(1) extra memory space.

The following examples may clarify this behavior:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.