Cracking the Coding Interview by Gayle McDowell

• Big-O time is the language and metric we use to describe the efficiency of algorithms. Not understanding it thoroughly can really hurt you in developing an algorithm.
• In academia, Big-O describes an upper bound on the time.
• Big-omega is the equivalent concept but for lower bounds.
• Big-theta means both big-o and big-omega. That is, an algorithm is big-theta if it is both big-o and big-omega. Big-theta gives a tight bound on runtime.
• We rarely ever discuss best case time complexity, because it’s not a very useful concept. After all, we could take essentially any algorithm, special case some input, and then get an O(1) time in the best case.
• For many--probably most-algorithms, the worst and the expected case are the same.
• Big O, big omega, and big theta describe the upper, lower, and tight bounds for the runtime.
• Space complexity is a parallel concept to time complexity. If we need to create an array of size n, this will require O(n) space. If we need a two-dimensional array of size NxN, this will require O(n^2) space.
• When you have a recursive function that makes multiple calls, the runtime will often (but not always) look like O(branches^depth), where branches is the number of times each recursive call branches.
• Generally speaking, when you see an algorithm with multiple recursive calls, you’re looking at exponential runtime.
• Here’s a list of the absolute, must-have knowledge:
• Data Structures
• Linked lists
• Trees, tries, and graphs
• Stacks & queues
• Heaps
• vectors/ArrayLists
• Hash tables
• Algorithms
• Breadth-first search
• Depth-first search
• Binary search
• Merge sort
• Quick sort
• Concepts
• Bit manipulation
• Memory (stack vs heap)
• Recursion
• Dynamic programming
• big-O time & space
• In particular, hash tables are an extremely important topic. Make sure you are very comfortable with this data structure.
• Despite being possibly slow, a brute force algorithm is valuable to discuss. It’s a starting point for optimizations, and it helps you wrap your head around the problem.
• Once you have a brute force algorithm, you should work on optimizing it.
• Perhaps the most useful approach I’ve found for optimizing problems. “BUD” is a silly acronym for: bottlenecks, unnecessary work, duplicated work.
• A bottleneck is a part of your algorithm that slows down the overall runtime.
• Optimizing a bottleneck can make a big difference in your overall runtime.
• Be particularly aware of any “optimizations” you intuitively or automatically made.
• The best conceivable runtime is, literally, the best runtime you could conceive of a solution to a problem having. You can easily prove that there is no way you could be the BCR.
• Best Conceivable Runtime is not a “real” algorithm concept, in that you won’t find it in algorithm textbooks. But I have found it personally very useful, when solving problems myself, as well as while coaching people through problem.s
• One sign of a careful coder is that she doesn't make assumptions about the input. Instead, she validates that the input is what it should be, either through ASSERT statements or if-statements.
• All else being equal, of course stability is a good thing. No one wants to be fired or laid off. However, all else isn’t actually equal. The more stable companies are also often growing more slowly.
• A hash table is a data structure that maps keys to values for highly efficient lookup. There are a number of ways of implementing this.
• In some languages, arrays (often called lists in this case) are automatically resizable. The array or list will grow as you append items. In other languages, like Java, arrays are fixed length. The size is defined when you create the array.
• When you need an array-like data structure that offers dynamic resizing, you would usually use an ArrayList. An ArrayList is an array that resizes itself as needed while still providing O(1) access. A typical implementation is that when the array is full, the array doubles in size.
• A linked list is a data structure that represent a sequence nodes. In a singly linked list, each node points to the next node in linked list. A doubly linked list gives each node pointers to both the next node and the previous node.
• Unlike an array, a linked list does not provide constant time access to a particular index within the list. This means that if you'd like to find the K-th element in the list, you will need to iterate through K elements.
• The benefit of a linked list is that you can add and remove items from the beginning of the list in constant time.
• The “runner” technique means that you iterate through the linked list with two pointers simultaneously, with one ahead of the other. The “fast” node might be ahead by a fixed amount, or it might be hopping multiple nodes for each one node that the “slow” node iterates through.
• A stack can also be used to implement a recursive algorithm iteratively.
• A binary search tree is a binary tree in which every node fits a specific order property: all left descendants <= n < all right descendants. This must be true for each node n.
• A trie (sometimes called a prefix tree) is a funny data structure. It comes up a lot in interview questions, but algorithm textbooks don’t speed much time on this data structure.
• Bidirectional search is used to find the shortest path between a source and destination node. It operates by essentially running two simultaneous breadth-first searches, one from each node. When they search Coolidge, we have found a path.
• The Sieve of Eratosthenes is a highly efficient way to generate a list of primes. It works by recognizing that all non-prime numbers are divisible by a prime number.
• Be careful you don’t fall into a trap of constantly trying to find the “right” design pattern for a particular problem. You should create the design that works for that problem. In some cases it might be an established pattern, but in many other cases it is not.
• The Singleton pattern ensures that a class has only one instance and ensures access to the instance through the application. It can be useful in cases where you have a “global” object with exactly one instance.
• It should be noted that many people dislike the Singleton design pattern, even calling it an “anti-pattern”. One reason for this is that it can interfere with unit testing.
• The Factory Method offers an interface for creating an instance of a class, with its subclasses deciding which class to instantiate. You might want to implement this with the creator class being abstract and not providing an implementation for the Factory method. Or, you could have the Creator class be a concrete class that provides an implementation for the Factory method.
• While there are a large number of recursive problems, many follow similar patterns. A good hint that a problem is recursive is that it can be built off of subproblems.
• Recursive algorithm can be very space inefficient. Each recursive call adds a new layer to the stack, which means that if your algorithm resources to a depth of n, it uses at least O(n) memory.
• Dynamic programming is mostly just a matter of taking a recursive algorithm and finding the overlapping subproblems (that is, the repeated calls). You then cache those results for future recursive calls.
• One of the simplest examples of dynamic programming is computing the nth Fibonacci number. A good way to approach such a problem is often to implement it as a normal recursive solution, and then add the caching part.
• Drawing the recursive calls as a tree is a great way to figure out the runtime of a recursive algorithm.
• A system can be scaled one of two ways:
• Vertical scaling means increasing the resources of a specific node. For example, you might add additional memory to a server to improve its ability to handle load changes.
• Horizontal scaling means increasing the number of nodes. For example, you might add additional servers, thus decreasing the load on any one server.
• Typically, some frontend parts of a scalable website will be thrown behind a load balancer. This allows a system to distribute the load evenly so that one server doesn’t crash and take down the whole system. To do so, of course, you have to build out a network of cloned servers that all have essentially the same code and access to the same data.
• Sharding means splitting the data across multiple machines while ensuring you have a way of figuring out which data is one which machine.
• An in-memory cache can deliver very rapid results. It is a simply key-vale pairing and typically sits between your application layer and your data store.
• Slow operations should ideally be done asynchronously. Otherwise, a user might get stuck waiting and waiting for a process to complete.
• Some of the most important metrics around networking include:
• Bandwidth: This is the maximum amount of data that can be transferred in a unit of time. It is typically expressed in bits per second.
• Throughput: Whereas bandwidth is the maximum data that can be transferred in a unit of time, throughput is the actual amount of data that is transferred.
• Latency: This is how long it takes data to go from one end to the other. That is, it is the delay between the sander sending information and the receiver receiving it.
• MapReduce allows us to do a lot of processing in parallel, which makes processing huge amounts of data more scalable.
• MapReduce is often associated with Google, but it’s used much more broadly than that. A MapReduce program is typically used to process large amounts of data.
• Understanding the common sorting and searching algorithms is incredibly valuable, as many sorting and searching problems are tweaks of the well-known algorithms. A good approach is therefore to run through the different sorting algorithms and see if one applies particularly well.
• Learning the common sorting algorithms is a great way to boost your performance. Of the five algorithms explained below, merge sort, quick sort, and bucket sort are the most commonly used in interviews.
• No product is fail-proof, so analyzing failure conditions needs to be a part of your testing. A good discussion to have with your interviewer is about when it’s acceptable (or even necessary) for the product to fail, and what failure should mean.
• All data members and methods are private by default in C++. One can modify this by introducing the keyword public.
• The constructor of a class is automatically called upon an object’s creation. If no constructor is defined, the compiler automatically generates one called the Default Constructor. Alternatively, we can define our own constructor.
• The destructor cleans up upon object deletion and is automatically called when an object is destroyed. It cannot take an argument as we don’t explicitly call a destructor.
• Unlike pointers, references cannot be null and cannot be reassigned to another piece of memory.
• Templates are a way of reusing code to apply the same class to different data types.
• Normalized databases are designed to minimize redundancy, while denormalized databases are designed to optimize read time.
• Threads within a given process share the same memory space, which is both a positive and negative. It enables threads to share data, which can be valuable. However, it also creates the opportunity for issues when two threads modify a resource at the same time.
• For more granular control, we can utilize a lock. A lock (or monitor) issued to synchronize access to a shared resource by associating the resource with the lock. A thread gets to a shared resource by first acquiring the lock associated with the resource. At any given time, at most one thread can hold the lock and, therefore, only one thread can access the shared resource.

