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)

This is the last one of the android algorithm interview series that I plan to do. Firstly, since I came to the United States, I have been so busy with work every day that I have little time to summarize something completely except weekends. But the second reason, and the most important reason, is that AFTER this I plan to accumulate a good precipitation, and then share more experience.

In this video I’m going to talk a little bit about topological sorting. Specific implementation and some details in Java. I try not to use too many technical terms here, but to explain some concepts in a more general way. (Actually, my dog’s mouth can’t spit anything… I have already returned my algorithm knowledge to my teacher.

In fact, topological sorting and breadth-first search algorithm are really similar in code, in fact, graph traversal, but the traversal order and rules are slightly different.

I believe that all computer science students should have a deep shadow of advanced mathematics or college physics… I still remember that I felt that I was going to fail after taking the college Physics 2, so I couldn’t resist making a call to the teacher to beg for help. Although the teacher said that I was far from failing in the end, the 69 points in the college Physics 2 also made me lose the scholarship for that semester.

Some people may ask why computer majors do not directly learn Java, C++ or web development? Must go to college physics or advanced mathematics first? Having said so much nonsense, the point I want to make is that each subject has its own curriculum arrangement, and some basic courses must be supported before learning a specialized course. We can’t skip to machine learning without learning advanced math and linear algebra, and we can’t jump to Web projects without learning Java or Python. This leads to this installment, topology sorting, on how to list the order of prerequisites for certain nodes given that they are known. For example, if I know the sequence of certain courses, I will arrange the time schedule of my four years in college and print it into a class schedule.

For example, in the picture above, how can we smoothly arrange the dependencies of its courses in order of precedence? This is one of the problems that can be solved by topological ordering, which is also the most classic problem.

1. How do you define data structures

First of all, for the graph, we need to know how many children, or successor nodes, each node has, which in the course arrangement example can be understood as the course B that can be learned after learning course A. So A is the precursor of B, and B is the successor of A. In Java we can do this using HashMap, or, depending on the topic, other data structures such as two-dimensional arrays. But I personally like HashMap.

So the relationship of nodes can be represented by a HashMap, and the course uses a String

// The successor node of the node
HashMap<String, HashSet<String>>  courses = new HashMap();

Copy the code

Also, in topological sorting, we also need to record the number of forerunners of a node, because we can only process a node if its forerunner is 0. Corresponding to course learning, that is, only when we have learned all the precursor courses of a course, we can learn the course. For example, the computer networking course in the picture requires the same principles of composition and communication.

// Record the number of precursor nodes at each point
HashMap<String,Integer> preCount = new HashMap<String,Integer>
Copy the code

2. Topology sort

Suppose we have these two data structures and the data is already populated. So we can start doing topological sorting. The algorithm is very simple, put the node with the number of precursor nodes 0 into the queue first, and reduce the preCount of its successor nodes by 1 each time it is ejected from the queue. If the preCount of successor nodes is reduced to 0, the node is added to the queue. In this case, the point of popping up a node is to learn a course.

This is easy to understand, for example, after we have studied the principles of composition, we are one class away from learning computer networks.

When we finish learning the principle of communication, the number of precursor nodes of the computer network is reduced from 1 to 0, we can learn the computer network.

In code, it looks like this

Queue<String> Queue = new LinkedList<>(); List<String> sequence = new ArrayList<>();while(! Queue.isempty ()) {String currentCourse = queue.poll(); String currentCourse = queue.poll(); sequence.add(currentCourse); // When a course is finished, find its successorfor(String course: courses.get(currentCourse)) {// The number of previous nodes is greater than 0, indicating that the course has not been learnedifPreCount. Put (course, preCount. Get (course) -1); // If it goes to 0, we can start the course, // add it to the queueif(preCount.get(course) == 0) { queue.add(course); }}}}return sequence;
Copy the code

3. Different from breadth first

As you can see from the code, topological sort is a kind of breadth-first search, but there are some restrictions on how children can be inserted into the queue. Here it is:

 if (preCount.get(course) == 0) {
                        queue.add(course);
                    }

Copy the code

In the general breadth-first method, all the nodes of the current node are inserted into the queue once the current node is traversed. In topological sorting, since the number of precursor nodes per node may be greater than one, it is not possible to simply insert child nodes (or successors), but rather requires an additional data structure, the preCount HashMap, to determine whether the successors can be inserted.

4. A ring?

One of the classic questions in graph search is, what if there are rings? Similarly, in topological sort, it is possible to have rings. Such as

In this case, students can’t learn…

However, under topological sorting, the method of judging whether there is a ring is not quite the same. For example, in the case of width-first search, we can use a HashSet called Visited to record the nodes that have been visited. But topological sort doesn’t work.

Take the picture below

After we have learned A, we can’t actually go through all the nodes, because B and C both have one precursor node, and the program is running through the first loop

  while(! Queue. IsEmpty ()) {// get A String currentCourse = queue. Poll (); sequence.add(currentCourse);Copy the code

After that, it will be straight over. So the way we actually judge rings is — > whether we can get through all the lessons.

HashMap<String, HashSet<String>> courses = new HashMap(); // Suppose we finish all the lessons in the endif(result.size() == course.keySet().size()){
     return true;
}else{
     return false;
}

Copy the code

5. Scope of application

Topological sorting can appear many kinds of topics, but are all the same, we need to master the data structure, skilled write breadth-first algorithm template code, in fact, everything is ok. In the future, there will be similar problems, such as software installation, such as to install A, to install dependency C, etc., and so on, I believe we can be easily solved. In summary, once we find that we need to sort between dependencies, there is nothing wrong with using topology sorting.

6. Topic code

The Course Schedule in Leetcode, you can practice it yourself. The part THAT I didn’t talk about is the data initialization part, but it’s pretty easy to figure it out. My answer

public int[] findOrder(int numCourses, int[][] prerequisites) {
		// record dependecy counts
		HashMap<Integer, Integer> dependeciesCount = new HashMap<>();
		HashMap<Integer, HashSet<Integer>> dependeciesRelation = new HashMap<>();
		for (int i = 0; i < numCourses; i++) {
			dependeciesCount.put(i, 0);
			dependeciesRelation.put(i, new HashSet<>());
		}
		for (int i = 0; i < prerequisites.length; i++) {
			int pre = prerequisites[i][1];
			int suf = prerequisites[i][0];
			dependeciesCount.put(suf, dependeciesCount.get(suf) + 1);
			dependeciesRelation.get(pre).add(suf);
		}
		Queue<Integer> queue = new LinkedList<>();
		for (Map.Entry<Integer, Integer> entry : dependeciesCount.entrySet()) {
			if (entry.getValue() == 0) { queue.add(entry.getKey()); }}int[] index = new int[numCourses];
		int currentIndex = 0;
		while(! queue.isEmpty()) { Integer currentCourse = queue.poll(); index[currentIndex] = currentCourse; currentIndex++;for (Integer nei : dependeciesRelation.get(currentCourse)) {
				if (dependeciesCount.get(nei) > 0) {
					dependeciesCount.put(nei, dependeciesCount.get(nei) - 1);
					if (dependeciesCount.get(nei) == 0) { queue.add(nei); }}}}int[] empty = {};
		return currentIndex == numCourses ? index : empty;
	}
Copy the code

Afterword.

The last algorithm tutorial is finished, in fact, I feel that if we can fully understand these 7 blocks, facing most of the company’s algorithm interview is not much of a problem. This is also my experience of interviewing algorithm questions of various companies from 2017 to 2018. Although my title always starts with an interview, I think the most important thing is the process of learning, or reviewing algorithms. The process of understanding and learning is the essence. Of course, these content is also to go to school should learn well, review afresh now, also be to repay debt (technical debt)… The original intention of looking back at this series is to hope that you can review some of the knowledge you learned in school while facing the interview, so that you can learn something new by reviewing the past. As long as the reader saw my article, can issue a kind of “dig groove this seems to have learned before” exclamation, I also satisfied ~

2019 is a new starting point for me, and I will keep urging myself to work hard, reflect more and learn more, and strive to share more high-quality articles and knowledge in the future. I hope I never forget my ambition to interview silicon Valley companies.