❤️ Google and Amazon love this

Welcome back, Interview Masters!

Today’s coding challenge is a Google and Amazon favorite. Let’s see if you can solve it in O(n).

In today’s newsletter, we’ll cover:

• Longest Consecutive Sequence

• How to design X (Twitter)?

Read time: under 4 minutes

CODING CHALLENGE

Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Solve the problem here before reading the solution.

REFER TO WIN $500

Corium helps tech companies in the US hire top 1% developers. Here is how you can win a referral bonus from Corium:

1. Talk to a US-based hiring manager about Corium - for example, your own manager or anyone who might be hiring developers.

2. Explain how Corium can help them hire high quality engineering talent quickly at lower cost.

3. Submit this form indicating that you've spoken with someone about Corium.

4. If they hire someone from Corium, you will earn a $500 referral bonus!

SOLUTION

To solve this problem in O(n) time, we can use a HashSet to store all the numbers in the array. This will allow us to check if a number is present in the set in O(1) time.

We'll iterate through each number in the array. For each number, we'll check if its previous consecutive number (num - 1) is not in the set. If it's not, it means this number is the start of a sequence.

We'll then keep incrementing the number and checking if the next consecutive number is in the set. We'll do this until we find a number that is not in the set, which marks the end of the sequence.

We'll update the longest sequence length if the current sequence length is greater.

The time complexity of this solution is O(n) because we iterate through the array once, and each HashSet operation takes O(1) time on average.

SYSTEM DESIGN EXPLAINED

How to design X (Twitter)?

The key requirements are: Posting new tweets, following users, viewing a newsfeed of tweets from followed users and searching.

We'll use a microservices architecture with services for Newsfeed generation, User information, Tweet information and Search. Services will communicate via REST or gRPC.

The Newsfeed service will pre-generate and cache feeds for fast access. It can use a ranking algorithm like EdgeRank to prioritize relevant tweets. An approach like fan-out on write can immediately push new tweets to followers' feeds.

For data partitioning and scalability, we'll shard databases using consistent hashing. Cassandra or PostgreSQL can store core data while Elasticsearch enables fast searches.

To store photos and videos, we will use Object Storage like S3. We can cache them on a CDN for fast delivery.

You can dive into more details here.

NEWS

This week in the tech world

Apple Unveils AI Plans: Apple announced its AI push called "Apple Intelligence" with AI across devices and apps. It's integrating ChatGPT into iOS 18 via Siri. Other updates include custom AI emojis, AI writing tools, and AI enhancements for apps like Photos.

Mistral AI Funding: French AI startup Mistral AI raised $645 million at a $6 billion valuation. Microsoft is an investor. Mistral aims to take on OpenAI and become Europe's generative AI champion, building large language models similar to GPT.

Apple Surpasses Microsoft: Apple briefly became the world's most valuable company again this Wednesday June 12th, fueled by enthusiasm over its artificial intelligence plans announced at WWDC. Its market cap hit $3.3 trillion, edging out Microsoft's $3.2 trillion, but the lead didn't last until the closing bell.

OpenAI Executive Hires: OpenAI hired Sarah Friar from Nextdoor as CFO and Kevin Weil from Planet Labs as chief product officer. OpenAI also announced a deal to integrate ChatGPT with Apple's Siri.

Humane Selloff: AI hardware startup Humane, founded by ex-Apple designers, is seeking a buyer after its AI Pin device received bad reviews. The company is in talks with HP, telecom firms and has hired an investment bank to advise on a potential deal.

Microsoft Outsources AI: Microsoft is effectively outsourcing its best AI R&D to OpenAI, reducing itself to an "AI consultancy" role, according to Okta CEO Todd McKinnon. This could benefit Google's organic AI efforts.

AI in Education Booms: Almost half of U.S. teachers and students now use ChatGPT weekly, with 70% of students approving of AI chatbots in education. Adoption has spiked sharply over the past year despite cheating concerns.

BONUS

Just for laughs 😏

REFER FOR THE WIN

👋 Hey! Share your referral link with friends to unlock Hidden Treasures:

📌 Share your referral link on LinkedIn or with your friends to unlock the treasures quicker!
📌 Check your referrals status here.

YOUR FEEDBACK

Until next time, take care! 🚀

Cheers,

Sahil + Sarra