Massive Algorithms: December 2019

Google Interview Questions Deconstructed

https://medium.com/@alexgolec

https://medium.com/@alexgolec/introducing-google-interview-questions-deconstructed-a012e41ea631

https://hackernoon.com/google-interview-questions-deconstructed-the-knights-dialer-f780d516f029
More at LeetCode 935 - Knight Dialer

I like it because it hits number of sweet spots:

It’s easy to state and understand.
It has a number of solutions, each requiring varying degrees of algorithms and data structures knowledge. Also, a little bit of insight goes a long way.
Each solution can be implemented in relatively few lines, making it perfect for a time-constrained environment.

Google Interview Questions Deconstructed: The Knight’s Dialer (Logarithmic Time Edition)

Google Interview Questions Deconstructed: Synonymous Queries

Imagine you operate a popular search engine and in your logs you observe two queries, let’s say “obama approval ratings” and “obama popularity rate.” Those two queries are different strings, but I think we can all agree that they’re basically searching for the same thing, and should be considered equivalent when counting queries, showing results, etc. How can we detect that two queries are synonymous?

To make this concrete, here is a sample input to illustrate:

SYNONYMS = [
('rate', 'ratings'),
('approval', 'popularity'),
]

QUERIES = [
('obama approval rate', 'obama popularity ratings'),
('obama approval rates', 'obama popularity ratings'),
('obama approval rate', 'popularity ratings obama')
]

Part 1: The (Not So) Simple Case

However candidates arrive at these questions, they inevitably end up asking me for an answer, and I always start off with the simplest case possible: words can have multiple synonyms, order matters, synonyms are not transitive, and synonyms can only map from one word to another. This makes for a pretty limited feature in a search engine, but there’s more than enough subtlety in it to make for an interested interview question.

You’d think, but there’s more subtlety here than you’d see at first glance. By far the trickiest component of this simple algorithm is the synonym comparison. While simple to understand and describe, there are a lot of ways the synonym comparison component can go wrong. I’ll go into some of the more common ones I’ve seen here.

To be clear, none of these mistakes are disqualifying in my mind; if the candidate produced an implementation with an error, I would simply point it out, they would adjust their solution, and we would move on. However, an interview is, first and foremost, a battle against time. Making, noticing, and correcting mistakes is expected, but it saps time that could be spent elsewhere, such as producing a more optimal solution. Very few candidates make no mistakes, but candidates who make fewer make more progress simply because they spend less time cleaning up after themselves.

This is why I like this problem: unlike the knight’s dialer, which requires a flash of algorithmic insight followed by a (hopefully) simple implementation, this question requires a multitude of small, incremental steps in the right direction. Each step represents a tiny hurdle over which the candidate can either leap gracefully or trip and have to recover. Good candidates avoid these little pitfalls using their experience and intuition and are rewarded with a more fleshed-out and correct solution, while weaker ones waste time and energy on mistakes and are usually left with buggy code.

While every interview saw a different mix of leaps and faceplants, here is a small sampling of the more common errors I saw.

Accidental Runtime Killers

In terms of practical advice, this is actually an easy mistake to avoid. First off, never forget the types of your objects, even if you’re using an untyped language like python! Second, remember that when you use the in keyword on a list, that’s a linear search. Unless that list is guaranteed to always be very small, it’s going to be a performance killer.

Reminding candidates that the input structure is a list is usually enough to rouse them. What happens after I give a hint is very informative. The better candidates immediately think to preprocess the synonyms somehow, which is a good start. However, that approach is not without its pitfalls…

Use the Right Data Structure

Which of these two the candidate chooses is less interesting to me than what they put in it. (By the way, never use a dict/hashmap that goes to True or False. That’s called a set.) Most candidates settle on some sort of dict/hashmap. The most common error I see is a subconscious assumption that each word can have at most one synonym:

A slightly more serious problem is not realizing that the synonym relationship goes both ways. You’ll notice the above code does this. Correcting this, however, can be error prone. Consider the following approach to implementing this property:

