İnterval ağacı

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon google Intuit Kahin Kvalifikasiya
AğacBaxılıb 82

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Aralıqda ağac problem, bir sıra fasilələr və üç növ sorğu verdik

  1. addInterval (x, y): Çoxluğa (x, y) bir aralıq əlavə edin
  2. removeInterval (x, y): Çoxluqdan (x, y) aralığı silin
  3. checkInterval (x, y): (x, y) intervalının bəzi mövcud interval ilə üst-üstə düşdüyünü yoxlayın

Yuxarıda göstərilən 3 əməliyyatı yerinə yetirmək üçün bir məlumat strukturu (Interval Tree) dizayn edin.

misal

İnterval ağacıPin

Input
Taxmaq (5, 10)
Taxmaq (3, 8)
Taxmaq (10, 15)
Taxmaq (16, 18)
Taxmaq (9, 11)
Taxmaq (1, 1)
CheckOverlap (1, 2)
CheckOverlap (7, 11)
CheckOverlap (20, 25)
Sil (1, 1)
Sil (10, 15)
CheckOverlap (12, 14)
CheckOverlap (8, 15)
CheckOverlap (1, 2)
Sil (5, 10)
Sil (1, 2)
Sil (8, 15)
Buraxılış
doğru
doğru
saxta
saxta
doğru
saxta

Interval ağacının alqoritmi

Fikir genişlənmiş özünü tarazlaşdırma istifadə etməkdir İkili ağac. Hər qovşaq aşağıdakı məlumatları saxlayır

  • İnterval [l, r], burada l intervalın başlanğıc nöqtəsidir, r isə intervalın bitmə nöqtəsidir.
  • max, bu düyünlə köklənmiş sol və sağ alt ağacdakı maksimum bitmə nöqtəsi.

Daxil etmə və silinmə

İnvalın başlanğıc nöqtəsi (l) özünü tarazlaşdıran İkili Axtarış Ağacında nizamın qorunması üçün istifadə olunur.
Taxmaq və Sil əməliyyatları ümumi özünü tarazlaşdıran İkili Axtarış Ağacı ilə eyni şəkildə həyata keçirilir.

Axtarış üst-üstə düşür

I (x, y) intervalının özünü tarazlaşdıran İkili Axtarış Ağacındakı bəzi intervallarla üst-üstə düşdüyünü axtarın,

  1. Kökdən başlayın, əgər mən (x, y) kök ilə üst-üstə düşsəm, kökü qayıdın.
  2. Cari düyünün maksimum dəyəri I-nin başlanğıc nöqtəsindən çoxdursa, sol alt ağacda axtarın.
  3. Sağ alt ağacdakı başqa axtarış.

Interval Ağacı üçün JAVA Kodu

public class IntervalTree {
    // class representing the node of interval tree
    static class Node {
        int l;
        int r;
        int max;

        Node left, right;

        public Node(int l, int r) {
            this.l = l;
            this.r = r;
            this.max = r;
        }
    }

    // Function to insert an interval in interval tree
    public static Node insert(Node root, int l, int r) {
        // Insert like normal BST, by considering root.l as the key element
        if (root == null) {
            return new Node(l, r);
        }

        if (l < root.l) {
            root.left = insert(root.left, l, r);
        } else if (l > root.l) {
            root.right = insert(root.right, l, r);
        } else {
            if (r < root.r) {
                root.left = insert(root.left, l, r);
            } else {
                root.right = insert(root.right, l, r);
            }
        }

        // If current node's max is less than r, then update max
        if (root.max < r) {
            root.max = r;
        }

        return root;
    }

    private static boolean checkOverlap(Node root, int l, int r) {
        // If current node is null, return false
        if (root == null) {
            return false;
        }

        // If overlaps return true
        if (root.l <= r && l <= root.r) {
            return true;
        }

        // If max value of current is greater than starting point of I(l)
        // search in left subtree
        if (root.left != null && root.left.max >= l) {
            return checkOverlap(root.left, l, r);
        }

        // Else search in right subtree
        return checkOverlap(root.right, l, r);
    }

    // Function to delete a binary tree, same as normal delete in a BST
    private static Node delete(Node root, int l, int r) {
        if (root == null) {
            return null;
        }

        if (l < root.l) {
            root.left = delete(root.left, l, r);
        } else if (l > root.l) {
            root.right = delete(root.right, l, r);
        } else {
            if (r < root.r) {
                root.left = delete(root.left, l, r);
            } else if (r > root.r) {
                root.right = delete(root.right, l, r);
            } else {
                if (root.left == null)
                    return root.right;
                else if (root.right == null)
                    return root.left;

                // Find the minimum value in the right subtree of root
                Node curr = root.right;
                while (curr.left != null) {
                    curr = curr.left;
                }
                root.l = curr.l;
                root.r = curr.r;

                root.right = delete(root.right, root.l, root.r);
            }
        }

        return root;
    }

