Android programmer interview:

Android programmer interview will encounter algorithm (part 1 about binary tree that thing) attached Offer situation

Android Programmer Interview Algorithms (Part 2 Breadth-First Search)

Android Programmer Interview algorithms (Part 3 depth-first Search – Backtracking)

Android Programmer interview algorithms (Part 4 Message queue applications)

Algorithms encountered by Android Programmers (Part 5 Dictionary Tree)

Algorithms encountered by Android programmers (Part 6 PriorityQueue)

Algorithms encountered by Android Programmers (Part 7 Topological Sorting)

Last time we finished the binary tree topic analysis, we did a simple binary tree sequence traversal (breadth-first search) template code, we should remember, breadth-first to use the Queue, AKA -> Queue data structure to do. Let’s go over it again using Java pseudocode

public void levelTraverse(TreeNode root){
	if(root == null) {return;
    }
    // Initialize the queue
	Queue queue = new LinkedList();
    // queue the root node
    queue.add(root);
    // Start traversing the queue
    while(! queue.isEmpty()){ TreeNode current = queue.poll(); System.out.println(current.toString());// As long as the left and right nodes of the current node are not empty, we can add them to the end of the queue and wait for the next iteration, we continue the while loop
        if(current.left ! =null){
        	queue.add(current.left);
        }
        if(current.right ! =null){ queue.add(current.right); }}}Copy the code

As we can see from the template code above, the core of breadth-first search is to use the Queue to do a while loop, in which in addition to processing the current node, the child node of the current node needs to be placed at the end of the Queue. So we have a simple breadth-first search.

It’s that simple!

So, the question is, given that the core part is so simple, what are the applications of breadth-first search?

The focus of today’s article is on common problems that can be solved with breadth-first search.

1. How many friend questions?

Those of you who are familiar with social networking sites will find that they often give you recommendations for potential friends, as well as “friendship” hints on how to recommend them. Here we focus on the recommendation mode of several degrees of friends.

As the name suggests, the number of degrees of friends represents the number of degrees between the user and you, that is, how many people. Stanley Milgram, a professor of psychology at Harvard University, came up with something called the six degrees of separation theory, where each person is only six people away from another random stranger. That means there could be six people between you and Donald Trump.

Ok, so much background, we can start to think about a problem, if we already have friends related information, how does the recommendation system find the corresponding degree of friends?

Here’s an example. Renren now wants to recommend a user to put his friends within 3 degrees in the recommendation bar, how do we get it?

Post the user’s data structure first

public class User{

	// Friends are direct friends of the user.
	private List<User> friends;
    private String name;
    
    // Get the list of friends
    public List<User> getFriends(a){
    	return Collections.unmodifiableList(friends);
    }
    
    public String getUserName(a){
    	returnname; }}Copy the code

Assume that we have such a good friend structure in our memory, in the actual scene, of course, we can’t all of a social network user information existing in Ram, it’s not reality, but to find several friends principle must be the same, just get the user information in a distributed scenario process a lot more complicated). Each User has a List called Friends to save their immediate friends.

Based on the above conditions, we can think of it as follows: Is the degree of the friend that we need to find actually the level of the sequence traversal? Isn’t x degree of difficulty x level? With this information, we know that with a few tweaks to the breadth-first template code above, we can get friends up to level X (x degrees).

