大厂的面试准备要点，关于Coding 和 system design
79091
这个面试准备总结的挺细致，分享给准备面试的同学. Many candidates have mentioned that these resources were particularly helpful:
Practice: Cracking the Coding Interview, Top Coder, LeetCode, Stack Overflow, Project Euler
ENGINEERING ONSITE STUDY GUIDE:
1) What to Expect
Five, 45 minute technical interviews with an interviewer from Software Engineering. The interviewer will be interested in your knowledge of computer science principles and how they can be used in your solutions. Typically there is more than one question in each interview, make sure you keep on pace!
2) Interview Questions
Be ready to code on the white board. No laptop will be provided. Interview topics may cover anything on your resume, developing complex algorithms and analyzing their performance characteristics. Computer Science fundamentals are prerequisite for all engineering roles due to the complexities and global scale of the projects you would end up participating in.
3) How to succeed
We believe in collaboration and sharing ideas. Most importantly, you'll need more information from the interviewer to analyze and answer the question to its full extent. If there is anything you don’t understand - it is okay to ask your interviewer for help or clarification. Many of the questions asked in interviews are deliberately underspecified because our engineers are looking to see how you engage the problem. If you need to assume something - verbally check that it is a correct assumption. Always let your interviewer know what you are thinking as he/she is as interested in your thought process and how you approach the problem as the solution itself. If you're stuck, they may provide hints if they know what you're doing.
The Coding & Algorithm Interviews
Coding - You should know at least one programming language really well, preferably C++, Java, Python, Go, or C. You will be expected to know APIs, Object Oriented Design and Programming, how to test your code, as well as come up with corner cases and edge cases for code. Note that we focus on conceptual understanding rather than memorization.
Algorithms - Approach the problem with both bottom-up and top-down algorithms. You will be expected to know the complexity of an algorithm and how you can improve/change it. Algorithms that are used to solve problems include sorting (plus searching and binary search), divide-and-conquer, dynamic programming/memoization, greediness, recursion or algorithms linked to a specific data structure. Know Big-O notations (e.g. run time) and be ready to discuss complex algorithms like Dijkstra and A*. We recommend discussing or outlining the algorithm you have in mind before writing code.
Sorting - Be familiar with common sorting functions and on what kind of input data they’re efficient on or not. Think about efficiency means in terms of runtime and space used. For example, in exceptional cases insertion-sort or radix-sort are much better than the generic QuickSort/MergeSort/HeapSort answers.
Data structures - You should study up on as many data structures as possible. Data structures most frequently used are arrays, linked lists, stacks, queues, hash-sets, hash-maps, hash-tables, dictionary, trees and binary trees, heaps and graphs. You should know the data structure inside out, and what algorithms tend to go along with each data structure.
Mathematics - Some interviewers ask basic discrete math questions. This is more prevalent at Google than at other companies because counting problems, probability problems and other Discrete Math 101 situations surround us. Spend some time before the interview refreshing your memory on (or teaching yourself) the essentials of elementary probability theory and combinatorics. You should be familiar with n-choose-k problems and their ilk.
Graphs - Consider if a problem can be applied with graph algorithms like distance, search, connectivity, cycle-detection, etc. There are three basic ways to represent a graph in memory (objects and pointers, matrix, and adjacency list) — familiarize yourself with each representation and its pros and cons. You should know the basic graph traversal algorithms, breadth-first search and depth-first search. Know their computational complexity, their tradeoffs and how to implement them in real code.
Recursion - Many coding problems involve thinking recursively and potentially coding a recursive solution. Use recursion to find more elegant solutions to problems that can be solved iteratively.
The System Design Interview
System Design - Questions are used to assess a candidate's ability to combine knowledge, theory, experience and judgement toward solving a real-world engineering problem. In other words, can a candidate "design policies, processes, procedures, methods, tests, and/or components from the ground up.
Sample topics include: features sets, interfaces, class hierarchies, distributed systems, designing a system under certain constraints, simplicity, limitations, robustness and tradeoffs. You should also have an understanding of how the internet actually works and be familiar with the various pieces (routers, domain name servers, load balancers, firewalls, etc.). Other topics include: traverse a graphs, run-time complexity of graphs, distributed hash table system, resource estimation with real systems, big product design picture, translation of an abstract problem to a system, API discussions, binary trees, cache, mapreduce, for loop problems, index, reverse link-list, compilers, memory cache, networks and also common topics.
Operating Systems - You should understand processes, threads, concurrency issues, locks, mutexes, semaphores, monitors and how they all work. Understand deadlock, livelock and how to avoid them. Know what resources a process needs and a thread needs. Understand how context switching works, how it's initiated by the operating system and underlying hardware. Know a little about scheduling. We are rapidly moving towards multi-core, so know the fundamentals of "modern" concurrency constructs.
How to approach a system design interview question
The system design interview is an open-ended conversation. You are expected to lead it.
You can use the following steps to guide the discussion. To help solidify this process, work through the System design interview questions with solutions section using the following steps.
Step 1: Outline use cases, constraints, and assumptions
Gather requirements and scope the problem. Ask questions to clarify use cases and constraints. Discuss assumptions.
Who is going to use it?
How are they going to use it?
How many users are there?
What does the system do?
What are the inputs and outputs of the system?
How much data do we expect to handle?
How many requests per second do we expect?
What is the expected read to write ratio?
Step 2: Create a high level design
Outline a high level design with all important components.
Sketch the main components and connections
Justify your ideas
Step 3: Design core components
Dive into details for each core component. For example, if you were asked to design a url shortening service, discuss:
Generating and storing a hash of the full url
MD5 and Base62
Hash collisions
SQL or NoSQL
Database schema
Translating a hashed url to the full url
Database lookup
API and object-oriented design
Step 4: Scale the design
Identify and address bottlenecks, given the constraints. For example, do you need the following to address scalability issues?
Load balancer
Horizontal scaling
Caching
Database sharding
Discuss potential solutions and trade-offs. Everything is a trade-off. Address bottlenecks using principles of scalable system design.
Back-of-the-envelope calculations
You might be asked to do some estimates by hand. Refer to the Appendix for the following resources:
Use back of the envelope calculations
Powers of two table
Latency numbers every programmer should know
Practice: Cracking the Coding Interview, Top Coder, LeetCode, Stack Overflow, Project Euler
ENGINEERING ONSITE STUDY GUIDE:
1) What to Expect
Five, 45 minute technical interviews with an interviewer from Software Engineering. The interviewer will be interested in your knowledge of computer science principles and how they can be used in your solutions. Typically there is more than one question in each interview, make sure you keep on pace!
2) Interview Questions
Be ready to code on the white board. No laptop will be provided. Interview topics may cover anything on your resume, developing complex algorithms and analyzing their performance characteristics. Computer Science fundamentals are prerequisite for all engineering roles due to the complexities and global scale of the projects you would end up participating in.
3) How to succeed
We believe in collaboration and sharing ideas. Most importantly, you'll need more information from the interviewer to analyze and answer the question to its full extent. If there is anything you don’t understand - it is okay to ask your interviewer for help or clarification. Many of the questions asked in interviews are deliberately underspecified because our engineers are looking to see how you engage the problem. If you need to assume something - verbally check that it is a correct assumption. Always let your interviewer know what you are thinking as he/she is as interested in your thought process and how you approach the problem as the solution itself. If you're stuck, they may provide hints if they know what you're doing.
The Coding & Algorithm Interviews
Coding - You should know at least one programming language really well, preferably C++, Java, Python, Go, or C. You will be expected to know APIs, Object Oriented Design and Programming, how to test your code, as well as come up with corner cases and edge cases for code. Note that we focus on conceptual understanding rather than memorization.
Algorithms - Approach the problem with both bottom-up and top-down algorithms. You will be expected to know the complexity of an algorithm and how you can improve/change it. Algorithms that are used to solve problems include sorting (plus searching and binary search), divide-and-conquer, dynamic programming/memoization, greediness, recursion or algorithms linked to a specific data structure. Know Big-O notations (e.g. run time) and be ready to discuss complex algorithms like Dijkstra and A*. We recommend discussing or outlining the algorithm you have in mind before writing code.
Sorting - Be familiar with common sorting functions and on what kind of input data they’re efficient on or not. Think about efficiency means in terms of runtime and space used. For example, in exceptional cases insertion-sort or radix-sort are much better than the generic QuickSort/MergeSort/HeapSort answers.
Data structures - You should study up on as many data structures as possible. Data structures most frequently used are arrays, linked lists, stacks, queues, hash-sets, hash-maps, hash-tables, dictionary, trees and binary trees, heaps and graphs. You should know the data structure inside out, and what algorithms tend to go along with each data structure.
Mathematics - Some interviewers ask basic discrete math questions. This is more prevalent at Google than at other companies because counting problems, probability problems and other Discrete Math 101 situations surround us. Spend some time before the interview refreshing your memory on (or teaching yourself) the essentials of elementary probability theory and combinatorics. You should be familiar with n-choose-k problems and their ilk.
Graphs - Consider if a problem can be applied with graph algorithms like distance, search, connectivity, cycle-detection, etc. There are three basic ways to represent a graph in memory (objects and pointers, matrix, and adjacency list) — familiarize yourself with each representation and its pros and cons. You should know the basic graph traversal algorithms, breadth-first search and depth-first search. Know their computational complexity, their tradeoffs and how to implement them in real code.
Recursion - Many coding problems involve thinking recursively and potentially coding a recursive solution. Use recursion to find more elegant solutions to problems that can be solved iteratively.
The System Design Interview
System Design - Questions are used to assess a candidate's ability to combine knowledge, theory, experience and judgement toward solving a real-world engineering problem. In other words, can a candidate "design policies, processes, procedures, methods, tests, and/or components from the ground up.
Sample topics include: features sets, interfaces, class hierarchies, distributed systems, designing a system under certain constraints, simplicity, limitations, robustness and tradeoffs. You should also have an understanding of how the internet actually works and be familiar with the various pieces (routers, domain name servers, load balancers, firewalls, etc.). Other topics include: traverse a graphs, run-time complexity of graphs, distributed hash table system, resource estimation with real systems, big product design picture, translation of an abstract problem to a system, API discussions, binary trees, cache, mapreduce, for loop problems, index, reverse link-list, compilers, memory cache, networks and also common topics.
Operating Systems - You should understand processes, threads, concurrency issues, locks, mutexes, semaphores, monitors and how they all work. Understand deadlock, livelock and how to avoid them. Know what resources a process needs and a thread needs. Understand how context switching works, how it's initiated by the operating system and underlying hardware. Know a little about scheduling. We are rapidly moving towards multi-core, so know the fundamentals of "modern" concurrency constructs.
How to approach a system design interview question
The system design interview is an open-ended conversation. You are expected to lead it.
You can use the following steps to guide the discussion. To help solidify this process, work through the System design interview questions with solutions section using the following steps.
Step 1: Outline use cases, constraints, and assumptions
Gather requirements and scope the problem. Ask questions to clarify use cases and constraints. Discuss assumptions.
Who is going to use it?
How are they going to use it?
How many users are there?
What does the system do?
What are the inputs and outputs of the system?
How much data do we expect to handle?
How many requests per second do we expect?
What is the expected read to write ratio?
Step 2: Create a high level design
Outline a high level design with all important components.
Sketch the main components and connections
Justify your ideas
Step 3: Design core components
Dive into details for each core component. For example, if you were asked to design a url shortening service, discuss:
Generating and storing a hash of the full url
MD5 and Base62
Hash collisions
SQL or NoSQL
Database schema
Translating a hashed url to the full url
Database lookup
API and object-oriented design
Step 4: Scale the design
Identify and address bottlenecks, given the constraints. For example, do you need the following to address scalability issues?
Load balancer
Horizontal scaling
Caching
Database sharding
Discuss potential solutions and trade-offs. Everything is a trade-off. Address bottlenecks using principles of scalable system design.
Back-of-the-envelope calculations
You might be asked to do some estimates by hand. Refer to the Appendix for the following resources:
Use back of the envelope calculations
Powers of two table
Latency numbers every programmer should know
- 58
1条回复