Data Structure Flashcards
to what DB the questions of Strings is similar to?
Arrays
How does hash map works?
check
what is the problem in hash map?
number of collision is very high
worst case runtime of hash map?
O(N) n is the number of keys, but good implementation keeps collision to minimum the run time is O(1)
how to implement hash table with balanced binary search tree?
IDK
what is an array list? and what is it’s access run time?
it’s an array that resize itself as needed while providing O(1) access
what is the run time of resizing the array list?
O(N) n is the number of items in the array list, but it happens so rarely, we can say that the insertion time is O(1)
why the run time of insertion in array list is O(1)
IDK
what is a linked list?
it’s a data structure that represent a sequence of nodes.
linked list vs array?
IDK
How to implement a linked list?
IDK
what is the difference between looping while(n.next != null), while(n!= null), or while(n.next.next != null).
where n is the current node.
IDK
what is the difference between singly and doubly linked list?
IDK
what is the runner technique in Linked lists?
it’s a second pointer technique.
means iterate through the linked list with two pointers simultaneously.
linked list and recursion.
IDK
what operations does stack uses?
pop() remove the top item from the stack
push(item) add an item to the top of the stack
peek(): return the top of the stack
isEmpty() return true if and only if the stack is empty
sum all the cons and pros of all data structures in table.
++++++++++++++++++++++++++_+
what operations does a queue uses?
add(item): add an item to the end of the list
remove(): remove the first item in the list
peek() return the top of the queue
isEmpty() return true if and only if the queue is empty
where do we often use queues?
in BFS or implementing a cache.
what the heap is used for? and what it’s operation and complexity time?
Heaps are commonly used to implement priority queues
insertion: O(log N) where ‘N’ is the number of elements. insert it at the end then rearrange the heap
deletion O(log N) delete then rearrange the heap.
peek: O(1) peek the root
