Geekly Articles each Day
📜 ⬆️ ⬇️

Tasks for interviews in Yandex

There are always vacancies for the position of developer in Yandex. The company is developing, and there are not enough good programmers all the time. And applicants for these posts, too, more than enough. The main difficulty is to select the really suitable candidates. And in this regard, Yandex is not much different from most large IT-companies. So the basic principles described in this article can be applied not only to Yandex.

However, it is worth making a reservation that the article is still about the selection of developers. Those. actually those eighty percent of employees on whom mass development keeps. Often we hire people for special vacancies: for example, computer vision systems developers, linguists, machine learning experts. In this case, the format of the interview may differ markedly.

image

What to expect at the interview


Resume and work experience allows you to make a first impression about the candidate, but there is some problem: the ability to write a good resume and the ability to program are not strongly correlated. So there are a huge number of people who, with an excellent resume and “experience”, cannot write a working code, and there are a number of candidates whose resume is depressing, and the people themselves are worthwhile professionals. Therefore, in order to truly appreciate the possibilities of a developer, one cannot do without direct communication.
')
Sometimes, to understand that a candidate does not fit, ten minutes is enough: if a person is embarrassed by basic questions about the syntax of the language in which he claims he wrote for several years, further conversation does not make sense. That is why most often the first stage of a series of interviews in Yandex is usually conducted via Skype. Still, to deny a person who got to the office an hour by traffic jams in the fifth minute of the interview is not good from the point of view of politeness, and another 2 hours to torment him, knowing that you most likely will not take it from the point of view of ethics. Accordingly, a remote interview allows you to save time and nerves for both parties.

With questions about syntax, the main thing is not to overdo it, intentionally trying to catch it on some little-known fact. There are programming languages ​​with a very long and difficult history, which have about half of their capabilities - some kind of historically complex and unnecessary crutches. These include, for example, our favorite C ++. If you are not a C ++ compiler developer, you can almost always find something that you don’t know in the language. It's just not clear why you might need it.

We usually use pre-prepared language tests that include 10-15 questions on the knowledge of syntax, language capabilities, memory management principles, etc. Most often, to successfully complete answers to all the questions is not required, 70-80 percent is enough. And in general, the test itself is rather not a test, but a set of topics for which you need to talk, we are more interested in not the answer itself (we already know it), and why the candidate chose it.

An important point is the knowledge of algorithms. Here, too, you need not to overdo it, probably very few of the people who conduct interviews themselves, remember by heart how to rotate the red-ebony tree, but to know how your favorite language containers are arranged in order to know their limitations and be able to choose the right ones - is necessary. In fact, reading Knut in order to study this area is not necessary, in fact, you can prepare for this stage by carefully reading about 30 pages on Wikipedia.

List of articles
en.wikipedia.org/wiki/Data_structures

en.wikipedia.org/wiki/Sorting_algorithm


In addition to reading articles from the list, it is necessary to go through all the relevant links in them, just to study them thoughtfully, and if necessary go even deeper.

Write the code


But the main thing for a developer is, of course, the ability to write good code. And to hire a programmer only on the basis of his theoretical knowledge, to put it mildly, is strange. Here you can recall an excerpt from the book The Human Factor by Tom de Marco and Timothy Lister:
Manager: "How long have you been juggling?"
Candidate: "Well, about six years old."
Manager: “Can you juggle with three, four, five balls?”
Candidate: "Yes, yes and yes."
Manager: "Do you work with burning objects?"
Candidate: “Of course.”
Manager: "... knives, axes, open boxes with cigars, soft wide-brimmed hats?"
Candidate: "I do not care how to juggle."
Manager: “Do you know any funny patter?”
Candidate: "Onabespodobna".
Manager: “Well, I like it. I think we will take you. ”
Candidate: “Ahhh ... You don't want to see how I juggle?”
Manager: "Hmm, somehow it did not occur to me."

Therefore, at the last stage, the candidate is invited to perform a practical task.

Now we will give you an analysis of a task similar to the fact that they can get you on an interview. We came up with it specifically to demonstrate the average level of complexity.

By the condition of the problem, you have a formula with numbers, operations + - * / and brackets. You need to write a program that calculates it. The formula can be big. It would be desirable, that the program could be finished easily, entering functions, parameters, etc.

Before leaving the candidate alone with the task, we usually ask how he is going to solve it. Not enough after 2 hours to find out that a person has no idea which side to proceed with the task. At the time of discussion, you can send a little and prompt the algorithm.

