D. E. Shaw India | DESIS Ascend Educare - Edition 4 Coding Round questions Experience
Round 1
Questions:
-
Sync Servers (25min)
In a development environment, there are
n
servers, and their bootstrap scripts are out of sync.There is an array
versions
ofn
integers, whereversions[i]
represents the script version on thei
-th server. There is async
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 thesync
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 thesync
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
andversions = [2, 4, 5, 3, 3]
.One of the optimal ways to sync all the servers:
- Take the subarray
[4, 5, 3, 3]
and call thesync
function on it. The versions become[2, 3, 3, 3, 3]
. - Take the subarray
[2, 3]
and call thesync
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 ofsync
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]
- Take the subarray
-
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
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.