Sleepless Sysadmins
(4 marks + 1 mark for documentation)
You work on a big tech company and are responsible for defining the schedules of the sys-
tem administrators that will be on duty in the night shifts for the next 30 nights (numbered
Copyright By PowCoder代写 加微信 powcoder
There is a set of n system administrators (numbered 0, 1,
-1) that are available for taking
some night shifts and get paid a higher hourly rate. But each of those system administrators
have their own preferences regarding the nights they want to work (and the ones they don’t
want to work)
You are given as input a list of lists preferences. Each interior list represents a different day.
preferences [i] [j] is equal to 1 if the sysadmin numbered j is interested in working in the
shift of the night numbered i, and preferences [i] [i] is equal to 0 otherwise.
Your company established the following policies:
There is an integer parameter sysadmins_per_night that specifies the exact number of
sysadmins that should be on duty each night (the same number of sysadmins will be
needed on each night). It holds that 0 < sysadmins_per_night < n.
• There is an integer parameter max_unwanted_shifts, and each of the n sysadmins should
be allocated to at most max_unwanted_shifts night shifts for which she was not inter-
ested. It holds that 0 < max_unwanted_shifts < n.
• There is an integer parameter min_shifts, and each of the n sysadmins should be allo-
cated to at least min_shifts night shifts. It holds that 0 < min_shifts < n.
• As long as you comply with the three constraints above, you are free to allocate one
sysadmin to as many night shifts as you want.
To solve this problem, you should write a function allocate (preferences, sysadmins_per_night
max_unwanted_shifts, min_shifts) that returns:
• None (i.e., Python NoneType), if an allocation that satisfy all constraints does not exist.
Otherwise, it returns a list of lists allocation. allocation[i] [j] should be equal to
1 if the sysadmin numbered j is allocated to work on the the night numbered i, and
allocation[i] [j] should be equal to O if the sysadmin numbered j is not allocated to
work on the the night numbered i.
Complexity
Your solution should have a worst-case time complexity of O (n?).
A Chain of Events
+ 1 mark for documentation)
There is usually a tragic backstory to every villain - you as Dr Weird want to understand why
Master X turned to the dark side. In order to do so, you retrieve the timelines of Master X
being evil; with focus on the chain of events that caused him extreme sadness.
For timeline 1:
• Event 1: Master X lost Daisy, his pet rabbit.
• Event 2: Master X lost 10 games of games against Professor Chaos.
Event 3: Master X's taco fell to the floor on Taco Tuesday.
For timeline 2:
• Event 1: Master X got chased by a scary clown holding a red balloon.
Event 2: Master X lost 10 games of games against Professor Chaos.
Event 3: Master X's taco fell to the floor on Taco Tuesday.
• Event 4: Master X pet hamster Hammy bit him.
• Event 5: Master X couldn't return home because the Tree Sentinel is blocking his way.
For timeline 3:
• Event 1: Master X watched the final season of Game of Thorns.
Event 2: Master X got chased by a scary clown holding a red balloon.
• Event 3: Master X lost 10 games of games against Professor Chaos.
• Event 4: Master X's taco fell to the floor on Taco Tuesdav.
From the 3 timelines above, the longest shared chained events for all 3 events are (1) Master
X lost 10 games of games against Professor Chaos; followed by (2) Master X's taco fell to the
These are the 2 events that drove Master X to despair and to be the villain that he is
today in all 3 timelines.
There could be countless timelines, and each timeline could have countless events. Thus, you
once again harness the magic of Algorithms and Data Structures! To do so, you turn this
problem into a trie; or more specifically a generalised suffix trie" using encoding magic where
each timeline is turned into a word consisting of events as characters. Thus:
Timeline 1 as abc
Timeline 2 as dbcef
• Timeline 3 as gdbc
. and the longest chain of events that drove Master X mad in all 3 timelines are events
... and the longest chain of events that drove Master X mad in 2 timelines for example
are events dbc.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com