Yandex interview questions

Interview on math/statistics. 1. In a fully-connected graph, each *edge* is painted with one of two colours. Find the probability that the graph contains a fully-connected subgraph on 3 vertices that has edges of different colours. 2. In a city, 85% of all cars are green, and 15% of cars are red. There happened an accident. The witness claims that a red car is to blame. The probability the witness is correct is only 80%. Compute the posterior probability that the car was red given the witness’ words. 3. There is a ranking algorithm that maps pairs (query, documents) to relevance values. The loss function that compares the predicted relevance to the ground-truth relevance, is given. We can add a new feature of the pair (query, document). How to detect if it improves the model significantly? What if we have several candidate features?

Interview on algorithms. You are not required to write code, it is enough to explain your algorithm to the interviewer. 1. There is a 2D polygon. The order of vertices is known. How to check if it contains a given 2D point? Now assume that we can build an indexing data structure off-line. Propose an algorithm that executes queries using logarithmic time w.r.t. number of vertices. 2. We have a large file of pairs (query, quantity) that defines a multiset on queries. You need to get an unbiased sample of about 1000 queries from that multiset. The challenge is to maintain O(1) space complexity. Can you do it in one pass?

C++ coding interview (using a laptop; should compile and run). Implement input and evaluation of an arithmetic expression in abstract Polish notation. Should support non-negative integers and 4 standard arithmetic operations. Error handling and design matter. 1 hour.

System design. 1. Develop an architecture for an Instagram-like service. There are millions of users that may have friends. You need to handle the queries to load 10 latest photos from one’s friend feed. 2. Using an online editor, define the interfaces for classes shared_ptr and weak_ptr. Explain how you would implement reference counting within them.