求职面试问题使用树，要保存哪些数据? [英] Job Interview Question Using Trees, What data to save?

问题描述

我正在解决以下求职面试问题，并解决了大部分问题，但最后一项要求却失败了.

问::构建支持以下功能的数据结构:

Init -初始化空白DS.O(1)时间复杂度.

SetPositiveInDay(d，x)-将添加到DS中的 d 天恰好是 x 的新人感染了covid-19.O(log n)时间复杂度.

WorseBefore(d)-从插入DS的日期开始，并且比小 d天，返回最后一个，其中新感染人数更多比d.O(log n)时间复杂度.

例如:

  Init()SetPositiveInDay(1,10)SetPositiveInDay(2,20)SetPositiveInDay(3,15)SetPositiveInDay(5,17)SetPositiveInDay(23,180)SetPositiveInDay(8,13)SetPositiveInDay(13,18)WorstBefore(13)//返回第2天SetPositiveInDay(10,19)WorstBefore(13)//返回第10天 

重要提示:您不能假设将按订单输入日期，也不能假设不会出现空白".几天之间.(有些日子可能不会保存在DS中，有些日子之后可能会保存.)

---

我做了什么?

我使用了AVL树(我也可以使用2-3棵树).对于每个节点，我都有:

生病-当天新感染的人数.

maxLeftSick -左儿子的最大感染人数.

maxRightSick -右儿子的最大感染人数.

当插入一个新节点时，我确保旋转数据不会丢失，对于从新节点到根节点的每个节点，我都会这样做:

但是我没有成功实现 WorseBefore(d).

解决方案

在哪里搜索?

首先，您需要在按天数排序的树中找到与 d 对应的节点 node .令 x = Sick(node).这可以在O(log n)中完成.

如果 maxLeftSick(node)>x ，解决方案必须在 node 的左侧子树中.在此处搜索解决方案并返回答案.可以在O(log n)中完成-参见下文.

否则，从 node 开始，将树向上朝根方向遍历，直到找到满足此属性的 first 节点 nextPredecessor (取O(log n)):

• nextPredecessor 小于 node ，
• 和
  1. Sick(nextPredecessor)>x 或
  2. maxLeftSick(nextPredecessor)>x .

如果不存在这样的节点，我们将放弃.在情况1中，只需返回 nextPredecessor ，因为这是最好的解决方案.

在情况2中，我们知道解决方案必须必须在 nextPredecessor 的左侧子树中，因此请在此处搜索并返回答案.同样，这需要O(log n)-见下文.

---

请注意，无需在 nextPredecessor 的 right 子树中进行搜索，因为在该子树中只有小于 node 的节点将是 node 本身的左子树，我们已经排除了它.

还请注意，由于这些节点甚至更小，因此没有必要比 nextPredecessor 沿树进一步遍历，并且我们正在寻找满足所有约束的最大节点

---

如何搜索?

确定，那么我们如何在子树中搜索解决方案?使用 maxLeftSick 和 maxRightSick 信息:

1. 如果 q 有一个正确的孩子，并且 maxRightSick(q)>x ，然后在 q 的右侧子树中搜索.
2. 如果 q 没有合适的孩子，并且 Sick(q)>x ，返回 Day(q).
3. 如果 q 有一个左孩子，并且 maxLeftSick(q)>x ，然后在 q 的左侧子树中搜索.
4. 否则，子树 q 中没有解决方案.

我们正在有效地使用 maxLeftSick 和 maxRightSick 修剪搜索树，使其仅包括更差"的内容.节点，并且在那棵经过修剪的树中，我们得到了最右边的节点，即一天中最大的节点.

很容易看出该算法在 O(log n)中运行，其中 n 是节点总数，因为步数受高度限制树的

伪代码

这是伪代码(假设 maxLeftSick 和 maxRightSick 如果没有相应的子节点，则返回-1):

 //返回小于d的最大日期，使其//感染人数大于第d天的感染人数.//如果不存在这样的一天，则返回-1.int WorstBefore(int d){节点=查找(d);//尝试在左侧子树中找到解决方案如果(maxLeftSick(node)> Sick(node)){返回FindLastWorseThan(node-> left，Sick(node));}//向上移至根，直到找到第一个节点//小于`node`并且//Sick(nextPredecessor)>生病(节点)或//maxLeftSick(nextPredecessor)>生病(节点).nextPredecessor = findNextPredecessor(node);如果(nextPredecessor == null)返回-1;//情况1如果(Sick(nextPredecessor)> Sick(node))返回nextPredecessor;//情况2:maxLeftSick(nextPredecessor)>生病(节点)返回FindLastWorseThan(nextPredecessor-> left，Sick(node));}//在根目录为"node"的给定子树中查找最新的日期；在哪里//感染数大于x.在O(log(size(q)))中运行.int FindLastWorseThan(Node q，int x){if(((q-> right)= null并且Sick(q)> x)返回Day(q);如果(maxRightSick(q)> x)返回FindLastWorseThan(q-> right，x);如果(maxLeftSick(q)> x)返回FindLastWorseThan(q-> left，x);返回-1;} 