To check the level of complexity of the task, we gave it to two of our employees: a programmer and a manager, who was previously a programmer but has not been practicing for several years. We asked both of them not to refresh the theory and write from memory. The first coped with the task in two hours, and the second took four hours to solve. The task turned out to be somewhat more complicated than the standard ones, the solution of which usually goes from half an hour to two. For example, analyze the solution as clearly as possible. An experienced developer is aware of all this without thinking.

So, we parsim formula. As a result, we want to get a syntactic tree, where there will be operations in the nodes, and constants in the leaves. If there were no brackets, the tree would be very simple. We have two priorities of operations, respectively, the tree turns out to be two-level: on the top is + and -, on the bottom * and /.

But since brackets are present, the tree can have unlimited nesting. The naive solution to the problem is as follows: we find the brackets and completely bite them out of the resulting string and replace, for example, with the names of the variables a1, a2, a3, a4 ... After parsing we get a two-level tree. Then, in each node of the tree where the variable remains, we analyze what was in the brackets and insert the results instead of the corresponding pieces of the subtree.

However, we have an algorithm with quadratic time complexity at worst, since if we have, for example, 100 million nested brackets, then at each step we will have to look for a closing bracket, and then parse this line again, passing it entirely without left and right characters. By and large, it is already possible to count it for the right decision, such a program will work.

But the majority of programmers will mark this approach as too head-on and inefficient, going straight to the search for a linear algorithm. For this, obviously, starting recursion with parentheses does not need to immediately look for the closing one. Both of our test candidates went this way. As a result, both got something similar to the recursive descent parser (a subspecies of the LL parser ).

Manager Code
#include <string>
#include <cassert>
#include <memory>
#include <stdexcept>
#include <vector>
#include <iostream>
#include <cstdio>

using namespace std;

struct Token {
        enum Type { value, operation, opening_bracket, closing_bracket};
        Type type;
        string text;
};

struct Tokenizer {
        //I am too lazy to write real tokenizer, it is very simple. I hope formula generator for fake tokenizer will be ok. 
public:
        Tokenizer() { content=generate(); pos=content.begin(); } ;
        const Token* peek() { return pos!=content.end() ?&*pos:0; } ;
        const Token* get() { if (pos!=content.end()) { cout << pos->text << " "; } return pos!=content.end()?&*pos++:0; } ;
private:
    vector<Token> generate(int level=0);
    
private:
        vector<Token>::iterator pos;
        vector<Token> content;
};

//To be honest using classes for expression parsing is a bit overkill, old style could save some code. 
class Expression;
typedef struct auto_ptr<Expression> ExpressionPtr;

//Represents abstract expression
class Expression {
public:
        Expression() {}
        virtual ~Expression() {}
        //actually this static parse functions should be constructor in most classes. I.e. this is violation of principle 'Resource Acquisition Is Initialization'.
        //but some functions return different classes depending on context, i.e. this is some kind of 'virtual constructor' (see Operation::parse for example)
        //so I made decision to make static construction function in all classes, just for uniformity
        static ExpressionPtr parse(Tokenizer& tokens);
        virtual float calc()=0;
        virtual void debug(string prefix)=0;
};


//Represents single value: for example 3.1415
class Value: public Expression {
public:
        Value() {}
        virtual ~Value() {}
        static bool isItYou(Tokenizer& tokens);
        static ExpressionPtr parse(Tokenizer& tokens);
        virtual float calc() { return _value; }
        virtual void debug(string prefix) { cout << prefix << "Value(" <<  calc() <<"): " << _value << endl; } 
protected:
        float _value;
};

//Represents operation: + or -
class Operation: public Expression {
public:
        Operation() {};
        virtual ~Operation() {}
        static ExpressionPtr parse(Tokenizer& tokens, ExpressionPtr& l);
        virtual float calc();
        virtual void debug(string prefix) { cout << prefix << "Operation(" <<  calc() <<"): " << _operation << endl; if ( _left.get() ) _left->debug(prefix + "\t"); if ( _right.get() ) _right->debug(prefix + "\t"); } 
protected:
        std::auto_ptr<Expression> _left;
        std::auto_ptr<Expression> _right;
        string _operation;
};

//Represents operation: * or /
class PriorityOperation: public Operation {
public:
        PriorityOperation() {};
        virtual ~PriorityOperation() {}
        static ExpressionPtr parse(Tokenizer& tokens, ExpressionPtr& left);
        //virtual float calc(); inherit it
        virtual void debug(string prefix) { cout << prefix << "PriorityOperation(" <<  calc() <<"): " << _operation << endl; if ( _left.get() ) _left->debug(prefix + "\t"); if ( _right.get() ) _right->debug(prefix + "\t"); } 
};


