Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CSE 214 FINAL > FINAL > Flashcards

FINAL Flashcards

1
Q

What is overriding?

A

A subclasses method “hides” the parent’s method with the same name and parameters.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is overloading?

A

A class has two methods with same names, but different parameters.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is a final method?

A

A method that cannot be overridden.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a final class?

A

A class that cannot have a subclass.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a final value?

A

A value that can only be declared once.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a public method?

A

A method that is visible to all classes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is a private method?

A

A method that is not visible to any classes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is a package-private method?

A

A method that is only visible to classes in the same package.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

How do you declare a package-private method?

A

By not labeling it as any type. (public, private, protected)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is a protected method?

A

A method that is visible to the same package and any subclasses of the class it is in.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Why would you mark a method or variable as static?

A

It belongs to the class, not an instance of the class.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is the time complexity of searching a LinkedList for an element?

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the time complexity of searching for the first element of a LinkedList?

A

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the time complexity of retrieving an element from an index in a LinkedList?

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is the time complexity of adding/removing to the beginning of a LinkedList?

A

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is the time complexity of adding/removing to a random index of a LinkedList?

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is the time complexity of generic Stack methods?

A

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is the average time complexity of generic BST methods?

A

O(log(n))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is the worst case time complexity of generic BST methods, and why?

A

O(n), if all the elements are to one side of the root, it becomes a linked list.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Describe the process of inserting into a LinkedList for all scenarios.

A

Beginning - set element’s next equal to root and then root equal to element.

Middle - traverse through linked list until you reach right before the index, set element’s next equal to current node’s next, and then set current’s next equal to element.

End - traverse through the linked list until you reach the last element, then set the last element’s index equal to element

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Describe the process of removing an element from a LinkedList in all scenarios?

A

Find the element:
Beginning - set root equal to root’s next

Anywhere - maintain a pointer to the previous element and traverse to the element to be removed, set the previous element’s next to the current element’s next.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Describe the process of searching for an element in a BST.

A

Recursively, check if the element is equal to the root of the sub tree, if not, if the element is less than the root search the left subtree and if it is more search the right subtree.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Describe the process of inserting an element into a BST.

A

Recursively, search for where the element should be and once the node you are at is equal to null set it equal to element.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Describe the process of removing an element from a BST.

A

Find the element then apply one of the following cases:

Leaf node: set the parent’s pointer equal to null

One child: set the parent’s pointer to the child

Two children: replace the element by removing its successor(left-most element in its right subtree)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What are the two ways a stack can be implemented?

A

Linked List Backing

Array Backing(can overflow)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is the difference between a queue and a stack?

A

A queue has the same time complexities as a stack, but a queue is LIFO(last in first out).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is the time complexity of the insert and remove methods of a Heap?

A

O(log n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Describe the process of removing from a Heap.

A

Replace the root index with the last index of the heap. Then check if the value is out of order and swap with child node until sorted. (depends on if it is a min or a max heap)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What is a Heap backed by?

A

An array

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

What’s the formula for accessing the left child of an index in a Binary Heap?

A

(2 * index) + 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

What’s the formula for accessing the right child of an index in a Binary Heap?

A

(2 * index) + 2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

What’s the formula for accessing the parent of an index in a Binary Heap?

A

(index - 1) / 2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Describe the process of inserting into a Heap.

A

Add the element at the next empty index of the array, resizing the array if necessary, compare the value to its parents node and swap until sorted. (depends on if it is min or max heap)

34
Q

What are the rules for a RBT?

A

1)Node must be black
2)Red nodes can’t have red children
3)All leaf nodes should be an equal amount of black nodes away from the root

35
Q

What is the time complexity of RBT operations?

A

O(log n)

36
Q

Describe the process of inserting into a RBT.

A

Search for where to insert the element like a normal binary search tree, insert the node and make it red. Then rotate and recolor based on:

If the uncle node is black or doesn’t exist, rotate the tree to balance it and then recolor.

If the uncle node is red just recolor the tree.

37
Q

Describe the process of searching for an element in a RBT.

A

