Title: Theory / Unimportant / CS / Cracking the code interview+11;
Tags: computer_to_instruction toQuestion declaration todo_declaration

Name: Screening
Definition: Quizz over phone/skype to test whether the candidate has basic knowledge
Page: 6
Chapter: 1

Question: What to do if answer does not come in a week.
Answer: Follow up with the recruiter
Page: 6
Chapter: 1

Question: What is the training of recruiter about recruiting
Answer: Legal question
Page: 7
Chapter: 1
Answer2: how to deal with angry candidate

Question: Who decide questions asked to candidates
Answer: the interviewer, and not the company, usually
Page: 7
Chapter: 1

Question: What to do one year before the interview
Answer: Build projects outside school/works
Page: 7
Chapter: 1
Answer2: Expand network
Answer3: Professional: forucs work on "meaty projects"
Student: take classes with large project
Answer4: Build website/portfolio showcasing your experience

Question: What to do 3-12 monthes before the interview
Answer: create draft of resume and sent it out for a resume review
Page: 7
Chapter: 1
Answer2: make target list of preferred companies
Answer3: Practice interview questions using Java c++
Answer4: Continue working on project
Answer5: Form mock interview group with friends to interview each other

Question: What to do 1-3 monthes before the interview
Answer: Do mini-projects to solidify understanding of key concepts
Page: 7
Chapter: 1
Answer2: Do several mock interviews
Answer3: Continue to practice interviews questions
Answer4: Create list to track mistakes you've made solving problems

Question: What to do 4 weeks before the interview
Answer: Create interview prep grid
Page: 7
Chapter: 1
Answer2: Review/update resume
Answer3: Mock i

Question: What interview is supposed to be about
Answer: Prior experience
Page: 10
Chapter: 1
Answer2: culture fit
Answer3: coding skills
Answer4: analytical ability

Question: What interview is really about
Answer: coding skills
Page: 10
Chapter: 1
Answer2: analytical ability/intelligence

Question: What to do if you disagree with the interviewer
Answer: Don't argue; don't be percieved as arrogant
Page: 10
Chapter: 1

Question: What is taken into account when code is evaluated.
Answer: The final solution, not the intermediary step
Page: 11
Chapter: 1
Answer2: How fast did you solve it

Question: What to wear at interview
Answer: Start-up/big tech company: Khakis, slacks, nice jeans. Polo shirt, dress shirt, nice top, sweater
Page: 12
Chapter: 1
Answer2: For non tech (bank): Suit, no tie (or in pocket, just in case). For women: nice slacks with a nice top

Question: How to practice code interview
Answer: Don't compile; you won't have a compiler if its paper/pen
Page: 13
Chapter: 1
Answer2: solve problem loud, for the interviewer to know what you are doing
Answer3: Take your time
Answer4: Code nicely
Answer5: Test
Answer6: Fix mistake as soon as it occurs
Answer7: Don't give up

Question: How to practice appart from the code
Answer: Do a mock interview,
Page: 13
Chapter: 1
Answer2: Prep behavioral questions
Answer3: Don't try to memorize solution

Question: What should occur if you already know the question
Answer: Tell the interviewer.
Page: 13
Chapter: 1

Question: Why should you tell interviewer if you already know the question
Answer: You have honesty point.
Page: 15
Chapter: 1
Answer2: It may make you discover the question changed slightly
Answer3: You can't fake the right number of strugling

Question: What means hiring manager at microsoft
Answer: It means you have done well on previous step
Page: 19
Chapter: II

Name: Bar raiser
Definition: Person trained to ensure that interivew bar is high. Interview outside of its group
Page: 19
Chapter: II
Context: code interview

Question: What does it means, at amazon, that you have a third screening phone
Answer: Either one of the two first was not convinced,
Page: 19
Chapter: II
Answer2: or they may consider you for a different team

Question: What's particularly important at amazon
Answer: Scalability
Page: 20
Chapter: II

Question: What's particularly important at google
Answer: bit manipulation
Page: 21
Chapter: II

