Meta logo

Meta Software Engineer Interview Questions

46 practice questions for Meta Software Engineer interviews

Meta software engineer interviews cover algorithms, data structures, system design, and coding problems drawn from real interview rounds.

Software Engineer Backend Engineer Frontend Engineer Full Stack Engineer Mobile Engineer Data Engineer Data Scientist ML Engineer DevOps Engineer DevOps Engineer Product Manager SRE Security Engineer Engineering Manager Data Analyst UX/UI Designer QA Engineer
coding Hard Verified Question #1

1. OA[CodeSignal] Cloud File Storage System


Category: Graph coding problem

Question Your task is to implement a simple in-memory cloud storage system that maps objects (files) to their metadata (name, size, etc.). You...

Input: Graph (nodes and edges)
Output: Array
Want to practise this one?
Create a free account to open the full question and practise Meta questions with AI.
Sign up free
coding Hard Verified Question #2

2. OA[CodeSignal] Design Banking System


Category: Graph coding problem

Question Design a banking system that supports account management, transactions, and various financial operations.

Input: Graph (nodes and edges)
Output: Computed result
coding Medium Verified Question #3

3. Friend Requests Sent


Category: Algorithm coding problem

Question Given a list of ages representing users in a social network, calculate the total number of friend requests each user will send based on...

Input: List
Output: Computed result
coding Hard Verified Question #4

4. Minimum Prefix Subset


Category: Tree coding problem

Question Given a list of strings, find the minimum subset of prefixes that can represent the entire input set. A string is "represented" if it...

Input: Array of strings
Output: Integer
coding Medium Verified Question #5

5. Shortest Substring with Alphabet


Category: Sliding window coding problem
*This is a popular twist Meta interviewers often put on the classic leetcode problem to find a minimum window substring.* Given an input string and...
Input: String
Output: Integer
coding Medium Verified Question #6

6. Shortest Substring with N Unique Characters


Category: String coding problem

Shortest Substring with N Unique Characters *This is a variation of the leetcode problem* Given a string s and an integer n, find the length of...

Input: String
Output: Computed result
coding Hard Verified Question #7

7. OA[CodeSignal] In-Memory Database


Category: Graph coding problem

Description Implement a simplified in-memory database that supports record manipulation with various operations. The system should handle basic...

Input: Graph (nodes and edges)
Output: Array
coding Easy Verified Question #8

8. [CodeSignal] Count Non-Dominant Elements


Category: Array coding problem