//Represents bracketed expression: (expr)
class BracketExpression: public Expression {
public:
        static bool isItYou(Tokenizer& tokens);
        static ExpressionPtr parse(Tokenizer& tokens);
        virtual float calc() { return _internal->calc(); } ;
        virtual void debug(string prefix) { cout << prefix << "Brackets(" <<  calc() <<"): "  << endl; _internal->debug(prefix + "\t"); } 
protected:
        std::auto_ptr<Expression> _internal; 
};


ExpressionPtr Expression::parse(Tokenizer& tokens)
{
    //cout << "Expression::parse" << endl;
    
        if (!tokens.peek()) return ExpressionPtr();

        if ( BracketExpression::isItYou(tokens) )
        {
                return BracketExpression::parse(tokens);
        }
        else
        if ( Value::isItYou(tokens) )
        {        
                return Value::parse(tokens);
        }
        else
        {
                throw logic_error("(Expression) Wtf is that: " + tokens.peek()->text );
        }
}

bool Value::isItYou(Tokenizer& tokens) 
{
        const Token* t = tokens.peek();
        if ( !t || t->type != Token::value ) return false; 

        char* endptr;
        strtod( t->text.c_str(), &endptr);
        return *endptr == 0;
}

ExpressionPtr Value::parse(Tokenizer& tokens)
{
    //cout << "Value::parse" << endl;
    
        std::auto_ptr<Value> foo( new Value );

        const Token* t=tokens.get();
        assert( t && t->type == Token::value ); 

        char* endptr;
        foo->_value = strtod( t->text.c_str(), &endptr);
        return ExpressionPtr(foo.release()); //lack of heterosexual auto_ptr conversions is killing me
}

bool BracketExpression::isItYou(Tokenizer& tokens) 
{
        return tokens.peek() && tokens.peek()->type == Token::opening_bracket;
}


ExpressionPtr BracketExpression::parse(Tokenizer& tokens)
{
    //cout << "BracketExpression::parse" << endl;
        const Token* t=tokens.get();
        assert ( t->type == Token::opening_bracket );

        auto_ptr<BracketExpression> result ( new BracketExpression );
        ExpressionPtr null;
        result->_internal = Operation::parse(tokens, null);

        t = tokens.get();
        if ( t ==0 || t->type != Token::closing_bracket )
        {
                throw logic_error("(BracketExpression) mismatched brackets ");
        }

        return ExpressionPtr(result.release());
}


ExpressionPtr Operation::parse(Tokenizer& tokens, ExpressionPtr& l)
{
    //cout << "Operation::parse:" << l.get() << endl;
        ExpressionPtr left;

        if (l.get()) 
        {
                left=l;
                // left is assigned for us.
        }
        else
        {
                left=Expression::parse(tokens);
        }        

        const Token *t=tokens.peek();
        if (!t || t->type == Token::closing_bracket  ) return left; //just return Value, sorry no operation guys

        if (t->type == Token::operation && (t->text=="*" || t->text=="/") )
        {
                ExpressionPtr result = PriorityOperation::parse(tokens, left);                 
                //we got exit after priority operations will end, parse position will be on + or - or at end
                left = result;        

                t=tokens.peek();
                if (!t || t->type == Token::closing_bracket  ) return left; //just return Value, sorry no operation guys
        }

    //cout << "Operation::parse again" << endl;
        if (t->type == Token::operation && (t->text=="+" || t->text=="-") )
        {
                tokens.get(); //just commit previous peek

                auto_ptr<Operation> result ( new Operation );
                result->_operation = t->text;
                result->_left=left; //smart ptr giveup ownership
        
        //cout << "Operation::parse before token" << endl;
        ExpressionPtr foo=Expression::parse(tokens);
        //cout << "Operation::parse after expression" << endl;
        
        const Token *t=tokens.peek();
        
        if (t != 0 && (t->text=="*" || t->text=="/"))
        {
            //cout << "Operation::parse to priority" << endl;
            foo = PriorityOperation::parse(tokens,foo);
        }
        
        result->_right=foo;
        
        ExpressionPtr bar(result.release());
        return Operation::parse(tokens, bar);
                
        }
        else
        {
                throw logic_error("(Operation) Wtf is that: " + tokens.peek()->text);
        }
}

