A human defeats AI in coding

Welcome back!

This week’s coding challenge is hard to finish in an actual interview. Let’s see if you can solve it within 45 minutes.

Today we will cover:

• Design Add and Search Words Data Structure

• Cache Eviction Policies

Read time: under 4 minutes

CODING CHALLENGE

Design Add and Search Words Data Structure

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

• WordDictionary() Initializes the object.

• void addWord(word) Adds word to the data structure, it can be matched later.

• bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]

Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

Solve the problem here before reading the solution.

PRESENTED BY THE RUNDOWN AI

Learn AI in 5 minutes a day

This is the easiest way for a busy person wanting to learn AI in as little time as possible:

1. Sign up for The Rundown AI newsletter

2. They send you 5-minute email updates on the latest AI news and how to use it

3. You learn how to become 2x more productive by leveraging AI

Sign up to start learning.

SOLUTION

To solve this problem efficiently, we'll use a Trie (prefix tree) data structure. This allows us to efficiently add words and search for patterns, especially with wildcard characters. The Trie will help us handle both exact word matches and pattern searches with dots. We'll implement a recursive search method to handle the dot wildcard matching.

Here's the implementation:

1. We use a TrieNode class to represent each node in the Trie.

2. addWord method adds words to the Trie character by character.

3. search method uses depth-first search (DFS) to handle wildcard matching.

4. For dot ('.') characters, we try all possible child nodes recursively.

5. The search is efficient for exact matches and provides flexibility for wildcard searches.

Time complexity:

• addWord: O(m), where m is the length of the word

• search: O(26^m) in the worst case with many dot wildcards

Space complexity: O(n*m), where n is the number of words and m is the average word length

SYSTEM DESIGN

Cache Eviction Policies

Cache is a high-speed storage layer that sits between an application and its primary data store. It holds frequently accessed data to speed up reads. When a program needs to fetch data, it first checks the cache before going to the slower main storage.

Cache storage typically uses RAM which is costlier than the main storage on disc. Due to this cost constraint, cache size is usually limited. When this limited cache becomes full and we need to add new items, we must decide which existing items to remove. This is where cache eviction policies come into play.

The simplest approach to cache eviction is First-In-First-Out (FIFO). As the name suggests, FIFO removes the item that was added to the cache first. Think of it as maintaining a queue of cached items – when we need space, we remove the item at the front of the queue (the oldest one) and add the new item at the back. While FIFO is straightforward to implement, it has a significant drawback. Consider a scenario where a particular piece of data is accessed very frequently but happened to be cached first. Under FIFO, this frequently used item would be the first to be removed despite being the most useful item in the cache.

This limitation leads us to consider frequency of access as a metric for eviction, bringing us to the Least Frequently Used (LFU) policy. LFU keeps track of how many times each cached item has been accessed and removes the item with the lowest access count when space is needed. This works well for many scenarios, but LFU too has its shortcomings. Consider a situation where certain data was accessed many times in the past but hasn't been used recently. With LFU, this item would stay in cache due to its high historical access count, even though it's no longer needed.

This brings us to the Least Recently Used (LRU) policy, which focuses on recency rather than frequency. LRU tracks when each item was last accessed and removes the item that hasn't been accessed for the longest time. This policy works particularly well for workloads where items accessed recently are likely to be accessed again soon. LRU handles both the FIFO problem of evicting frequently used items and the LFU problem of holding onto items that were popular in the past but are no longer useful.

FEATURED COURSES

5 Courses of the Week

✅ Artificial Intelligence A-Z: Comprehensive AI course building 8 different AIs including LLM business agents, Q-Learning warehouse optimization, Deep Q-Learning moon landing, and fine-tuned medical chatbots, with intuition-focused tutorials and Google Colab implementation.

✅ Intro to Programming: Fundamental programming skills course covering essential concepts and techniques used across all programming disciplines including app development, web development, and data analysis.

✅ AI & ML Basics: Beginner-friendly introduction explaining what AI and ML are, how they function, and their transformative impact across industries, completed in under one hour.

✅ Rust Programming: Ground-up introduction to Rust programming language, developing skills to build efficient and scalable applications from beginner to advanced levels.

✅ PHP Programming: Two-part course covering PHP fundamentals (data types, arrays, OOP, databases) then building a complete job listing website from scratch with custom routing, CRUD operations, authentication, and security features without frameworks.

MASTER AI 

Start learning AI in 2025

Keeping up with AI is hard – we get it!

That’s why over 1M professionals read Superhuman AI to stay ahead.

• Get daily AI news, tools, and tutorials

• Learn new AI skills you can use at work in 3 mins a day

• Become 10X more productive

Sign up and start mastering AI

NEWS

This Week in the Tech World

Polish Programmer Beats AI in Coding Contest: A Polish programmer defeated OpenAI's AI model in a 10-hour coding championship in Tokyo. Despite being "completely exhausted," he narrowly won with a 9.5% margin, proving human skill still matters in competitive programming.

Amazon Cuts Cloud Computing Jobs: Amazon confirmed layoffs in its AWS cloud division, including the training and certification unit. The cuts are part of ongoing workforce streamlining efforts, not primarily due to AI investments.

Microsoft SharePoint Under Attack: Microsoft warned of "active attacks" on SharePoint servers affecting global businesses and governments. The vulnerability allows unauthenticated access and code execution. Fixes have been released for affected versions.

Meta Rejects EU AI Agreement: Meta declined to sign Europe's AI code of practice, calling it an overreach that will "stunt" companies. The rules aim to improve AI transparency and safety but Meta says they create legal uncertainties.

Uber Partners with Lucid for Robotaxis: Uber announced a six-year deal to deploy over 20,000 robotaxis with Lucid Motors and Nuro. Uber will invest $300 million in Lucid, with the first robotaxis launching in a major US city next year.

YouTube Removes 11,000 Propaganda Channels: Google removed nearly 11,000 YouTube channels linked to state propaganda from China, Russia, and other countries in Q2. Over 7,700 channels were Chinese, promoting Xi Jinping and commenting on US affairs.

Nvidia CEO Sells More Shares: Jensen Huang sold another $12.94 million worth of Nvidia shares as part of his plan to sell up to 6 million shares. The sales come as Nvidia's market cap surpassed $4 trillion, making it the world's most valuable company.

Microsoft Stops Using Chinese Engineers for Pentagon: Microsoft revised practices to ensure China-based engineers no longer provide technical support to US defense clients using Azure cloud services, addressing national security concerns.

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