Why perform two insertions and use double the memory when you can use no additional memory and perform two checks?

The takeaway: always ask yourself if you can do less work! In hindsight, permuting the lookup is an obvious way of saving time if you look for it, but using a suboptimal implementation suggests the candidate didn’t think to look for ways to optimize. Again, I’m happy to give a hint, but it’d be better if I didn’t have to.

Transitivity: Naive Approaches

The first constraint I like to relax is the one around transitivity, meaning that if words A and B are synonymous, and if words B and C are synonymous, then words A and C are synonymous. Sharp candidates quickly realize they can adapt their earlier solution to solve this because they’re still determining whether simple pairs of words represent synonym pairs, whereas the other relaxations invalidate the core logic of the earlier algorithm.

So far, so good, but there’s clearly no blinding performance just yet. The genius of this structure is in a procedure called compaction.

Yes you can, it turns out. In a way, every element in this tree is destined to arrive at “fast.” Instead of traversing the tree multiple times, why not simply change the parent of each element along the way to “fast” and save ourselves the work? This process is called compaction

This leaves us with a few more follow-ups: a version of this question where word order doesn’t matter, and one where synonyms can span multiple words. The solutions to each of these are challenging and delightful.

Google Interview Problems: Ratio Finder

More at LeetCode 399 - Evaluate Division

Given a list of conversion rates (formatted in the language of your choice) as a collection of origin unit, destination unit, and multiplier, for example:

foot inch 12

foot yard 0.3333333

etc…

Such that ORIGIN * MULTIPLIER = DESTINATION, design an algorithm that takes two arbitrary unit values and returns the conversion rate between them.

For context, framing is the act of translating a problem where the solution is not obvious into an equivalent one where the solution yields naturally. If that sounds completely abstract and unapproachable, forgive me because it is

For instance, what if there is no conversion? The obvious approach doesn’t tell you anything about whether there actually is a conversion, and if I were given a thousand conversion rates, I would have a very difficult time determining whether such a conversion exists. Perhaps I’m being asked to convert between unfamiliar (or made up) units called wobbles and a thingles, and I have no idea where to even start. How would the intuitive approach handle that?

I have to admit, that’s kind of a contrived scenario, but there’s another, more realistic one to consider. You’ll notice that my problem statement only includes units of distance. This is very intentional. What if I ask my system to translate from inches to kilogram? You and I both know this can’t be done because those units measure different things, but our input tells us nothing about the “kind” of thing each unit measures.

This is where the careful statement of the question allows strong candidates to shine. Strong candidates think through the edge cases of a system before they design an algorithm, and this problem statement purposefully gives them an opportunity to ask me whether we’ll be translating different units. It’s not a huge deal if they don’t catch this issue early on, but it’s always a good sign when someone asks me “what should I return if there is no conversion?” Stating the question this way gives me an indication.

The Graph Framing

Framing the problem as a graph unlocks all the classic graph search problems. In particular, two algorithms are useful here: breadth first search (BFS) and depth first search (DFS).

We don’t want to find whether a path exists, we want to find the conversion rate! This is where the candidate must make a leap: it turns out you can modify any search algorithm to find the conversion rate, simply by keeping additional state as you traverse.

This is a fine implementation, but it suffers from two major weaknesses. First off, it is recursive. If it turns out the path we need is more than a thousand or so hops long, we’ll crash. Sure, it’s not likely, but if there’s one thing you don’t want happening in a long-running service, it’s crashing. Second off, even if we were to stop successfully, our answer has some undesirable properties.

I actually already gave you a hint way up at the top of the post. Did you notice how Google says the conversion rate is 1.0739e-17 but the conversion I computed manually came out to 1.0737e-17? It turns out given all the floating point multiplications we’re performing, we have to start worrying about error propagation. The subtleties are a little more than I want to go into for this post, but the gist of it is we want to perform as few floating point multiplications as possible to avoid errors accumulating and causing trouble.

DFS is a fine search algorithm, and if a solution exists it will find it, but it lacks a crucial property: it does not necessarily find the shortest path. This is relevant to us because a shorter path means fewer hops, which means fewer error-propagating floating point multiplications. To get around this, we’ll want to use BFS.

