Design a phone directory that initially has maxNumbers empty slots that can store numbers. The directory should store numbers, check if a certain slot is empty or not, and empty a given slot.
Implement the PhoneDirectory class:
- PhoneDirectory(int maxNumbers) Initializes the phone directory with the number of available slots maxNumbers.
- int get() Provides a number that is not assigned to anyone. Returns -1 if no number is available.
- bool check(int number) Returns true if the slot number is available and false otherwise.
- void release(int number) Recycles or releases the slot number.
https://leetcode.com/problems/design-phone-directory/description/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
class PhoneDirectory { //Doubly connected Linked List Head private Node head; //Doubly connected Linked List Tail private Node tail; //A map having key as an Integer and value as Doubly connected linked list node private Map<Integer, Node> map; public PhoneDirectory(int maxNumbers) { this.head = new Node(-1); this.tail = new Node(-1); //connect the head and the tail of the doubly connected linked list //head <-> tail this.head.next = tail; this.head.prev = tail; this.tail.prev = head; this.tail.next = head; //initialize the map //a. create a node //b. add it to the map this.map = new HashMap<>(); for(int i=0; i<maxNumbers; i++){ Node node = addNode(i); this.map.put(i, node); } } private Node addNode(int val){ //create a node Node node = new Node(val); //connect the node to the head of the doubly connected linkedlist //head <-> node <-> ... <-> tail Node next = this.head.next; this.head.next = node; node.prev = this.head; next.prev = node; node.next = next; return node; } private void deleteNode(Node node){ //prev <-> node <-> next Node prev = node.prev; Node next = node.next; //prev <-> next prev.next = next; next.prev = prev; } public int get() { //check if map is not empty if(map.size()!=0){ //remove the first node //head <-> node <-> ... <-> tail Node node = this.head.next; int val = node.val; //delete the node from the doubly connected linked list deleteNode(node); //delete the node from the map this.map.remove(val); return val; } return -1; } public boolean check(int number) { //check if the number exist in the map return this.map.containsKey(number); } public void release(int number) { //number shouldn't exist in the map if(!this.map.containsKey(number)){ Node node = addNode(number); this.map.put(number, node); } } //convenience method private void print(){ Node p = this.head.next; while(p!=this.tail){ System.out.print(p.val + "->"); p = p.next; } System.out.println(); System.out.println(this.map); } //class representing a node in a Doubly connected linkedlist static class Node { int val; Node prev; Node next; public Node(int val){ this.val = val; } } } /** * Your PhoneDirectory object will be instantiated and called as such: * PhoneDirectory obj = new PhoneDirectory(maxNumbers); * int param_1 = obj.get(); * boolean param_2 = obj.check(number); * obj.release(number); */ |