Exam Review - Part 1

Python basics

100

Python uses _____ to denote blocks of code

whitespace

200

reverse the following string

s = "hello world"

s[::-1]

300

What is the output of the following snippet of code?

```

s = "CWSFAGPHRJOKCIKXS"

s[::1]

```

CSAPROCKS

400

What is the output of the following piece of code?

```

s = "Sri is the best SI"

s[4] = "h'

```

error, strings are immutable

500

Unlike Java, which is both compiled and interpreted, Python is only ___________

interpreted

Recursion/Sorting

100

Which sort function splits its input into buckets based on a pivot element?

Quicksort

200

What are the two cases in a recursive function

base case and recursive case

300

What does it mean for a function to be tail recursive?

Tail recursion means that the last line is the recursive call. No operations are performed on the output of the recursive call.

400

Which sorting function has the same time complexity across all inputs?

Merge sort

500

Show the substitution trace of the following code:

def fib(n):
      if 0 <= n <= 1:
            return 1
      elif n > 1:
            return fib(n-2) + fib(n-1)
print(fib(3))

fib(3) = fib(1) + fib(2)
         = 1 + fib(2)
         = 1 + ( fib(1) + fib(0) )
         = 1 + ( 1 + fib(0) )
         = 1 + ( 1 + 1 )
         = 1 + 2
         = 3

Time Complexity/Hashing

100

What is the time complexity of merge sort (best, average, worst)

O(NlogN)

200

What is the time complexity of checking if an element exists in a set?

O(1)

300

What is a hash collision

A hash collision occurs when 2 inputs are hashed to the same output by the hash function

400

What are two approaches to resolve a hash collision?

open addressing, chaining

500

Explain Binary search, its preconditions and its time complexity

Time complexity if O(Log n). Binary search works only on sorted data. It works by comparing the target against the middle value, and throwing away half the data, and repeating until the position of the target is found

Java Basics

100

To use an interface, you use this keyword

implement

200

To subclass a parent class, you use this keyword. It creates _____ relationship between the classes

extends, is_a

300

What does UML stand for?

Unified Modelling Language

400

Give an example of an annotation in Java and when/where you'd use it

Override - to override parent class function  - more specifically toString, equals, hashcode etc.

500

Make a UML for a bottle class extending a container superclass, that (bottle) inherits from a action interface.

Draw a UML with meaningful functions/attributes

Java Collections Framework

100

This feature lets you store any datatype in any datastructure in JCF

generics

200

This data structure allows for unordered storage of key value pairs and O(1) access times -

Bonus points if you can name an ordered storage of key-value pairs and O(1) access times

HashMap

TreeMap

300

What is the rule that enforces structure in a binary search tree? In other words, how is a BST different from a regular Binary Tree

Binary Search trees require that the left value be less than root and right be greater than root.

400

Time complexity of TreeSet/TreeMap for contains/get/add/remove

O(LogN)

500

What is the difference between comparable and comparator?

Both are interfaces. Comparable has function compareTo. implements natural ordering. Takes another object of same class as argument. Implemented in same class. Comparator has function compare. overrides natural ordering. Takes two instances of same class as argument. Implemented in a separate class