☕ New version of Vue!

Hey guys,

Hope you’re all having a terrific Saturday!

Here’s your interview problem and industry news for today.

Interview Problem

You’re given a list of 2-dimensional points (x, y coordinates) and an integer K.

Return the K closest points to the origin (0, 0).

You should use the Euclidean Distance Formula. If K is greater than the number of points, then just return all the points in the list. The answer is guaranteed to be unique and can be in any order.

Example

Input - [[1, 1], [-1, 0], [2,2]], K = 2

Output - [[-1, 0], [1,1]]

We’ll send out the solution (with working code & test-cases) in our next email, so make sure you move our emails to primary, so you don’t miss them!

Gmail users—move us to your primary inbox

• On your phone? Hit the 3 dots at top right corner, click "Move to" then "Primary"

• On desktop? Back out of this email then drag and drop this email into the "Primary" tab near the top left of your screen

Apple mail users—tap on our email address at the top of this email (next to "From:" on mobile) and click “Add to VIPs”

Industry News

• Vue v3.0.0 has been released - After 2 years of development efforts, Vue.js 3.0 has finally been released. Huge congratulations to Evan You (creator of Vue.js) and the rest of the team. The new major version of the framework provides improved performance, smaller bundle sizes, better TypeScript integration and new APIs for large scale use cases.

• Unity stock closes up 31% after IPO - So, the equity markets are going absolutely bananas right now, and a lot of companies are taking advantage of this by going public. Unity has joined the party and ended the day with shares trading at $68.35, well above the range of between $44 - 48 dollars a share. Other IPOs that have happened recently (and have gone extremely well) are Sumo Logic, Snowflake and JFrog.

• Lex Fridman interviews Commander David Fravor - If you don’t follow Lex Fridman, you should definitely check him out. He hosts the Artificial Intelligence podcast, where he mostly interviews Engineers, AI Researchers, Mathematicians and Scientists. In the latest episode, he interviewed Commander David Fravor. Commander Fravor was a Navy Pilot, and he was the pilot in charge during the famous “Tic Tac” incident off the coast of San Diego. He engaged with an Unidentified Flying Object (UFO) which was actively jamming his radar (considered an act of war). When he tried to approach the UFO in his fighter jet, the UFO disappeared, accelerating at a speed that was like nothing he’d ever seen. The USS Nimitz (United States Aircraft Carrier) had previously been tracking these UFOs on radar, and Commander David Fravor was the first to directly engage them in this jet. The story has been extensively covered in the NY Times and by CBS News. I know it’s not really “tech industry news”, but it’s Saturday so I thought we’d take a bit of break. It’s a fascinating interview and you can check it out here. I might be a bit of a UFO nut haha.

Previous Solution

As a refresher, here’s the previous question

Design an autocomplete system with insert, search and startsWith methods.

Example

words = Autocomplete()

words.insert(“Quastor”)

words.insert(“Coding”)

words.search(“Quastor”) // True

words.search(“Interview”) // False

words.startsWith(“Qu") // True

words.startsWith(“Ca”) // False

Solution

The best data structure to implement the autocomplete system would be a Trie.

If you’re unfamiliar with Tries, you can check out Gayle Laakman McDowell’s video on the data structure here.

Here’s a Python 3 REPL with the implementation and test cases.

The time and space complexity of insert are both linear.

The time complexity of search and startsWith is linear and the space complexity for both methods is constant.