- InstaByte
- Posts
- Microsoft ❤️ Backtracking
Microsoft ❤️ Backtracking
Welcome back!
Today’s challenge will give you a refresher on backtracking. Also, a Coldplay concert in India crashed the ticket booking platform BookMyShow. So this week we want to see how ticket booking system works.
Here’s what to expect today:
Subsets problem
How to design BookMyShow?
Read time: under 4 minutes
CODING CHALLENGE
Subsets
Given an integer array nums
of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
Solve the problem here before reading the solution.
PRESENTED BY ELEKS
Timely, budget-aligned software delivery meeting your business goals
Quick start and timely project delivery
Industry-leading expertise covering your entire SDLC
ELEKS-owned responsibility for your project's success
SOLUTION
To solve this problem, we can use a backtracking approach. We'll start with an empty subset and progressively add elements to it. For each element, we have two choices: include it in the current subset or not.
We'll use recursion to generate all possible combinations. At each step, we'll decide whether to include the current element or not.
The time complexity of this solution is O(2^n)
, where n
is the number of elements in the input array. This is because for each element, we have two choices, and we explore all possible combinations.
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.
SYSTEM DESIGN
How to design BookMyShow?
Source: Finshots
This week, a Coldplay concert in India crashed the ticket booking platform BookMyShow. Let’s see how a ticket booking system works.
The main challenges are handling concurrent bookings and maintaining seat availability information.
BookMyShow implements a timeout locking mechanism to handle concurrent bookings. When a user selects seats, they're locked for a short period (5-10 minutes) using Redis Time-to-live (TTL).
For real-time seat availability, BookMyShow either connects directly to theater databases or uses theater APIs.
MySQL is used for transactional data like cities, theaters, screens and seats whereas Cassandra is used for high-volume data like movie details, comments, and reviews.
Elasticsearch powers the search functionality for movies and shows. To handle time-consuming tasks like ticket generation and notifications, message queues (RabbitMQ or Kafka) and workers (Python Celery) are used.
NEWS
This Week in the Tech World
Qualcomm Cuts Jobs: Qualcomm will lay off 226 employees in San Diego, mostly from engineering. The chip giant cites the need to prioritize resources amid potential Intel takeover rumors. This follows 1,200 job cuts last year.
Meta Unveils $299 Quest 3S VR Headset and First AR Glasses: Meta announced the Quest 3S, a cheaper VR headset priced at $299. The company also showcased Orion, a prototype of fully augmented reality smart glasses. New AI features for Ray-Ban Meta glasses were introduced.
Amazon Introduces AI Assistant for Sellers: Amazon launched Amelia, an AI tool to help third-party sellers resolve account issues and access sales data. It's the latest in Amazon's generative AI push, following tools like Rufus and Q for businesses.
Qualcomm Eyes Intel Takeover: Qualcomm approached Intel about a potential acquisition. Intel shares rose 3% on the news. The deal, if realized, would be one of the largest tech mergers ever, given Intel's $90 billion market cap.
Physics Wallah Raises $210M: Indian ed-tech startup Physics Wallah secured $210 million at a $2.8 billion valuation. CEO Alakh Pandey aims to expand the business and make acquisitions. The funding comes amid troubles in the ed-tech sector, including Byju's collapse.
Alibaba Releases 100+ AI Models: Alibaba unveiled over 100 open-source AI models called Qwen 2.5, targeting various sectors. The company also launched a text-to-video generation tool, competing with rivals like Baidu and OpenAI in the AI space.
Nio Launches Budget EV Brand: Chinese EV maker Nio's new brand, Onvo, unveiled its L60 SUV starting at 149,900 yuan ($21,210) with battery subscription. The price undercuts Tesla's Model Y in China. Nio plans to launch Onvo in Europe as soon as next year.
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,