Same as a normal BST.

38
Q

What is the purpose of a RBT?

A

To ensure that the worst case scenario of a BST can’t happen. It self-balances itself to make sure the time complexity remains O(log n).

39
Q

What are the rules of a B-Tree of Min = x?

A

1) Every node has at most 2x children.
2) Every child has at least x children.
3) The root node has at least two children if it is not a leaf.
4) All leaves appear on the same level.
5) A non-leaf node with k children contain k-1 values.

40
Q

What is the time complexity of B-Tree operations?

A

O(log n)

41
Q

Describe the process of searching in a B-Tree.

A

Recursively, increment through the current node’s values, if the value is equal to the element, return an object containing the node and its index, otherwise once the value is greater than the element search the child at that index of the children list.

42
Q

Describe the process of inserting into a B-Tree.

A

Recursively, if the node you are at is full, split it, search for where an element should go and go to that index’s child value and search until you find a leaf node where it belongs and insert it into the right area.

43
Q

What is the purpose of a B-Tree.

A

It is a binary search tree that is self-balancing and can handle huge amounts of data by making the height of the tree smaller.

44
Q

What is hashing with chaining?

A

It is a way of handling collisions within a hash table where collisions are stored in a LinkedList.

45
Q

What is the time complexity of searching in a hash table that utilizes chaining?

A

⍬(1+the load factor) or O(1)

46
Q

What is the time complexity of inserting in a hash table that utilizes chaining?

A

O(1)

47
Q

What is the division method for hash code?

A

To find where to insert in the hash table we do the key mod the total number of spaces.

48
Q

What is the multiplication method for hash code?

A

To find where to insert in the hash table we multiply the key by some constant number between 0 and 1 and then take the result mod 1 to only get the decimals. Then we multiply it by the number of spaces.

49
Q

What is open addressing?

A

A form of a hash table where there are no linked lists and collisions are handled by moving to the next open address.

50
Q

Advantages of open addressing.

A

Saves memory because there are no pointers to save.
Searching is faster for small amounts of data.

51
Q

Disadvantages of open addressing.

A

Becomes very slow and memory heavy if load factor increases.

52
Q

Time complexities of open addressing?

A

O(1) but gets slower based on load factor.

53
Q

What is double hashing?

A

A way to improve open addressing by doing a different hash test on a key if it is colliding with something.

Example:
1) k % 8 = 5 (collision)
2) 4 - (k % 4) = 3 (no collision)

54
Q

What is an enum type in Java?

A

An enum allows variables to be a set of predefined constants, this means the variable must be one of the predefined values.

55
Q

Describe a left rotation of a tree node.

A

Save a reference to the nodes right child. Pass the right child’s left children to become the node’s right children. And change the reference to the parent. Link the right child to the old parent of the node. Set the right child’s left node to the node and set it as the parent of the node.

56
Q

Describe an equality check of two objects.

A

First check if it is the same memory address by doing (this == object). Then check to make sure it is not an instance of the class by doing !(object instanceof class) then cast the object to the class and check if every attribute is equal.

57
Q

Describe inorder traversal.

A

Recursively, check the left tree, then the current node, then the right tree.

58
Q

Describe preorder traversal.

A

Recursively, check the current node, then the left tree, then the right tree.

59
Q

Describe postorder traversal.

A

Recursively, check the left tree, then the right tree, then the current node.

60
Q

Describe the balanced paranthesis algorithm.

A

Create a stack and read through the input:

If it is an open parentheses or bracket, put it on the stack.

If it is a close parentheses, if the stack is empty raise an error, if not pop the stack, if the popped element doesn’t match the current character raise an error.

If the end of the input is reached and the stack is not empty, raise an error.

61
Q

Describe the infix to postfix algorithm.

A

Create a stack and read through the input:

Number - place it at the end of the output.

Right Parentheses - pop the stack and write the elements until you pop a left parenthesis.

Left Parentheses or Operator - Pop the stack and place it at the end of the output until an element of lower priority is popped then push the left parentheses or the operator onto the stack.

Done with input - pop the stack and place it onto the end of the output until the stack is empty.

