D. E. Shaw India | DESIS Ascend Educare - Edition 4 Coding Round questions Experience

Round 1

Questions:

1. Sync Servers (25min)

   In a development environment, there are n servers, and their bootstrap scripts are out of sync.

   There is an array versions of n integers, where versions[i] represents the script version on the i-th server. There is a sync function that accepts an even-length array and syncs the first half of the array using the values from the second half.

   For example, suppose versions = [1, 2, 3, 4, 5, 6]. If we pass the subarray [3, 4, 5, 6] to the sync function, the first half [3, 4] is synced with the second half [5, 6] and the resultant subarray is [5, 6, 5, 6]. After calling the sync function, versions = [1, 2, 5, 6, 5, 6].

   Find the minimum number of sync function calls required to have the same version of the script on all the servers.

   Example

   Given n = 5 and versions = [2, 4, 5, 3, 3].

   One of the optimal ways to sync all the servers:

   1. Take the subarray [4, 5, 3, 3] and call the sync function on it. The versions become [2, 3, 3, 3, 3].
   2. Take the subarray [2, 3] and call the sync function on it. The versions become [3, 3, 3, 3, 3].

   The minimum number of calls required is 2.

   Function Description

   Complete the function getMinCalls in the editor below.

   getMinCalls has the following parameter:

   • int versions[n]: the version numbers of the bootstrap script

   Returns:

   • int: the minimum number of sync function calls required to sync all the servers

   Constraints

   • 1 ≤ n ≤ 10^5
   • 1 ≤ versions[i] ≤ n

   Input

   versions[] size n = 4
   versions = [4, 3, 2, 1]

   Output: 2

   Explanation One optimal method:

   • Sync [2, 1] so versions=[4, 3, 1, 1]
   • Sync [4, 3, 1, 1] so versions = [1, 1, 1, 1]

   

2. Extra Time Reduction (35min)

   A company has built a new software that takes a string 's' of lowercase English letters as input.

   Whenever a string s is given to the software, the string is processed in the following way:

   • Each pair of characters of the input string 's' is processed.
   • Whenever a pair of same characters is processed, the software takes 1 second extra time due to a bug in the software. Hence, extra_time is equal to the number of pairs of matching characters in the input string s. For example, the string "aacca" will incur an extra_time of 4 since there are 3 different pairs of 'a' and 1 pair of 'c'.

   In order to reduce the extra time taken by the software, the input string s can be divided into substrings. Hence, the total extra time will be the sum of the extra time of each of the substrings. Also, dividing a string into two strings will cause the total_extra_time to increase by k seconds as the software has to reboot itself to take a new input.

   Given input string s and an integer k, find the minimum total_extra_time that can be obtained by dividing the input string 's' optimally.

   Function Description

   Complete the function getMinTotalExtratime in the editor below.

   getMinTotalExtratime takes the following arguments:

   • string s: the input string
   • int k: the extra time to divide the string

   Returns:

   • int: the minimum total_extra_time

   Constraints

   • 1 ≤ |s| ≤ 3 * 10^3
   • 1 ≤ k ≤ 10^2
   • s consists of lowercase English letters only

   Input:

   S="aaaaa" k=12
   

   Output: 10

   Input:

   S="azazaa" k=4
   

   Output: 6