Question Given an array of integers numbers, count all elements that are not equal to numbers[0] or numbers[1] (if those indices exist in the...

Input: Array of integers
Output: Computed result
coding Easy Verified Question #9

9. [CodeSignal] Sort Words By Vowel Consonant Difference


Category: Array coding problem

Question You are given a string text consisting of unique lowercase English words separated by spaces. For each word, compute the absolute...

Input: Array
Output:** Computed result
coding Medium Verified Question #10

10. [CodeSignal] Warehouse Robot Commands


Category: Matrix coding problem

Question In a highly automated warehouse, a robot organizes packages stored in a rectangular grid. The grid is represented as a 2D list of integers...

Input: Matrix (2D array)
Output: Computed result
coding Hard Verified Question #11

11. [CodeSignal] House Segments After Destruction


Category: Array coding problem

Question You are monitoring the building density in a district of houses. The district is represented as a number line, where each house is located...

Input: Array of integers
Output: Array
coding Medium Verified Question #12

12. Distribution Center Placement


Category: Array coding problem
A logistics company is expanding its distribution network along a single highway. You are given an array of integers locations representing the...
Input: Array of integers
Output: Computed result
coding Hard Verified Question #13

13. Expression Simplifier


Category: String coding problem
Given an algebraic expression string containing single lowercase-letter variables, the operators + and -, and parentheses ( and ), simplify...
Input: String
Output: Computed result
coding Medium Verified Question #14

14. Minimum Sum Tree Path


Category: Binary tree coding problem

Minimum Sum Tree Path

Input: Binary tree
Output: Computed result
technical Medium Verified Question #15

15. How to pass AI Enabled Coding Rounds From FAANG Interviewer


Category: Algorithm coding problem

Tips For AI Coding Rounds AI coding rounds are not as different from regular coding rounds as you might think. The interviewer still needs to get...

Input: Given input
Output: Computed result
coding Hard sliding window #1

1. [AI Enabled Coding] WhatsApp Business Delivery Admission Engine


Scenario


Meta's WhatsApp Business delivery infrastructure needs an auditable admission step before outbound messages enter delivery queues. Implement a batch-replay engine that protects recipients from bursts and enforces business-level delivery budgets; you may use an AI assistant while coding, but must explain and test its output. The limits below are hypothetical interview requirements, not actual WhatsApp policies.

Part 1 — Default delivery safeguards


  • Every message is a map containing string values for id, timestamp, tenant, sender, recipient, campaign, and bytes. timestamp is an integer number of seconds and bytes is the nonnegative payload size, both encoded as strings.

  • Process messages in ascending numeric timestamp order, breaking ties by ascending ASCII id. Return decisions in that order, regardless of input order.

  • Apply payload_size: a message may contain at most 1000 bytes.

  • Apply sender_rate: each (tenant, sender) may admit at most 3 messages in a rolling 60-second window.

  • Apply recipient_rate: each (tenant, recipient) may admit at most 2 messages in a rolling 60-second window.

  • For a message at time t, a window of width w contains previously admitted messages with timestamps in (t - w, t], plus the current message when calculating projected usage. Earlier processed messages at the same timestamp count.

  • Evaluate every rule. Admit the message only if every projected usage is at or below its limit. Rejected messages consume no budget under any rule. Return every violated rule name in ascending ASCII order.

  • Your return type is up to you; the examples use a list of decisions containing id, status (ADMITTED or REJECTED), and violations.


Function signature: evaluate_messages(messages: list[dict[str, str]]) -> candidate_defined

Example 1:


Input:
{
  "messages": [
    {"id":"m1","timestamp":"0","tenant":"T","sender":"a","recipient":"x","campaign":"C","bytes":"400"},
    {"id":"m2","timestamp":"1","tenant":"T","sender":"a","recipient":"x","campaign":"C","bytes":"600"},
    {"id":"m3","timestamp":"2","tenant":"T","sender":"a","recipient":"x","campaign":"C","bytes":"100"},
    {"id":"m4","timestamp":"3","tenant":"T","sender":"a","recipient":"y","campaign":"C","bytes":"1000"},
    {"id":"m5","timestamp":"4","tenant":"T","sender":"a","recipient":"z","campaign":"C","bytes":"100"},
    {"id":"m6","timestamp":"5","tenant":"T","sender":"b","recipient":"z","campaign":"C","bytes":"1001"}
  ]
}

Output:
[
  {"id":"m1","status":"ADMITTED","violations":[]},
  {"id":"m2","status":"ADMITTED","violations":[]},
  {"id":"m3","status":"REJECTED","violations":["recipient_rate"]},
  {"id":"m4","status":"ADMITTED","violations":[]},
  {"id":"m5","status":"REJECTED","violations":["sender_rate"]},
  {"id":"m6","status":"REJECTED","violations":["payload_size"]}
]

Explanation: m3 would be the third admitted message to recipient x, exceeding 2. Because it is rejected, m4 becomes sender a's third admitted message and is allowed, including its exactly-1000-byte payload. m5 would be sender a's fourth message. m6 exceeds the payload limit by 1 byte.

Part 2 — Configurable overlapping budgets


Other WhatsApp Business teams now need tenant-wide byte budgets and campaign-specific message budgets, with independently configurable windows. Extend the engine without replacing the Part 1 rules. The approach must be flexible enough to support future additions of the same kind without adding a special branch for each new rule.
Discuss how your return type changes before implementing this extension.
  • Accept extra_rules, a list of maps whose keys and values are strings. Each map contains id, group_by, metric, window_seconds, and limit.

  • group_by is a comma-separated list of distinct fields chosen from tenant, sender, recipient, and campaign, with no whitespace. All fields together form the rule's grouping key.

  • metric is either messages, contributing 1 per admitted message, or bytes, contributing the message's payload size. window_seconds is a positive integer string; limit is a nonnegative integer string.

  • Each extra rule applies to every message, independently for each grouping key. Its projected usage is the sum of contributions from prior admitted messages in its window plus the current contribution. A rule fires only when projected usage is strictly greater than its limit.

  • Admission is atomic across the default and extra rules: evaluate every rule against the same previously admitted history, then commit to all applicable histories only if none fires.

  • Provide rejection diagnostics containing each violated rule's rule, numeric projected, and numeric limit, sorted by rule ID. For payload_size, projected usage is simply the current payload size.

  • Also provide batch-wide admitted_totals containing numeric messages and bytes. These totals include all admitted messages in the batch, even if their rolling-window entries later expire.

  • The examples use an object containing decisions and admitted_totals; an equivalent typed representation is acceptable.


Extended signature: evaluate_with_rules(messages: list[dict[str, str]], extra_rules: list[dict[str, str]]) -> candidate_defined

Example 2:


Input:
{
  "messages": [
    {"id":"m1","timestamp":"0","tenant":"T","sender":"a","recipient":"x","campaign":"C","bytes":"700"},
    {"id":"m2","timestamp":"10","tenant":"T","sender":"b","recipient":"y","campaign":"C","bytes":"600"},
    {"id":"m3","timestamp":"20","tenant":"T","sender":"c","recipient":"z","campaign":"C","bytes":"300"},
    {"id":"m4","timestamp":"30","tenant":"T","sender":"c","recipient":"z","campaign":"D","bytes":"200"},
    {"id":"m5","timestamp":"60","tenant":"T","sender":"d","recipient":"w","campaign":"C","bytes":"700"}
  ],
  "extra_rules": [
    {"id":"tenant_bytes","group_by":"tenant","metric":"bytes","window_seconds":"60","limit":"1500"},
    {"id":"campaign_cap","group_by":"tenant,campaign","metric":"messages","window_seconds":"30","limit":"2"}
  ]
}

Output:
{
  "decisions": [
    {"id":"m1","status":"ADMITTED","violations":[]},
    {"id":"m2","status":"ADMITTED","violations":[]},
    {"id":"m3","status":"REJECTED","violations":[
      {"rule":"campaign_cap","projected":3,"limit":2},
      {"rule":"tenant_bytes","projected":1600,"limit":1500}
    ]},
    {"id":"m4","status":"ADMITTED","violations":[]},
    {"id":"m5","status":"ADMITTED","violations":[]}
  ],
  "admitted_totals":{"messages":4,"bytes":2200}
}

Explanation: After m2, tenant usage is 700 + 600 = 1300 bytes and campaign C has 2 messages. m3 projects 1300 + 300 = 1600 bytes and 3 campaign messages, so both extra rules fire and neither budget changes. m4 belongs to campaign D and raises tenant usage to exactly 1300 + 200 = 1500. At time 60, m1 is excluded by the open left boundary; m5 projects 600 + 200 + 700 = 1500 tenant bytes. Campaign C has no prior admitted message in (30, 60], so its projected count is 1. Batch totals are 4 messages and 700 + 600 + 200 + 700 = 2200 bytes.

Example 3:


Input:
{
  "messages": [
    {"id":"m1","timestamp":"0","tenant":"T","sender":"a","recipient":"x","campaign":"C","bytes":"500"},
    {"id":"m2","timestamp":"1","tenant":"T","sender":"a","recipient":"x","campaign":"C","bytes":"500"},
    {"id":"m3","timestamp":"2","tenant":"T","sender":"a","recipient":"y","campaign":"D","bytes":"400"},
    {"id":"m4","timestamp":"3","tenant":"T","sender":"a","recipient":"x","campaign":"C","bytes":"200"},
    {"id":"m5","timestamp":"60","tenant":"T","sender":"a","recipient":"x","campaign":"C","bytes":"600"}
  ],
  "extra_rules": [
    {"id":"tenant_bytes","group_by":"tenant","metric":"bytes","window_seconds":"60","limit":"1500"},
    {"id":"campaign_cap","group_by":"tenant,campaign","metric":"messages","window_seconds":"30","limit":"2"}
  ]
}

Output:
{
  "decisions": [
    {"id":"m1","status":"ADMITTED","violations":[]},
    {"id":"m2","status":"ADMITTED","violations":[]},
    {"id":"m3","status":"ADMITTED","violations":[]},
    {"id":"m4","status":"REJECTED","violations":[
      {"rule":"campaign_cap","projected":3,"limit":2},
      {"rule":"recipient_rate","projected":3,"limit":2},
      {"rule":"sender_rate","projected":4,"limit":3},
      {"rule":"tenant_bytes","projected":1600,"limit":1500}
    ]},
    {"id":"m5","status":"ADMITTED","violations":[]}
  ],
  "admitted_totals":{"messages":4,"bytes":2000}
}

Explanation: Before m4, the tenant has 500 + 500 + 400 = 1400 admitted bytes, sender a has 3 admitted messages, recipient x has 2, and campaign C has 2. Therefore m4 simultaneously projects 1600 bytes, 4 sender messages, 3 recipient messages, and 3 campaign messages. At time 60, m1 expires from the 60-second windows and both earlier campaign C messages have expired from its 30-second window. m5 projects 500 + 400 + 600 = 1500 tenant bytes, 3 sender messages, 2 recipient messages, and 1 campaign message, so it is admitted. Batch totals are 4 messages and 500 + 500 + 400 + 600 = 2000 bytes.

Notes:


  • There are at most 100,000 messages and 20 extra rules. Do not rescan the entire admitted history for every decision; explain an amortized bound.

  • Inputs are valid: message IDs are unique, identifiers are nonempty ASCII strings of at most 32 characters, and extra-rule IDs are unique and do not reuse default-rule IDs. Numeric inputs are integers between 0 and 1,000,000,000, except window widths must be positive.

  • Each invocation starts with empty history. This is a deterministic, single-process replay problem, not a distributed concurrency or persistent-storage implementation.
Want to practise this one?
Create a free account to open the full question and practise Meta questions with AI.
Sign up free
coding Medium tree #2

2. Tree — Count Unique Binary Search Trees

Background: In Meta's various applications, understanding how to manage hierarchical data structures effectively is crucial. Binary Search Trees (BSTs) often support dynamic data management, as seen in features that require efficient querying and storage.
Problem statement: Given an integer n, return the number of unique Binary Search Trees (BST) that can be formed using n distinct integers from 1 to n. A Binary Search Tree is defined as a tree in which all nodes follow the left < current < right property.
Function/class signature:
  • def numTrees(n: int) -> int:


Example 1:
Input: n = 3
Output: 5
Explanation: The possible unique BSTs are:
1. 1 2 3
\ / \ /
2 1 1 2 2
\ \ \
3 3 1
Example 2:
Input: n = 1
Output: 1
Explanation: With only 1 node, there's only 1 unique BST possible.
Constraints:
  • 1 <= n <= 19
coding Medium tree #3

3. CODING — Serialize and Deserialize a Binary Tree

Background: In Facebook's backend services, managing user connections and interactions can be complicated, especially when handling data structures like trees. This problem directly relates to how user data can be organized and transferred over the network.
Problem statement: You need to implement two methods to serialize and deserialize a binary tree. The serialize function should convert the tree into a string form, so it can be easily saved or transmitted. The deserialize function should take this string and reconstruct the binary tree. Use pre-order traversal for serialization and handle null values appropriately.
Function/class signature:
  • def serialize(root: Optional[TreeNode]) -> str:

  • def deserialize(data: str) -> Optional[TreeNode]:

Example 1:
  • Input: root = [1,2,3,null,null,4,5]

  • Output: "1,2,#,#,3,4,#,#,5,#,#"

  • Explanation: The binary tree can be represented as a serialized string.

Example 2:
  • Input: data = "1,2,#,#,3,4,#,#,5,#,#"

  • Output: root = [1,2,3,null,null,4,5]

  • Explanation: It accurately reconstructs the original binary tree from the serialized string.

Constraints:
  • The number of nodes in the tree is in the range [0, 10^4].

  • Each node's value is a string representing an integer in the range [-10^4, 10^4].
coding Medium dynamic programming #4

4. Dynamic Programming — Maximum Number of Events that Can Be Attended

Background: As Meta develops features for its events platform, optimizing the number of events a user can attend without overlap is crucial for enhancing user experience.
Problem statement: You are given an array of events, where each event is represented as a pair of integers [start, end]. An individual can attend an event if they can arrive at the event's start time or after the event has started. Each event must be completed to move to the next one. Your task is to return the maximum number of events that can be attended.
Function/class signature:
  • def max_events(events: List[List[int]]) -> int:

Example 1:
  • Input: events = [[1,2],[2,3],[3,4]]

  • Output: 3

  • Explanation: All the events do not overlap, so the user can attend all three.

Example 2:
  • Input: events = [[1,4],[4,6],[6,8],[3,5]]

  • Output: 4

  • Explanation: The user can attend all events as they fall into a sequence without overlaps.

Constraints:
  • 1 <= len(events) <= 10^4

  • 1 <= start <= end <= 10^5
coding Medium two pointers #5

5. [Two Pointers] — Finding Unique Triplets with a Given Sum


Background: Meta's platforms involve vast amounts of user data, where identifying unique patterns can help in creating better user experiences and targeted advertisements. The 3Sum problem is integral to analyzing interactions.
Problem statement: Given an integer array nums of size n, return all the unique triplets [nums[i], nums[j], nums[k]] such that i, j, and k are different indices, and their sum equals to zero. The result must not include duplicate triplets, hence the order of results does not matter.
Function/class signature:
  • def three_sum(nums: List[int]) -> List[List[int]]:


Example 1:
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Explanation: The above combinations sum up to zero and are unique.
Example 2:
Input: nums = []
Output: []
Explanation: No triplets can be formed from an empty list.
Constraints:
  • 0 <= n <= 3000

  • -10^5 <= nums[i] <= 10^5
coding Medium tree #6

6. [Graph] — Level Order Traversal with Custom Sorting

Background: In the context of Meta's messaging platform, ensuring efficient data presentation is crucial. Users want to see their messages organized in a specific order for improved readability and usability.
Problem statement: Given a binary tree representing the messages, where nodes contain the message sender and timestamp, implement a function that performs a level order traversal of the tree, but with each level sorted by the timestamp of the messages. Return the list of messages in the required order. Note: If there are multiple messages with the same timestamp, maintain their relative order from the original tree.
Function/class signature:
  • def level_order_sorted_messages(root: Optional[TreeNode]) -> List[Tuple[str, int]]:

Example 1:
  • Input: root - a tree with nodes representing messages sent by different users at various timestamps

  • Output: [("Alice", 1), ("Bob", 2), ("Charlie", 3)]

  • Explanation: Messages are shown in order based on their timestamps.

Example 2:
  • Input: A different tree where timestamps are not in sequential order.

  • Output: [("David", 4), ("Eve", 5), ("Frank", 7)]

Constraints:
  • The binary tree will contain at most 10^4 nodes.

  • Timestamps are non-negative integers.

  • Each message is a string up to 100 characters long.
coding Hard tree #7

7. Binary Tree Serialization — serialize and deserialize a binary tree

Background: At Meta, efficient data storage and retrieval are essential for features like News Feed and Messenger. Serializing a binary tree allows for easy transfer and storage of tree structures, especially those representing user relationships or posts.
Problem statement: Implement the methods serialize and deserialize that convert a binary tree into a single string representation and back again. The representation must be unique and should correctly reconstruct the original tree structure. You can use any traversal method.
Function/class signature:
  • def serialize(root: Optional[TreeNode]) -> str:

  • def deserialize(data: str) -> Optional[TreeNode]:

Example 1:
  • Input: root = [1,2,3,null,null,4,5]

  • Output: "1,2,3,null,null,4,5"

  • Explanation: The binary tree is represented in a level-order format as a string.

Example 2:
  • Input: root = [1]

  • Output: "1,null"

  • Explanation: A single-node tree is represented correctly.

Constraints:
  • The tree will have between 0 and 10^4 nodes.

  • The node values will be integers in the range [-1000, 1000].

coding Medium hash map #8

8. Hash Map — Find the Complementary Pair in User IDs

1. Background: At Meta, user experience is crucial, particularly when leveraging social graphs. Understanding user connections through complementary pairs can optimize recommendations in platforms like Facebook.
2. Problem statement: Given an array of user_ids and a target_sum, return the indices of the two user IDs such that their corresponding values add up to the target_sum. You may assume that each input would have exactly one solution, and you may not use the same element twice.
3. Function/class signature:
- def find_complementary_pair(user_ids: List[int], target_sum: int) -> List[int]:
4. Example 1:
Input: user_ids = [3, 5, 2, 8, 6], target_sum = 10
Output: [0, 3]
Explanation: User IDs 3 and 8 add up to 10.
5. Example 2:
Input: user_ids = [1, 4, 5, 6, 7], target_sum = 11
Output: [2, 3]
Explanation: User IDs 5 and 6 add up to 11.
6. Constraints:
- 2 <= len(user_ids) <= 10^4
- -10^9 <= user_ids[i] <= 10^9
- 2 <= target_sum <= 2 * 10^9
coding Hard graph #9

9. [OA] Graph Traversal — Find shortest path for the Facebook Events navigation

This problem simulates navigation through Facebook Events. Efficient pathfinding is crucial for enhancing user experience in discovering events.
Given an undirected graph represented as an adjacency list, return the shortest path from node start to node end.
Example 1:
Input: edges = [[0, 1], [1, 2], [2, 3]], start = 0, end = 3
Output: [0, 1, 2, 3]
Explanation: The shortest path from node 0 to node 3 is 0 -> 1 -> 2 -> 3.
Example 2:
Input: edges = [[0, 1], [1, 2], [0, 2], [2, 3]], start = 0, end = 3
Output: [0, 2, 3]
Constraints:
  • 1 <= edges.length <= 10^4

  • Each edge is a pair of distinct integers.
coding Hard sliding window #10

10. [OA] Sliding Window — Find the longest substring containing at most two distinct characters for Facebook Messenger

This problem is important for optimizing the chat list experience in the Messenger app. By ensuring quick access to frequently used contacts, we can enhance user engagement.
Given a string s, find the length of the longest substring containing at most two distinct characters.
Example 1:
Input: s = "eceba"
Output: 3
Explanation: The substring is "ece" which its length is 3.
Example 2:
Input: s = "ccaabbb"
Output: 5
Explanation: The substring is "aabbb" which its length is 5.
Constraints:
  • 1 <= s.length <= 10^5

  • s consists of English letters, digits, symbols, and spaces.
system design Medium messaging #11

11. Design WhatsAppMailbox — reliable message delivery through polling APIs


Background
WhatsApp clients may need to retrieve messages through request/response APIs rather than a persistent WebSocket connection. Model an in-memory service that supports retry-safe sending, non-destructive polling, and explicit acknowledgments when clients reconnect. This is a scoped OOP adaptation of a community-reported Meta interview prompt about WhatsApp-style messaging using API calls instead of WebSockets, not a description of WhatsApp's production implementation.
Requirements
1. Implement a WhatsAppMailbox class for direct messages. Each recipient has an independent sequence starting at 1. Every new message for that recipient receives the next sequence number, regardless of its sender.
2. Make sending idempotent using (sender_id, request_id). Retrying with the same recipient and text returns the original sequence number without creating another message, even if the original was acknowledged. Reusing that key with a different recipient or text raises ValueError without changing state.
3. poll returns up to limit unacknowledged messages in ascending sequence order. Polling does not remove messages: consecutive polls without an acknowledgment return the same prefix. Track the highest sequence ever returned by a poll for each recipient.
4. acknowledge cumulatively removes all messages through the supplied sequence. The sequence must be between 0 and that recipient's highest-ever-polled sequence, inclusive; otherwise raise ValueError without changing state. Valid acknowledgments at or below the already-acknowledged sequence are no-ops. Return the number of newly removed messages.
5. unread_count returns the number of unacknowledged messages, including messages already polled. Unknown users have empty mailboxes, a highest-ever-polled sequence of 0, and an unread count of 0. Returned messages must be immutable so callers cannot modify stored message data.
Class API
  • WhatsAppMailbox() — Construct an empty service.

  • send(sender_id: str, recipient_id: str, request_id: str, text: str) -> int — Enqueue a new message or return the sequence from an identical retry.

  • poll(recipient_id: str, limit: int) -> list[Message] — Return the earliest pending messages; raise ValueError unless 1 <= limit <= 100.

  • acknowledge(recipient_id: str, through_sequence: int) -> int — Cumulatively acknowledge messages, subject to the delivery bound above.

  • unread_count(recipient_id: str) -> int — Return the current pending-message count.

  • Message — An immutable record with sequence: int, sender_id: str, recipient_id: str, and text: str.


Example 1:
Input sequence, starting with a new service:
[
  {"method":"send","args":["alice","bob","req-1","Hi"]},
  {"method":"send","args":["alice","bob","req-1","Hi"]},
  {"method":"send","args":["carol","bob","req-1","Hello"]},
  {"method":"poll","args":["bob",1]},
  {"method":"poll","args":["bob",1]},
  {"method":"acknowledge","args":["bob",1]},
  {"method":"poll","args":["bob",10]},
  {"method":"unread_count","args":["bob"]}
]

Output, with immutable records serialized as JSON objects:
[
  1,
  1,
  2,
  [{"sequence":1,"sender_id":"alice","recipient_id":"bob","text":"Hi"}],
  [{"sequence":1,"sender_id":"alice","recipient_id":"bob","text":"Hi"}],
  1,
  [{"sequence":2,"sender_id":"carol","recipient_id":"bob","text":"Hello"}],
  1
]

Explanation: Alice's retry creates no message. Carol can use the same request ID because idempotency keys include the sender. Polling twice returns sequence 1 twice. Acknowledging it leaves only sequence 2 pending.
Example 2:
Input sequence, starting with a new service:
[
  {"method":"send","args":["alice","bob","r1","Hi"]},
  {"method":"acknowledge","args":["bob",1]},
  {"method":"poll","args":["bob",10]},
  {"method":"acknowledge","args":["bob",1]},
  {"method":"send","args":["alice","bob","r1","Hi"]},
  {"method":"send","args":["alice","bob","r1","Changed"]},
  {"method":"acknowledge","args":["bob",1]},
  {"method":"unread_count","args":["bob"]}
]

Output; the test harness represents a raised ValueError as an error object and continues:
[
  1,
  {"error":"ValueError"},
  [{"sequence":1,"sender_id":"alice","recipient_id":"bob","text":"Hi"}],
  1,
  1,
  {"error":"ValueError"},
  0,
  0
]

Explanation: The first acknowledgment fails because no message has been polled. After polling, acknowledging sequence 1 removes one message. Retrying the original send returns 1 without restoring that message, and changing its text is rejected.
Constraints
  • At most 100,000 method calls and 10,000 distinct users per service instance. IDs are nonempty strings of at most 64 characters; text contains 1–4,096 characters.

  • Calls are single-threaded. Inputs satisfy the stated types and string bounds; explicitly validate poll limits, acknowledgment bounds, and conflicting idempotency keys.

  • State is in memory only. Keep idempotency information for the lifetime of the instance; persistence, authentication, encryption, group messaging, and time-based expiration are out of scope.

  • Target expected O(1) send and count operations, O(k) polling for k returned messages, and O(r + 1) acknowledgment for r removed messages, excluding string hashing/comparison costs.
system design Hard caching #12

12. [OA] LRU Cache — Implement the caching system for Instagram feed

Instagram relies on providing quick access to user feeds, which requires an efficient cache management system. Design an LRU Cache to ensure optimal performance.
Class LRUCache:
  • LRUCache(int capacity): Initializes the cache with a positive size capacity.

  • int get(int key): Returns the value of the key if the key exists, otherwise returns -1.

  • void put(int key, int value): Update the value of the key if present, or add the key-value pair if not existing. When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.


Example 1:
Input: LRUCache(2); cache.put(1, 1); cache.put(2, 2); cache.get(1); cache.put(3, 3); cache.get(2); cache.put(4, 4); cache.get(1); cache.get(3); cache.get(4);
Output: 1; -1; 3; 4
Constraints:
  • capacity is always positive and will not exceed 1000

  • The operations get and put will always be called with valid keys.

Related Meta Software Engineer interview prep

Start practicing Meta questions

Sign up for free to access walkthroughs, AI-generated questions, and more.

Get Started Free