62
Q

Describe the algorithm to evaluate a postfix expression.

A

Create a stack and read through the input:

Number - push it onto the stack

Operator - pop the stack twice and apply the operator to the two elements and then push the result onto the stack

Input finished - pop the stack for your answer

63
Q

What is the worst case amount of probes for a double hashed hash table?

A

1 / (1 - the load factor)

64
Q

What is a load factor for a hash table?

A

Amount of elements divided by the amount of spaces in the hash table.

65
Q

What’s the formula for accessing the left child of an index in a Ternary Heap?

A

(3 * index) + 1

66
Q

What’s the formula for accessing the right child of an index in a Ternary Heap?

A

(3 * index) + 3

67
Q

What’s the formula for accessing the parent of an index in a Ternary Heap?

A

(index - 1) / 3

68
Q

Describe the process of selection sort.

A

Divide the list into two parts, sorted and unsorted. Then iterate through the list finding the smallest element in the unsorted portion and then swap it with the leftmost element in the unsorted portion.

69
Q

Selection Sort

A
  • Splits your list into an unsorted and sorted portion
  • Find the smallest element of the unsorted portion and place it at the end of the sorted portion until sorted
  • Runs in quadratic time O(n^2)
  • Takes up little space because it is in-place
70
Q

Describe the process of Bubble Sort.

A

Iterates through the array swapping adjacent elements until fully sorted.

71
Q

Bubble Sort

A
  • Takes up little memory because it is an in-place sort
  • Has special cases where in the worst case the list is reversed.
    -Takes O(n^2) or quadratic time
  • Traverse through the array swapping out of order adjacent elements over and over until the list is sorted
72
Q

Describe the process of insertion sort.

A

Divides the list into a sorted portion and unsorted portion. Iterates through the unsorted portion inserting the first element into the sorted portion in its proper place.

73
Q

Insertion Sort

A
  • Takes up little memory because it is an in-place sort
    -Takes O(n^2) or quadratic time but on average faster than selection sort and bubble sort
  • Traverse through the array placing elements in their correct spot in the sorted portion of the array
74
Q

Describe Merge Sort top-down and bottom-up.

A

Top-down:
Recursively divide the list in half and then merge and sort the sorted portions

Bottom-up:
Split the list and then indices by powers of two.

75
Q

Merge Sort

A
  • splits a bigger list into smaller sublists and merges them to sort
  • example of dynamic programming
  • runs in log-linear time O(n log n)
  • takes up more memory because it creates copies of sublists
76
Q

Describe Quicksort.

A

Pick a pivot element the sort the list by dividing into numbers less than the pivot and more than the pivot, uses two pointers to sort around the pivot

77
Q

Quicksort

A
  • picks a pivot element and then sorts the list by less than that element and more than that element
  • example of dynamic programming
  • runs in log-linear time O(n log n)
  • takes up more memory because it creates a call stack but takes up O(log n) space as opposed to merge sort’s O(n)
    -worst case if you get really unlucky with the pivot elements over and over quick sort will take O(n^2) or quadratic time.
78
Q

Describe heap sort.

A

Turns the list into a max-heap. Swap the last value of the heap with the first value and then reheapify the list other than the first element. Makes the end of the list the sorted portion.

79
Q

Heap Sort

A
  • takes the largest element from a heap places it at the end of the list then reheapifies the other elements.
  • example of dynamic programming
  • runs in log-linear time O(n log n)
  • doesn’t take up a lot of memory because it can be done in-place.
80
Q

Describe evaluating infix expressions.

A

Iterate through input:

Number - put it on number stack

Operator(stack empty) - push it on operator stack

Operator - if the operator is lower precedence than the top of the stack then pop and do operation on top two in number stack until the operator is higher precedence than the top of the stack or the stack is empty

Left Parentheses - push onto operator stack

Right Parentheses - pop and compute operator stack until left parentheses is popped

Once input done - compute rest of stacks

81
Q

What is a non-branching node?

A

A node with at most one child in a tree.

CSE 214 FINAL (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions