Algorithms and Data Structures

Question 1

Linked List

Answer 1

Access and insert O(n)
head insert O(I)
Best of sequencial access cases
Stacks (LIFO) and queues (FIFO)

Question 2

Double Linked List

Answer 2

Inserts head and tail O(1)
Access O(n)
Deques
MRU: Most receent access to the head.

Question 3

Binary Search Tree

Answer 3

Access is O(log(n)), O(n) worst case
Insert and delete O(log(n)), need of other search to rearrange things

Question 4

Hash Table

Answer 4

Hash function maps key to a ‘bucket’
That bucket is then searched for the keys value
Hash collitions, when more than one key maps to the same bucket
Inser, lookups and delete O(1)
Hash collitons O(n)

Question 5

Graphs

Answer 5

Social Network, Paths i a city
Vertices, Edges
bfs, dfs

Question 6

Binary Search

Answer 6

Starts with a sorted list
Start in the middle, split list and lookup into the part you have to
O(log(n))

Question 7

Search and Info retrieval

Answer 7

Forward inex of keywords of each doc
Generate inverted index that maps keywords to docs
Docs need to be ranked. ex. how often the word appears and where

Question 8

TF-IDF

Answer 8

Term frenquency just measures how often a word occurs in a doc.
Document Frequency how often a word occurs in an entire set of docs.
Relevancy of a word in a doc: Term Frequency / Document Frequency.