    public static void main(String[] args) {
        Node root = null;
        root = insert(root, 5, 10);
        root = insert(root, 3, 8);
        root = insert(root, 10, 15);
        root = insert(root, 16, 18);
        root = insert(root, 9, 11);
        root = insert(root, 1, 1);

        System.out.println(checkOverlap(root, 1, 2));
        System.out.println(checkOverlap(root, 7, 11));
        System.out.println(checkOverlap(root, 20, 25));

        root = delete(root, 1, 1);
        root = delete(root,10, 15);

        System.out.println(checkOverlap(root, 12, 14));
        System.out.println(checkOverlap(root, 1, 2));
        System.out.println(checkOverlap(root, 8, 15));
    }
}
true
true
false
false
false
true

İnterval Ağacı üçün C ++ Kodu

#include <bits/stdc++.h>
using namespace std;

// class representing the node of interval tree
class Node {
    public:
    int l, r, max;
    Node* left;
    Node* right;
    Node(int lVal, int rVal) {
        l = lVal;
        r = rVal;
        max = rVal;
        left = right = NULL;
    }
};

// Function to create a new Node
Node* newNode(int l, int r) {
    Node* node = new Node(l, r);
    return node;
}

// Function to insert an interval in interval tree
Node* insert(Node* root, int l, int r) {
    if (root == NULL) {
        return newNode(l, r);
    }
    
    if (l < root->l) {
        root->left = insert(root->left, l , r);
    } else if (l > root->l) {
        root->right = insert(root->right, l, r);
    } else {
        if (r < root->r) {
            root->left = insert(root->left, l, r);
        } else {
            root->right = insert(root->right, l, r);
        }
    }
    
    // If current node's max is less than r, then update max
    if (root->max < r) {
        root->max = r;
    }
    
    return root;
}

bool checkOverlap(Node *root, int l, int r) {
    // If current node is null, return false
    if (root == NULL) {
        return false;
    }
    
    // If overlaps return true
    if (root->l <= r && l <= root->r) {
        return true;
    }
    
    // If max value of current is greater than starting point of I(l)
    // search in left subtree
    if (root->left != NULL && root->left->max >= l) {
        return checkOverlap(root->left, l, r);
    }
    
    // Else search in right subtree
    return checkOverlap(root->right, l, r);
}

// Function to delete a binary tree, same as normal delete in a BST
Node* deleteInterval(Node* root, int l, int r) {
    if (root == NULL) {
        return NULL;
    }
    
    if (l < root->l) {
        root->left = deleteInterval(root->left, l, r);
    } else if (l > root->l) {
        root->right = deleteInterval(root->right, l, r);
    } else {
        if (r < root->r) {
            root->left = deleteInterval(root->left, l, r);
        } else if (r > root->r) {
            root->right = deleteInterval(root->right, l, r);
        } else {
            // This is the interval to be deleted
            if (root->left == NULL)
                return root->right;
            else if (root->right == NULL)
                return root->left;
                
            // Find the minimum value in the right subtree of root
            Node* curr = root->right;
            while (curr->left != NULL) {
                curr = curr->left;
            }
            root->l = curr->l;
            root->r = curr->r;
            
            root->right = deleteInterval(root->right, root->l, root->r);
        }
    }
    
    return root;
}

int main() {
    Node *root = NULL;
    root = insert(root, 5, 10);
    root = insert(root, 3, 8);
    root = insert(root, 10, 15);
    root = insert(root, 16, 18);
    root = insert(root, 9, 11);
    root = insert(root, 1, 1);
    
    if (checkOverlap(root, 1, 2))
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
        
    if (checkOverlap(root, 7, 11))
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
    
    if (checkOverlap(root, 20, 25))
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
        
    root = deleteInterval(root, 1, 1);
    root = deleteInterval(root,10, 15);
    
    if (checkOverlap(root, 12, 14))
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
        
    if (checkOverlap(root, 8, 15))
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
        
    if (checkOverlap(root, 1, 2))
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
        
    return 0;
}
true
true
false
false
true
false

İnterval Ağac üçün Mürəkkəblik Analizi

Daxil etmək və silmək üçün:

Zaman Mürəkkəbliyi = O (h), burada h BST (Binary Search Tree) hündürlüyü və balanslaşdırılmış BST h üçün log (n).

Axtarış üçün:

Zaman Mürəkkəbliyi = O (h), burada h BST (Binary Search Tree) hündürlüyü və balanslaşdırılmış BST h üçün log (n).

References

Crack Sistemi Dizayn Müsahibələri
Translate »