the recursive DFS solution’s major weaknesses are that it’s recursive and it doesn’t minimize the number of multiplications. BFS,as we’ll soon see, does minimize the number of multiplications, and it also happens to be very tricky to implement recursively.

Understand the question
Frame the conversion network as a graph
Realize conversion rates can be mapped to paths through the graph
Recognize they can use search algorithms to accomplish this
Choose their favorite algorithm and modify it to track the conversion rate
If they implemented DFS as a naive solution, realize its weaknesses
Implement BFS
Step back and examine the edge cases:
What if we’re asked for a nonexistent node?
What if the conversion rate does not exist?
Realize the reversing the conversions is possible and likely necessary

Part 4: Can You Do Any Better?

Part 4: Constant Time

So it turns out that the “cache everything” solution is actually not far off from the mark. In that approach, we (eventually) end up with an edge between each node and every other node, meaning our conversion happen in a single edge lookup. But do we really need to store conversion from every node to every node? What if we just stored the conversion rates from one node to every other node?

But Wait, There’s More!

First, a warm-up: in the constant time solution I laid out, I chose the root node of each connected component arbitrarily. In particular, I use the first node of that component we encounter. This is not optimal, because for all we know we’ve chosen some node way off on the fringes of the graph, while some other node might be more central and so have shorter paths to all other nodes. Your assignment is to replace this arbitrary choice with one which minimizes the number of multiplications required and this the floating point error propagation.

Second, this whole discussion assumes all equal-length paths through the graph are created equal, which isn’t always the case. One interesting variant of this problem is currency conversions: nodes are currencies, and edges from A to B and vice-versa are the bid/ask prices of each currency pair. We can rephrase the unit conversion question as a forex arbitrage question: implement an algorithm that, given a currency conversion graph, computes a cycle through the graph that can leave a trader with more money than when they started. Assume no transaction fees.

Finally, a real doozie: some units are expressed as a combination of various basic units. For instance, the watt is defined, in SI units, as “kilogram meters squared by seconds cubed”. The final challenge is to extend this system to support converting between these units given only the definitions of the basic SI units.

How to Conduct Algorithm interview

https://medium.com/@alexgolec/introducing-google-interview-questions-deconstructed-a012e41ea631

After each interview is done, the interviewer writes up feedback. For entry-level technical roles, this feedback is only on your technical abilities: How well did you apply your data structures and algorithms knowledge? How well do you code? Did your solution handle all the edge cases? How close did your solution get to optimal time and space complexity for the problem? How well did you communicate your thoughts and respond to questions?

When I interview, I only care about your ability to solve problems and communicate as you do it. In other words, don’t spend too much time worrying about the your outfit or the strength of your handshake.

https://hackernoon.com/google-interview-questions-deconstructed-the-knights-dialer-f780d516f029

Every interview I conduct basically breaks down into two parts: first we find an algorithmic solution and then the candidate implements it in code. I say “we” find a solution because I’m not a mute spectator: 45 minutes is not a lot of time to design and implement anything under the best circumstances, never mind under pressure. I let candidates take the lead in the discussion, generating ideas, solving instances of the problem, etc., but I’m more than happy to give a nudge in the right direction. The better the candidate, the fewer hints I tend to have to give, but I have yet to see a candidate who required no input from me at all.

I should underscore this, because it’s important: as an interviewer, I’m not in the business of sitting back and watching people fail. I want to write as much positive feedback as I can, and I try to give you opportunities to allow me to write good things about you. Hints are my way of saying “okay, I’m gonna give this bit to you, but only so you can move on and show me what you’ve got on the other parts of the question.”

With that being said, your first action after hearing the question should be stepping up to the whiteboard and solving small instances of the problem by hand. Never dive right into code! Solving small instances lets you spot patterns, observed and edge cases, and also helps crystallize a solution in your head. As an example, suppose you start on 6 and have two hops to make. Your sequences will be…

