Завдання на 3/3/24

tasks-20240303.md

Наступної неділі будемо обговорювати задачки вищче + те що було на сьогодні

Завдання на 3/3/24

• [M] https://leetcode.com/problems/snapshot-array
  • Solution
• [M] https://leetcode.com/problems/detonate-the-maximum-bombs
  • Solution
• [M] https://leetcode.com/problems/delete-nodes-and-return-forest
  • Solution
• Task 1: Servers & Tasks умова нижче
  • Solution
• Task 2: Addressbook умова нижче
  • Solution
• Task 3 Task 3: Encode & Decode Sequence умова нижче

Task 1: Servers & Tasks

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 second 1/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/8 to itself and handles second 1/8 to other connected server
  • and so on until it ends up with 1 task - the remaining single task. It is the task first server going to assign to itself

• For the second server: similar algo: it receives 1/2 tasks 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]) among k-1 connected 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

Input

• 2^k servers
• 2^k tasks
• servers are represented as array of connected srevers connections = [(source, target)] e.g. pairs of (source server id, target server id)

API to implement

int getTaskId(connections, int targetServer) { ... } // returns the task id assigned to target server

Some edge cases

• 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 k connected servers) - in this case output any working solution for task-2-server mapping

More clarifications

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]

Solution

Task 2: Addressbook

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)

Solution

Task 3: Encode & Decode Sequence

Part 1

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]]

Part 2

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]