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:
0804840 0813840 0822840 0831840 0840840
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
8888888
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
0020100 0021000 0120000 1020000
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.