CS | Priority

Question 1

What is the relationship between best/worst/expected case and big O/theta/omega?

algorithms big-O

Answer 1

Best/worst/expected case describe big O for particular inputs or scenarios. Big O/theta/omega describe the upper/lower/tight bounds for the runtime.

Cracking the Coding Interview 6E p.40

Question 2

When the number of elements gets halved each time, this indicates big O of what?

algorithms big-O

Answer 2

O(log N)

Cracking the Coding Interview 6E p.44

Question 3

When you have a recursive algorithm with multiple calls, what is the big O likely to be?

algorithms big-O

Answer 3

O(branches^depth). E.g. O(2^N).

Cracking the Coding Interview 6E p.45

Question 4

Big O describes the __ __ . Draw a graph to depict this for some of the common big O times.

algorithms big-O

Answer 4

Rate of increase. (See source material.)

Cracking the Coding Interview 6E p.41-42

Question 5

When do you add runtimes (simple phrase)? When do you multiply runtimes (simple phrase)?

algorithms big-O

Answer 5

Add: If your algorithm is in the form, “do this, then, when you’re all done, do that”. Multiply: If your algorithm is in the form, “do this for each time you do that”.

Cracking the Coding Interview 6E p.43

Question 6

Steps of the problem-solving flowchart.

Answer 6

(See source material.) Listen: write the unique information down. Example: Draw a specific, large enough, not special case example. Brute force. Optimize with BUD; unused info, manually on an example, solve it incorrectly, make time vs space tradeoff, precompute. Walk-through. Implement: modularized, error checks, classes, var names. Test: conceptual, weird code, hot spots, small test cases, special cases.

Cracking the Coding Interview 6E p.62

Question 7

What are 5 optimize and solve techniques?

Answer 7

BUD; DIY; simplify and generalize; base case and build; data structure brainstorm.

Cracking the Coding Interview 6E p. 67-72

Question 8

What is great way to figure out the runtime of a recursive algorithm?

Answer 8

Draw the recursive calls as a tree.

Cracking the Coding Interview 6E p. 132

Question 9

When you see an algorithm with multiple recursive calls, what is the likely runtime?

Cracking the Coding Interview 6E p. 53

Answer 9

exponential

Cracking the Coding Interview 6E p. 53

Question 10

What is the ordering property of a binary search tree?

Cracking the Coding Interview 6E p. 101

Answer 10

all left descendants <= n < all right descendants

Cracking the Coding Interview 6E p. 101

Question 11

Can a binary search tree have duplicates?

Cracking the Coding Interview 6E p. 101

Answer 11

Clarify with the interviewer.

Cracking the Coding Interview 6E p. 101

Question 12

Does balancing a tree mean that the left and right subtrees are the same size?

Cracking the Coding Interview 6E p. 101

Answer 12

No.

Cracking the Coding Interview 6E p. 101

Question 13

What is a complete binary tree?

Cracking the Coding Interview 6E p. 102

Answer 13

Every level of the tree is fully filled except perhaps the last one, which is filled left to right.

Cracking the Coding Interview 6E p. 102

Question 14

What is a full binary tree?

Cracking the Coding Interview 6E p. 102

Answer 14

Every node has either 0 or 2 children.

Cracking the Coding Interview 6E p. 102

Question 15

What is a perfect binary tree? Should you assume a binary tree is perfect?

Cracking the Coding Interview 6E p. 102

Answer 15

Both full and complete. No.

Cracking the Coding Interview 6E p. 102

Question 16

What is a min-heap?

Cracking the Coding Interview 6E p. 103

Answer 16

Complete binary tree where each node is smaller than its children.

Cracking the Coding Interview 6E p. 103

Question 17

Basic idea of insertion into a min heap. Time complexity?

Cracking the Coding Interview 6E p. 104

Answer 17

Bottom, rightmost; bubble up. O(log n).

Cracking the Coding Interview 6E p. 104

Question 18

Basic idea of extracting min element from a min-heap?

Cracking the Coding Interview 6E p. 104

Answer 18