Question: What do interviewer at google after your interview
Answer: Give a note from 1.0 to 4.0 to hiring comittee
Page: 21
Chapter: II

Question: Which kind of note google hiring comitte want
Answer: At least one great scores
Page: 21
Chapter: II

Question: What is important in Apple interview
Answer: Being an apple fan
Page: 22
Chapter: II

Question: What is important in yahoo interview
Answer: System design
Page: 22
Chapter: II

Question: In which matter is experience taken into account
Answer: software engineering, since it comes with experience
Page: 26
Chapter: III
Answer2: your past project
Answer3: question on your experience, e.g. hardest bug to solve

Question: What is important for program/product manager
Answer: Able to handle ambiguity
Page: 28
Chapter: III
Answer2: Customer focus, attitude and technical skills
Answer3: Multi-level communication
Answer4: Passion for technology

Name: Acquihires
Definition: A company buying another one for talent aquisition
Page: 19
Chapter: III

Name: Acquired
Definition: A company beeing bought by another one for talent aquisition
Page: 19
Chapter: III

Name: Sanity check
Definition: Easy problem-solving or design questions.
Page: 25
Chapter: III
Context: Interview question

Name: Quality check
Definition: the more challenging questions, often in problem-solving or design
Page: 25
Chapter: III
Context: Interview question

Name: Specialist question
Definition: questions test knowledge of specific topics, such as Java or machine learning.
Page: 25
Chapter: III
Context: Interview question

Name: Proxy Knowledge
Definition: knowledge that is not quite at the specialist level, but that you would expect a candidate at their level to know
Page: 25
Chapter: III
Context: Interview question

Name: Kind of questions in interview
Definition: Sanity check
Page: 25
Chapter: IV
Context: Interview question
Definition2: Quality check
Conjdef: All of
Definition3: Specialist question
Definition4: Proxy knowledge

Question: Why to prefer short resume
Answer: screener will concentrate on the strong things you did
Page: 27
Chapter: IV
Answer2: Some screener reject long resume

Question: Strong resume bullet point
Answer: Accomplished X by implementing Y which led to Z
Page: 27
Chapter: IV

Question: Which language should you list
Answer: the ones you'd be confortable to be questionned about
Page: 28
Chapter: IV
Answer2: At least three languages, really varying, not only different flavour of the same

Name: Behavioral question about past projects
Definition: Challenges
Page: 28
Chapter: IV
Context: What you'd do differently
Definition2: Mistakes/failures
Conjdef: all of
Definition3: Enjoyed
Definition4: Leadership
Definition5: Conflicts

Question: What kind of questions to ask interviewer
Answer: Genuine question you want an answer about
Page: 28
Chapter: IV
Answer2: Insightful question: showing you know the technology they use, and want to understand their choice
Answer3: Passion question: designed to demonstrate your passion for technology. They show that you're interested in learning and will be a strong contributor to the company.

Question: How to answer behavioral questions
Answer: Be specific
Page: 34
Chapter: IV
Answer2: limit the details
Answer3: focus on your part of the job

Name: Nugget first
Definition: Start by stating what your story will be about, then tell it
Page: 34
Chapter: IV
Context: Structured answer

Name: Situation, action, result
Page: 34
Chapter: IV
Context: Structured answer
Abbreviation: SAR

Question: What part is important in stories about your past experiences
Answer: what action you took
Page: 36
Chapter: IV
Answer2: what this story tells about you

Question: Which hobbies should you talk about ?
Answer: Unique (fire breathing)
Page: 37
Chapter: IV
Answer2: Technical, to show your passion for skillset
Answer3: show a positive personallity

Question: big O
Answer: Omitted
Chapter: VI

Question: How to prepare technical questions ?
Answer: Try to solve problem on your own
Page: 60
Chapter: VII
Answer2: Write code on paper
Answer3: test code on paper
Answer4: implement code as-in into a computer,
Answer5: list the errors you make often

Question: important data structures to know
Answer: linked list
Page: 60
Chapter: VII
Answer2: Trees, tries, graphs
Answer3: stacks & queues
Answer4: Heaps
Answer5: Vectors/arraylists
Answer6: Hash Table

