Python basics
Python uses _____ to denote blocks of code
whitespace
Which sort function splits its input into buckets based on a pivot element?
Quicksort
What is the time complexity of merge sort (best, average, worst)
O(NlogN)
To use an interface, you use this keyword
implement
This feature lets you store any datatype in any datastructure in JCF
generics
reverse the following string
s = "hello world"
s[::-1]
What are the two cases in a recursive function
base case and recursive case
What is the time complexity of checking if an element exists in a set?
O(1)
To subclass a parent class, you use this keyword. It creates _____ relationship between the classes
extends, is_a
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
What is the output of the following snippet of code?
```
s = "CWSFAGPHRJOKCIKXS"
s[::1]
```
CSAPROCKS
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.
What is a hash collision
A hash collision occurs when 2 inputs are hashed to the same output by the hash function
What does UML stand for?
Unified Modelling Language
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.
What is the output of the following piece of code?
```
s = "Sri is the best SI"
s[4] = "h'
```
error, strings are immutable
Which sorting function has the same time complexity across all inputs?
Merge sort
What are two approaches to resolve a hash collision?
open addressing, chaining
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.
Time complexity of TreeSet/TreeMap for contains/get/add/remove
O(LogN)
Unlike Java, which is both compiled and interpreted, Python is only ___________
interpreted
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
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
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
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