(This quiz does not cover object-oriented programming or sorting algorithms. For a Python quiz, see this.)
1. What is a sink in a directed graph?
__________________
Answer: A vertex with no route/edge to another vertex; a terminating vertex. Source: Elements of Programming Interviews in Python
2. What is the difference between a vertex and a node?
__________________
Answer: There is no difference. Source: StackOverflow.
3. Space complexity of a program, or its memory usage requirements, are often irrelevant compared to the computational complexity of the solution.
True
False
Answer: False. Source page 238 of The Mythical Man-Month.
4. What usually happens when a data set is too large for memory but the data set needs to be ordered?
_____________________
Answer: Data is separated into subfiles that are small enough to be read into memory two at a time. These subfiles are read into memory, sorted, and persisted into files again. Source: Page 149 of Programming Interviews Exposed: Secrets to Landing Your Next Job.
5. How is an anchor case different from a base case in recursion?
a. An anchor case ensures the recursion doesn't go on forever, and the base case handles the iterations (the main benefit of recursion).
b. The case ensures the recursion doesn't go on forever, and the anchor case handles the iterations (the main benefit of recursion).
c. There is no such thing as an "anchor" case in recursion.
d. There is no such thing as a "base" case in recursion.
e. None of the above as they are synonyms.
Answer: E. Taken from https://www.datacamp.com/community/tutorials/understanding-recursive-functions-python
The base case allows for termination (according to IBM's website).
We find the term "anchor case" to be used less frequently than the term "base case" in the context of recursion. Sometimes the term is called a "termination condition" or a "terminating condition".
6. What is the computational complexity of an operation going through a list of m lists with n items?
a. O(m)
b. O(n)
c. O (m log n)
d. O(n*m) (a quadratic)
Answer: D. Source: Page 40 of Cracking the Coding Interview.
7. What is the space complexity of an algorithm with an operation that exists simultaneously on the call stack for every list of m lists and every n item of those lists when the lists have a length of n?
a. O(1)
b. O(N)
c. O(m log n)
d. O(n log m)
e. O(n*m)
Answer: E. Source: Pages 40 and 41 of Cracking the Coding Interview. Recursion can involve simultaneous calls.
8. What is the space complexity of an operation going through a list of m lists where each list has n items with no simultaneous calls to the stack? The operation happens one at a time and does not simultaneously keep each individual operation on the stack.
a. O(1)
b. O(N)
c. O(m log n)
d. O(n log m)
e. O(n*m)
Answer: A. Source: Page 41 of Cracking the Coding Interview. Avoiding recursion can involve non-simultaneous call stack usage.
9. What is the significance of 10**9 + 7?
a. The highest integer value for a float.
b. The way to calculate pi to 9 decimal places.
c. 1000000007, a very large prime number used regularly in computer programming.
d. The largest known prime number.
e. None of the above
Answer: C. Source https://www.geeksforgeeks.org/modulo-1097-1000000007/
10. Can a Boolean conditional statement be considered ternary operator if there is one expression for True and one expression for False?
Yes.
No.
Answer: Yes. The conditional statement evaluating to True/False is the first expression. The action for True and the action for False are the second and third statements respectively. The word "ternary" means pertaining to three.
For the source of this answer see this: https://www.geeksforgeeks.org/conditional-or-ternary-operator-in-c-c/
11. To do CI, you must have automated testing.
True
False
Answer: False
Sources and their relevant excerpts:
"… automated testing is not strictly part of CI it is typically implied." taken from CloudBees' website.
"Simply put, CI is the process of integrating code into a mainline code base…CD is more complicated. CD is about the processes that have to happen after code is integrated for app changes to be delivered to users. Those processes involving testing, staging and deploying code." Taken from
https://devops.com/continuous-integration-vs-continuous-delivery-theres-important-difference/
12. What could be the best space complexity of a given "for" loop that iterates through n items calling a function each time?
a. O(1)
b. O(n)
c. O(nlog(n))
d. None of the above.
Answer: A. Source page 41 of Cracking the Coding Interview. To paraphrase, the calls do not simultaneously exist on the stack. Avoiding recursion can involve non-simultaneous call stack usage.
13. What is a mutex?
a. A binary semaphore
b. A system-wide lock
c. A mutually exclusive lock
d. A concept for thread synchronization in multi-threading programming
e. All of the above
f. None of the above
Answer: E.
Source: These three links help explain why:
StackOverlfow.com. (for A and B)
Sciencedirect.com. (For C)
Geeksforgeeks.org. (For D)
14. Which of the following statements is true for programs that solve problems with subproblems?
a. Dynamic programming excels when you do not need to compute every sub-problem and memoization is preferred when every sub-problem must be solved.
b. Memoization excels when you do not need to compute every sub-problem and dynamic programming is preferred when every sub-problem must be solved.
c. Dynamic programming is optimal compared to memoization.
d. Memoization is optimal compared to dynamic programming.
e. None of the above.
Answer: B. Source: https://stackoverflow.com/questions/6184869/what-is-the-difference-between-memoization-and-dynamic-programming
Explanation:
You can use memoization for only the subproblems you definitely need.
Dynamic programming can involve building up a table of subproblems. This can involve working backward from a solution where an algorithm is designed to compute different combinations of sub-problems; this is considered a bottom-up approach and it is ideal when every sub-problem must be evaluated any way (for business reasons).
The top-down approach of memoization involves keeping the call stack open and iterating through the subproblems to find a solution; the business requirement of avoiding certain sub-solutions could make the top-down approach of memoization ideal.
15. What is the computational complexity of looking for a node in a heap?
a. O(1)
b. O(log n)
c. O(n log n)
d. O(n)
e. None of the above.
Answer: D. Source page 80 of Programming Interviews Exposed by Mongan, Kindler and Giguere. See also stackoverflow.com.
16. What book says that "Representation is the essence of programming."?
a. The Art of Programming
b. The Mythical Man-Month
c. The Cathedral and the Bazaar
d. The DevOps Handbook
e. Refactoring by Beck and Fowler
f. Design Patterns: Elements of Reusable Object-Oriented Software
g. None of the above.
Answer: B. Page 229 of the 20th Anniversary Edition of The Mythical Man-Month.
17. What are the differences between "string interpolation", "variable interpolation", "variable substitution", and "variable expansion"?
____________________
Answer: There are no differences. A constant expression in computer programming is a placeholder of a variable. The terms to describe this practice are "string interpolation", "variable interpolation", "variable substitution", and "variable expansion"?