1
$\begingroup$

Got inspiration while reading history book. Inspired by: China, the cake of kings and emperors, Le Petit Journal 1898

Background:

After the Second Opium War, United Kingdom(UK), France, Russia, Germany and Japan have a meeting to dividing China the cake.

The cake have fixed size but can be break down into many small pieces with different size. To make it is easier to divide, the cake start point is denoted as 0 and end point is denoted as 1, then a piece of cake can be denoted as P(i, S) with i is the position of that piece in the cake and S is the size of that piece

Initially, UK grab half of the cake, the rest grab few pieces at different location and some pieces of the cake no one want it. Then France noticed that UK take too much and start to complain. UK then split that big piece in to many smaller pieces and give other country some pieces among them, of course there are also pieces no one want among them, then UK take another not so large piece somewhere else. But this piece is overlapped with one piece Germany have, so Germany have no choice but to give up on their piece and pick somewhere else. After few more debates everything has become a mess and hard to track which piece belong to whom. UK then make a call to his brother America and ask him which data structure can be used to represent this cake.

Problem: To avoided starting World War over China the cake, America must think of a data structure to store <Country - Cake pieces> information which as efficient as possible to perform these following operation:

  1. Given P(i, S), find out the previous piece and the next piece and check if it is overlapped or not
  2. Given P(i, S), add owner information
  3. Given i, find out the owner of cake piece contain it
  4. Given P(i, S), remove owner information
  5. From the start position to the end position of the cake, list all owned cake pieces in order

Data structure do not need to store unowned cake pieces

Question:

  1. If you are America, what data structure would you suggest if all operation have same frequency of usage and show complexity of each required operation to prove your opinion?
  2. Given that operation 2 and 5 is used the most, what data structure would you used?
$\endgroup$
8
  • $\begingroup$ It is unclear if the data structure will allow overlaps (and represent them) or just prevent overlaps when a change is made. $\endgroup$
    – user16034
    May 15, 2023 at 12:35
  • $\begingroup$ If overlaps are allowed, "previous" and "next" piece may lose meaning. And a piece can be overlapped by more than one. $\endgroup$
    – user16034
    May 15, 2023 at 12:39
  • $\begingroup$ Can a piece overlap the start (presumably identical to the end) position ? $\endgroup$
    – user16034
    May 15, 2023 at 12:39
  • $\begingroup$ @YvesDaoust The start cannot be identical to the end (size = 0 is meaningless). Overlapped is not allowed. Every overlapped pieces must be removed before adding new piece. Example: to add P(0.5, 0.4) to C{ P(0.4, 0.2), P(0.6, 0.1), P(0.7, 0.25) } everything must be removed $\endgroup$
    – FEEDC0DE
    May 15, 2023 at 16:32
  • $\begingroup$ You didn't get my question. Can a piece overlap the start ? $\endgroup$
    – user16034
    May 15, 2023 at 16:35

1 Answer 1

0
$\begingroup$

Assumption :The cake is not 'cut' but 'marked' because cut result in partitions and hence there will be no overlaps.

An Interval tree can be used to solve this problem. Interval tree is a self-balancing BST. Each cake piece P(i,S) forms a node with range values i and i+S.
The structure of an Interval tree is given below

struct Interval
{
  float left;       \\ left - stores the leftmost value of the range
  float right;       \\right-stores the rightmost value of the range
 }
struct node
{
  Interval *interval;
  string ownerinfo;  \\ storing the name of the owner
   node *leftchild,*rightchild;  \\leftchild and rightchild are the pointers to the left subtree and right subtree of a node
 }

Each cake pieces P(i,S) are inserted into the tree takes O(logn) in worst case.

Queries :
1)The previous pieces inserted into the tree can be stored into a temporary variables. Checking whether the pieces overlap takes O(1) time.
2)Adding owner information takes O(logn) time in worst case. Traversing from a root node to the node representing the piece P(i,S) takes O(logn). The traverse is analogous to binary search.
3)The range or piece in which a point is contained can be find in O(logn) time .Since there is a possibility for the pieces to overlap a point i can be present in more than one cake pieces.Thus multiple answers are possible.
4)Similar to addition removal takes O(logn) time. Since removing owner information result in unowned cake pieces the nodes have to be removed and subtrees must altered. Deletion is similar to AVL trees.
5)The preorder traversal gives the owned pieces in the order.It takes O(n) time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.