Question: important algorithm to know
Answer: breadth-first search
Page: 60
Chapter: VII
Answer2: Depth-first search
Answer3: Binary search
Answer4: merge sort
Answer5: quick sort

Question: important concepts to know
Answer: bit manipulation
Page: 60
Chapter: VII
Context: code interview
Answer2: memory (stack vs heap)
Answer3: recursion
Answer4: dynamic programming
Answer5: big o

Question: Walking through a problem
Answer: Listen to the problem, pay attention to details
Page: 60
Chapter: VII
Answer2: Work examples, and special cases,
Answer3: give a brute force answer
Answer4: optimize with BUD optimization
Answer5: Walk through the approach in detail
Answer6: Implement
Answer7: test

Name: BUD optimization
Definition: Bottlenecks
Page: 60
Chapter: VII
Definition2: Unnecessary work
Definition3: duplicated work

Question: How should an example be ?
Answer: Specific. It should use real numbers or strings (if applicable to the problem).
Page: 64
Chapter: VII
Context: Code interview
Answer2: Sufficiently large. Most examples are too small, by about 50%.
Answer3: Not a special case. Be careful. It's very easy to inadvertently draw a special case. If there's any way your
example is a special case (even if you think it probably won't be a big deal), you should fix it.

Question: Why should you state the brute force algorithm ?
Answer: To differentiate yourself from candidate who can't even see it
Page: 64
Chapter: VII

Question: How to save time writting code on whiteboard
Answer: Assume that you have access to function/class for straightforward things which would be easy and long to write (array initialization; a class of pair of objects)
Page: 66
Chapter: VII
Answer2: Abbreviate long variable name after first repetition

Question: How to test whiteboard code
Answer: Conceptual test: explain each line
Page: 66
Chapter: VII
Answer2: concentrate on lines looking weird
Answer3: Hot spots (base case, division by 0...)
Answer4: Small test
Answer5: Special case(null,0,empty container)

Question: What to do when you find a bug ?
Answer: Carefully analyze why the bug occurred
Page: 66
Chapter: VII
Answer2: ensure your fix is the best one

Name: Optimize and solve techniques
Definition: BUD
Page: 66
Chapter: VII
Definition2: DIY
Definition3: Simplify and Generalize
Definition4: Base Case and Build
Definition5: Data Structure Brainstorm
Definition6: Best Conceveilable runtime

Name: DIY
Definition: Try to solve the problem on an example without thinking about how to create an algorithm from it
Page: 66
Chapter: VII
Context: Optimize and solve techniques

Name: Simplify and Generalize
Definition: First we simplify or tweak some constraint, such as the data type. Then, we solve this new simplified version of the problem. Finally, once we have an algorithm for the simplified problem, we try to adapt it for the more complex version.
Page: 71
Chapter: VII
Context: Optimize and solve techniques

Name: Base Case and Build
Definition: Try to figure out how to solve bigger problem from smaller ones
Page: 71
Chapter: VII
Context: Optimize and solve techniques

Name: Data Structure Brainstorm
Definition: Enumerate all known datastructure, try to apply it to your problem
Page: 72
Chapter: VII
Context: Optimize and solve techniques

Name: Best conceivable runtime of P
Definition: the best runtime you could conceive of a solution of P
Page: 72
Chapter: VII
Variables: P a problem
Context: Code interview
Abbreviation: BCR

Question: What's the point of BCR ?
Answer: Telling when to stop searching
Page: 72
Chapter: VII
Variables: P a problem
Answer2: Letting guess which part of the algorithm could be optimized
Answer3: Telling that some computations are for free, when they are O(BCR)

Question: What to take into account while choosing the language in which you program
Answer: Whether you actually can code in it right now for the exercices
Page: 76
Chapter: VII
Context: Code interview
Answer2: whether the interviewer know it,or at least can read it
Answer3: Whether you introduce unrelated problem such as memory management in C
Answer4: Whether language is verbose

Question: What is a good code?
Answer: Correct
Page: 78
Chapter: VII
Answer2: efficient
Answer3: simple
Answer4: readable
Answer5: maintenable

Question: How to handle rejection
Answer: Try to ask when/how you can re apply.
Page: 82
Chapter: VII
Context: Code interview

Question: How to decline an offer
Answer: Give an explenation for your rejection, which can't be argued about
Page: 82
Chapter: VII

Question: What to do if you hesitate to accept
Answer: Tell the company you need more time, and explain what you are waiting for in order to make your decision
Page: 82
Chapter: VII
Context: Code interview

Question: How to evaluate the financial aspect of a propositon
Answer: Take into account salary, but also
Page: 84
Chapter: VII
Context: Job interview
Answer2: one time bonus when you arrive (e.g. for relocation.)
Answer3: cost of living where you go
Answer4: annual bonus
Answer5: stock options/grants

Question: How to evaluate how interesting a job offer is
Answer: financial aspect
Page: 84
Chapter: VII
Answer2: career development
Answer3: company stability
Answer4: hapiness factor

Name: Career development
Definition: what you'll learn, how it will advance your career
Page: 83
Chapter: VII
Definition2: how can I progress in the company
Definition3: How is the company/team growing
Definition4: how easy it is to change company leaving this one (geographically, and will it looks good on resume?)

Name: Happyness factor
Definition: How much do you love your product
Page: 84
Chapter: VII
Context: Code interview
Definition2: how nice are manager and teammates?
Definition3: What is the company's culture
Definition4: How many hours do you work by week ?

Question: Why to negociate your salary
Answer: They won't reject you because you negociate
Page: 84
Chapter: VII

Question: how to negociate your salary
Answer: Have a viable alternative. It'll let them know you can actually reject
Page: 84
Chapter: VII
Answer2: Tell a precise amount (more than what you actually want)
Answer3: Ask for equity/bonus/etc... not only for salary
Answer4: do it using the medium you're the most confortable with

Question: What to do when a collegue leaves
Answer: Send a friendly note a few weeks after the departure
Page: 85
Chapter: VII

Question: What to do once recruited (apart from the job)
Answer: Set a deadline, about when/what should make you leave (e.g. not learning anything new)
Page: 85
Chapter: VII
Answer2: Make strong relationships
Answer3: Tell manager what you want to learn/experiment with next
Answer4: keep interviewing

Question: Brain teaser are usually worder
Answer: either in terms of minimizing an action
Page: 122
Chapter: 6
Answer2: Doing someting at most a specific number of times

Name: Worst case balancing
Definition: A technic to adapt an algorithm, in order to decrease its worst-case by increasing its best-case
Page: 122
Chapter: 6

Question: What's the goal of object-oriented question ?
Answer: Give interviewer insight into your coding style
Page: 125
Chapter: 7

Question: How to approach object-oriented questions ?
Answer: Handle ambiguity: who will use it/how is it going to be used
Page: 125
Chapter: 7
Answer2: Define core objects
Answer3: Analyze relationships
Answer4: Investigate actions

Question: Which are the most important design patterns ?
Answer: Singleton class
Page: 126
Chapter: 7
Answer2: Factory method

Question: Hint to recognize recursive problem
Answer: The problem can be built off of subproblems
Page: 141
Chapter: 8

Name: Bottom up approach
Definition: We start with knowing how to solve the problem for a simple case, like a list with only one element. Then we figure out how to solve the problem for two elements, then for three elements, and so on. The key here is to think about how you can build the solution for one case off of the previous case (or multiple previous cases).
Page: 141
Chapter: 8
Context: Solving problem

Name: Top-down approach
Definition: we think about how we can divide the problem for case N into subproblems.
Be careful of overlap between the cases
Page: 141
Chapter: 8
Context: Solving problem

Name: Half-and-half approach
Definition: Divide the data set in half, solve them, combine the two halves
Page: 131
Chapter: 8
Context: Solving problem

Question: What to do before implementing a recursive algorithm
Answer: Discuss with the interviewer about the tradeoff between a recursive and an iterative implementation
Page: 131
Chapter: 8
Context: Solving problem

Name: Dynamic programming
Definition: taking a recursive algorithm and finding the overlapping subproblems (that is, the repeated calls). You then cache those results for future recursive calls.
Page: 131
Chapter: 8
Context: Solving problem

Question: How to figure out computation time of a recursive algorithm ?
Answer: Draw the tree of recursive calls
Page: 132
Chapter: 8
Context: Solving problem

Question: How to solve a scalability problem
Answer: Scope the problem
Page: 138
Chapter: 9
Context: Solving problem
Answer2: Make reasonable assumptions
Answer3: Draw the major components
Answer4: Identify the key issues
Answer5: Redesign for the key issues

Name: Vertical scaling
Definition: increasing the resources of a specific node
Page: 140
Chapter: 9
Example: add additional memory to a server to improve its ability to handle load changes.

Name: Horizontal scaling
Definition: increasing the number of nodes
Page: 140
Chapter: 9
Context: Scaling
Example: add additional servers, thus decreasing the load on any one server.

Name: Load balancer
Definition: A system distributing requests to a bunch of identical servers to ensure each are used as much as the others
Page: 140
Chapter: 9

Name: Denormalization
Definition: adding redundant information into a database to speed up reads
Page: 140
Chapter: 9
Context: Database

Name: Sharding
Definition: splitting the data across multiple machines while ensuring you have a way of figuring out which data is on which machine.
Page: 140
Chapter: 9
Context: Database

Name: Vertical partitionning
Definition: partitioning by feature
Page: 141
Chapter: 9
Context: Database Sharding
Example: if you were building a social network, you might have one partition for tables relating to profiles, another one for messages, and so on. One drawback of this is that if one of these tables gets very large, you might need to repartition that database

Name: Key/Hash-based partitionning
Definition: partitioning according to the value of some data
Page: 141
Chapter: 9
Context: Database Sharding
Example: allocate N servers and put the data on mod (key, n)

Name: Directory-based partitionning
Definition: Database sharding which have a lookup table stating where each data can be found
Page: 141
Chapter: 9
Context: Database Sharding

Name: Caching
Definition: Saving data accessed in some quick memory. Data is searched in this memory before being searched in the database.
Page: 141
Chapter: 9
Intuition: Way to easily improve data access speed, possibly adding some delay for update to occur

Name: Bandwidth
Definition: maximum amount of data that can be transferred in a unit of time
Page: 141
Chapter: 9
Context: Network metric

Name: Throughput:
Definition: Actual amount of data transferred by unit of time
Page: 141
Chapter: 9
Context: Network metric

Name: Latency
Definition: how long it takes data to go from one end to the other.
Page: 141
Chapter: 9
Context: Network metric

Question: What to consider when designing a system
Answer: Failures: Essentially any part of a system can fail. You'll need to plan for many or all of these failures.
Page: 142
Chapter: 9
Answer2: Availability and Reliability: Availability is a function of the percentage of time the system is opera
tional. Reliability is a function of the probability that the system is operational for a certain unit of time.
Answer3: Read-heavy vs. Write-heavy: Whether an application will do a lot of reads or a lot of writes impacts the
design. If it's write-heavy, you could consider queuing up the writes (but think about potential failure
here!). If it's read-heavy, you might want to cache. Other design decisions could change as well.
Answer4: Security: Security threats can, of course, be devastating for a system. Think about the types of issues a
system might face and design around those.