Remove root; swap root with last element; bubble down.

Cracking the Coding Interview 6E p. 104

Question 19

Runtime of a prefix check in a trie?

Cracking the Coding Interview 6E p. 105

Answer 19

O(K) where K is the length of the string

Cracking the Coding Interview 6E p. 105

Question 20

If a problem involves a list of valid words, or searching on related prefixes repeatedly, use a ?

Cracking the Coding Interview 6E p. 105

Answer 20

Trie.

Cracking the Coding Interview 6E p. 105

Question 21

If you want to visit each node in a graph, what method is simplest?

Cracking the Coding Interview 6E p. 107

Answer 21

DFS.

Cracking the Coding Interview 6E p. 107

Question 22

If you want to find the shortest path in a graph, what method is preferred?

Cracking the Coding Interview 6E p. 107

Answer 22

BFS.

Cracking the Coding Interview 6E p. 107

Question 23

What is the preferred method to find the shortest path between a source and destination node?

Cracking the Coding Interview 6E p. 108

Answer 23

Bidirectional search.

Cracking the Coding Interview 6E p. 108

Question 24

How are stacks sometimes used in recursive algorithms?

Cracking the Coding Interview 6E p. 97

Answer 24

To push temporary data, then remove as you backtrack (e.g. if recursive check fails).

Cracking the Coding Interview 6E p. 97

Question 25

What part of a queue implementation is easy to mess up? ## Footnote Cracking the Coding Interview 6E p. 98

Answer 25

Updating the first and last nodes. ## Footnote Cracking the Coding Interview 6E p. 98

Question 26

What situations are queues used for? ## Footnote Cracking the Coding Interview 6E p. 98

Answer 26

BFS or cache. ## Footnote Cracking the Coding Interview 6E p. 98

Question 27

What is a denormalized database? ## Footnote Cracking the Coding Interview 6E p169

Answer 27

(See source material.) ## Footnote Cracking the Coding Interview 6E p169

Question 28

What are examples of problems heaps / priority queues can help solve?

Answer 28

scheduling periodic tasks and merging log files; top/bottom; best/worst; min/max; optimal; paths ## Footnote [Source](https://realpython.com/python-heapq-module/)

Question 29

In the context of OO design for a game piece, what is a lesson to keep in mind?

Answer 29

Discuss if a Piece class should be subclassed or keep state composed with it. ## Footnote Cracking the Coding Interview 6E Chapter 7 p325

Question 30

In the context of OO design for a game with a board, what is a lesson to keep in mind?

Answer 30

Discuss if Board and Game classes should be separate. ## Footnote Cracking the Coding Interview 6E Chapter 7 p325

Question 31

In the context of OO design for a game, what is a lesson to keep in mind about the score?

Answer 31

Discuss which class should keep the score. ## Footnote Cracking the Coding Interview 6E Chapter 7 p325

Question 32

In the context of OO design for a game, what is a lesson to keep in mind about how to treat the Game class?

Answer 32

Discuss if the game should be a singleton. ## Footnote Cracking the Coding Interview 6E Chapter 7 p325

Question 33

In the context of OO design for a game, what is a lesson about what concepts need objects?

Answer 33

Objects for abstract concepts like Hand in a card game. ## Footnote Cracking the Coding Interview 6E Chapter 7

Question 34

In the context of OO design for a game, what is a lesson about how to get user input?

Answer 34

Function to get user input. ## Footnote Cracking the Coding Interview 6E Chapter 7

Question 35

In the context of OO design for a game, what is a lesson about representing enumerations?

Answer 35

Enum class for any enumeration. ## Footnote Cracking the Coding Interview 6E Chapter 7

Question 36

In the context of OO design for a game, what is a lesson about collections of objects?

Answer 36

Are there any collections of objects that will be used as an exhaustible resource? E.g. deck of cards. If, so both the collection and the objects need to keep state about the objects' availability. E.g. deck tracks number of cards used, card tracks if available. ## Footnote Cracking the Coding Interview 6E Chapter 7

Question 37