ExpressionPtr PriorityOperation::parse(Tokenizer& tokens, ExpressionPtr& left)
{
    //cout << "PriorityOperation::parse" << endl;
    
    // left is already assigned for priority operation
        const Token *t=tokens.peek();
        if (!t || t->type == Token::closing_bracket  ) return left; //just return Value, sorry no operation guys

        if (t->type == Token::operation && (t->text=="*" || t->text=="/") )
        {
                tokens.get(); //commit previuos peek

                auto_ptr<PriorityOperation> result ( new PriorityOperation ); 
                result->_operation = t->text;
                result->_left=left;
                result->_right=Expression::parse(tokens);
                ExpressionPtr rs(result.release());

                return PriorityOperation::parse(tokens, rs);

        }
        else if (t->type == Token::operation && (t->text=="+" || t->text=="-") )
        {
                return left;
        }
        else
        {
                throw logic_error("(PriorityOperation) Wtf is that: " + tokens.peek()->text );
        }
}


float Operation::calc()
{
        if (_operation == "+")
        {
                float l=_left.get()?_left->calc():0.0f;
                float r=_right.get()?_right->calc():0.0f;
                return l+r;
        }
        else
        if (_operation == "-")
        {
                float l=_left.get()?_left->calc():0.0f;
                float r=_right.get()?_right->calc():0.0f;
                return l-r;
        }        
        else
        if (_operation == "*")
        {
                float l=_left.get()?_left->calc():1.0f;
                float r=_right.get()?_right->calc():1.0f;
                return  l*r; 
        }        
        else
        if (_operation == "/")
        {
                float l = _left.get()?_left->calc():1.0f;
                float r = _right.get()?_right->calc():1.0f;
                return l/r;
        }
        else
        {
                throw logic_error("Wft: operation udefined");
        }                
}

//returning vector by value, will be slow( O(n*n) actually ), but it is just testing code.
vector<Token> Tokenizer::generate(int level)
{
    //be careful with this value - formula size is approx 2^level
    if (level > 6)
    {
        Token t;
        char f[100];
        snprintf(f,100,"%d",int(rand() % 100));
        t.text=f;
        t.type=Token::value;
        return vector<Token>(&t,&t+1);
    }

    if (rand() % 10 == 0)
    {
            vector<Token> result;
            Token t1,t2;
            t1.type=Token::opening_bracket;
            t1.text="(";
            t2.type=Token::closing_bracket;
            t2.text=")";
            result.push_back(t1);
            vector<Token> r=generate(level+1);
            result.insert(result.end(),r.begin(),r.end());
            result.push_back(t2);

            return result;
    }        

    char op = "+-*/"[rand()%4];
    Token t;
    t.type=Token::operation;
    t.text=op;

    vector<Token> result=generate(level+1);
    result.push_back(t);
    vector<Token> r2=generate(level+1);
    result.insert(result.end(),r2.begin(),r2.end());

    return result;
}

int main()
{        
        try
        {
                //create fake tokenizer
                Tokenizer tk;

                //parse it
                ExpressionPtr null;
                ExpressionPtr foo = Operation::parse(tk,null);
                cout << endl;
                foo->debug("");
                float result = foo->calc();        
                cout << "result = " << result << endl;
        }
        catch(exception& e)
        {
                cout << e.what() << endl;
                return 1;                  
        }

        return 0;
}


#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <string>
#include <vector>
#include <stdexcept>

struct token {
    enum { E_UNDEF, E_NUMBER, E_OPERATOR, E_LEVEL  } type;

    union {
        double d_val;
        int i_val;
        char c_val;
    } data;

    token() {
        type = E_UNDEF;
    }

    token(double val) : type(E_NUMBER) {
        data.d_val = val;
    }
    token(int val) : type(E_LEVEL) {
        data.i_val = val;
    }
    token(char val) : type(E_OPERATOR) {
        data.c_val = val;
    }
};

typedef std::vector<token> tokens;

void push_level(tokens &pr, int level) {
    if (pr.empty() || pr.back().type != token::E_LEVEL) {
        pr.push_back(token(level));
    } else {
        pr.back().data.i_val += level;
    }
}

void push_operator(tokens &pr, char op) {
    pr.push_back(token(op));
}

void push_number(tokens &pr, int num) {
    if (pr.empty() || pr.back().type == token::E_LEVEL || (pr.back().type == token::E_OPERATOR && pr.size() > 1 && pr[pr.size() - 2].type == token::E_NUMBER) ) {
        pr.push_back(token((double)num));
    } else if (pr.back().type == token::E_OPERATOR && (pr.size() == 1 || pr[pr.size() - 2].type == token::E_LEVEL) ) {
        if (pr.back().data.c_val == '*' || pr.back().data.c_val == '/') {
            throw std::domain_error("unexpected operator");
        }
        if (pr.back().data.c_val == '-') {
            num = -num;
        }
        pr.pop_back();
        pr.push_back(token((double)num));
    } else {
        throw std::domain_error("unexpected number");
    }
}