Cracking the PM Interview by Gayle McDowell & Jackie Bavaro

• A PM is responsible for making sure that a team ships a great product.
• The PM needs to set vision and strategy.
• The PM defines success and makes decisions.
• The day-to-day work of a product manager varies over the course of the product life cycle, you’ll be figuring out what to build; in the middle you’ll help the team make progress; at the end you’ll be preparing for launch.
• During implementation, one of the most important parts of the job is helping the engineers work efficiently. The product manager will check in regularly with his team and learn how things are going.
• For mature products, such as market leaders, most of the work will be iterating on the product and trying to improve it. PMs often have feedback from previous versions as to which areas need the most improvement and can focus on them.
• As a PM on a mature product, it can be very important to make sure you don’t get stuck making small incremental improvements.
• Often, a mature product’s biggest competitor is the last version of that same product. At the same time, mature products often have the luxury of time to make big bets on new ideas.
• PMs are responsible for seeing the entire project through to a successful completion.
• Product managers are able to reduce the number of meetings their teammates need to attend because they’re able to represent the team to other groups and find productive ways of communicating that don’t require meetings.
• Not trusting the engineers’ estimates and promising other teams that the work will be done sooner than the engineers agree to it is one of the fastest ways to ruin your relationship with the team.
• While most roles on the team are crisply defined, product managers have a more fluid role. When you’re a product manager, your job is anything that isn’t being covered by other people.
• As a PM, you’re responsible for the success of failure of your product, and no job is beneath you.
• One of the best ways to get a signal on the culture at a startup is to look at where the founders, PMs, and early employees came from.Since product management doesn’t have a single, well-known definition, teams generally bring along the definition that they learned from their past companies.
• The big difference in being a PM at a startup comes from the scale.
• Since startups don’t have large management structures, the PMs naturally become important leaders for the company. Additionally, startups have fewer resources, so there’s more “white space” for the PMs to fill in and more of a need to be really scrappy.
• Engineers at startups love shipping code quickly and are very wary of overhead, so it’s important to be careful when adding processes like Agile.
• If you ask interviewers what they're looking for in PM candidates, they’ll unusually say that they are looking for smart people who get stuff done.
• One of the best ways to rise above the crowd is to have a side project like a mobile app. This gives you a chance to show your customer focus and product design skills.
• LinkedIn is one of the most valuable sites to focus on for recruiting.
• The most important way a product manager is judged is by the products she’s launched.
• Many people without a background in computer science struggle to form strong working relationships with engineers.
• Great product managers are action-oriented and passionate about delivering results. They will try to take care of what they can themselves, whether that’s gathering data or fixing typos in the product. This frees up development from the more tedious tasks so they’ll be able to do more valuable work.
• Customer Focus is the most important thing to develop when moving from engineering to product management. Engineers and developers can usually pick up most of the other important skills on the job, but a customer focus is one of the defining characteristics of good PMs.
• Many engineers are comfortable in the world of analytical thinking. As an engineer, it’s better to prove things through data than charisma. As a product manager, you need to master both.
• It will be hard to be successful as a PM if you’re still handling a lot of engineering responsibilities; you need to pick up some escape velocity. Consider taking time off between the role switch or having some kind of hand off or party to mark the transition. Then you can dive into your new PM role fully.
• One of the best ways to improve your candidacy for a product management position is to start a side project. This side project gives you a chance to gain experience shipping a product, builds up your resume, shows off your technical skills, shows off your product design skills, and gives you a lot to talk about during your interview. If you hired people to help you, it might also give you a chance to show leadership skills.
• As a PM, the biggest measure of your success will be the products you launch.
• At a growing company, new opportunities are always opening up, and you quickly become one of the more senior employees. This means that even if you had to join a different team or take on a different title from what you wanted, you’d likely get a chance to transition soon.
• Infrastructure teams often don’t sound like a fun place to be a PM, but they’re critically important to the company. The improvements you make as an infrastructure PM can be magnified throughout the company, so they can be a great place for career advancement.
• At some point in your career, your visibility across the company is going to matter if you want to be promoted to higher positions.
• The most straightforward way to build credibility is delivering results. Your teammates all want a good outcome, so they'll naturally start out second guessing your opinions, asking lots of questions, and suggesting different ways of doing things. However, over time they’ll start to see that you’re showing good judgement and getting things done, and they’ll feel comfortable trusting you.
• Another way to build credibility is paying attention to people’s perceptions of you and ensuring that you’re creating the perception you want.
• Make sure you’re building a reputation as a smart, skillful, competent, and dependable person with good judgement.
• Getting an MBA just for the sake of getting an MBA is not worthwhile in tech, at least not in silicon Valley.
• It’s not your experience that lands you an interview; it’s how your resume presents that experience. Even the best candidate in the world won’t get an interview with a lousy resume. After all, a company wouldn’t know that she’s the best candidate in the world.
• A resume isn’t read; it’s skimmed. A resume screen will glance at your resume for about 15 seconds (or maybe less) to make a decision about whether or not to interview you.
• A good rule of thumb is to limit your resume to one page if you have less than 10 years of experience. In more than 10 years, you might be able to justify 1.5 or 2 pages, particularly if you’ve held many different jobs.
• Focus on what is important, and leave out the rest.
• Read through your resume. Anything that’s three lines of text or more should be condensed. Additionally, you should aim to have no more than 50 percent of your bullets expand to two lines. That is, at least half of your bullets should be just one line, with the remainder being two lines.
• People don’t care what you were told to do; they care what you did.
• You want to focus on your accomplishments. Prove to the resume screener you had an impact.
• As much as possible, quantify your accomplishments.
• A good resume is reasonably compact and quickly showcases your highlights.
• Employers want PMs who have technical skills, love technology, possess initiative, are leaders, and will have an impact. A resume is a chance to showcase these parts of your background.
• Don’t list something from a long time ago unless it really makes you stand out.
• You should understand what the company is doing at a deep level.
• You should know not only what the company is doing, but why it is doing it. Knowing the “why” will help your answers fit the company’s view of the world.
• Successful people tend to know where they’re going in life. If you don’t have a plan, an interviewer might worry you’re not very serious about your career.
• Understanding other people is a fundamental part of teamwork, leadership , and persuasion, and therefore a fundamental part of a product management role.
• Failure is okay; helplessness is not.
• Here’s a fun and useful tip: if you need to calculate how long until something doubles, divide 72 by the percent increase.
• Interviewers are looking for structured thinking. The easiest way to show this is to give a structured answer and call out which part of the structure you’re on.
• Strengths are the internal factors that benefit a product. This can include anything about the costs, product features, company culture, reputation, infrastructure, or other aspects.
• SWOT Analysis: strengths, weaknesses, opportunities, threats.
• The two most common good ways to sort an array are quicksort and merge sort. The others are less efficient in general or only work with specific assumptions.
• Big O notation is a way to express the efficiency of an algorithm. If you’re going to be working with code, it is important that you understand big O. It is, quite literally, the language we use to express efficiency.
• Recursion can be a useful strategy to solve a large number of problems. It works well when the solution to a problem can be defined in terms of the solutions to subproblems.
• Any problem that can be solved recursively can also be solved iteratively, although sometimes doing so is much more complicated. However, recursion comes with a drawback, which is memory usage.
• The top 10% of product managers excel at a few of these things. The top 1% excel at most or all of them.
• Think big - A 1% PM’s thinking won’t be constrained by the resource available to them today or today’s market environment. They’ll describe large disruptive opportunities, and develop concrete plans for how to take advantage of them.
• Communicate - A 1% PM can make a case that is impossible to refute or ignore. They’ll use data appropriately, when available, but they’ll also tap into other biases, beliefs, and triggers that can convince the powers that be to part with headcount, money, or other resources and then get out of the way.
• Simplify - A 1% PM knows how to get 80% of the value out of any feature or project with 20% of the effort. They do so repeatedly, launching more and achieving compounding effects for the product or business.
• Prioritize - A 1% PM knows how to sequence projects. They balance quick wins vs platform investments appropriately. They balance offense and defense projects appropriately. Offense projects are ones that grow the business. Defense projects are ones that protect and remove drag on the business.
• Forecast and measure - A 1% PM is able to forecast the approximate benefit of a project, and can do so efficiently by applying past experience and leverage comparable benchmarks. They also measure benefit once projects are launched, and factor those learning into their future prioritization and forecasts.
• Execute - A 1% PM grinds it out. They do whatever is necessary to ship. They recognize no specific bounds to the scope of their role. As necessary, they recruit, they produce buttons, they do biz dev, they escalate, they tussle with internal counsel, they…
• Understand technical trade-offs - A 1% PM does not need to have a CS degree. They do need to be able to roughly understand the technical complexity of the features they put on the backlog, without any costing inputs from devs. They should partner with devs to make the right technical trade-offs.
• Understand good design - A 1% PM doesn’t have to be a designer, but they should appreciate great design and be able to distinguish it from good design. They should also be able to articulate the difference to their design counterparts, or at least articulate directions to pursue to go from good to great.
• Write effective copy - A 1% PM should be able to write a concise copy that gets the job done. They should understand that each additional word they write dilutes the value of the previous ones. They should spend time and energy trying to find the perfect words for key copy, not just words that will suffice.