Page: 146
Implementation: start at the beginning of the array and swap the first two elements if the first is greater than the second. Then, we go to the next pair, and so on, continuously making sweeps of the array until it is sorted.
Chapter: 10
Effect: Sorts the array
Name: Bubble sort
Time complexity: \(O(n^2)\)
Space complexity: \(O(1)\)
Input: An array of sortable elements
Intuition: the smaller items slowly"bubble" up to the beginning of the list.

Page: 146
Implementation: Find the smallest element using a linear scan and move it to the front (swapping it with the front element)
Chapter: 10
Effect: Sorts the array
Name: Selection sort
Time complexity: \(O(n^2)\)
Space complexity: \(O(1)\)
Input: An array of sortable elements

Page: 146
Implementation: divides the array in half, sorts each of those halves, and then merges them back together. Each
of those halves has the same sorting algorithm applied to it.
Chapter: 10
Effect: Sorts the array
Name: Merge sort
Time complexity: \(O(n \log(n))\)
Space complexity: \(O(n)\)
Input: An array of sortable elements

Page: 146
Implementation: we pick a random element and partition the array, such that all numbers that are less than the
partitioning element come before all elements that are greater than it. The partitioning can be performed efficiently through a series of swaps
Chapter: 10
Effect: Sorts the array
Name: Quick sort
Time complexity: \(O(n \log(n))\) average, \(O(n^2)\) worst case
Space complexity: \(O(\log n)\)
Input: An array of sortable elements

