- InstaByte
- Posts
- Google Microsoft clash. Who'll win?
Google Microsoft clash. Who'll win?
ALSO: What is Consistent Hashing?
InstaByte
December 04, 2024
Together with
Welcome back!
Most people are scared of Microsoft and Google interviews. But sometimes, they do ask easy problems. We’ll solve one such problem this week.
Today we will cover:
Diameter of Binary Tree problem
Consistent Hashing
Last week’s AMA with Sahil on Discord was a lot of fun. Thanks to everyone who showed up. In case you did not join our free Discord community yet, come join us here. 🙌
Read time: under 4 minutes
CODING CHALLENGE
Diameter of Binary Tree
Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
The length of a path between two nodes is represented by the number of edges between them.
Example:
Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].Solve the problem here before reading the solution.
PRESENTED BY MAPIFY
The simplest tool for summarizing knowledge
Mapify is the ultimate AI-powered tool that turns anything into clear mind maps with one click. Perfect for developers to quickly grasp complex concepts and accelerate learning.
Check out their 50% off Black Friday Deal if you are looking to boost your productivity.
SOLUTION
To solve this problem, we'll use a depth-first search (DFS) approach. Here's how it works:
For each node, we need to find the height of the subtree rooted at this node. The height of a subtree is the longest path from the node to any leaf, excluding the node itself.
After that, calculate the diameter at the node. The diameter passing through a node is the sum of heights of its left and right subtrees.
Lastly, update the maximum diameter if current node gives a larger value and return the height of current node's subtree.
The time complexity is O(n) where n is the number of nodes because we visit each node exactly once.
Note that in the solution below, we store max_diameter in a list. You can also use self.max_diameter if you prefer using an integer.
LATEST DEV TOOLS
Instantly add file uploads to your app with Pinata’s API
Pinata’s File API lets developers integrate file uploads and retrieval in just minutes. No complex setup, no configuration headaches—just fast and scalable file management.
SYSTEM DESIGN
Consistent Hashing
Consistent Hashing is a clever way to distribute data across multiple servers. Consistent Hashing helps us minimize chaos when a new server is added or a server goes down. Let’s see how it works.
When you need to store data across multiple servers (or nodes), you need a system to decide which data goes where. The simplest approach might be to take your data's hash value and do a modulo operation (%) with the number of servers. But this has a big problem. When you add or remove a server, most of your data needs to move to different locations. This creates unnecessary network traffic and strain on your system.
Consistent hashing solves this by creating a ring which maps to different hash values. So, if our hash value lies between 0 to 360, 0 to 60 degrees on the ring represent hash values between 0 and 60. The next 60 degrees represent hash values between 60 to 120 and so on. If you understood that, here’s how Consistent Hashing works:
First, you pick a value K (let's say K=3) which represents how many "virtual copies" each server gets on the ring. Each server is placed at K different positions around the ring. When you need to store a piece of data, you hash it and find its position on the ring. You then move clockwise until you hit the first server - that's where the data is stored.
The beauty of this approach is what happens when servers change. If a server fails, only the data that was specifically assigned to that server needs to move - everything else stays put. Similarly, when you add a new server, it only takes some data from its immediate neighbors on the ring, rather than triggering a massive reshuffle.
NEWS
This Week in the Tech World
Source: Getty
Google CEO Challenges Microsoft: Sundar Pichai fired back at Microsoft CEO Satya Nadella, offering to do a "side-by-side comparison" of their AI models. Pichai noted that while Microsoft uses others' models, Google develops its own.
Bitcoin Breaks $100,000: Bitcoin hit $100,000 for the first time ever, reaching $103,544. Fed chair Jerome Powell compared it to gold, and the rally comes amid growing institutional adoption and President-elect Trump's pro-crypto stance.
OpenAI Hits 300M Users: OpenAI revealed it now has 300 million weekly active users and aims for 1 billion next year. The company recently hired its first chief marketing officer and is expanding amid fierce AI competition.
Twitch Star Breaks Record: Creator Kai Cenat broke Twitch's subscriber record with nearly 727,700 subscribers during a 30-day nonstop livestream. He earned approximately $3.6 million and featured guests like Snoop Dogg and Bill Nye.
Intel CEO Ousted: Pat Gelsinger was removed as Intel CEO after a contentious board meeting over the company's struggles against Nvidia in AI and poor stock performance. Intel CFO David Zinsner and MJ Holthaus named interim co-CEOs.
Amazon Debuts AWS Buy Button: Amazon launched a "Buy with AWS" button for software vendors to sell directly to cloud customers. Similar to Buy with Prime, the feature lets customers use AWS credentials for easier purchases.
TikTok Shop Gains Momentum: TikTok Shop is attracting Amazon sellers and major retailers despite a potential U.S. ban in January. The platform hit $100 million in Black Friday sales as sellers embrace its social commerce model.
FEATURED COURSES
LEARN AI
There’s a reason 400,000 professionals read this daily.
Join The AI Report, trusted by 400,000+ professionals at Google, Microsoft, and OpenAI. Get daily insights, tools, and strategies to master practical AI skills that drive results.
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.
BONUS
Just for laughs 😏
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,