background

I had met the first two sides of ali CBU department before, and then the interviewer called me and said that I needed to do a written test, which lasted 30 minutes and consisted of one question (maybe I had not been asked algorithm questions in the interview before).

The written test was conducted on Ali’s Bole system yesterday (March 11), and the interviewers called first. Here is more embarrassing is that I was sitting in front of the computer water group, typing time do not hang up the phone for the first time… Fortunately, the interviewer followed up right away. Then while we were on the phone, he sent me the link of the written test and posted the questions after entering. Here is a general description of the topic, I don’t remember very clearly.

Here are a few points of the Bole system:

  • Autocomplete is not supported, in other words, if you’re not highlighting code you’re writing code in Notepad
  • Unable to compile and run
  • The video that the interviewer told me was on or off

Topic describes

N strings of the form “stringA, stringB”, indicating that there is some kind of relationship between the two strings, which can be passed, and finally m questions “stringA? StringB “to determine whether stringA is related to stringB. In other words, if A is related to B, and B is related to C, then A is related to C.

My process

I guess this is probably the original leetcode, but I haven’t done much leetcode (no more than 40 lines in total) so I haven’t seen it. If a and B are related, there is an edge between a and B, and then the adjacency matrix is used to store the graph. Because the first point is the correctness of thinking, the second point is speed. “And then I ran Floyd and it was almost done. It takes, like, a few minutes.

After writing, the interviewer asked me to talk about the thought and time complexity. I said that this problem could be extended to the graph’s reachable path, and I just needed to change the shortest circuit. Because I used Floyd here, the time complexity was O (), the minimum time complexity of the shortest circuit can reach O (), but I didn’t write that one because it required a heap. The Floyd used here is realized based on the idea of dynamic programming, and then Blabla introduces dynamic programming and Floyd. The interviewer told me that I thought of the complex, if not reachable path this way should be how to deal with, about 30 seconds, thought of using and search set to do this problem (and search set, the query time complexity O (1), I think this is the optimal solution because it needs to deal with the input). And blabla did a bunch of them and looked them up and said somethingAccording to the rank mergerandPath to the compressionA wave of time complexity is analyzed. Because the time complexity of the union lookup is obtained by amortization analysis, the asymptotic curve of the final value isAnti-ackerman function[1]It’s only about 4 million times, so the general assumption is that the query time to look up the set is O (1), and then let me write it roughly. Write in about 1 minute (and look up the set code very short, path compression 3 lines, merge 4 lines). The interviewer didn’t say anything. And then he asked me if there was another way to do it, and then he said I could DFS and label it, but it’s the same idea but in a different way.

It is important to note that I normally written in c + + algorithm problem more (more cleanliness, don’t like algorithm written in Java, it is too much trouble to write so I this interview is written in c + +, then the interviewer can ask me through some kind of data structure to solve this problem, in the Java that didn’t think of a better container classes, he said that he didn’t know.

A little experience

  • When writing a paper, forget about the optimal solution, the priority is to solve the problem at the lowest complexity you can think of. If you can’t solve the problem, it doesn’t matter if you have all kinds of optimizations planned in advance
  • Speed, speed, speed.
  • It is desirable to be able to think of multiple solutions, and to analyze, analogy, and extend the surrounding algorithms and data structures involved in each solution

The above experience is personal imagination, you see their own grasp good ~

Afterword.

Today (March 12), the interviewer added me to wechat and congratulated me on passing the written test, but there are still three rounds of interviews (really difficult…). They are supervisor + boss + HR.

In fact, I still have a lot of things I want to share after I finish reading and wish you get the Offer. The interview experience and skills I summarized by myself have not received the result from Ali yet, so I plan to write the second version based on my experience with CBU after cooling off (or getting the offer), which will be published on my public account Bestsort. I hope you pay more attention to it

The resources

[1]

Against Mr Ackermann function: https://baike.baidu.com/item/%E9%98%BF%E5%85%8B%E6%9B%BC%E5%87%BD%E6%95%B0/10988285?fr=aladdin

This article is formatted using MDNICE