Sometimes interviewers will ask us some simple, but difficult questions, mainly to see how you deal with the problem. If you have not been exposed to these questions, you may really do not know how to deal with the better, this kind of questions is more important is a kind of thinking, today to share a few questions encountered in the interview algorithm (of course, not MYSELF encountered, is someone else encountered, I picked out)

Case 1

1+2+3+… +n, do not use multiplication, division, for, while, if, else, switch, case and other keywords and condition statement (A? B, C).

Holy crap, summation doesn’t allow multiplication and division, and we’re not allowed to use loops, but if those two restrictions are alone, we can use recursion, for example:

int f(int n){
    if(n == 0){
        return n;
    }else{
        returnf(n-1) + n; }}Copy the code

If, else, case and other keywords are not used, so I use the ternary operator (A? B: C), and the ternary operator with the judgment statement is also not used, I’m going to screw that up.

So this is definitely going to have to be solved recursively, and the whole point of recursion is to determine if the recursion is over, and they don’t allow us to use conditional statements. So what are we going to do? You can think about it.

We can actually replace A with something like this, right? B:C, such a judgmental ternary operator

n ! = 0 && (f(n-1) + n) ! = 0;Copy the code

The && identifier is: if n! F (n-1) + n)! = 0 = 0 is also executed if n! (f(n-1) + n))! (f(n-1) + n)! = 0 will not be executed, and by doing so, we can achieve our goal of recursively ending the condition.

And just to illustrate, f of n minus 1 plus n factorial. F (n-1)+n = 0 = 0 because the Boolean && only supports Boolean, not int.

The final code is as follows

public int f(int n) { int sum = n; boolean t = (n ! = 0) && (sum += f(n - 1))! = 0;return sum;
    }
Copy the code

If you’ve done this type of problem, it’s probably pretty easy, if you haven’t done it, you might want to think about it a little bit, but then you can just skip ahead.

Case 2

Write a function to find the sum of two integers. Do not use +, -, *, or/inside the function.

Oh, my god! No addition, no subtraction, no multiplication! Interviewer, can not be so capricious, good addition, subtraction, multiplication and division actually do not give use.

But I believe that you can think of the first time to solve the problem with bit operations, maybe in college, you can learn circuit related knowledge and write the code, but some people can also do it bit by bit. For example, I first process the first bit, see if there is a carry, then process the second bit, add the second bit if there is a carry in the first bit, and then process the third bit…..

If that’s how you did it, then congratulations, you’ve got something to gain by reading this problem. In fact, the above solution is also possible, but it is too complicated, and it can be judged by all kinds of judgment. In fact, this problem can be solved like this: for the sake of explanation, I’m going to give you the code first, and then I’m going to give you a detailed explanation, so it might be easier for you to see the explanation after you look at the code

    public int Add(int num1,int num2) {
        int tmp = 0;
        while(num1 ! = 0){ tmp = num1 ^ num2; num1 = (num1 & num2) << 1; num2 = tmp; }return num2;
    }
Copy the code

Num1 = 101, num2 = 001, TMP = num1 ^ num2, TMP = 100. The TMP result is the sum of two binary digits (num1,num2). The result of num1 = (num1 & num2) << 1 is the binary bits that need to be carried when the two numbers are added. For example, (101&001) << 1 = 010, then we add the first digit to the second digit.

A + b = a ^ b + (a & b) << 1.

In the code, if num1 == 0, it means that there is no carry, and then we can exit the loop.

For those of you who rarely use bitwise calculations, this may seem a bit confusing, so I recommend watching it a few times and then doing the simulation once. Later encounter this kind of problem can be directly killed in seconds.

Case 3

Here I want to make it clear that case 3 is not a tricky question, but I’m here to quiz you. You can think about it for yourself after you see the question. You can’t hit me if you see the answer.

Implement the multiplication of two integers without using the multiplication operator and loop

You guys can think about it.

This problem may be a lot of people think of recursion, as if I said most of the algorithm, will use recursion, so say you do not understand recursion, see my public number on the line, do not understand also have to change to understand is not. The code is as follows:

int mul(int a, int b){
    if (a == 0 || b == 0)
        return 0;
    if (b == 1)
        return a;
    if (a == 1)
        return b;
    returna + mul(a, b - 1); } int mult(int a,int b){sum = mul(a, abs(b));return(b<0)? (-sum):sum; }Copy the code

Is that how you do it? In fact, we have a better way oh, here

Hell, you can’t multiply, I didn’t say you can’t divide, so let me just divide instead of multiplying, for example a times b is the same thing as a over b. The code is as follows:

int mult2 (int a,int b){
    returnb ! = 0? (int)(a/(1.0 / b) + 0.99): 0; }Copy the code

Int was needed to convert the type, and division might cause the mantissa to be lost, so I added 0.99. Int < 1; int < 1; int < 1; Of course, I’m using the Java language here, and other languages are up to you.

conclusion

Today’s questions, more is a kind of opportunistic, but see you see a strange topic, how you will deal with the idea, this is still very important drop, and read more ideas, slowly your ideas will become more.

If you find this article inspiring, in order to reach more people, it’s ok

1, like, so that more people can see this content (collection does not like, are playing rogue -_-)

Pay attention to me and column, let us become a long-term relationship

3, pay attention to the public number “helpless and painful code farmers”, mainly write algorithm, computer basics and other articles, which have more than 100 original articles

Helpless and painful code farmers