Pergunta de entrevista da empresa Infinidat
Implement a data structure the support the following interface void push(Integer) - O(1) Integer pop() - O(1) - pop the last element that inserted Integer get_middle() - O(1) - get the middle element value get_k(k) - O(K) - get the first k elements values.
Respostas da entrevista
Sigiloso
class Node { public: int val; Node* prev= nullptr; Node* next= nullptr; }; class LinkedList { Node* root; Node* last; Node* middle; int count = 0; public: void Push(int val) { Node * n= new Node; n->val = val; if (root == nullptr) { root = n; last = root; middle = root; } else { n->next = root; root->prev=n; root = n; if (count % 2 == 0) { middle = middle->prev; } } count++; } int pop() { if (root == nullptr) { return -1; } Node tmp = *root; root = root->next; //free(tmp); count--; if (count != 0 && count != 1 && count % 2 == 0) { middle = middle->next; } return tmp.val; } int Get_Middle() { return middle->val; } int Get_K(int k) { k = k > count ? count : k; Node * nk = last; for (int i = 0; i prev; } return nk->val; } };