- InstaByte
- Posts
- π§ Must-know interview problem
π§ Must-know interview problem
ALSO: API design patterns
Welcome back!
This week we will cover a popular Stack problem. Letβs dive in.
Hereβs what to expect today:
Min Stack problem
5 common API design patterns
Read time: under 4 minutes
CODING CHALLENGE
Min Stack
Design a Stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack
class:
MinStack()
initializes the stack object.void push(int val)
pushes the elementval
onto the stack.void pop()
removes the element on the top of the stack.int top()
gets the top element of the stack.int getMin()
retrieves the minimum element in the stack.
You must implement a solution with O(1)
time complexity for each function.
Example:
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
Solve the problem here before reading the solution.
PRESENTED BY ONELEET
Want SOC 2 compliance without the Security Theater?
Get the all-in-one platform for SOC 2
Build real-world security πͺ
Penetration testing, compliance software, 3rd party audit, & vCISO
SOLUTION
To solve this problem, we'll use two stacks. The first stack, which is the main stack, will store all elements. The other stack will keep track of the minimum elements.
When pushing an element, we'll add it to the main stack. If it's smaller than or equal to the current minimum, we'll also add it to the minimum stack.
For pop operations, we'll remove from both stacks if the popped element is the current minimum.
The top operation will return the top of the main stack, while getMin will return the top of the minimum stack.
This approach ensures all operations have O(1)
time complexity because each operation only involves adding or removing elements from the top of the stacks, which are constant-time operations.
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 EXPLAINED
5 Common API Design Patterns
1. REST: A way to build web services that use regular web methods (like GET and POST) to share information. Each request contains all the info needed, so the server doesn't need to remember past requests.
2. SOAP: A method for exchanging information using a special format called XML. It can remember information between requests and has strict rules for better security.
3. gRPC: A fast way to connect services. It uses a special language to define how data should look, which makes sending data quicker and uses less space than other methods.
4. WebSocket: Instead of asking for information and waiting for a reply each time, WebSocket keeps a constant connection open. This is great for when you need to send and receive updates quickly.
5. GraphQL: This lets the person asking for information choose exactly what they want. It can also send updates in real-time when information changes on server.
NEWS
This Week in the Tech World
Cisco cuts 7% of workforce: Cisco is laying off 7% of staff despite beating earnings estimates. The networking giant reported declining revenue for the third straight quarter as it shifts to more software and subscription offerings.
Ola Electric IPO pops 20%: Indian EV startup Ola Electric surged 20% in its market debut, valuing the company at $4.8 billion. The SoftBank-backed firm aims to tap into India's growing electric two-wheeler market.
Google launches AI-powered Android: Google announced new Android features powered by its Gemini AI assistant. The company also unveiled the Pixel 9 phone series with updated AI capabilities as it races to get AI products to consumers.
YouTube ex-CEO dies at 56: Former YouTube CEO Susan Wojcicki has died at 56 from cancer. She was a key early Google employee and one of few female tech CEOs in Silicon Valley.
Huawei plans new AI chip: Chinese tech giant Huawei is set to launch a new AI chip to challenge Nvidia's H100, despite U.S. sanctions. The move signals Huawei's ability to develop advanced tech amid restrictions.
UK eyes tougher online safety laws: Britain considers strengthening internet safety regulations after riots sparked by misinformation. The move follows controversial comments by X owner Elon Musk about the situation.
Intel sells Arm stake: Intel has sold its 1.18 million shares in chip designer Arm Holdings amid company-wide restructuring efforts. The sale likely raised nearly $147 million as Intel cuts costs to compete in the chip race.
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,