In the context of OO design for a game, what is a lesson about abstraction for related objects?

Answer 37

When objects have different state/behaviors, as an optimization, consider abstraction to create a small hierarchy of objects. E.g. Card, BlackjackCard; Hand, BlackjackHand. Can represent complicated logic about specific types of cards, e.g. Ace, without creating objects for individual types of cards. ## Footnote Cracking the Coding Interview 6E Chapter 7

Question 38

In the context of OO design for a game, what is a lesson about types of abstraction for behaviors?

Answer 38

When using abstraction, consider abstract adjectives describing behaviors. E.g. Movable, Drawable. ## Footnote Cracking the Coding Interview 6E Chapter 7

Question 39

In the context of OO design for a game, what is a lesson about how to run the game?

Answer 39

For a game, conside an Automator class with high-level methods to run the game, e.g. dealInitial(), playAllHands(). https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2007.%20Object-Oriented%20Design/Q7_01_Deck_of_Cards/BlackJackGameAutomator.java ## Footnote Cracking the Coding Interview 6E Chapter 7

Question 40

In the context of OO design for a game, what is a lesson about how to set up the game initially?

Answer 40

Do high-level methods to initialize data structures. ## Footnote Cracking the Coding Interview 6E Chapter 7

Question 41

In the context of OO design for a game, what is a lesson about how to run a game with an exhaustible resource like cards?

Answer 41

For a game with an exhaustible resource like cards, to run the game, can use functions that return booleans: false is returned when the cards are exhausted. ## Footnote Cracking the Coding Interview 6E Chapter 7

Question 42

8 tips for handling system design questions.

Answer 42

(See source material.) ## Footnote Cracking the Coding Interview 6E Chapter 9 p137

Question 43

5 steps for system design questions.

Answer 43

(See source material.) ## Footnote Cracking the Coding Interview 6E Chapter 9 p138

Question 44

4 steps for scalability in system design questions.

Answer 44

(See source material.) ## Footnote Cracking the Coding Interview 6E Chapter 9 p139

Question 45

Define horizontal and vertical scaling.

Answer 45

## Footnote Cracking the Coding Interview 6E Chapter 9 p140

Question 46

3 ways of doing data partitioning.

Answer 46

(See source material.) ## Footnote Cracking the Coding Interview 6E Chapter 9 p141

Question 47

3 important networking metrics.

Answer 47

bandwidth, throughput, latency ## Footnote Cracking the Coding Interview 6E Chapter 9 p141

Question 48

4 main considerations.

Answer 48

failures, availability and reliability, read-heavy vs. write-heavy, security ## Footnote Cracking the Coding Interview 6E Chapter 9 p142

Question 49

Find kth largest element: What is the runtime for a heap-based algorithm? For a quick-select-based algorithm? ## Footnote LC/NC https://www.youtube.com/watch?v=XEmy13g1Qxc&ab_channel=NeetCode

Answer 49

O(N+klogN). O(N) in average case (O(N^2) in worst case).

Question 50

Powers of 2 up through 2^9. ## Footnote Cracking the Coding Interview 6E p.61

Answer 50

4=16, 5=32, 6=64, 7=128, 8=256, 9=512

Question 51

What are the exact values / approximate values / approximation of those bytes to MB, GB, etc.? 2¹⁰ 2²⁰ 2³⁰ 2⁴⁰ ## Footnote Cracking the Coding Interview 6E p.61

Answer 51

"2¹⁰ = 1024 ≈ 1 thousand ≈ 1K 2²⁰ = 1,048,576 ≈ 1 million ≈ 1MB 2³⁰ = 1,073,741,824 ≈ 1 billion ≈ 1GB 2⁴⁰ = 1,099,511,627,776 ≈ 1 trillion ≈ 1TB"

Question 52

What are the exact values / approximate values / approximation of those bytes to MB, GB, etc.? 2^16 2^32 ## Footnote Cracking the Coding Interview 6E p.61

Answer 52

"2¹⁶ = 65,536 ≈ 64K 2³² = 4,294,967,296 ≈ 4GB"