Наступної неділі будемо обговорювати задачки вищче + те що було на сьогодні
- [M] https://leetcode.com/problems/snapshot-array
- [M] https://leetcode.com/problems/detonate-the-maximum-bombs
- [M] https://leetcode.com/problems/delete-nodes-and-return-forest
- Task 1: Servers & Tasks умова нижче
- Task 2: Addressbook умова нижче
- Task 3 Task 3: Encode & Decode Sequence умова нижче
You need to distribute 2^k tasks to 2^k servers using divide and conquer algorithm:
-
For the first server
- First server when receiving tasks, splits tasks into two halfs: first half portion of tasks keeps to itself (
1/2), second half handles to connected server (1/2) - Remaining first half of tasks first server: keeps fist
1/4(the first half of remaining first half of tasks from prev step) to itself and handles over the second1/4(the second half of remaining first half of tasks from prev step) of tasks to other connected server - Remaining fist quarter of tasks first server: keeps first
1/8to itself and handles second1/8to other connected server - and so on until it ends up with
1task - the remaining single task. It is the task first server going to assign to itself
- First server when receiving tasks, splits tasks into two halfs: first half portion of tasks keeps to itself (
-
For the second server: similar algo: it receives
1/2tasks from first server (second half of tasks first sever received on start) - and needs to redistribute them(1/2 x 2^k tasks = 2^[k-1])amongk-1connected servers applying the same rule -
...and so on..
-
For the nth server: ...
All servers should be assigned one task in the end
Your task is to select a sequence of servers so that every server is mapped to one tasks
2^kservers2^ktasksserversare represented as array of connected sreversconnections = [(source, target)]e.g. pairs of(source server id, target server id)
int getTaskId(connections, int targetServer) { ... } // returns the task id assigned to target server
-
There might be not enough connections b/w servers - underconnected network of servers - in this case return
null -
Serevers might be overconnected (connections more than required, e.g. the first selected server have more than
kconnected servers) - in this case output any working solution for task-2-server mapping
tasks are not given in problem statetement, but I assume its ok to have just array of incremented ids, starting from 1, e.g. tasks = taskIds = [1,2,3,...,2^k]
You have address book in a form (number, city, street, state) records - all not null fields
And have a query: (number, city, street, state) - same set of fields, but some of the fields can be null
Return if any of the records in address book match the search query.
NULL = any, search is case sensitive, e.g. NewYork and newYork are different cities. No regular expressions etc - only full word match is required
e.g.
addressbook = [
(number: 42, city: "Seattle", street: "Brandon", state: "Washington"),
(number: 42, city: "San Francisco", street: "baz", state: "foobar")
]
calls
query: (number: null, city: "Seattle", street: null, state: "Washington") should return true
query: (number: 42, city: "Seattle", street: "Xoxoxo", state:null) should return false
query: (number: null, city: null, street: null, state:null) should return true
query: (number: null, city: "seattle", street: null, state: "Washington")
should return false (Seattle in address book starts with capital letter)
You are given array of integers
Your task is to write encode function that s going to encode array into pairs: [(value, fq)], where value is a number from input array, and fq - as number of consecutive repeats of value in original array
Example
input:
a = [1,1,1,2,1,2,3,3,3,3,4,4,1,-1]
output:
pairs = [[1:3],[2:1],[1:1],[2:1],[3:4],[4:2],[1:1],[-1:1]]
API
encode(a: [int]) -> [[int: int]]
Write value_for_idx & values_for_idxs that s going to return the actual value from input array based on passed index in original array & pairs - array of [value: fq] pairs
value_for_idx(idx: int, pairs: [[int: int]]) -> int
values_for_idxs(idxs: [int], pairs: [[int: int]]) -> [int]