vsb's blog

By vsb, 9 months ago, In English,

I'm Viktor Barinov (vsb), and I'd like to share a little about my experience with coding competitions and working at Level 5, Lyft's self-driving division. I graduated from Taurida National University, and have been an avid competitor in programming contests since high school.

My first introduction to ACM ICPC problems was at Timus in 2003. I was intrigued by math and algorithmic problems with tricky edge cases. Then I became hooked, solving a few problems from the archive daily. I later discovered UVA Online and started participating in local Ukrainian competitions, trying to advance to all-Ukrainian Finals and ACM ICPC SEERC. I then started competing at TopCoder and Codeforces. After a long path of learning, coding, and debugging, I became red on TopCoder, advanced to onsites with Google Code Jam, Mail.ru Cup, Petrozavodsk training camp, and finally got into ACM ICPC World Finals in 2009 and 2011.

I could spend whole days on problems while at my university and dreamed of turning my hobby into a career. I worked for a few companies before Lyft with more or less computer science challenges, but nothing as exciting as Lyft Level 5. Working on robotics and AI is extremely interesting and a great opportunity. Our division is a year old and operates like a startup — we have lots of high impact projects and a short feedback loop.

I'm grateful to be working on developing this important technology of the future. Having a background in Applied Math and Competitive Programming has set me up for success in my role and enabled me to learn new things for each project. Here are a few examples of projects and problems we're tackling at Level 5:

Big Data

Cars collect a lot of data from sensors and services. One car can generate a few hundred megabytes per second, and a small fleet can generate terabytes of data daily that have to be persisted and indexed in the Cloud for future analysis.

Machine Learning

Perception is a major piece of the self-driving puzzle and requires building high precision and low latency algorithms to detect cars, pedestrians, traffic signs, and more.

Motion planning

These are algorithms that generate car trajectory based on many constraints. Motiong Planning includes computational geometry, optimization methods, numerical methods, and more.

Localization and Mapping

We build 2D and 3D maps from camera and LIDAR data that is used in realtime to improve precision of localization. These problems include computational geometry, data structures and many other Computer Science areas.

Reliable and high performance software

This is a combination of competitive programming and building distributed systems. There are tons of subproblems that need to be solved, function correctly, and fit into some time limits. This needs to be an extremely reliable system — lives depend on it.

And these are just a few parts to developing a self-driving system. It requires a lot of infrastructure work, data platforms and pipelines, and more due to Big Data and High Load.

I am currently focused on building a Data Platform that allows all other projects to run data processing at a petabyte scale, and learning exciting details of all domains in the meantime. As someone with an Applied Math degree and Competitive Programming background, I see a lot of exciting projects with other teams for me to work on for years to come.

Feel free to send me personal message or comment to this post with any questions about Lyft and our Level 5 group.

Read more »

 
 
 
 
  • Vote: I like it
  • +158
  • Vote: I do not like it

By vsb, 5 years ago, In English,

Hi All,

When we solve geometry problems we often need to debug them. Using a simple paper and a pencil is boring and it would be much better when you have access to some advanced tools where you have user friendly way to input set of primitives (points, segments).

I know one really cool tool: Dynamic Geometry (DG). It is a little bit outdated and works only for Windows. But there are really cool possibilities to build geometry objects, intersections, perpendiculars, circles, tangents, etc. Then you can move base points and whole picture will move dynamically. It is awesome! Unfortunately it takes some time to add objects from your test.

It would be great to have something similar to DG that allows easily to construct input directly from your C++ or Java code and then you can open it in the tool and see the picture, modify, find intersections, etc.

I am wondering if something similar does already exist and what other tools people use when they want to debug geometry?

Read more »

 
 
 
 
  • Vote: I like it
  • +48
  • Vote: I do not like it

By vsb, 9 years ago, In Russian,
Всем привет!

Несколько раз встречался со следующей задачкой и так и не знаю как ее решать, может кто-то поможет?

Есть N человек расположенных на оси OX. Каждый из них сказал, сколько человек строго справа от него и сколько строго слева -- right[i], left[i] (в одной точке может находиться несколько человек). Требуется подсчитать сколько максимум человек говорят правду.

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By vsb, 9 years ago, In Russian,
Всем привет!

Мне рассказали решение за O(n^2) с использованием КМП, я написал для начала решение, но вместо умного КМП использовал обычный string::find, и общая сложность всего решения должна была быть чуть ли ни O(n^4). 
Послал и получил ОК...
Ощущения какой-то мистики, кто сможет "зачеленжить" мое решение или объяснить, какая его истинная ассимптотика?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it