One of the surprises I had when I started using this problem is how often candidates get stuck on computing the keys to which we can hop from a given position, also known as the neighbors. My advice is: when in doubt, write an empty placeholder and ask the interviewer if you can implement it later. This problem’s complexity does not lie in the neighbor computation; I’m paying attention to how well you count full numbers. Any time spent on neighbor computation is effectively wasted.

I would accept “let’s assume there’s a function that gives me the neighbors” along with the following stub. Of course, I’ll probably ask you to double back and implement this later, but only if we have time. You can simply write a stub like this and move on:

def neighbors(position):
    ...

Also, you don’t really lose much by asking to use a stub: if the question’s complexity is elsewhere I’ll allow it. If not, I’ll ask you to actually implement it. I don’t mind when candidates don’t realize where the complexity of a question lies, especially in the early stages when they might not have fully explored the problem.

As for the neighbors function here, given that it never changes you can simply create a map and return the appropriate value:

Always start by solving a small instance of the problem by hand. In this problem the recurrence relation and the repetition of function calls become much more obvious when you hand-solve a problem.
Pay attention to when your solution is computing things you don’t need, like how the naive counting solution generates the sequences but doesn’t actually use them. Reducing unnecessary computation can often provide simpler solutions, if not open the door to more efficient ones.
Know your recursion. It’s almost useless in most production code because it blasts through the stack, but it’s a very powerful algorithm design tactic. Recursive solutions can often be adapted and improved: the difference between the exponential time naive solution and the linear time nearly-optimal memoization solution is minimal.
Know your Big-O analysis! You’re practically guaranteed to be asked this at some point during the interview process.
Always be on the lookout for opportunities to memoize. If your function is deterministic and you’ll be calling it multiple times with the same inputs, your solution may benefit from memoization.
Find and write out the recurrence relation. In this case writing it out makes it obvious that counts for N hops depend only on counts for N-1 hops.

Google Interview Questions Deconstructed: Synonymous Queries

Questions, Questions

On the face of it, this is a simple problem. However, the closer you look, the more complex it becomes. Right off the bat, it becomes clear this problem is pretty under-defined. Can words have multiple synonyms? Does word order matter? Are synonym relationships transitive, meaning if A is synonymous with B, and B is synonymous with C, does that mean A is synonymous with C? Can synonyms span multiple words, such as how “USA” is synonymous with “United States of America” or “United States”?

This ambiguity immediately gives good candidates an opportunity to set themselves apart. The first thing a good candidate does is sniff out these sorts of ambiguities and try to resolve them. How they do this varies from candidate to candidate: some step up to the whiteboard to try to manually solve specific cases, whereas some take one look at the question and see the gaps immediately. In any case, spotting these issues early is crucial.

I place a lot of importance on this question’s “problem understanding” phase. Software engineering is what I like to call a fractal discipline, meaning it shares a quality with fractals where zooming in reveals additional complexity. Just when you think you understand a problem, you look closer and realize there’s a subtlety you overlooked, or there’s an implementation detail you can improve on, or there’s a new way of framing the problem that reveals additional insight.

An engineer’s caliber is largely determined by how deeply they can understand a problem. Transforming a vague problem statement into a detailed set of requirements is step zero in this process, and purposefully under-defining the problem allows me to assess how well a candidate approaches novel situations.

As an aside, there are also the trivial questions like “does capitalization matter?” that, unbeknownst to the candidate, don’t affect the core algorithmic problem. For these questions, I always give whatever answer is easiest on the candidate (in this case, “assume everything is already preprocessed to be lowercase”).

Google Interview Questions Deconstructed: Synonymous Queries

