Arrays, Linked Lists, & Strings
Two array edge cases
What are ...
(1) empty array
(2) array with 1 or 2 elements
(3) array with repeated elements
(4) array with elements that are not allowed
?
The three O(nlogn) sorting algorithms
What are Merge Sort, Heap Sort, and Quick Sort?
LIFO data structure
A tree
What is an acyclic, connected graph?
Two Reasons why Inheritance is useful
v(1) enables you to define shared properties and actions once
(2) derived classes can preform same actions as base classes without having to redefine the actions
(3) Actions can be redefined if desired (method overriding)
(4) Code readability
The two pointers technique
What is ...
Given a sorted array A (sorted in ascending order), having N integers, find if there exists any pair of elements (A[i], A[j]) such that their sum is equal to X.
We take two pointers, one representing the first element and other representing the last element of the array, and then we add the values kept at both the pointers. If their sum is smaller than X then we shift the left pointer to right or if their sum is greater than X then we shift the right pointer to left, in order to get closer to the sum. We keep moving the pointers until we get the sum as X.
?
A sorting algorithm that uses O(n) space
What is Mergesort?
The time complexity for inserting into a binary heap
What is O(log n)?
A binary search tree
What is a node-based binary tree data structure which has the following properties:
(1) The left subtree of a node contains only nodes with keys lesser than the node’s key.
(2) The right subtree of a node contains only nodes with keys greater than the node’s key.
(3) The left and right subtree each must also be a binary search tree.
Output of following program:
class Base {
void display() {System.out.print("Base ");}
}
class Child extends Base {
void display() {System.out.print("Child ");}
}
Base b = new Base();
Child c = new Child();
Base ref = b;
ref.display();
ref = c;
ref.display();
What is "Base Child"?
The fast i slow j technique
What is an algorithm with two pointers, slow and fast, that both start from the head of linked list. We move slow one node at a time and fast two nodes at a time. If there is a loop, then they will definitely meet?
A search algorithm you would use on a tree
What is breadth first search or depth first search?
The method of determining whether or not a tree is a complete tree
What is ...
(1) Calculate the number of nodes (count) in the binary tree.
(2) Start recursion of the binary tree from the root node of the binary tree with index (i) being set as 0 and the number of nodes in the binary (count).
(3) If the current node under examination is NULL, then the tree is a complete binary tree. Return true.
(4) If index (i) of the current node is greater than or equal to the number of nodes in the binary tree (count) i.e. (i>= count), then the tree is not a complete binary. Return false.
(5) Recursively check the left and right sub-trees of the binary tree for same condition. For the left sub-tree use the index as (2*i + 1) while for the right sub-tree use the index as (2*i + 2).
?
Tries
What is a type of tree in which each node can have any number of children (not strictly 2) and is usually used to store vocabulary sets of words?
The two ways to program with Dynamic Programming
What is top down and bottom up?
The sliding window approach
What is ...
Let k be the size of window size. Compute the sum of first k elements out of n terms using a linear loop and store the sum in a variable. Go linearly over the array till it reaches the end and simultaneously keep track of maximum sum.To get the current sum of block of k elements just subtract the first element from the previous block and add the last element of the current block.
?
If m is the length of the string and n is the length of the substring, the worst and best case complexity of searching for the substring within the string.
What is O(mn) for worst case and O(m+n) for best case
The difference between a min heap and max heap
Min Heap: The value of the node must be less than or equal to the values of its children.
Max Heap: The value of the node must be greater than or equal to the values of its children.
The difference between breadth first search and depth first search
What is ...
BFS: We start at a node in a graph, and explore each neighbor before going on to any of their children
DFS: We start at a node in a graph, and fully explore a branch before moving on to another branch. Much easier to implement recursively
?
The Fibonachi Problem using Dynamic Programming
What is saving computed values in an array and when we want to access previous Fibonacci numbers, then access the array (which takes O(1) time) instead of recomputing the entire sequence each time?
The most efficient solution to the valid parenthesis problem
What is ...
(1) Declare a character stack
(2) Traverse string. If the current character is a starting bracket then push it to the stack. If the current character is a closing bracket then pop from the stack and check if the popped character is the matching open parenthesis. If not, return false
(3) After complete traversal, if there is a starting bracket left in the stack then it is not balanced.
?
The Binary Search Algorithm
What is an efficient O(logn) algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.
# to heapify a subtree with root
# at given index
def MaxHeapify(arr, i, n):
l = 2 * i + 1
r = 2 * i + 2
largest = i
if l < n and arr[l] > arr[i]:
largest = l
if r < n and arr[r] > arr[largest]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
MaxHeapify(arr, largest, n)
A method of determining whether or not a tree is complete (give run and space time).
A complete binary tree is defined as a binary tree in which every level, except possibly the deepest, is completely filled. At deepest level, all nodes must be as far left as possible.
What usually happens when a class tries to extend two or more classes
the compiler gets confused, and you get an error at compile time. You won’t even be able to run your code.