Page: 148
Implementation: Sort according to the first digit, then the second one, then the third, etc...
Chapter: 10
Effect: Sorts the array
Name: Radix sort
Time complexity: \(O(kn)\)
Assuming: Elements are sorted according to some lexicographical order with \(k\) basis elements each having a small number of possible values
Space complexity: \(O(\log n)\)
Input: An array of sortable elements

Question: Different kind of search algorithm
Answer: Binary search in a sorted array
Page: 149
Chapter: 10
Answer2: Binary search tree
Answer3: Hashtable

Question: Different kind of tests
Answer: Test a real world object (like a pen)
Page: 152
Chapter: 11
Answer2: Test a piece of software;
Answer3: Write test code for a function;
Answer4: Troubleshoot an existing issue

Question: Testing real world object
Answer: Who will use it? And why ?
Page: 153
Chapter: 11
Answer2: What are the use cases
Answer3: What are the bounds of use?
Answer4: What are the stress/ failure conditions?
Answer5: How would you perform the testing?

Question: Example of «who will use paperclip»
Answer: The answer could be "by teachers, to hold papers together;' or it could be "by artists,
to bend into the shape of animal:' Or, it could be both.
Page: 153
Chapter: 11
Context: Testing real world object

Question: Example of «paperclip usecase»
Answer: simply fastening
paper together in a non-damaging (to the paper) way.
Page: 153
Chapter: 11
Context: Testing real world object

