data structures

Question 1

How to solve hash table collisions? What are the advantages and disadvantages?

Answer 1

Chaining with Linked List –> you can just add an item to the linked list if there is a collision. It’s efficient if there are not many collisions, but in the worst case it’s O(n), where the n is the number of elements in the table. This is the most commonly used solution.

Chaining with binary search trees –> instead of linked list we can use BSTs, it would bring down the worst case to O(logN). This is rarely used.

Open Addressing with Linear Probing –> When a collision occours we move to the next index (or some other) and put it there. This can be efficient with low number of collisions, but it’s a drawback that the array size is limited. Also clustering could occur.

Quadratic Probing and Double Hashing –> the probe distance not necessarily need to be linear, it can be quadratic or can be an other hash function calculating the distance.

Question 2

Describe the two main types of linked list.

Answer 2

Singly linked lists have only one reference to the next node.
Doubly linked lists have reference to both the previous and the next node.

Question 3

How linked lists inserting a node to the list?

Answer 3

Inserting to the beginning, the new node becomes the head of the list:

• creating node
• add the head node to be the next of the created node
• if doubly : add the new node as previous node to the (old) head, new node’s previous is null
• change the head reference to point to the new node

Inserting after a given node:

• check if the given node is null
• create new node
• change the new node’s next reference to the given node’s next reference
• if doubly : change the next node’s previous reference to be the new node
• change the given node’s next reference to new node
• if doubly: add the given node to be previous node of new node

Inserting in the end:

• check if list is null, if so add it as head
• create new node
• add null to be the new node’s next reference
• find last node
• change the last node’s next reference to be new node
• if doubly: change the new node’s previous reference to be last node

Question 4

How linked lists delete nodes?

Answer 4

1) Find the previous node of the node to be deleted.
2) Change the next of the previous node to be the node that was next to the node we deleting
3) if doubly: change the previous reference of this next node to be the previous node

Question 5

What is a stack and what kind of operations it offers? In which cases is it used most commonly? How Java implements stack?

Answer 5

Stack is a linear data structure and use last-in first-out ordering, which means, that you add element to the top, and remove it from there. (like stack of books)

operations:

• pop() remove the top item
• push(item) add item to top
• peek() return but not remove the top element

Usually it used for recursive algorithms.

Java has a Stack class which inherits from Vector. ArrayDeque can be used as well, which is recommended in some cases.

Question 6

What is a queue data structure? Describe it’s useful methods. In which cases is it used? How Java implements it?

Answer 6

Queue is a linear data structure and use first-in first-out ordering. This is similar to a real-life queue.

operations:

• add(item): add an item to the end
• remove(): remove the first item
• peek(): return the first item

Used for breadth-first search and implementing a cache.

Java implements it with multiple data structured, but LinkedList, PriorityQueue and PriorityBlockingQueue are the most commonly used.

Question 7

what’s the definition of a binary tree?

Answer 7

a binary tree is a tree where each node has up to two children

Question 8

what’s the definition of a binary search tree?

Answer 8

A binary search tree is a binary tree in which every node fits a specific ordering:

• left descendents are smaller or equal
• right descendents are greater

This definition can vary slightly:

• sometimes there cannot be duplicates in the tree
• sometimes equal values will be on the right or either side

Question 9

how an AVL tree calculates if it is balanced or not?

Answer 9

It is balanced if the difference between heights of left subtree and right subtree is not more than 1.

Question 10

what is a complete binary tree?

Answer 10

A binary tree in which every level of the tree is fully filled, except the last level. The last level is filled from left to right.

Question 11

what is a full binary tree?

Answer 11

A binary tree in which every node has either zero or two children. No nodes have 1 child.

Question 12

what is a perfect binary tree?

Answer 12

a binary tree which is full and complete. All leaf nodes will be the same level and that level has the maximum number of nodes.

Question 13

what is a binary heap and its types?

Answer 13

A binary heap is a complete binary tree. if it is a min-heap than each node is smaller that its children. The root therefore the minimum element. A max-heap is the reverse of this.

Question 14

What is a trie?

Answer 14

trie is a variant of a tree in which characters are stored in each node. Each path down the trie may represent a word.

the * nodes or null nodes are used, to indicate that you reached the end of the word. The actual implementation of this null node can be a special node or just a flag on the parent node.

Each node can have up to alphabet size + 1 children, or just alphabet size if the flag is used to indicate the end of the word.

Question 15

What is a graph?

Answer 15

A graph is a collection of nodes with edges between some of them.

Question 16

Name and explain the two most common ways to represent a graph in programming.

Answer 16

Adjacency List
The most common way. Every vertex (node) has a list of adjacent vertices.

Adjacency Matrices
It’s an NxN matrix, where N is the number of vertices. A boolean matrix has a ‘true’ value where there is an edge between the two nodes, an integer matrix has zeros and ones.