Invalid Tweets II solution and explanation
The problem
Table: Tweets
+----------------+---------+ | Column Name | Type | +----------------+---------+ | tweet_id | int | | content | varchar | +----------------+---------+ tweet_id is the primary key (column with unique values) for this table. This table contains all the tweets in a social media app.
Write a solution to find invalid tweets. A tweet is considered invalid if it meets any of the following criteria:
- It exceeds
140characters in length. - It has more than
3mentions. - It includes more than
3hashtags.
Return the result table ordered by tweet_id in ascending order.
The result format is in the following example.
Example:
Input:
Tweets table:
+----------+-----------------------------------------------------------------------------------+ | tweet_id | content | +----------+-----------------------------------------------------------------------------------+ | 1 | Traveling, exploring, and living my best life @JaneSmith @SaraJohnson @LisaTaylor | | | @MikeBrown #Foodie #Fitness #Learning | | 2 | Just had the best dinner with friends! #Foodie #Friends #Fun | | 4 | Working hard on my new project #Work #Goals #Productivity #Fun | +----------+-----------------------------------------------------------------------------------+
Output:
+----------+ | tweet_id | +----------+ | 1 | | 4 | +----------+
Explanation:
- tweet_id 1 contains 4 mentions.
- tweet_id 4 contains 4 hashtags.
Approach overview
Problem Overview: Each row in the Tweets table contains a tweet's text. A tweet becomes invalid if it includes more than three @ mentions. The task is to return the tweet_id values for tweets where the number of @ characters exceeds three.
Approach 1: LENGTH() + REPLACE() Character Counting (O(n * m) time, O(1) space)
The key observation: the number of occurrences of a character can be computed using string length differences. Calculate LENGTH(content), then remove all @ characters with REPLACE(content, '@', ''). The difference between these lengths equals the number of mentions. If the difference is greater than three, the tweet is invalid. This works because REPLACE removes every matching character, so the length shrink directly reveals the count.
In SQL, the query filters rows using LENGTH(content) - LENGTH(REPLACE(content, '@', '')) > 3. The database scans each tweet string once to compute both lengths. No additional data structures are required, making the approach efficient and easy to implement directly in a query.
The same logic translates cleanly to Python. Compute the original string length and subtract the length after replacing @ with an empty string. The difference gives the mention count. This pattern is common when solving string counting problems where built‑in counting utilities are unavailable.
This approach is preferred in database problems because it avoids loops or joins and keeps the entire computation inside a single query. It leverages native SQL string functions, which are highly optimized inside database engines.
Recommended for interviews: The LENGTH() - LENGTH(REPLACE()) pattern is the expected solution. It demonstrates that you understand how to count character occurrences using SQL string functions without procedural logic. Interviewers often look for this trick because it converts a seemingly iterative problem into a single declarative filter condition.
Solution
We can use the LENGTH() function to calculate the length of the string, calculate the length after excluding @ or #, then use the OR operator to connect these three conditions, filter out the corresponding tweet_id, and sort by tweet_id in ascending order.
import pandas as pd
def find_invalid_tweets(tweets: pd.DataFrame) -> pd.DataFrame:
invalid_tweets = tweets[
(tweets["content"].str.len() > 140)
| (tweets["content"].str.count("@") > 3)
| (tweets["content"].str.count("#") > 3)
].sort_values(by="tweet_id")
return invalid_tweets[["tweet_id"]]# Write your MySQL query statement below
SELECT tweet_id
FROM Tweets
WHERE
LENGTH(content) > 140
OR (LENGTH(content) - LENGTH(REPLACE(content, '@', ''))) > 3
OR (LENGTH(content) - LENGTH(REPLACE(content, '#', ''))) > 3
ORDER BY 1;Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| LENGTH() + REPLACE() Character Counting | O(n * m) | O(1) | Best for SQL queries where you must count character occurrences directly inside the database. |
| Direct String Scan (Python) | O(n * m) | O(1) | Useful in scripting environments when processing tweet text outside the database. |
Frequently asked questions
Is Invalid Tweets II easy or hard?
Invalid Tweets II is categorized as an Easy database problem. The challenge mainly checks familiarity with SQL string functions and the common trick of counting characters using a LENGTH difference.
Invalid Tweets II Python/Java solution
In Python, compute len(content) - len(content.replace('@','')). If the result is greater than three, the tweet is invalid. The same logic works in Java using string length and replace methods, making the solution consistent across languages.
How to solve Invalid Tweets II in O(n)?
Within database queries, the closest practical complexity is O(n * m) because each tweet string must be scanned. Using LENGTH(content) - LENGTH(REPLACE(content, '@', '')) counts mentions in a single pass per string and avoids extra joins or loops, which keeps the query efficient.
What is the best approach for Invalid Tweets II?
The most efficient solution counts the number of '@' characters using LENGTH() and REPLACE() functions. Compute LENGTH(content) minus LENGTH(REPLACE(content, '@', '')). If the result is greater than three, the tweet is invalid. This approach runs in O(n * m) time where n is the number of tweets and m is the average tweet length.
Is Invalid Tweets II asked at Google/Amazon/Meta?
Problems like Invalid Tweets II appear in SQL interview rounds at companies that test database fundamentals. The question focuses on string manipulation and filtering rows using SQL functions, which are common skills evaluated in data engineering and backend interviews.
What data structure is used in Invalid Tweets II?
No specialized data structure is required. The solution operates directly on strings stored in a database column and uses SQL string functions such as LENGTH() and REPLACE() to compute the number of occurrences of a character.
What is the time complexity of Invalid Tweets II?
The solution scans each tweet string to compute its length and the length after replacement. If n is the number of rows and m is the average length of each tweet, the complexity is O(n * m). Space complexity remains O(1) because no additional structures are created.