All FAANGs asked this problem

Happy New Year! 🎊

We hope that you had a good break and you are ready to crush 2025. This week’s coding challenge is easy but very popular with FAANG companies.

Today we will cover:

• Majority Element

• Cache Eviction Policies

Read time: under 4 minutes

CODING CHALLENGE

Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. 

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Solve the problem here before reading the solution.

PRESENTED BY HUBSPOT

Use AI as Your Personal Assistant

Ready to save precious time and let AI do the heavy lifting?

Save time and simplify your unique workflow with HubSpot’s highly anticipated AI Playbook—your guide to smarter processes and effortless productivity.

Download the free guide today.

SOLUTION

To solve this problem, we can use the Boyer-Moore Voting Algorithm. This is a clever algorithm that uses the fact that the majority element appears more than n/2 times.

The algorithm works by keeping a count and a candidate. When we find the same element as the candidate, we increase the count. When we find a different element, we decrease the count.

If the count becomes 0, we pick a new candidate and reset count to 1. The key insight is that the majority element will always remain as the final candidate.

The time complexity of this solution is O(n), where n is the length of the array. The space complexity is O(1) since we only use two variables.

IN THE AI WORLD

Writer RAG tool: build production-ready RAG apps in minutes

RAG in just a few lines of code? We’ve launched a predefined RAG tool on our developer platform, making it easy to bring your data into a Knowledge Graph and interact with it with AI. With a single API call, writer LLMs will intelligently call the RAG tool to chat with your data.

Integrated into Writer’s full-stack platform, it eliminates the need for complex vendor RAG setups, making it quick to build scalable, highly accurate AI workflows just by passing a graph ID of your data as a parameter to your RAG tool.

Learn more about our production ready RAG tooling here.

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

✅ Data Analyst in Python: Learn to analyze and visualize data using Python's key libraries like pandas, NumPy and Seaborn.

✅ Become an AI Engineer: Build AI applications by integrating LLMs through OpenAI, Hugging Face and LangChain. Learn to create chatbots, recommendation engines and search systems.

✅ The Web Developer Bootcamp 2025: Learn HTML, CSS, JavaScript, NodeJS, Express and much more.

✅ 100 Days of Code: Master the Python programming language by building 100 unique projects over 100 days.

✅ Microservices with Node JS and React: Architect large, scalable apps using a collection of microservices using React and Node.

NEWS

This Week in the Tech World

Nvidia Unveils Project Digits: Nvidia launches $3,000 desktop AI supercomputer aimed at researchers and students. The compact device features a Grace Blackwell Superchip capable of running 200B parameter models and will be available in May 2025.

Microsoft Cuts Jobs: Microsoft implements performance-based job cuts affecting less than 1% of its 228,000 employees. The company says the move aligns with its focus on high-performance talent, despite strong financials and 38% net income margin.

Meta Drops Fact-Checking: Meta eliminates third-party fact-checking program in favor of "Community Notes" system similar to X. CEO Zuckerberg cites reducing censorship and restoring free expression as key motivations for the change.

Cybertruck Blast Investigation: Police reveal Vegas Cybertruck explosion suspect used ChatGPT to plan the incident. Officials identify the driver as Matthew Livelsberger, marking the first known use of ChatGPT for explosive device planning in US.

Apple AI Alerts Misfire: Apple's AI notification summarization feature generates false news alerts, including incorrect claims about sports results and celebrities. The company promises a fix in coming weeks to clarify when content is AI-generated.

eBay-Meta Partnership: eBay shares surge 9% as Meta allows listings on Facebook Marketplace. The test launching in Germany, France, and US aims to boost eBay's competitiveness against rivals like Amazon and Walmart.

GET AHEAD OF AI

Learn how to make AI work for you

AI won’t take your job, but a person using AI might. That’s why 800,000+ professionals read The Rundown AI – the free newsletter that keeps you updated on the latest AI news and teaches you how to use it in just 5 minutes a day.

Sign up to start learning.

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