Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?


Which one best describes the time complexity of the following code?

```C
int factorial(int n) {
  if (n < 0) {
    return -1;
  } else if (n == 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}
```


What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?


What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?


Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?


What is the running time of the following code?

```C
int sqrt(int n) {
  for (int guess = 1; guess * guess <= n; guess++) {
    if (guess * guess == n) {
      return guess;
    }
  }
  return -1;
}
```


What is the **space** complexity of the following code?

```C
int sum(int n) {
  if (n <= 0) {
    return 0;
  }
  return n + sum(n - 1);
}
```


Which of the following shows the order of node visit in a **Breadth-first Search**?

![](https://algomonster.s3.us-east-2.amazonaws.com/bfs_intro.png)


Which algorithm is best for finding the shortest distance between two points in an
unweighted graph?


What data structure does Breadth-first search typically uses to store intermediate states?


Which type of traversal does breadth first search do?


Which algorithm should you use to find a node in a narrow but deep tree when either algorithm works?


Which algorithm should you use to find a node that is close to the root of the tree?


Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
`___` in the given code snippet.


What is the best way of checking if an element exists in a sorted array once in terms of
time complexity? Select the best that applies.


What is the best way of checking if an element exists in an unsorted array once in terms of
time complexity? Select the best that applies.


A person thinks of a number between 1 and 1000. You may ask any number questions to them,
provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to
know the number that the person is thinking?


How many ways can you arrange the three letters A, B and C?


What's the output of running the following function using input `56`?


Which of the following is a good use case for backtracking?


Which of the following problems can be solved with backtracking (select multiple)


Which data structure is used in a depth first search?


Which data structure is used to implement recursion?


What are the most two important steps in writing a depth first search function? (Select 2)


The three-steps of Depth First Search are:

1. Identify states;
2. Draw the state-space tree;
3. DFS on the state-space tree.


Which of these pictures shows the visit order of a depth-first search?
![](https://algomonster.s3.us-east-2.amazonaws.com/bfs_intro.png)


Depth first search is equivalent to which of the tree traversal order?


How many times is a tree node visited in a depth first search?


What's the output of running the following function using the following tree as input?
![](https://algomonster.s3.us-east-2.amazonaws.com/serializing_tree.png)


Which of the following uses divide and conquer strategy?


How does quick sort divide the problem into subproblems?


How does merge sort divide the problem into subproblems?


What are the two properties the problem needs to have for dynamic programming to
be applicable? (Select 2)


What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?


Consider the classic dynamic programming of fibonacci numbers, what is the
recurrence relation?


Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements
of the subsequence are sorted in increasing order.

For example, the length of LIS for `[50, 3, 10, 7, 40, 80]` is `4` and LIS is
`[3, 7, 40, 80]`.

What is the recurrence relation?


What's the relationship between a tree and a graph?


Which of these properties could exist for a graph but not a tree?


Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?


Depth first search can be used to find whether two components in a graph are connected.


Breadth first search can be used to find the shortest path between two nodes in a directed graph.


Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?


Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?


Is the following code DFS or BFS?

```C
void search(Node root) {
  if (!root) return;
  visit(root);
  root.visited = true;
  for (Node node in root.adjacent) {
    if (!node.visited) {
      search(node);
    }
  }
}
```


Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?


How would you design a stack which has a function `min` that returns the minimum element in the stack, in addition to `push` and `pop`? All `push`, `pop`, `min` should have running time `O(1)`.


Which of the following is a min heap? ![](https://algomonster.s3.us-east-2.amazonaws.com/heap_intro.png)


What's the output of running the following function using input `[30, 20, 10, 100, 33, 12]`?


Which of the following array represent a max heap?


In a binary min heap, the minimum element can be found in:


In a binary min heap, the maximum element can be found in:


Which data structure is used to implement priority queue?


Which technique can we use to find the middle of a linked list?


Which of the following is the prefix sum of array `[1, 2, 3, 4, 5]`?


Which two pointer technique does Quick Sort use?


Which two pointer techniques do you use to check if a string is a palindrome?


Evaluator

Q. 1 of 0