Analyze a problem statement and recognize where it is ambiguous and under-defined, clarifying where necessary to develop an unambiguous problem statement. Continue doing this as you progress through a solution and encounter new questions. For maximal efficiency, do as much of this stage as early as possible because recovering from errors becomes more costly as your work progresses.
Frame the problem in such a way that makes it easier to approach and solve. In this case, the most important point is the observation that you can line up corresponding words in the queries.
Implement your solution. This involves choosing optimal data structure and algorithms, as well as designing your logic to be readable and easy to modify in the future.
Circle back and try to spot bugs and errors. These could be actual bugs like how I forgot to insert a “continue” statement above, or performance bugs like using an incorrect data structure.
When the problem definition changes, repeat this process and adapt your solution whenever appropriate, and scrap it where not. Knowing when to do both is a critical skill, both in an interview and in the real world.
Keep your data structures and algorithms knowledge at your fingertips. The disjoint set data structure is not exactly a common structure, but it’s not really that rare and refined either. The only way you can ensure you know the tool for the job is by learning as much as you can.

Google Interview Problems: Ratio Finder

However, I can remember many who were not sufficiently prepared for the interview, or worked at too slow a pace, or required too much supervision to solve a problem, or communicated in an unclear way, or failed to translate their ideas into code, or had an attitude that simply wasn’t going to lead them to success in the long term, etc. The definition of “worth hiring” is squishy and varies by company, and the interview process is there to see how well each candidate fits into a given company’s definition.

This bears repeating: when in doubt, write out a naive solution! Even if it’s not fully optimal, having code on the board is an accomplishment, and you can often iterate on it to get to a proper solution. Another way of saying this is: never let work go to waste. Odds are you thought of a naive solution but didn’t want to throw it out there because you know it’s not optimal. If you have a better solution on the tip of your tongue, that’s fine, but if not make sure you bank the progress you’ve made before you move on to more sophisticated things.

If we break solving this problem into four hurdles (framing discussion, algorithm choice, implementation, constant time discussion), almost all candidates made it as far as “algorithm choice” by the end of the interview. As I suspected, the framing discussion turned out to be a good separator: candidates either got it immediately or struggled to grasp it despite substantial hints.

Algorithm choice, on the other hand, turned out not to be a particularly useful source of signal. People who got over the framing stage usually arrived at using this algorithm without much trouble. I suspect this comes from the fact that search algorithms are almost always taught alongside graphs themselves, so if someone is familiar with one they’re likely to know the other.

Implementation turned out to be tricky. Many people had no problems implementing DFS recursively, but as I mentioned above, that implementation is not going to cut it in a production setting. To my surprise, the iterative BFS and DFS implementations do not seem to be at the tips of peoples’ fingers, and I often found that even after I gave substantial hints, people often faltered.

LeetCode 1256 - Encode Number

https://www.acwing.com/file_system/file/content/whole/index/content/150815/

Given a non-negative integer num, Return its encoding string.

The encoding is done by converting the integer to a string using a secret function that you should deduce from the following table:

Example 1:

Input: num = 23
Output: "1000"

Example 2:

Input: num = 107
Output: "101100"

Constraints:

0 <= num <= 10^9

http://qiujiaqi.cn/leetcode/encode-number/

这题一开始我的思路是，加密后的字符串长度 len 可以用 $l o g_{2} (n + 1)$ 计算，而尾值即可用 (n + 1) 对最大的 2 的幂的数求余得出，即 $(n + 1) \mod 2^{l e n}$ ，将这个尾值转化为二进制，再往这个尾值头部插入 0，直至长度为 len
例如：

6，加密后长度为 $l o g_{2} (6 + 1)$ ，即 2，尾值为 $(6 + 1) \mod 2^{2}$ ，即为 11，长度已经足够不需补 0，得 11

7，加密后长度为 $l o g_{2} (7 + 1)$ ，即 3，尾值为 $(7 + 1) \mod 2^{3}$ ，即为 0，往头部补 0，得 000

8，加密后长度为 $l o g_{2} (8 + 1)$ ，即 3，尾值为 $(8 + 1) \mod 2^{3}$ ，即为 1，往头部补 0，得 001

    public String encode(int num) {
        if (num == 0) {
            return "";
        }
        int len = (int) (Math.log(num + 1) / Math.log(2));
        int r = (int) ((num + 1) % Math.pow(2, len));
        String res = "";
        String tail = Integer.toString(r, 2);
        for (int i = 0; i < len - tail.length(); i++) {
            res += "0";
        }
        res += tail;
        return res;
    }