token calc3(tokens &pr) {
    token s2 = pr.back(); pr.pop_back();
    token op = pr.back(); pr.pop_back();
    token s1 = pr.back(); pr.pop_back();

    if (s1.type != token::E_NUMBER || op.type != token::E_OPERATOR || s2.type != token::E_NUMBER) {
        throw std::domain_error("unexpected closing brace");
    }

    switch (op.data.c_val) {
        case '+':
            s1.data.d_val += s2.data.d_val;
            break;
        case '-':
            s1.data.d_val -= s2.data.d_val;
            break;
        case '*':
            s1.data.d_val *= s2.data.d_val;
            break;
        case '/':
            s1.data.d_val /= s2.data.d_val;
            break;
        default:
        throw std::domain_error("internal error");
    }

    return s1;
}

void pop_level(tokens &pr, int level) {
    if (level == 0) {
        if (pr.size() > 3) {
            pr.push_back(calc3(pr));
        }
        return;
    }
    if (pr.empty() || pr.back().type == token::E_LEVEL || pr.back().type == token::E_OPERATOR) {
        throw std::domain_error("unexpected closing brace");
    } else if (pr.size() > 1 && pr[pr.size() - 2].type == token::E_LEVEL) {
        if (pr[pr.size() - 2].data.i_val > level) {
            pr[pr.size() - 2].data.i_val -= level;
        } else {
            int delta = level - pr[pr.size() - 2].data.i_val;
            token tmp = pr.back();
            pr.pop_back(); pr.pop_back();
            pr.push_back(tmp);
            pop_level(pr, delta);
        }
    } else if (pr.size() > 3) {
        token s1 = calc3(pr);

        if (pr.back().type == token::E_LEVEL) {
            if (pr.back().data.i_val > level) {
                pr.back().data.i_val -= level;
                pr.push_back(s1);
            } else {
                int delta = level - pr.back().data.i_val;
                pr.pop_back();
                pr.push_back(s1);
                pop_level(pr, delta);
            }
        } else if (pr.back().type == token::E_OPERATOR) {
            pr.push_back(s1);
            pop_level(pr, level);
        } else {
            throw std::domain_error("unexpected closing brace");
        }
    } else {
        throw std::domain_error("unexpected closing brace");
    }
}

double process(const std::string &str) {
    tokens program;

    push_level(program, 3);
    for (std::string::const_iterator cit = str.begin(); cit != str.end(); ++cit) {
        switch (*cit) {
            case '(':
                push_level(program, 3);
                break;
            case ')':
                pop_level(program, 3);
                break;
            case '*':
            case '/':
                pop_level(program, 1);
                push_operator(program, *cit);
                push_level(program, 1);
                break;
            case '+':
            case '-':
                if (cit == str.begin() || strchr("(+/-*", *(cit-1))) {
                    push_operator(program, *cit);
                } else {
                    pop_level(program, 2);
                    push_operator(program, *cit);
                    push_level(program, 2);
                }
                break;
            case ' ':
                break;
            case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':
                {
                    int curnum = 0;
                    while (cit != str.end()) {
                        curnum = 10*curnum + (*cit - '0');
                        if ((cit + 1) == str.end() || !isdigit(*(cit+1))) {
                            break;
                        }
                        ++cit;
                    }
                    push_number(program, curnum);
                }
                break;
            default:
                throw std::domain_error("unexpected symbol");
        }
    }
    pop_level(program, 3);

    if (program.size() == 0 || program.size() > 1) {
        throw std::domain_error("incomplete expression");
    }

    return program.back().data.d_val;
}

int main() {
    std::string line;
    while (!std::cin.eof()) {
        std::getline(std::cin, line);

        if (line.length() > 0) {
            try {
                std::cout << process(line) << std::endl;
            } catch (std::exception &e) {
                std::cout << "error: " << e.what() << std::endl;
            }
        }
    }

    return 0;
}

- , . - .

, shunting yard algorithm. Recursive descent parser LR-.


senior-, , .

. , , , , , , , .

– , . , . , , , .

, . . , , . , – .

, , . , , . , .

, - , . , . . , , , – , .

++
  • , « + = »
  • , , «: »
  • « ++»
  • Scott Meyers. Effective C++. More Effective C++. Effective STL
  • Herb Sutter «Exceptional C++» «More Exceptional C++»


(, .)

Source: https://habr.com/ru/post/206234/

More articles:


All Articles