I was solving the following job interview question and solved most of it but failed at the last requirement.

Q: Build a data structure which supports the following functions:

Init - Initialise Empty DS. O(1) Time complexity.

SetPositiveInDay(d,x) - Add to the DS that in day d exactly x new people were infected with covid-19. O(log n)Time complexity.

WorseBefore(d) - From the days inserted into the DS and smaller than d return the last one which has more newly infected people than d. O(log n)Time complexity.

For example:

Init()
SetPositiveInDay(1,10)
SetPositiveInDay(2,20)
SetPositiveInDay(3,15)
SetPositiveInDay(5,17)
SetPositiveInDay(23,180)
SetPositiveInDay(8,13)
SetPositiveInDay(13,18)
WorstBefore(13) // Returns day #2
SetPositiveInDay(10,19)
WorstBefore(13) // Returns day #10

Important note: you can't suppose that days will be entered by order and can't suppose too that there won't be "gaps" between days. (Some days may not be saved in the DS while those after it may be).

---

What I did?

I used AVL tree (I could use 2-3 tree too). For each node I have:

Sick - Number of new infected people in that day.

maxLeftSick - Max number of infected people for left son.

maxRightSick - Max number of infected people for right son.

When inserted a new node I made sure that in rotation data won't get missed plus, for each single node from the new one till the root I did:

But I wasn't successful implementing WorseBefore(d).

解决方案

Where to search?

First you need to find the node node corresponding to d in the tree ordered by days. Let x = Sick(node). This can be done in O(log n).

If maxLeftSick(node) > x, the solution must be in the left subtree of node. Search for the solution there and return the answer. This can be done in O(log n) - see below.

Otherwise, traverse the tree upwards towards the root, starting from node, until you find the first node nextPredecessor satisfying this property (this takes O(log n)):

• nextPredecessor is smaller than node,
• and either
  1. Sick(nextPredecessor) > x or
  2. maxLeftSick(nextPredecessor) > x.

If no such node exists, we give up. In case 1, just return nextPredecessor since that is the best solution.

In case 2, we know that the solution must be in the left subtree of nextPredecessor, so search there and return the answer. Again, this takes O(log n) - see below.

---

Note that there is no need to search in the right subtree of nextPredecessor since the only nodes that are smaller than node in that subtree would be the left subtree of node itself, and we have already excluded that.

Note also that it is not necessary to traverse further up the tree than nextPredecessor since those nodes are even smaller, and we are looking for the largest node satisfying all constraints.

---

How to search?

OK, so how do we search for the solution in a subtree? Finding the largest day within a subtree rooted in q that is worse than an infection number x is simple using the maxLeftSick and maxRightSick information:

1. If q has a right child and maxRightSick(q) > x then search in the right subtree of q.
2. If q has no right child and Sick(q) > x, return Day(q).
3. If q has a left child and maxLeftSick(q) > x then search in the left subtree of q.
4. Otherwise there is no solution within the subtree q.

We are effectively using maxLeftSick and maxRightSick to prune the search tree to include only "worse" nodes, and within that pruned tree we get the right most node, i.e. the one with the largest day.

It is easy to see that this algorithm runs in O(log n) where n is the total number of nodes since the number of steps is bounded by the height of the tree.

Pseudocode

Here is the pseudocode (assuming maxLeftSick and maxRightSick return -1 if no corresponding child node exists):

// Returns the largest day smaller than d such that its 
// infection number is larger than the infection number on day d.
// Returns -1 if no such day exists.
int WorstBefore(int d) {
    node = find(d);
    
    // try to find the solution in the left subtree
    if (maxLeftSick(node) > Sick(node)) {
        return FindLastWorseThan(node -> left, Sick(node));
    }
    // move up towards root until we find the first node
    // that is smaller than `node` and such that
    // Sick(nextPredecessor) > Sick(node) or 
    // maxLeftSick(nextPredecessor) > Sick(node).
    nextPredecessor = findNextPredecessor(node);
    if (nextPredecessor == null) return -1;

    // Case 1
    if (Sick(nextPredecessor) > Sick(node)) return nextPredecessor;
    
    // Case 2: maxLeftSick(nextPredecessor) > Sick(node)
    return FindLastWorseThan(nextPredecessor -> left, Sick(node));
}

// Finds the latest day within the given subtree with root "node" where
// the infection number is larger than x. Runs in O(log(size(q)).
int FindLastWorseThan(Node q, int x) {
    if ((q -> right) = null and Sick(q) > x) return Day(q);
    if (maxRightSick(q) > x) return FindLastWorseThan(q -> right, x);
    if (maxLeftSick(q) > x) return FindLastWorseThan(q -> left, x);
    return -1;
}

这篇关于求职面试问题使用树，要保存哪些数据?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！