CS | Priority Flashcards
What is the relationship between best/worst/expected case and big O/theta/omega?
algorithms big-O
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
When the number of elements gets halved each time, this indicates big O of what?
algorithms big-O
O(log N)
Cracking the Coding Interview 6E p.44
When you have a recursive algorithm with multiple calls, what is the big O likely to be?
algorithms big-O
O(branches^depth). E.g. O(2^N).
Cracking the Coding Interview 6E p.45
Big O describes the __ __ . Draw a graph to depict this for some of the common big O times.
algorithms big-O
Rate of increase. (See source material.)
Cracking the Coding Interview 6E p.41-42
When do you add runtimes (simple phrase)? When do you multiply runtimes (simple phrase)?
algorithms big-O
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
Steps of the problem-solving flowchart.
(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
What are 5 optimize and solve techniques?
BUD; DIY; simplify and generalize; base case and build; data structure brainstorm.
Cracking the Coding Interview 6E p. 67-72
What is great way to figure out the runtime of a recursive algorithm?
Draw the recursive calls as a tree.
Cracking the Coding Interview 6E p. 132
When you see an algorithm with multiple recursive calls, what is the likely runtime?
Cracking the Coding Interview 6E p. 53
exponential
Cracking the Coding Interview 6E p. 53
What is the ordering property of a binary search tree?
Cracking the Coding Interview 6E p. 101
all left descendants <= n < all right descendants
Cracking the Coding Interview 6E p. 101
Can a binary search tree have duplicates?
Cracking the Coding Interview 6E p. 101
Clarify with the interviewer.
Cracking the Coding Interview 6E p. 101
Does balancing a tree mean that the left and right subtrees are the same size?
Cracking the Coding Interview 6E p. 101
No.
Cracking the Coding Interview 6E p. 101
What is a complete binary tree?
Cracking the Coding Interview 6E p. 102
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
What is a full binary tree?
Cracking the Coding Interview 6E p. 102
Every node has either 0 or 2 children.
Cracking the Coding Interview 6E p. 102
What is a perfect binary tree? Should you assume a binary tree is perfect?
Cracking the Coding Interview 6E p. 102
Both full and complete. No.
Cracking the Coding Interview 6E p. 102
What is a min-heap?
Cracking the Coding Interview 6E p. 103
Complete binary tree where each node is smaller than its children.
Cracking the Coding Interview 6E p. 103
Basic idea of insertion into a min heap. Time complexity?
Cracking the Coding Interview 6E p. 104
Bottom, rightmost; bubble up. O(log n).
Cracking the Coding Interview 6E p. 104
Basic idea of extracting min element from a min-heap?
Cracking the Coding Interview 6E p. 104
Remove root; swap root with last element; bubble down.
Cracking the Coding Interview 6E p. 104
Runtime of a prefix check in a trie?
Cracking the Coding Interview 6E p. 105
O(K) where K is the length of the string
Cracking the Coding Interview 6E p. 105
If a problem involves a list of valid words, or searching on related prefixes repeatedly, use a ?
Cracking the Coding Interview 6E p. 105
Trie.
Cracking the Coding Interview 6E p. 105
If you want to visit each node in a graph, what method is simplest?
Cracking the Coding Interview 6E p. 107
DFS.
Cracking the Coding Interview 6E p. 107
If you want to find the shortest path in a graph, what method is preferred?
Cracking the Coding Interview 6E p. 107
BFS.
Cracking the Coding Interview 6E p. 107
What is the preferred method to find the shortest path between a source and destination node?
Cracking the Coding Interview 6E p. 108
Bidirectional search.
Cracking the Coding Interview 6E p. 108
How are stacks sometimes used in recursive algorithms?
Cracking the Coding Interview 6E p. 97
To push temporary data, then remove as you backtrack (e.g. if recursive check fails).
Cracking the Coding Interview 6E p. 97
What part of a queue implementation is easy to mess up?
Cracking the Coding Interview 6E p. 98
Updating the first and last nodes.
Cracking the Coding Interview 6E p. 98
What situations are queues used for?
Cracking the Coding Interview 6E p. 98
BFS or cache.
Cracking the Coding Interview 6E p. 98
What is a denormalized database?
Cracking the Coding Interview 6E p169
(See source material.)
Cracking the Coding Interview 6E p169
What are examples of problems heaps / priority queues can help solve?
scheduling periodic tasks and merging log files; top/bottom; best/worst; min/max; optimal; paths
In the context of OO design for a game piece, what is a lesson to keep in mind?
Discuss if a Piece class should be subclassed or keep state composed with it.
Cracking the Coding Interview 6E Chapter 7 p325
In the context of OO design for a game with a board, what is a lesson to keep in mind?
Discuss if Board and Game classes should be separate.
Cracking the Coding Interview 6E Chapter 7 p325
In the context of OO design for a game, what is a lesson to keep in mind about the score?
Discuss which class should keep the score.
Cracking the Coding Interview 6E Chapter 7 p325
In the context of OO design for a game, what is a lesson to keep in mind about how to treat the Game class?
Discuss if the game should be a singleton.
Cracking the Coding Interview 6E Chapter 7 p325
In the context of OO design for a game, what is a lesson about what concepts need objects?
Objects for abstract concepts like Hand in a card game.
Cracking the Coding Interview 6E Chapter 7
In the context of OO design for a game, what is a lesson about how to get user input?
Function to get user input.
Cracking the Coding Interview 6E Chapter 7
In the context of OO design for a game, what is a lesson about representing enumerations?
Enum class for any enumeration.
Cracking the Coding Interview 6E Chapter 7
In the context of OO design for a game, what is a lesson about collections of objects?
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
In the context of OO design for a game, what is a lesson about abstraction for related objects?
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
In the context of OO design for a game, what is a lesson about types of abstraction for behaviors?
When using abstraction, consider abstract adjectives describing behaviors. E.g. Movable, Drawable.
Cracking the Coding Interview 6E Chapter 7
In the context of OO design for a game, what is a lesson about how to run the game?
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
In the context of OO design for a game, what is a lesson about how to set up the game initially?
Do high-level methods to initialize data structures.
Cracking the Coding Interview 6E Chapter 7
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?
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
8 tips for handling system design questions.
(See source material.)
Cracking the Coding Interview 6E Chapter 9 p137
5 steps for system design questions.
(See source material.)
Cracking the Coding Interview 6E Chapter 9 p138
4 steps for scalability in system design questions.
(See source material.)
Cracking the Coding Interview 6E Chapter 9 p139
Define horizontal and vertical scaling.
Cracking the Coding Interview 6E Chapter 9 p140
3 ways of doing data partitioning.
(See source material.)
Cracking the Coding Interview 6E Chapter 9 p141
3 important networking metrics.
bandwidth, throughput, latency
Cracking the Coding Interview 6E Chapter 9 p141
4 main considerations.
failures, availability and reliability, read-heavy vs. write-heavy, security
Cracking the Coding Interview 6E Chapter 9 p142
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
O(N+klogN).
O(N) in average case (O(N^2) in worst case).
Powers of 2 up through 2^9.
Cracking the Coding Interview 6E p.61
4=16, 5=32, 6=64, 7=128, 8=256, 9=512
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
“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”
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
“2¹⁶ = 65,536 ≈ 64K
2³² = 4,294,967,296 ≈ 4GB”
