Boy juice, what do you want to knock the socks off the magic, better ask yourself:

Did you swipe LeetCode today? Do you still feel like a SB after reading the title? Do you have any ideas about hard problems?

You see, rather than tangle with those amazing strange techniques, it is better to do a good job, do right, do thoroughly.

I worked as an interviewer at Facebook North America, brushing over 2,500 questions and interviewing over 300 people. Facebook’s coding exam is known for being difficult. During this process, I summarized many skills and helped hundreds of students get on the beach. Next, I’ll go from simple to profound, and give you algorithmic solutions that interviewers will say “wow.”

Start with a simple graph clone problem and see how a small improvement can make a big difference in your problem-solving process.

This question has been asked 100+ times in Facebook interviews, and most people give me the answer

  • The code to the right of the BFS width-first search algorithm is used
  • Do a width-first search and find all the points
  • And then I copy all the points
  • One side copies all the edges
  • And when you copy edges, you copy points

The code process is as follows:

Of course, the resulting code will run, but in practice it will run into a lot of problems, not to mention wow.

I give a better way to do this, breaking the algorithm down into three steps:

  • Find all the points
  • Copy all points
  • Copy all edges

Make your code more readable and maintainable by decoupling it. The final code can be optimized to look like this:

If you’re interested, we can keep going.

In fact, 80% of the topics can be realized by summarizing the law – coding code template – brute force cracking – step by step optimization.

It is recommended that beginners brush the problem according to the algorithm and data structure of the knowledge point classification to brush, brush more later slowly can find the characteristics of this kind of problem, and the corresponding solution method and solution ideas, the interview problem can be solved, I will present a ugly.

Binary search tree non-recursive BST Iterator

Step one, open LintCode. Filter the data structures and algorithms you want to conquer:

The conditions for non-recursive use of binary search tree summarized by me include:

  • The middle order traversal of binary tree is realized by non-recursion/Iteration
  • Often used for BST but not only for BST

The complexity of the

  • Time complexity O(n)
  • Space complexity O(n)

The code template

Java version

List<TreeNode> inorderTraversal(TreeNode root) { List<TreeNode> inorder = new ArrayList<>(); if (root == null) { return inorder; Dummy = new TreeNode(0);} // create a dummy node with the right pointer to root and place it in the stack. dummy.right = root; Stack<TreeNode> stack = new Stack<>(); stack.push(dummy); // Each time the iterator moves to the next point // adjust the stack so that the top is the next point while (! stack.isEmpty()) { TreeNode node = stack.pop(); if (node.right ! = null) { node = node.right; while (node ! = null) { stack.push(node); node = node.left; } } if (! stack.isEmpty()) { inorder.add(stack.peek()); } } return inorder; }Copy the code

Python version

def inorder_traversal(root): if root is None: Return [] # create a dummy node with a right pointer to root # and place it in the stack. Dummy = TreeNode(0) dummy. Right = root stack = [dummy] inorder = [] # iterator While stack: node = stack.pop() if node.right: node = node.right while node: stack.append(node) node = node.left if stack: inorder.append(stack[-1]) return inorderCopy the code

Do not understand, it is suggested to take this template to practice. Let’s go again:

Width first search BFS

Width-first search is more widely used, using conditions:

  • Topological sort (100%)
  • Keywords with connected blocks (100%)
  • Layered traversal (100%)
  • Simple graph shortest path (100%)
  • Given a transformation rule, at least a few steps from the initial state to the final state (100%)

The complexity of the

  • Time complexity: O(n + m)
  • N is the number of points, m is the number of edges
  • Space complexity: O(n)

The code template

Java version

ReturnType BFS (Node startNode) {// BFS must use queue, not stack! Queue<Node> queue = new ArrayDeque<>(); // A hashmap has two functions, one is to record whether a point has been thrown into the queue, to avoid repeated access // another is to record the shortest distance from startNode to all other nodes // If only for connectivity, // node < node, Integer> distance = new HashMap<>(); Queue.offer (startNode); // Put the starting point in the queue and hash table. distance.put(startNode, 0); // or 1 if necessary // while the queue is not empty, take out a point from the queue, expand the neighbor node into the queue. queue.isEmpty()) { Node node = queue.poll(); If (node is terminal) {break or return something; } for (Node neighbor : node.getNeighbors()) { if (distance.containsKey(neighbor)) { continue; } queue.offer(neighbor); distance.put(neighbor, distance.get(node) + 1); Return hashmap return distance if you want to return the distance between all points and the starting point; // To return all connected nodes, return distance.keyset () for all points in the HashMap; Return distance.get(endNode); // Return distance.get(endNode); }Copy the code

Python version

Def BFS (start_node): def BFS (start_node): Def BFS (start_node) def BFS (start_node) def BFS (start_node) # BFS must queue, not stack! Distance (dict) is used to record whether a point has been enqueued to avoid repeated visits. Distance (dict) is used to record the shortest distance between a start_node and all other nodes. Queue = collections.deque([start_node]) distance = {start_node: distance = {start_node: 0} # while queue: node = queue.popleft() # while node = queue. Popleft () # while node = queue. break or return something for neighbor in node.get_neighbors(): if neighor in distnace: Continue queue.append(neighbor) distance[neighbor] = distance[node] + 1 Return hashmap return distance # if you want to return all connected nodes, Return distance.keys() # return distance[end_node]Copy the code

If you want more, one more.

Depth-first search DFS

Conditions of use

① Find all solutions that satisfy a certain condition (99%)

The Binary Tree is a Binary Tree.

③ Combination problems (95%)

  • Problem model: Find all the “combinations” that satisfy the conditions
  • Judgment criteria: Elements in a combination are order independent

④ Arrangement problem (95%)

  • Problem model: Find all permutations that meet the criteria
  • Judgment criteria: The elements in the combination are sequentially “related”.

It is worth noting that there are also scenarios where DFS is not used:

  • Connected block problem (always use BFS or StackOverflow)
  • Topological sort (always use BFS or StackOverflow)
  • Everything BFS can solve

The complexity of the

Time complexity:

O(Number of schemes * time to construct each scheme)

  • Tree traversal: O(n)
  • Permutation problem: O(n! * n)
  • Combinatorial problem: O(2^n * n)

The code template

Java version

Public ReturnType DFS (argument list) {if (recursive exit) {record the answer; return; } for (all disassembly possibilities) {modify all parameters DFS (parameter list); } return something if necessary, there is no need to return something except divide-and-conquer.Copy the code

Python version

Def DFS (argument list): if recursive exit: record answer return for all possible disassembly: Change all parameters DFS (parameter list) Restore all parameters that have been modified. Return Something If necessary, most of the time you do not need a return value other than divide-and-conquerCopy the code

Many people will say: there are so many knowledge points about algorithms and data structures, do I have to master them all? Don’t panic, for this year’s spring recruitment algorithm interview investigation, I sorted out the algorithm and data structure of the high frequency test points, the more red color test more, gray does not test or the probability of less than one thousand.

For those who are pressed for time, brush the knowledge points with the deepest colors.

Finally, I would like to say that if you want to get the solution that makes others wrave, you can only brush the questions diligently, brush the questions, and brush the questions again. Whether it is to find the fun of brushing the questions, or to obtain a unique way of solving the questions, you need to pay more hard efforts than anyone else behind the success.

Of course, I must be very responsible to say that in an interview, it is not only good coding that can pass the interview, but also 100% of you can pass the interview even if you use code templates and algorithm questions. Communication with the interviewer is also important.