☕ Do, or Do Not. There is no Trie.

Hey,

Hope you’re all having a fantastic day!

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

Interview 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

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

• TikTok - TikTok will be removed from US app stores starting Sunday due to orders from the US Government. The removals come as Oracle (and Walmart?) and ByteDance continue talks with the Trump Administration over how to resolve concerns over the video app. Existing users will be able to keep the app on their phones for now, but software updates for the apps will not be available.

• Mozilla shuts down Firefox Send - Mozilla has permanently shut down it’s Firefox Send feature for transfering files. The feature would let users transfer files up to 1 GB in size without having to log in. Hackers had been exploiting the send feature to ship malware and conduct spear phishing attacks so Mozilla decided the feature wasn’t worth the expense of fixing/maintaining. Mozilla has been going through some hard times lately as they recently laid off a quarter of their 1,000 employees. This was due to shrinking revenue from search-engine partners like Google (Google pays Mozilla to be the default search engine on FireFox) during the COVID pandemic.

• Affirm raises $500 million dollars in it’s Series G - Affirm, the “Buy Now, Pay Later” fintech company has raised $500 million dollars, bringing its total funding to $1.3 billion dollars. The company was founded in 2012 by Max Levchin, the co-founder of PayPal ( other PayPal co-founders were Peter Thiel and Elon Musk) and provides installment loans for shoppers to finance their purchase (Buy Now, Purchase Later). The Series G was led by GIC, a wealth fund established by the Singapore Government, and Durable Capital Partners.

Previous Solution

As a refresher, here’s the previous question

You are given the root node of a Binary Search Tree and a L and R value.

Return the sum of values of all the nodes with a value between L and R inclusive.

The Binary Search Tree will have unique values.

Solution

We can solve this by utilizing a Depth-First Search.

We run a DFS on the Binary Search Tree and keep a running tally of the sum of the nodes in the tree (if the value of the node is between L and R).

Additionally, we can “prune” the tree by avoiding DFS on nodes that we know will be out of the L and R range based off the properties of a Binary Search Tree.

If node.value <= L then we don’t have to run the DFS on node.left.

If node.value >= R then we don’t have to run the DFS on node.right.

You can view the Python 3 code here.

The time complexity is linear and the space complexity is constant.