Question: Example of «paperclip bounds of use»
Answer: No dommage up to 30 sheets of paper. Bending until 50. Don't hold anymore after 50
Page: 153
Chapter: 11
Context: Testing real world object
Answer2: Cease to work on very warm temperature

Question: Example of «stress/failure condition»
Answer: A laundry with more than 30 piece may wash inadequately. Laundry with 45 pieces may refuse to wash, but not create flood or fire
Page: 153
Chapter: 11
Context: Testing real world object

Question: Example of «how to perform test on a chair»
Answer: Define number of normal sit by year. Create a robot doing it automatically
Page: 153
Chapter: 11
Context: Testing real world object

Name: Black box testing
Definition: Testing a program without having access to the source code
Page: 154
Chapter: 11

Name: White box testing
Definition: Testing a program with access to the source code
Page: 154
Chapter: 11

Question: How to test a piece of software
Answer: Determine whether its black or white box testing
Page: 154
Chapter: 11
Answer2: Test similar to an object

Question: Example of tests which should be devised to test a function
Answer: Normal case, covering a variety of case. For example, even and odd array to sort, because partitionning may fails there
Page: 155
Chapter: 11
Answer2: Extreme examples: empty list to sort, and list with a single element
Answer3: Illegal input: null, negative number, empty list ...
Answer4: strange input: a sorted list, a list sorted in reverse order..

Question: How to test a function
Answer: Define test cases
Page: 155
Chapter: 11
Answer2: Define expected result
Answer3: Write test code

Question: How to deal with troubleshooting question
Answer: Understand the scenarion
Page: 156
Chapter: 11
Answer2: Break down the problem
Answer3: Create Specific, Manageable Tests

Name: Normalized database
Definition: Database with minimum redundancy
Page: 169
Chapter: 12