(找规律) $O (\log n)$

可以很容易发现，编码的字符串在每个长度 $l$ 内都是按 0 到 $2^{l} - 1$ 的方式排列的。
首先寻找最终编码字符串的长度，寻找长度的过程中，让目标值减去当前长度能编码字符串的数量。

时间复杂度

寻找长度的时间复杂度为 $O (\log n)$ ，构造答案的时间复杂度为 $O (\log n)$ 。
故最终时间复杂度为 $O (\log n)$ 。

空间复杂度

需要额外 $O (\log n)$ 的空间存储答案。

    string encode(int num) {
        int len = 0;
        while (num >= (1 << len)) {
            num -= (1 << len);
            len++;
        }

        string ans;
        for (int i = 0; i < len; i++, num >>= 1)
            if (num & 1)
                ans += '1';
            else
                ans += '0';

        reverse(ans.begin(), ans.end());
        return ans;
    }

https://leetcode.jp/leetcode-1256-encode-number-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF%E5%88%86%E6%9E%90/

本题需要先观察出给定的加密规律，与普通的二进制数不同，当出现进位时，所有位数的值要变为0，比如：11加1后不是100，而应该是000，同理111加一后是0000，虽然在二进制中000与0000都代表0，但在本题中因为位数不同而所代表的的意义也是不同的。

接下来再看，1位数能代表2个数字，0和1，2位数能代表4个数，00，01，10，11。以此类推可得到：n位数能代表2的n次方个数字。通过题目给出的数字，首先我们可以算出该数字加密后的位数，方法很简单，在满足num大于等于0的前提下，不断的用num减去2的n次方（n>=0, n++），直到不能再相减为止，此时的n即为加密后数字的位数，同时num剩下的值即是当前位数长度下的二进制数字。（注意高位不足的地方需要补0）

public String encode(int num) {

    int length=0; // 加密后的位数

    while(true){

        // 计算当前位数下能有多少数字

        int n=(int)Math.pow(2,length);

        // 如果num不足以表示下n个数字，退出

        if(num-n<0) break;

        num-=n; // num减去n，继续循环

        length++; // 位数加一

    }

    String res=""; // 返回结果

    for(int i=0;i<length;i++){ // 循环位数计算二进制

        res = num % 2 + ""+ res;

        num /= 2;

    }

    return res;

}

https://blog.csdn.net/qq_17550379/article/details/103109066

找规律的问题，规律也非常的简单。通过观察

bin(0 + 1) -> 1
bin(1 + 1) -> 10
bin(2 + 1) -> 11
bin(3 + 1) -> 100
bin(4 + 1) -> 101

不难发现结果就是num+1的二进制取出第一位即可。当然也可以通过数学来得到，首先不难发现相同位数的数成等比数列

0位 -> 1
1位 -> 2
2位 -> 4

那么通过等于数列求和公式很容易得到每位的第一个数为2^n - 1（其中n表示位数），那么num显然就可以表示为bin(num + 1 - 2^n)，而n就是bin(num)的最高位1所在的位置+1，那么为了方便计算可以忽略2^n，最后的结果就是bin(num + 1)去除最高位的结果。

class Solution:
    def encode(self, num: int) -> str:
        return bin(num + 1)[3:]

一开始参赛写出来很开心，最后发现，原来一句话就能写出来了，桑心。
num + 1 的二进制去掉首位就是了。

    public String encode(int num) {
        return Integer.toString(num + 1, 2).substring(1);
    }

Google Interview Questions Deconstructed

How to Conduct Algorithm interview

LeetCode 1256 - Encode Number

(找规律) $O (\log n)$

时间复杂度

空间复杂度

Labels

Popular Posts

Google Interview Questions Deconstructed

How to Conduct Algorithm interview

LeetCode 1256 - Encode Number

(找规律) O(log⁡n)

时间复杂度

空间复杂度

Labels

Popular Posts

(找规律) $O (\log n)$