Brainscape's Knowledge GenomeTM

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


See full index

Fundamentals > CS | Priority > Flashcards

CS | Priority Flashcards

1
Q

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

algorithms big-O

A

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

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

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

algorithms big-O

A

O(log N)

Cracking the Coding Interview 6E p.44

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

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

algorithms big-O

A

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

Cracking the Coding Interview 6E p.45

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

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

algorithms big-O

A

Rate of increase. (See source material.)

Cracking the Coding Interview 6E p.41-42

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

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

algorithms big-O

A

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

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

Steps of the problem-solving flowchart.

A

(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

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

What are 5 optimize and solve techniques?

A

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

Cracking the Coding Interview 6E p. 67-72

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

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

A

Draw the recursive calls as a tree.

Cracking the Coding Interview 6E p. 132

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

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

Cracking the Coding Interview 6E p. 53

A

exponential

Cracking the Coding Interview 6E p. 53

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

What is the ordering property of a binary search tree?

Cracking the Coding Interview 6E p. 101

A

all left descendants <= n < all right descendants

Cracking the Coding Interview 6E p. 101

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

Can a binary search tree have duplicates?

Cracking the Coding Interview 6E p. 101

A

Clarify with the interviewer.

Cracking the Coding Interview 6E p. 101

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

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

Cracking the Coding Interview 6E p. 101

A

No.

Cracking the Coding Interview 6E p. 101

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

What is a complete binary tree?

Cracking the Coding Interview 6E p. 102

A

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

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

What is a full binary tree?

Cracking the Coding Interview 6E p. 102

A

Every node has either 0 or 2 children.

Cracking the Coding Interview 6E p. 102

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

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

Cracking the Coding Interview 6E p. 102

A

Both full and complete. No.

Cracking the Coding Interview 6E p. 102

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

What is a min-heap?

Cracking the Coding Interview 6E p. 103

A

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

Cracking the Coding Interview 6E p. 103

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

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

Cracking the Coding Interview 6E p. 104

A

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

Cracking the Coding Interview 6E p. 104

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

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

Cracking the Coding Interview 6E p. 104

A

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

Cracking the Coding Interview 6E p. 104

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

Runtime of a prefix check in a trie?

Cracking the Coding Interview 6E p. 105

A

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

Cracking the Coding Interview 6E p. 105

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

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

Cracking the Coding Interview 6E p. 105

A

Trie.

Cracking the Coding Interview 6E p. 105

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

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

Cracking the Coding Interview 6E p. 107

A

DFS.

Cracking the Coding Interview 6E p. 107

22
Q

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

Cracking the Coding Interview 6E p. 107

A

BFS.

Cracking the Coding Interview 6E p. 107

23
Q

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

Cracking the Coding Interview 6E p. 108

A

Bidirectional search.

Cracking the Coding Interview 6E p. 108

24
Q

How are stacks sometimes used in recursive algorithms?

Cracking the Coding Interview 6E p. 97

A

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

Cracking the Coding Interview 6E p. 97

25
Q

What part of a queue implementation is easy to mess up?

Cracking the Coding Interview 6E p. 98

A

Updating the first and last nodes.

Cracking the Coding Interview 6E p. 98

26
Q

What situations are queues used for?

Cracking the Coding Interview 6E p. 98

A

BFS or cache.

Cracking the Coding Interview 6E p. 98

27
Q

What is a denormalized database?

Cracking the Coding Interview 6E p169

A

(See source material.)

Cracking the Coding Interview 6E p169

28
Q

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

A

scheduling periodic tasks and merging log files; top/bottom; best/worst; min/max; optimal; paths

Source

29
Q

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

A

Discuss if a Piece class should be subclassed or keep state composed with it.

Cracking the Coding Interview 6E Chapter 7 p325

30
Q

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

A

Discuss if Board and Game classes should be separate.

Cracking the Coding Interview 6E Chapter 7 p325

31
Q

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

A

Discuss which class should keep the score.

Cracking the Coding Interview 6E Chapter 7 p325

32
Q

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

A

Discuss if the game should be a singleton.

Cracking the Coding Interview 6E Chapter 7 p325

33
Q

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

A

Objects for abstract concepts like Hand in a card game.

Cracking the Coding Interview 6E Chapter 7

34
Q

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

A

Function to get user input.

Cracking the Coding Interview 6E Chapter 7

35
Q

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

A

Enum class for any enumeration.

Cracking the Coding Interview 6E Chapter 7

36
Q

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

A

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.

Cracking the Coding Interview 6E Chapter 7

37
Q

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

A

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.

Cracking the Coding Interview 6E Chapter 7

38
Q

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

A

When using abstraction, consider abstract adjectives describing behaviors. E.g. Movable, Drawable.

Cracking the Coding Interview 6E Chapter 7

39
Q

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

A

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

Cracking the Coding Interview 6E Chapter 7

40
Q

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

A

Do high-level methods to initialize data structures.

Cracking the Coding Interview 6E Chapter 7

41
Q

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?

A

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.

Cracking the Coding Interview 6E Chapter 7

42
Q

8 tips for handling system design questions.

A

(See source material.)

Cracking the Coding Interview 6E Chapter 9 p137

43
Q

5 steps for system design questions.

A

(See source material.)

Cracking the Coding Interview 6E Chapter 9 p138

44
Q

4 steps for scalability in system design questions.

A

(See source material.)

Cracking the Coding Interview 6E Chapter 9 p139

45
Q

Define horizontal and vertical scaling.

A

Cracking the Coding Interview 6E Chapter 9 p140

46
Q

3 ways of doing data partitioning.

A

(See source material.)

Cracking the Coding Interview 6E Chapter 9 p141

47
Q

3 important networking metrics.

A

bandwidth, throughput, latency

Cracking the Coding Interview 6E Chapter 9 p141

48
Q

4 main considerations.

A

failures, availability and reliability, read-heavy vs. write-heavy, security

Cracking the Coding Interview 6E Chapter 9 p142

49
Q

Find kth largest element: What is the runtime for a heap-based algorithm? For a quick-select-based algorithm?

LC/NC https://www.youtube.com/watch?v=XEmy13g1Qxc&ab_channel=NeetCode

A

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

50
Q

Powers of 2 up through 2^9.

Cracking the Coding Interview 6E p.61

A

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

51
Q

What are the exact values / approximate values / approximation of those bytes to MB, GB, etc.? 2¹⁰ 2²⁰ 2³⁰ 2⁴⁰

Cracking the Coding Interview 6E p.61

A

“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”

52
Q

What are the exact values / approximate values / approximation of those bytes to MB, GB, etc.? 2^16 2^32

Cracking the Coding Interview 6E p.61

A

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

Fundamentals (9 decks)

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