Genpact Interview Questions and Answers

Given a string and an integer, create a new string by selecting the smallest character from the first K characters of the input string and repeating the process until the input string is empty.

• Iterate through the input string, selecting the smallest character from the first K characters each time.

• Remove the selected character from the input string and append it to the new string.

• Continue this process until the input string is empty.

• Return the final new string formed.

Merge K sorted arrays into a single sorted array.

• Create a min heap to store the first element of each array along with the array index.

• Pop the top element from the heap, add it to the result array, and push the next element from the same array back to the heap.

• Continue this process until all elements are processed.

• Time complexity can be optimized using a priority queue or merge sort technique.

Sort an array of 0s, 1s, and 2s in linear time complexity.

• Use three pointers to keep track of 0s, 1s, and 2s while iterating through the array.

• Swap elements based on the values encountered to sort the array in-place.

• Ensure to handle edge cases like all 0s, all 1s, and all 2s in the array.

Given an array of digits and an integer K, find the maximum number by swapping digits up to K times.

• Sort the digits in non-increasing order to maximize the number.

• Swap the digits to achieve the maximum number within the given number of swaps.

• Handle cases where there are repeating digits and leading zeros.

Move all zeroes to the end of an unsorted array while maintaining the order of non-zero elements.

• Iterate through the array and keep track of the index to place non-zero elements.

• Once all non-zero elements are placed, fill the rest of the array with zeroes.

• Ensure to maintain the relative order of non-zero elements.

• Example: Input: [0, 1, -2, 3, 4, 0, 5, -27, 9, 0], Output: [1, -2, 3, 4, 5, -27, 9, 0, 0, 0]

Delete a node with a given value from a binary search tree (BST).

• Traverse the BST to find the node with the value K to be deleted.

• Handle different cases like node with no children, one child, or two children.

• Update the pointers of the parent node and child nodes accordingly.

• Recursively delete the node and adjust the tree structure.

• Return the root of the modified BST after deletion.