🏝 This problem was asked 130 times

Welcome back, Interview Masters!

Ready for the summer challenge? Not push-ups, but a coding challenge asked more than 130 times by Amazon, Meta, Microsoft and others. Can you handle it?

In this newsletter, we’ll cover:

• Number of Islands problem

• How to design Google Docs?

Read time: under 4 minutes

CODING CHALLENGE

Number of Islands

Given an 'm x n' 2D binary grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Solve the problem here before reading the solution.

SOLUTION

To solve this problem, we'll use a depth-first search (DFS) approach.

We'll iterate through each cell in the grid. When we find a '1', we'll mark it as visited and explore all adjacent land cells using DFS. This process counts as one island. We'll do this for all cells in the grid.

The time complexity of this solution is O(m*n), where m is the number of rows and n is the number of columns in the grid. That’s because we visit each cell once.

SYSTEM DESIGN EXPLAINED

How to design Google Docs?

Google Docs is a collaborative online document editing platform. The main challenges are allowing multiple users to edit simultaneously without conflicts and merging edits effectively.

For real-time collaboration, Google Docs employs Operational Transformation (OT). This technique allows multiple users to edit a document simultaneously by transforming edits based on their order of arrival. The system maintains document state both on the client (web browser) and server side.

Google Docs uses a file system-like storage mechanism with concepts like directories, files, and owners. Each file object contains content, parent information, owner details, and metadata.

For access control, Google Docs implements Role-Based Access Control (RBAC). This allows for fine-grained permissions based on user roles, enhancing security and operational effectiveness.

To handle high loads, Google Docs uses techniques like sharding for database distribution and caching for frequent requests.

The system uses WebSockets for real-time updates between clients and servers, ensuring efficient communication without overwhelming the servers. You can dive into more details here.

NEWS

This week in the tech world

Samsung Unveils New Products: At its Unpacked event, Samsung introduced several new devices, including the Galaxy Ring for health tracking, two foldable smartphones, updated Galaxy Watch models, and redesigned wireless earbuds. The company emphasized AI features across its product line.

Neuralink Plans Second Human Implant: Elon Musk's brain-computer interface company, Neuralink, aims to implant its device in a second human patient within a week. The company is addressing hardware issues encountered with its first implant.

UiPath Announces Layoffs: Software developer UiPath will cut 10% of its workforce, about 420 jobs, as part of a company-wide restructuring. The move comes amid slowing revenue growth and recent leadership changes, with shares dropping 7% on the news.

HubSpot Shares Drop on Alphabet Acquisition News: HubSpot's stock plunged 12% following reports that Alphabet has shelved plans to acquire the software company. The news highlights ongoing regulatory scrutiny of big tech acquisitions and market sensitivity to potential deals.

Big Tech Bets on Humanoid Robots: Tesla, Amazon, Microsoft, and Nvidia are investing billions in AI-powered humanoid robots to face global labor shortages. Currently used in warehouses, these robots may soon expand to homes and offices.

Amazon Launches New Echo Spot: Amazon introduced a redesigned $79 Echo Spot with improved audio quality and a revamped display. The device is Amazon's first update to the Echo Spot since its 2017 debut and comes ahead of expected Alexa upgrades.

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