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?

Question

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?

Yandex

Sollicitatievraag bij Yandex

Gevolgde bedrijven

Vacatures