Nutanix | OA | MTS2 | Work Schedule

10/1/2024

Round 1

Questions: Question 1
An employee has to work exactly as many hours as they are told to each week, scheduling no more than a given daily maximum number of hours. On some days, the number of hours worked will be given. The employee gets to choose the remainder of their schedule, within the given limits.

A completed schedule consists of exactly 7 digits in the range 0 to 8 that represent each day's work hours. A pattern string similar to the schedule is given, but some of its digits are replaced by a question mark, ?, (ascii 63 decimal). Given a maximum number of hours that can be worked in a day, replace the question marks with digits so that the sum of the scheduled hours is exactly the hours that must be worked in a week.

Determine all possible work schedules that meet the requirements and return them as a list of strings, sorted ascending.

Example

pattern = '08??840'  
work_hours = 24  
day_hours = 4

There are 2 days on which they must work 24-20=4 more hours for the week. All of the possible schedules are listed below:

Function Description
Complete the function findSchedules in the editor below.
findSchedules has the following parameter(s):

int workhours: the hours that must be worked in the week
int dayhours: the maximum hours that may be worked in a day
int pattern: the partially completed schedule

Returns:

string arr[]: represents all possible valid schedules (must be ordered lexicographically ascending)

Constraints

1 ≤ work_hours ≤ 56
1 ≤ day_hours ≤ 8
| pattern | = 7
Each character of pattern ∈ {0, 1,...,8}
There is at least one correct schedule.

Sample Case 0
Sample Input

STDIN        Function  
-----        -----  
56       →   work_hours = 56  
8        →   day_hours = 8  
???8???  →   pattern = '???8???'

Sample Output

Explanation

work_hours = 56  
day_hours = 8  
pattern = '???8???'

There is only one way to work 56 hours in 7 days of 8 hours.

Sample Case 1
Sample Input

STDIN        Function  
-----        -----  
3        →   work_hours = 3  
2        →   day_hours = 8  
??2??00  →   pattern = '??2??00'

Sample Output

Explanation

work_hours = 3  
day_hours = 2  
pattern = '??2??00'

They only need to schedule 1 more hour for the week, and it can be on any one of the days in question.

Working Solution

import java.util.*;

public static List<String> findSchedules(int workHours, int dayHours, String pattern) {
    // Calculate the number of question marks in the pattern
    int questionMarks = 0;
    int fixedHoursSum = 0;

    for (char c : pattern.toCharArray()) {
        if (c == '?') {
            questionMarks++;
        } else {
            fixedHoursSum += Character.getNumericValue(c);
        }
    }

    // Calculate the remaining hours needed to be filled
    int remainingHours = workHours - fixedHoursSum;

    // Generate all possible combinations for the question marks
    List<String> possibleSchedules = new ArrayList<>();
    generateSchedules(pattern, dayHours, questionMarks, remainingHours, new int[questionMarks], 0, possibleSchedules);

    // Sort the possible schedules lexicographically
    Collections.sort(possibleSchedules);

    return possibleSchedules;
}

private static void generateSchedules(String pattern, int dayHours, int questionMarks, int remainingHours, int[] currentCombination, int index, List<String> possibleSchedules) {
    if (index == questionMarks) {
        // Check if the current combination is valid
        int sum = 0;
        for (int hours : currentCombination) {
            sum += hours;
        }
        if (sum == remainingHours) {
            // Create a schedule with the current combination
            StringBuilder schedule = new StringBuilder();
            int combIndex = 0;
            for (char c : pattern.toCharArray()) {
                if (c == '?') {
                    schedule.append(currentCombination[combIndex++]);
                } else {
                    schedule.append(c);
                }
            }
            possibleSchedules.add(schedule.toString());
        }
        return;
    }
    // Try all possible hours for the current question mark
    for (int i = 0; i <= dayHours; i++) {
        currentCombination[index] = i;
        generateSchedules(pattern, dayHours, questionMarks, remainingHours, currentCombination, index + 1, possibleSchedules);
    }
}

Candidate's Approach

No approach provided.

Interviewer's Feedback

No feedback provided.