Intel to lay off 22,000 employees

Welcome back!

This week, we’ll learn how to implement a very important data structure that is commonly used for string search. Any guesses which one I’m talking about?

Today we will cover:

• Implement Trie (Prefix Tree)

• Database Index Optimizing Techniques

Read time: under 4 minutes

CODING CHALLENGE

Implement Trie (Prefix Tree)

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.

• void insert(String word) Inserts the string word into the trie.

• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.

• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Solve the problem here before reading the solution.

PRESENTED BY SUPERHUMAN AI

Find out why 1M+ professionals read Superhuman AI daily.

AI won't take over the world. People who know how to use AI will.

Here's how to stay ahead with AI:

1. Sign up for Superhuman AI. The AI newsletter read by 1M+ pros.

2. Master AI tools, tutorials, and news in just 3 minutes a day.

3. Become 10X more productive using AI.

Join 1 million pros and start learning AI

SOLUTION

To implement a Trie, we'll create a TrieNode class that represents each node in the trie. Each node will have a dictionary to store its children nodes and a boolean flag to mark if it's the end of a word.

For inserting a word, we traverse the trie, creating new nodes for characters that don't exist. When we reach the end of the word, we mark that node as an end node.

For searching, we traverse the trie following the characters of the word. If we can't find a character or don't reach an end node, we return False.

For prefix searching, we just need to verify if we can traverse the trie following all characters in the prefix.

Time complexity for all operations is O(n) where n is the length of the word or prefix.

SYSTEM DESIGN

Database Index Optimizing Techniques

Indexes make database queries faster. But poorly designed indexes can actually slow things down. Let's explore some key techniques to optimize database indexes.

Choosing the right columns to index is crucial. Not every column needs an index. Start by looking at your WHERE clauses. If you frequently search for customers by email, that column needs an index. But if you rarely search by phone number, indexing it just wastes space and slows down writes.

Composite indexes (indexes on multiple columns) need special attention. The order of columns matters. Put the most selective columns first. For example, in a users table, indexing (city, country) is better than (country, city) because cities are more specific than countries. This way, when searching for users in a specific city, the database can quickly narrow down the results.

Covering indexes can dramatically improve query performance. A covering index includes all columns needed by a query, allowing the database to get results directly from the index without accessing the table. If you often run:

SELECT email, name FROM users WHERE city = 'New York'

Create an index on (city, email, name) instead of just (city).

Partial indexes are useful when you only search specific rows. Instead of indexing all order statuses, you might only index active orders:

CREATE INDEX idx_active_orders ON orders(order_date) WHERE status = 'active'

Here's a comparison of different indexing techniques:

Remember, every index makes writes slower because the database needs to update the index along with the table. The key is finding the right balance between read and write performance based on your application's needs.

FEATURED COURSES

5 Courses of the Week

✅ Meta Android Developer Certificate: 12-course series teaching Android programming with Kotlin to build mobile apps like Facebook. Includes portfolio-building projects.

✅ IBM Data Science Foundations: 8-course series by University of London and IBM covering statistics, programming, and machine learning with practical projects and degree pathways.

✅ Supervised Machine Learning: 3-module course teaching Python-based ML model training for prediction and classification using NumPy and scikit-learn.

✅ Complete LangChain & LLMs Guide: Comprehensive 14-module course covering LLM integration, building AI applications from setup to advanced projects like chatbots and generators.

✅ Introduction to RAG: Learn to build apps using LLMs, LangChain, and vector databases with your organizational data. Requires basic Python knowledge.

NEWS

This Week in the Tech World

Intel to lay off 20% of workforce: New CEO Lip Bu Tan is cutting 22,000 jobs to streamline management and revive Intel's engineering culture. The layoffs aim to eliminate bureaucracy that "kills innovation" as part of Tan's turnaround strategy. Intel faces challenges from competitors like TSMC, Apple's move to ARM-based chips, and Nvidia's AI dominance.

Google Hit With Second Antitrust Blow: A federal judge ruled Google holds illegal monopolies in online advertising markets. This is Google's second major antitrust loss in under a year, potentially forcing the company to divest parts of its ad-tech business while it also battles AI competitors.

Microsoft's "1-bit" AI Model Runs on CPU: Microsoft released a neural network model using just three distinct weight values (-1, 0, or 1) instead of complex floating point numbers. This reduces memory requirements by 85-96% while matching larger systems' performance on standard CPUs.

Brain Implant Cleared by FDA: Precision Neuroscience received FDA approval for its Layer 7 Cortical Interface, a microelectrode array thinner than human hair that can record and stimulate electrical activity on the brain's surface without damaging tissue. The company competes with Elon Musk's Neuralink.

Discord Sued Over Child Safety Features: New Jersey's attorney general sued Discord for allegedly misleading consumers about its child safety features. The lawsuit claims Discord's age verification process is flawed and that its Safe Direct Messaging feature doesn't adequately protect children.

FTC Sues Uber Over Subscription Practices: The FTC sued Uber on Monday, alleging deceptive billing practices with its Uber One subscription service. The complaint claims the company misled customers about savings, complicated cancellations, and charged users without consent. Uber has responded by stating its processes are clear and legal, expressing confidence in a favorable court ruling.

Instagram Launches Blend Feature: Instagram introduced "Blend," a feature that creates a personalized Reels feed shared between friends on an invite-only basis. The tool delivers fresh tailored videos daily and allows users to spark conversations by reacting to shared content.

BONUS

Just for laughs 😏

HELP US

👋 Hi there! We are on a mission to provide as much value as possible for free. If you want this newsletter to remain free, please help us grow by referring your friends:

📌 Share your referral link on LinkedIn or directly with your friends.
📌 Check your referrals status here.

YOUR FEEDBACK

Until next time, take care! 🚀

Cheers,

Sahil + Sarra