Data structures

Question 1

What is an array?

Answer 1

An array is a collection of items of same data type stored at contiguous memory locations

Question 2

What is a Linked List?

Answer 2

a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list. (look a like an array but on different memory locations)

Question 3

Downsides of a Linked List?

Answer 3

1. Searching is slow (linear search)
2. Takes more memory (because it also stores the memory location and value.
3. relative difficult to sort

Question 4

Upside of Linked List?

Answer 4

Faster to add or remove items

Question 5

What is a hashtable (hashmap)

Answer 5

Hash Table is a data structure which stores data in an associative manner. In a hash table, data is stored in an array format, where each data value has its own unique index value.

Question 6

Upside of a hashtable?

Answer 6

Fast searching, fast inserting

Question 7

Downside of a hashtable

Answer 7

Takes more memory

Question 8

What is a trie?

Answer 8

A trie (derived from retrieval) is a multiway tree data structure used for storing strings over an alphabet. It is used to store a large amount of strings. The pattern matching can be done efficiently using tries.

Question 9

Upside of using a Trie

Answer 9

1. In tries the keys are searched using common prefixes. Hence it is faster. The lookup of keys depends upon the height in case of binary search tree.
2. Tries take less space when they contain a large number of short strings. As nodes are shared between the keys.
3. Tries help with longest prefix matching, when we want to find the key.

Question 10

What a 3 downsides of using an Array?

Answer 10

1. insertion is bad
2. deleting items is bad
3. stuck with a fixxed size

Question 11

What are 3 upsides of using an array?

Answer 11

1. Looking up items is good
2. relative easy to sort an array
3. Relative small in memory-size