Panda Guru LogoPanda
Guru

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]

    image

  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


Candidate's Approach

No approach provided.

Interviewer's Feedback

No feedback provided.