The Worst Topics

Question 1

What order does pre order tree traversal go in?

Answer 1

N L R

Question 2

What order does in order tree traversal go in?

Answer 2

L N R

Question 3

What order does post order tree traversal go in?

Answer 3

L R N

Question 4

Name this notation and the traversal required to get this

2 + 3

Answer 4

Infix

In order traversal

Question 5

Name this notation and the traversal required to get this

2 3 +

Answer 5

Reverse Polish

Post order

Question 6

Name this notation and the traversal required to get this

+ 2 3

Answer 6

Polish

Pre order

Question 7

What is open addressing?

Answer 7

Use hashing to find a candidate bucket, have a strategy to remap colliding keys and find them afterwards

Question 8

What is secondary hashing?

Answer 8

Use a second hash function to pick the bucket, if there is still a collision, then revert to linear probing

Question 9

What is linear probing?

Answer 9

Walking along the bucket until you find a free space to place the key/value pair

Question 10

What is separate chaining?

Answer 10

The bucket is a list of key/value pairs. We hash to the bucket and then add it to the list at the position.

Question 11

What is extendable hashing?

Answer 11

Process of splitting the bucket, consuming another bit of the hash code, and placing values in the newly split parts of the bucket

Question 12

What features do we want from a hash function?

Answer 12

• Two keys that are close together, map far apart
• Low chance of two keys mapping to the same value
• Spread of the keys across the hash bucket

Question 13

Describe the parsing pipeline

Answer 13

Source Text
Tokeniser
Parser
Parse tree

Question 14

Describe the process of tokenising using a FSA

Answer 14

Tokenise the input source, generating a steam of tokens for the grammar, some tokens can carry values with them
FSA keeps track of the characters used, attaches them to the recognised symbol

Question 15

Describe the process of recursive descent parsing

Answer 15

Treats each production as a small recogniser that looks at the token stream and tries to recognise itself
Try it and see it method

Question 16

What is the job of terminal recognisers in recursive descent parsing?

Answer 16

Check if the current token in the token stream is the expected one

Question 17

What is the job of non terminal recognisers in recursive descent parsing?

Answer 17

Checks compound patterns, repetitions etc and saves and rewinds the token stream

Question 18

What are the four functions needed for recursive descent parsing?

Answer 18

nextToken()
advanceTokenStream()
getTokenStreamPosition()
setTokenStreamPosition()

Question 19

Describe the process of table driven parsing

Answer 19

Start with the tokens, see which productions could have given rise to them
Build the tree as a constraints problem

Question 20

What are the advantages of table driven parsing?

Answer 20

• Smaller and faster

- No need for back tracking

Question 21

What are the disadvantages of table driven parsing?

Answer 21

• Less clear

- Can be tripped up easily

Question 22

Describe the divide step in a divide and conquer algorithm

Answer 22

Take a problem S and split it into two smaller problems S1 and S2

Question 23

Describe the recurse step in a divide and conquer algorithm

Answer 23

Recursively solve S1 and S2, either directly (the base case of the recursion) or by further division

Question 24

Describe the conquer step in a divide and conquer algorithm

Answer 24

Combine the solutions to S1 and S2 into a solution to S

Question 25

Define polymorphism

Answer 25

Some values and variables may have more than one type

Question 26

What are the two categories of polymorphism?

Answer 26

Ad hoc and Universal

Question 27

What are the two types of Ad hoc polymorphism?

Answer 27

Overloading | Coercion

Question 28

What are the two types of Universal polymorphism?

Answer 28

Inclusion | Parametric

Question 29

What are the advantages of polymorphism

Answer 29

- Allows methods to perform similar tasks accessed under a common name - Allows you to define multiple constructors - Less repetition of code

Question 30

Describe overloading polymorphism

Answer 30

Same function name is used to denote different types, operators can be applied to operands of different types e.g. +

Question 31

Describe coercion polymorphism

Answer 31

Instance of one type forced to be interpreted as another e.g. if * could only be applied to real numbers, int types converted

Question 32

Describe inclusion polymorphism

Answer 32

Instance of a subtype can be manipulated as if it was an instance of the supertype

Question 33

Describe parametric polymorphism

Answer 33

Code features an implicit or explicit type parameter, coed can be used for value of any suitable type, does not depend on value at run time

Question 34

Describe the collections framework

Answer 34

Unified architecture for representing and manipulating collections Contains algorithms, interfaces and implementation

Question 35

Benefits of the collections framework

Answer 35

- Reduced programming effort - Reliable and optimised - Standard interfaces, so less to learn - Implementation of each interface interchangable

Question 36

What are the three design goals of the collection framework

Answer 36

1. Produce a reasonably small API (size and conceptual weight) 2. Small number of core interfaces 3. Only have methods if they are truly fundamental or there is a compelling performance reason

Question 37

Describe a factory

Answer 37

A factory is an OO design pattern that deals with creating objects without specifying the exact dates of object that is to be created

Question 38

What are the benefits of using factories?

Answer 38

1. Allows for a lot more long term flexibility, able to easily change application 2. Makes your code more testable, can mock interfaces and decoupled design 3. Makes rest of code easier to write, modify and maintain

Question 39

What is a parse tree?

Answer 39

Illustrated, pictorial version of the grammatical structure of the sentence. Diagrammed form of a sentence, and gives an concrete idea of the syntax of that particular sentence