- InstaByte
- Posts
- π¨ Google asked this easy problem
π¨ Google asked this easy problem
ALSO: Why Shard Databases? And How?
Welcome back!
Why did both Google and Meta ask this easy problem? Letβs find out.
Hereβs what to expect today:
Valid Palindrome
Why Shard Databases? And How?
Read time: under 4 minutes
COMMUNITY
InstaByte Question Bank
π§ Help each other by sharing the actual questions you were asked in a recent interview. Use this form to submit your question.
We will share the submitted questions on this weekly newsletter - stay tuned!
Note: Your submission is anonymous.
CODING CHALLENGE
Valid Palindrome
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s
, return true
if it is a palindrome, or false
otherwise.
Example 1:
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
Example 2:
Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.
Solve the problem here before reading the solution.
PRESENTED BY 1440
All your news. None of the bias.
Be the smartest person in the room by reading 1440! Dive into 1440, where 3.5 million readers find their daily, fact-based news fix. We navigate through 100+ sources to deliver a comprehensive roundup from every corner of the internet β politics, global events, business, and culture, all in a quick, 5-minute newsletter. It's completely free and devoid of bias or political influence, ensuring you get the facts straight.
SOLUTION
To solve this problem, we'll use a two-pointer approach. We'll have two pointers, one starting from the beginning and one from the end.
We'll move these pointers inwards, skipping non-alphanumeric characters and comparing the valid characters we find. We'll ignore case by converting characters to lowercase when comparing.
If at any point the characters don't match, it's not a palindrome.
The time complexity of this solution is O(n)
, where n
is the length of the string.
UPDATE
π¨ Did you notice? Interview Master is now InstaByte!
We've rebranded with a clear purpose in mind: to support you at every stage of your career, not just during interviews.
Look forward to content on design docs, promotions and more. We're thrilled to begin this new phase with you!
SYSTEM DESIGN EXPLAINED
Why Shard Databases? And How?
Imagine you have a big library with millions of books. You want to make it easy for people to find the books. Instead of having all the books in one giant shelf, you can divide the library into smaller sections.
Each section can now contain books on a specific topic like science, history, or fiction. If someone is looking for a book on history, they can go straight to the history section without having to search through the entire library.
Now, think of each section as a shard in a database. In the world of databases, sharding is like organizing data into smaller, manageable pieces.
Here are a few advantages of sharding:
Horizontal Scalability: Sharding allows a database to handle more data and traffic by distributing the load across multiple servers.
Increased Throughput: With data distributed across multiple shards, queries can be processed in parallel. This parallel processing improves overall system performance.
High Availability: If one shard fails, it doesn't affect the entire database. This increases the system's reliability and availability.
Here are some common ways to implement sharding:
Range-based: In this approach, data is divided based on a specific range of values, such as numerical ranges or alphabetical ranges. Each shard is responsible for storing data within a particular range. For example, you might have one shard for users with IDs 1-1000, another for IDs 1001-2000, and so on.
Modulo-Based Sharding: Modulo-based sharding uses the modulo operation on a key (e.g. user ID or timestamp) to determine the shard assignment. This distributes data evenly across shards, ensuring a uniform distribution of workload.
Hash-Based: Hash-based sharding involves applying a hash function to a piece of data (e.g. a user ID or a key) to determine which shard will store that data. Similar to modulo-based sharding, data is distributed uniformly across the shards.
Geography-Based: Geographical sharding involves distributing data based on the geographic location of users or resources. This can help reduce latency by storing data closer to users in different regions.
Consistent Hashing: Consistent hashing provides a way to balance the distribution of data across shards while minimizing the impact of adding or removing shards. It uses a hash ring to map keys to shards. This leads to a more elastic system where the addition or removal of a shard affects only a portion of the data.
NEWS
This Week in the Tech World
Image credit: Timmy Loen
Intel announces major layoffs: Intel plans to cut 15% of its workforce, about 15,000 jobs, as part of a $10 billion cost-reduction plan. The chipmaker also reported lower-than-expected quarterly results and reduced its dividend.
X sues advertisers over boycott: Elon Musk's X (formerly Twitter) is suing advertisers for an alleged "massive boycott" that cost billions. The lawsuit targets the World Federation of Advertisers and member companies like Unilever and Mars.
Turkey blocks Instagram: Turkey blocked access to Instagram nationwide, reportedly due to the platform's removal of posts related to Hamas leader Ismail Haniyeh's death. The government accused Instagram of censorship.
Google pulls controversial AI ad: Google removed an Olympics ad featuring its Gemini AI chatbot after backlash. The ad showed a child using AI to write a fan letter, sparking criticism about replacing human creativity with automation.
China launches Starlink rival: China sent its first batch of "Thousand Sails" internet satellites into orbit, aiming to rival SpaceX's Starlink. The constellation will eventually include over 15,000 satellites for global internet coverage.
Google loses antitrust case: A U.S. federal judge ruled that Google illegally monopolized search and text advertising markets. The decision focuses on Google's exclusive search arrangements on Android and Apple devices.
OpenAI co-founder leaves for rival: John Schulman, OpenAI co-founder, is leaving to join rival AI company Anthropic. He cites a desire to focus on AI alignment and return to hands-on technical work as reasons for the move.
Core Scientific expands AI business: Bitcoin miner Core Scientific announced a $6.7 billion partnership with CoreWeave to expand its AI infrastructure. This marks a significant pivot from crypto mining to AI computing services.
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
What did you think of this week's email?Your feedback helps us create better emails for you! |
Until next time, take care! π
Cheers,