Stacks & Queues
When do you use a stack over a queue and vice versa?
Stack: LIFO, Queue: FIFO
Use a queue when you want to get things out in the order that you put them in. Use a stack when you want to get things out in the reverse order than you put them in.
What is a situation where you would want to use Preorder traversal? Postorder?
Preorder – copy a tree
Postorder – delete a tree
Explain how a hash function works
Hash value(index) and array of buckets
Map value of arbitrary size to fixed-size values
What are the basic operations of a stack and a queue?
Stack: push, pop, isEmpty, peek, size
Queue: enqueue, dequeue, isEmpty, peek, size
What is the order that nodes are visited using Post-order traversal? [show image]
4, 12, 10, 18, 24, 22, 15, 31, 44, 35, 66, 90, 70, 50, 25
What is hash collision
When two pieces of data in a hash table share the same hash value.
What is the difference between Infix, Prefix, and Postfix expressions?
Postfix: operator appears after operands
Prefix: operator appears in expression before the operands
Infix: operator appears between two operands
When is merge sort preferred over quicksort?
If we want the relative order of equal elements after sorting the data to be preserved, merge sort would be the preferred choice since merge sort is a stable sorting algorithm while quicksort isn't.
How does the put() method of HashMap works in Java?
The hashcode() method is used in conjunction with a hash function to find the correct location for the object into the bucket. If a collision occurs, then the entry object which contains both key and value is added to a linked list, and that linked list is stored into the bucket location.
Convert the following string from Postfix to Prefix: “ABC/-AK/L-*”. Which data structure would you use to implement this conversion?
*-A/BC-/AKL
- Stack
What are the differences between selection sort, merge sort, and quicksort
Selection: in-place, sort elements one at a time (two pointers and keep track of min)
Merge sort: sort subarrays and the merge already sorted arrays
Quick sort: sorts each element by comparing each element with the pivot
What will happen if you try to store a key that is already present in HashMap?
It will override the old value with the new value, and put() will return the old value. There will not be any exception or error.
How can you implement a stack using a queue?
Use two queues. Newly entered element stays at the from of q1 so that pop operation dequeus from q1. q2 is used to put every new element in form of q1.
Given Preorder, Inorder, and Postorder traversal of some tree, check if they all are of the same tree.
Inorder: 4 2 5 1 3
Preorder: 1 2 4 5 3
Postorder: 4 5 2 3 1
Yes
How can a hashmap be used to check whether two given arrays are equal or not i.e they contain the same elements or not? Given the arrays can be unsorted.
First, create a hashmap and using a for loop fill the frequency of each and every element of array 1 in the hashmap.
Now, make another loop and decrement the frequency of each and every element of the second array in the hashmap.
In the next step, iterate over the hashmap and check whether all the frequencies are zero or not. Even if any frequency is 1 return false else return true.