🧠 Most asked Leetcode HARD problem

Welcome back, Interview Masters!

Today’s coding challenge is one of the most asked Leetcode hard problems. Let’s see if you can solve it.

Today, we’ll cover:

• Merge k Sorted Lists problem

• How to design Airbnb

Read time: under 4 minutes

CODING CHALLENGE

Merge k Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Solve the problem here before reading the solution.

REFER FOR THE WIN

🚨 We will host a Career Chat with a Googler on June 8th. Refer 10+ people to join a 30-minute Q&A session with Sahil. Looking forward to seeing many of you!

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

SOLUTION

Let’s imagine that we have a pointer at the beginning of each list. If we can find the minimum among all the numbers at the pointers, we can directly add this minimum number to the merged list.

Since we have already used the minimum number, we can move the pointer at this number to the next element in that list. Now, we just repeat the process of finding the minimum number, adding it to the merged list and moving the pointer.

To find the minimum number fast, we will use a min heap. First, we will push the first node of each linked list into the min heap. Then, we’ll pop the minimum element and append it to the merged list. After that, we push the next node of the merged element to the heap, if it exists.

Using a min heap keeps track of the pointers and adding the next element moves the pointer to the next number.

Our heap size will never exceed k. Pushing and popping elements on a heap of size k has log(k) time complexity. And we do this for each node which makes it N times. So, the overall time complexity is O(Nlog(k)).

SYSTEM DESIGN EXPLAINED

How to design Airbnb?

Let's design an online hotel booking service, like Airbnb.

The functional requirements are straightforward. Hotel managers should be able to register properties and update their information. Travelers should be able to search for and book hotels.

There are 4 main services: Hotel Registration Service, Hotel Search Service, Hotel Booking Service and Booking Management Service.

Content Delivery Network (CDN) stores hotel images for faster loading times whereas MySQL can be used for the rest of the hotel data and user data.

Kafka is used for real-time data communication, and elastic search helps users find hotels by supporting fuzzy matches.

Once a booking is complete, the information is moved to a Cassandra database. Check out this article for more details.

NEWS

This week in the tech world

ChatGPT arrives on iPhone: Apple is shaking up its AI game by adding ChatGPT, powered by OpenAI, to iPhones. This move suggests Siri might not be the only AI assistant on iPhones for much longer, with rumors swirling about Google's Gemini also joining the party.

Google eyes HubSpot acquisition: Shares for HubSpot surge on reports that Google's parent company, Alphabet, is considering an all-stock acquisition. This potential deal would be Google's biggest ever, dwarfing their previous record of $12.5 billion paid for Motorola Mobility in 2011.

Lucid Motors layoffs: Lucid Motors, a California-based company that manufactures luxury electric vehicles, is cutting 400 jobs, or about 6% of its workforce, by the end of Q3, despite recently raising $1 billion. The CEO says the layoffs are necessary to cut costs.

UiPath CEO out, stock tumbles: UiPath's stock price plunges 30% after CEO Rob Enslin resigns and co-founder Daniel Dines returns to the helm. Enslin had been CEO for just five months and did not provide a specific reason for his resignation.

Google's AI Overview misfires: AI Overview, designed to summarize search results, has raised expert concerns about providing misleading information. In one case, it incorrectly attributed Neil Armstrong's famous quote "one small step for man" to a cat. Experts warn it may perpetuate biases and spread misinformation. Google is working on a fix.

Musk’s xAI raised $6 Billion: Elon Musk's company, xAI, has raised $6 billion to develop AI products. The funding will be used for R&D and to bring xAI's products to market. Investors include Andreessen Horowitz, Sequoia Capital, and Fidelity Management. Elon Musk announced the formation of xAI in July of last year.

BONUS

Just for laughs 😏

YOUR FEEDBACK

Until next time, take care! 🚀

Cheers,

Sahil + Sarra