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)
It has been a year of ups and downs, but fortunately it has a happy ending. At the beginning of the New Year, due to a dispute with the company’S CTO, I was “put into the cold palace”. In the second half of the year, I began to look for a job, but the process was still quite difficult. First share the situation of offer
Domestic have
1. Offer from Ali
2.Wish(offer)
3.Booking(Offer)
4. Offer
5. 5. Smart refrigerator
What makes me most happy is that I got the offer from Silicon Valley!
An offer from FaceBook’s Menlo Park headquarters
Amazon Seattle headquarters offer
In the process of the interview, I deeply felt that for an excellent Android developer, the first thing is his/her basic quality as a software engineer. Whether you’re working on the front end or the back end, what defines you as good as a software engineer is the basics, the ability to learn, the ability to program, the ability to design. I also worked as an interviewer in my current company, and found that most of the code farmers in Singapore (southeast Asia) were really lacking in basic programming ability, and could not understand why they were proficient in using API.
Many students will get lost in the business logic development for a long time, and gradually become a habit of writing code, without thinking about the optimization of their own code, structure adjustment. This phenomenon is not only experienced by android developers, but also by any large company friends. So this series of articles is going to take a closer look at the algorithms you might encounter in an Android programmer interview. I also hope to cultivate the habit of thinking more and writing good code in your spare time.
So in the first chapter I’m going to focus on binary trees.
1. Recursive (depth-first) processing of binary trees
I’m sure you’ve seen this before in algorithms and data structures. For example, printing the first, middle, and last strings of a binary tree. Normally we would choose to print recursively, for example
/** ** binary tree node **/
public class TreeNode{
TreeNode left;
TreeNode Right;
int value;
}
/ / in the sequence
public void printInoderTree(TreeNode root){
//base case
if(root == null) {return;
}
// Recursively call printTree
printInoderTree(root.left);
System.out.println(root.val);
printInoderTree(root.right);
}
/ / in the sequence
public void printPreoderTree(TreeNode root){
//base case
if(root == null) {return;
}
// Recursively call printTree
System.out.println(root.val);
printPreoderTree(root.left);
printPreoderTree(root.right);
}
Copy the codeWhen I first went to school, I memorized these codes and didn’t understand them at all. The correct way to think about recursive operations on binary trees
- Think of each recursion as an operation on its subset (left and right subtrees), assuming that the recursion can already handle the left and right subtrees, then adjust the root node based on the left and right subtrees already handled.
In fact, this idea is similar to the divide-and-conquer method, which is to divide a big problem into smaller problems and then solve them. Let’s take the middle-order printing of a binary tree as an example.
For middle-order printing, we need to print binary trees in left-middle-right order. The following picture shows an example to break down the problem.
The GIF above explains divide-and-conquer in detail. First, we assume that the left and right subtrees of node A are separated and printed, so that only node A needs to be processed separately. For the B subtree, we do the same thing. So in the GIF, we have the B subtree, and then we go to the A node, and then we go to the C subtree.
And then finally we need to think about the end condition of this recurrence. We assume that both the left and right subtrees of Node A are empty, null, so when we call this method we need to return nothing when Node is empty. This condition is commonly referred to as a recursive Base Case. So every recursion is like this, first we figure out how we’re going to divide and conquer, then we figure out what the base cases are, what we’re going to do, and then we’re done with our recursion.
So the question is, why are we talking about recursion when we’re talking about depth first? What’s the connection?
In fact, recursion is depth-first for many data structures, such as binary trees, graphs. Because when we recurse, we go down layer by layer, so for example, for middle order printing in a binary tree, the left node of our recursion tree, unless the left node is empty, we go down, which is depth-first. So in general, for depth-first, we do recursion, because it’s the easiest thing to write. If you don’t want to use recursion, you can also use a Stack to solve the problem, which we will discuss in a future article.
Good! I’m sure I’ve already reminded you of your algorithms class in college! So let’s consolidate. Using divide-and-conquer plus recursion, we can already solve most binary tree problems. Let’s look at a topic ->
1.1 Flipping the binary Tree
This is a classic question. The author of HomeBrew, a famous software for Mac, was once asked in an interview with Google. He did not make it, so he was finally rejected. He took to his twitter account to complain:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
Eventually the focus shifted from the author’s rejection to the title… So let’s see how hard this is.
Before the turn
After the turn over
As cumbersome as it may seem, each subtree itself is flipped. But let’s use divide-and-conquer thinking, let’s say we have a function that flips binary trees. If we flip the B subtree, and then flip the C subtree, then all we have to do is simply assign the left of A node to C, and the right of A node to B. Would that solve the problem?
We can use the same divide-and-conquer thinking to recursively solve B and C. Describe it in a piece of code
public TreeNode reverseBinaryTree(TreeNode root){
// Handle base case first, when root ==null, do nothing, return null pointer
if(root == null) {return null;
}
else{
// Invert the left subtree
TreeNode left = reverseBinaryTree(root.left);
// Invert the right subtree
TreeNode right = reverseBinaryTree(root.right);
// Assign the left and right subtrees to the root node, but in reverse order
root.left = right;
root.right = left;
// return the root node
returnroot; }}Copy the codeAccording to the example, coupled with the order of the topic, we should have been able to easily understand, for questions or algorithm of binary tree, divide and conquer and recursive core idea, is to separate the left and right subtrees processing, finally in combine the results (the processing good around a tree corresponding to the root node for processing).
So let’s do a slightly more complicated problem
1.2 Smooth the binary tree
For this problem we need to turn a binary tree into something like a linked list, where all the children are moved to the right node, for example.
After the transformation
As you can see, the process of paving the binary tree is to first pave the left subtree and link it to the right node of the root node, and then pave the right subtree and link it to the last node of the left subtree. Finally, the root node is returned. So what we need to do from a macro point of view is to smooth out the left and right subtrees.
Suppose we have a method called flatten() that flattens a binary tree and returns the root node
public TreeNode flatten(TreeNode root){}Copy the codeSo from a macro point of view, we are done with the smoothing operation!! Next is the second step, again with an animation to illustrate the process.
The final code is as follows, with a comment
public TreeNode flatten(TreeNode root){
//base case
if(root == null) {return null;
}
else{
// Use the recursive idea of smoothing left and right first
TreeNode left = flatten(root.left);
TreeNode right = flatten(root.right);
// set the left and right Pointers to null.
root.left = null;
root.right = null;
// If the list generated by the left subtree is empty, it is ignored and the list generated by the right subtree points to the right pointer of the root node
if(left == null){
root.right = right;
return root;
}
// If the left subtree generated list is not empty, then use the while loop to get the last node, and its right pointer to the right subtree generated list head node
root.right = left;
TreeNode lastLeft = left;
while(lastLeft ! =null&& lastLeft.right ! =null){
lastLeft = lastLeft.right;
}
lastLeft.right = right;
returnroot; }}Copy the codeSo now that we’re done with this problem, hopefully you’ll have a good idea of what we call divide-and-conquer and how we handle left and right subtrees recursively in binary trees. Most of the binary tree algorithm is around this idea as the center, as long as from the macro to the left and right sub-tree processing logic to think clearly, then it is not difficult to solve.
1.3 Android development encountered tree structure?
Do we have a similar problem with Android development? Or is there going to be a tree algorithm in Android development?
The answer is yes!
FindViewById (int Id); findViewById(int Id); findViewById(int Id); How do we find and return the View that we’re looking for under the current ViewGroup?
This is also one of my favorite questions to ask candidates who apply to our company, but unfortunately, there is only one question I have been able to complete so far. (Again, we can see the level of southeast Asian developers.
So here’s the problem
Please complete the following method
// Return a View under vg with id as the second argument to the method
public static View find(ViewGroup vg, int id){}Copy the codeThe methods you can use are:
View -> getId()Return the id of an intViewGroup -> getChildCount()Returns the number of children in an intViewGroup -> getChildAt(int index)Returns a child with the return value View.
In the past, we did a binary tree, except left and right, but here we can have multiple children in each ViewGroup, and each child can be either a ViewGroup or just a View(ViewGroup is a subclass of View, Here is a knowledge point!
I’m not going to explain too much here, I’m going to post the code, and android itself does View lookup in this way.
// Return a View under vg with id as the second argument to the method
public static View find(ViewGroup vg, int id){
if(vg == null) return null;
int size = vg.getChildCount();
// Loop through all the children
for(int i = 0; i< size ; i++){ View v = vg.getChildAt(i);// If the current child id is the same, then return
if(v.getId == id) return v;
// If the current child id is different, but it is a ViewGroup, then we recurse down
if(v instance of ViewGroup){
/ / recursion
View temp = find((ViewGroup)v,id);
// If found, return temp. If not, continue the current for loop
if(temp ! =null) {returntemp; }}}The ViewGroup vg does not contain a child with this id
return null;
}
Copy the code2. Binary tree sequence processing (breadth first)
When you think of breadth first, most of you might think of graphs, but after all, a tree structure is a special kind of graph. So when we talk about trees in general, and especially binary trees in general we’re talking about sequence traversal.
Such as tree
The sequence print is A->B->C->D->D->E->F->G
For the correlation algorithm of sequential traversal, there is only one truth!
Is to useQueue (Queue)!
The idea is simple: each time the current node is traversed, take it out of the queue and add all of its children to the queue. over~
Here’s a simple print code
public void printTree(TreeNode root){
if(root == null) {return;
}
Queue queue = new LinkedList();
queue.add(root);
while(! queue.isEmpty()){ TreeNode current = queue.poll(); System.out.println(current.toString());if(current.left ! =null){
queue.add(current.left);
}
if(current.right ! =null){ queue.add(current.right); }}}Copy the codeThis code is very simple, using the first in, first out nature of the queue, we can print the nodes of the binary tree layer by layer.
So for the sequential traversal of binary trees, queues are generally used, which is routine. Therefore, binary tree sequence traversal is relatively simple, we see the next binary tree sequence traversal related interview questions, first bold and the interviewer say you plan to use a queue, certainly right!
Finally for the sequence traversal said that we come to a more representative topic!
2.1 Link the Next node in the binary tree
In addition to having Pointers to the left and right nodes of a binary tree node, you need to help it find the node to which its next pointer points.
It goes something like this:
In the figure above, the red arrow represents the point of the next pointer
The logic is simple: The next of each node points to the next node in the same layer, but if that node is the last node in the current layer, do not set next, or next is empty.
In fact, this problem is a typical sequence traversal, which can be easily solved by using a queue. Each time a node is polled, it can determine whether it is the last node of the current layer. If not, it can be set next to the next node in the queue. How do you determine which layer the node is at? Here’s a little trick: do a for loop with the size of the current queue and look at the code
public void nextSibiling(TreeNode node){
if(node == null) {return;
}
Queue queue = new LinkedList();
queue.add(node);
// This level is not really useful, but it can tell you how to determine the current node level.
int level = 0;
while(! queue.isEmpty()){int size = queue.size();
// With this for loop, I can ensure that no matter how many children I add to the queue, I only process nodes in the current layer
for(int i = 0; i<size; i++){// Take the current first node out
TreeNode current = queue.poll();
// Add child nodes to queue
if(current.left ! =null){
queue.add(current.left);
}
if(current.right ! =null){
queue.add(current.right);
}
if(i ! = size -1) {// Peek just gets the first node in the current queue, but does not remove it from the queuecurrent.next = queue.peek(); } } } level++; }}Copy the codeThat’s about it, and I’ll go into depth first and breadth first algorithms in the next article. Depth-first is a very, very broad knowledge point that is difficult to master completely. I will cover all depth-first basic questions in detail, including tree, depth-first search of graph, back of set and so on.
Part2: Algorithms encountered in Android Programmer Interviews (Part2 Breadth-first Search)
Topic link
- Flatten the binary tree
- Flip the binary tree