Question: Steps of small database design
Answer: Handle ambiguity
Page: 171
Chapter: 12
Answer2: Define the core objects
Answer3: Analyze realtionship
Answer4: Investigate actions

Name: Main thread
Definition: Thread running the main() method
Page: 174
Chapter: 15
Context: Java

Question: How to create thread in java
Answer: Implementing interface Runnable
Page: 174
Chapter: 15
Context: Java
Answer2: Extending java.lang.Thread class

Name: A runnable object
Definition: An object implementing the interface runnable
Page: 174
Chapter: 15
Context: Java

Question: To create threads, why extend Runnable and not Thread
Answer: Single inheritance means that it can't inherit Thread and something else
Page: 174
Chapter: 15
Context: Java
Answer2: A class might only be interested in being runnable, and therefore, inheriting the full overhead of the Thread class would be excessive.

Instruction: synchronize (foo){
 bar
}
Page: 177
Effect: Either execute bar or wait until another execution of bar with key foo ends.
Context: Java
Chapter: 15

Instruction: synchronized foo
Page: 177
Meaning: Defines foo and ensures that for each object, at most one execution of foo occurs simultaneously
Chapter: 15
Context: Java
Variables: foo a function definition

Question: What are the conditions for a lock to occurs
Answer: Mutual exclusion
Page: 177
Chapter: 15
Context: Java
Answer2: Hold and Wait
Answer3: No Preemption
Answer4: Circular wait

Name: Mutual exclusion
Definition: Only one process can access a resource at a given time.
Page: 179
Chapter: 15
Context: Deadlock

Name: Hold and Wait
Definition: Processes already holding a resource can request additional resources, without relinquishing their current resources.
Page: 179
Chapter: 15
Context: Deadlock

Name: No preemption
Definition: One process cannot forcibly remove another process' resource.
Page: 179
Chapter: 15
Context: Deadlock

Question: \(1+\dots+n\)
Answer: \(n(n+1)/2\)
Page: 630
Chapter: XI

Question: \(2^0+\dots+2^n\)
Answer: equals \(2^{n+1}-1\)
Page: 630
Chapter: XI

Question: \(\frac{\log[a]p}{\log[b]p}\)
Answer: \(\log[a]b\)
Page: 631
Chapter: XI

Name: \(n\) choose \(k\)
Definition: \(\frac{n!}{k!(n-k)!}\)
Page: 631
Chapter: XI
Notation: \(n\choose k\)
Intuition: Number of subset of \(k\) elements from a set of \(n\) elements

Question: Number of way to create a word of \(k\) distinct letters from an alphabet of \(n\) letters
Answer: \(\frac{n!}{(n-k)!}\)
Page: 631
Chapter: XI

Name: A topological ordering of \(G\)
Definition: A list of node of \(G\) such that if \((a,b)\in E\) then \(a\) occurs before \(b\)
Page: 631
Chapter: XI
Variables: \(G\) a directed graph
Assuming: acyclic graph

Name: Open Addressing with Linear Probing
Definition: An hashtable with two hashing functions \(f\) and \(g\). Element with key \(k\) is put in the first value \(g\circ\dots\circ g\circ f(k)\) free. When this element is looked-up, same computation is done until a free space is found
Page: 636
Chapter: XI
Context: Hash table

Page: 636
Implementation: find a hashing function \(f(a_0,\dots,a_s)\) such that \(f(a_1,\dots,a_{s},a_{s+1})=g(a_0,f(a_0,\dots,a_s),a_s)\) (for example \(f\) can be the sum, or \(\sum_ia_i26^i\mod c\) for some constant \(c\)
Compute the hash of each subset of \(S\) of length \(s\), add it in a hash-table. Then search for the hash value of each element \(l\) of \(L\) and check whether it corresponds to some substring equal to \(l\)
Chapter: XI
Name: Rabin-Karp Substring Search
Returns: The elements of \(L\) occurring in \(S\)
Input: A string \(S\) of length \(b\) and a list \(L\) of string of length \(s\)