public List<User> getXDegreeFriends(User user, int degree){
      List<User> results = new ArrayList<User>();
      Queue<User> queue = new LinkedList<User>();
      queue.add(user);
      // This is used to record users that have been traversed. Since A is A friend of B, B must also be A friend of A. They are in each other's friends list.
      HashSet<User> visited = new HashSet<User>();
      // Use a counter to record the current level.
      int count = degree;
      // The two conditions that end the while loop are the number of layers and whether the queue is empty, in case the current user doesn't have that many layers of the social network (e.g., he doesn't have any friends at all).
      while(count>=1 && !queue.isEmpty()){
          int queueSize = queue.size();
          for(int i = 0 ; i < queueSize; i++){
              User currentUser = queue.poll();
              // If the user has already traversed, then no processing is done.
              if(! visited.contains(currentUser)){ results.add(currentUser); queue.addAll(currentUser.getFriends(); visited.add(currentUser); } } count--; }return results;
}
Copy the code

It’s that simple! By Queue, we successfully pack all x degree friends of a User into a Queue and return them, thus completing a simple friend recommendation method!! .

And one small detail is that we’re using the HashSet data structure for rehash. Why do we have to go that extra step? Whether it is breadth-first or depth-first search, this step can be said to be the most important, because when we traverse nodes, we will encounter repeated traversal nodes. Such as:

Users A and B are friends of each other, so their getFriends() method returns each other.

Assuming we don’t use A de-weighted data structure in our code, the first step to put A will return B to join the queue, and the second step to call B’s getFriends() will return A… So the program would go on indefinitely, and the number of layers would not be correct. So the nodes that we walk through, we have to have some way of saving their information so that we don’t walk through them again.

2. Maze problem (shortest distance problem).

In terms of the shortest distance, the first thing we think of is the Dijtsla algorithm.

In a directed graph or undirected graph, each node has a different weight between nodes (can be understood as distance), and finally calculate the shortest distance between each point and its corresponding path.

This time we’re going to study a special case of this algorithm. That is, if the weights between nodes are equal, but there may be obstacles.

The classic is the maze problem.

Suppose that a two-dimensional integer matrix represents a maze, 0 represents a path, 1 represents a wall (you can’t walk through it), the upper left corner is the entrance, and the lower right corner is the exit (both guaranteed to be 0). Find the minimum number of steps required to get to the exit.

We also need to treat this problem with breadth first. Why is that?

Because for every node, go one layer is to step down (everyone equal distance weights), so we are in the process of mazes is actually like a decision tree, each layer need only one step to go out, so the steps, at the end of is actually depends on the end which layer of the node in the tree structure. The end point is at level X, which means it takes at least x steps to get there.

For example, in the figure above, starting from A, there are 1 layers to other nodes: B, C, D, 2 layers: F, E, 3 layers: H,G, 4 layers: I, and their corresponding distance from A is the number of layers.

Therefore, when solving the distance of a maze problem, we can do breadth-first traversal from the starting point, and keep track of the current number of layers. When we reach the end of the traversal, we can check the number of layers already traversed, which is also the number of steps.

public int getMinSteps(int[][] matrix) {

		int row = matrix.length;
		int col = matrix[0].length;
		// The maze can go in four directions. This two-dimensional array represents the offsets of x and y in four directions
		int[][] direction = { { 0.1 }, { 1.0 }, { 0, -1}, {-1.0}}; HashSet<Integer> visited =new HashSet<>();
		Queue<Integer> queue = new LinkedList<>();
		// Add the starting point to the queue
		queue.add(0);
		int level = 0;
		while(! queue.isEmpty()) {// Iterate over all nodes of the layer
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				int current = queue.poll();
				if(! visited.contains(current)) { visited.add(current);// Determine the x and y coordinates of this node
					int currentX = current / col;
					int currentY = current % col;
					// If this point is the key, then return level directly
					if (currentX == matrix.length - 1 && currentY == matrix[0].length - 1) {
						return level;
					}
					// If it is not, then we try to add each node in its four directions to the end of the queue, i.e. the next layer
					for (int j = 0; j < direction.length; j++) {
						int tempX = currentX + direction[j][0];
						int tempY = currentY + direction[j][1];
						// Since 1 stands for wall, we can't go, we can only add the point 0
						if (tempX > -1 && tempY > -1&& tempX <row&& tempY < col&& matrix[tempX][tempY] ! =1) {
							int code = tempX * col + tempY;
							queue.add(code);
						}
					}
				}
			}
			level++;
		}
		return -1;
	}

Copy the code

The code above is simple to solve the maze problem of shortest path, at the same time will also help determine the maze is there a feasible path to export (the above method will return 1 if no path), because the method in the while loop, all can traverse points from the starting point after traversal, we have not found the lower right corner point, The while loop ends.

3. Multi-end breadth first search.

Multi-end breadth-first search is similar to the previous maze problem, we just need to change the above conditions.

If there is more than one exit in the maze, how can we find the shortest path to any exit starting from the exit (the point 0,0)?

Some friends might say, well, let’s say I have K exits, so I’m just going to run the maze K times, comparing the shortest paths. Let’s say we have MN nodes, and that’s order km times n. Is there a faster way?

We can try to think of it the other way around. We used to do breadth-first search from a starting point. For multi-point problems, can’t we use the points as the starting point, join the queue, and keep updating the weight of the road until we find the starting point?

I’m not going to go into this algorithm, but if you’re interested, check out Gates and Wall in Leetcode

The answer is here

That’s all for today’s article, and the next installment will focus on a depth-first backtracking algorithm.