Fill Missing Data solution and explanation
Google
The problem
DataFrame products
+-------------+--------+
| Column Name | Type |
+-------------+--------+
| name | object |
| quantity | int |
| price | int |
+-------------+--------+
Write a solution to fill in the missing value as 0 in the quantity column.
The result format is in the following example.
Example 1: Input:+-----------------+----------+-------+ | name | quantity | price | +-----------------+----------+-------+ | Wristwatch | None | 135 | | WirelessEarbuds | None | 821 | | GolfClubs | 779 | 9319 | | Printer | 849 | 3051 | +-----------------+----------+-------+ Output: +-----------------+----------+-------+ | name | quantity | price | +-----------------+----------+-------+ | Wristwatch | 0 | 135 | | WirelessEarbuds | 0 | 821 | | GolfClubs | 779 | 9319 | | Printer | 849 | 3051 | +-----------------+----------+-------+ Explanation: The quantity for Wristwatch and WirelessEarbuds are filled by 0.
Approach overview
Problem Overview: You receive a sequence containing missing or placeholder values. The task is to scan the data and replace those missing entries with valid values based on a defined rule, typically derived from surrounding elements or previously seen data.
Approach 1: Iterate and Replace Using Conditional Logic (Time: O(n), Space: O(1))
The direct solution is a single pass through the sequence. While iterating, check each element for a missing marker such as null, None, or a sentinel value. When a missing entry appears, replace it using the rule defined by the problem (commonly the last valid value seen or another computed fallback). This approach relies on simple array traversal and conditional checks, so the logic stays predictable and efficient.
Because the array is processed once and updates are done in place, the time complexity is O(n) and the space complexity is O(1). This method is reliable for interview settings since it demonstrates strong control over iteration and state tracking.
Approach 2: Use Built-In Functions or Libraries (Time: O(n), Space: O(1) to O(n))
Many languages provide utilities that simplify missing-value handling. For example, libraries may offer forward-fill or replace operations that automatically propagate valid values into missing slots. Internally these functions still perform a sequential scan, but they hide the explicit loop and conditional checks from the user.
This approach keeps the time complexity at O(n) because the dataset must still be processed element by element. Space usage depends on the implementation: in-place replacements use O(1) space, while functions that return a new structure may require O(n). It works well in production code where readability and reliability matter more than manually implementing iteration.
Recommended for interviews: Start with the explicit iteration approach. Interviewers expect you to control the scan, track the last valid value, and update missing entries as you go. The built-in function approach is useful in real-world data processing, but writing the logic yourself demonstrates stronger understanding of array processing and sequential iteration.
Approach 1: Iterate and Replace Using Conditional Logic
This method involves iterating over each row of the DataFrame. We check if the 'quantity' value is null (or equivalent) and set it to zero if it is. This is a straightforward approach that uses conditional checks within loops appropriate for each programming language.
class Product:
def __init__(self, name, quantity, price):
self.name = name
self.quantity = quantity
self.price = price
products = [
Product("Wristwatch", None, 135),
Product("WirelessEarbuds", None, 821),
Product("GolfClubs", 779, 9319),
Product("Printer", 849, 3051)
]
for product in products:
if product.quantity is None:
product.quantity = 0
for product in products:
print(f"{product.name}: {product.quantity} {product.price}")import java.util.Arrays;
class Product {
String name;
Integer quantity;
Integer price;
Product(String name, Integer quantity, Integer price) {
this.name = name;
this.quantity = quantity;
this.price = price;
}
}
public class FillMissingData {
public static void fillMissingQuantities(Product[] products) {
for (Product product : products) {
if (product.quantity == null) {
product.quantity = 0;
}
}
}
public static void main(String[] args) {
Product[] products = {
new Product("Wristwatch", null, 135),
new Product("WirelessEarbuds", null, 821),
new Product("GolfClubs", 779, 9319),
new Product("Printer", 849, 3051)
};
fillMissingQuantities(products);
Arrays.stream(products).forEach(p -> System.out.println(p.name + ": " + p.quantity + " " + p.price));
}
}#include <iostream>
#include <vector>
struct Product {
std::string name;
int quantity;
int price;
};
void fillMissingQuantities(std::vector<Product>& products) {
for (auto& product : products) {
if (product.quantity == -1) { // assuming -1 stands in for 'None'
product.quantity = 0;
}
}
}
int main() {
std::vector<Product> products = {
{"Wristwatch", -1, 135},
{"WirelessEarbuds", -1, 821},
{"GolfClubs", 779, 9319},
{"Printer", 849, 3051}
};
fillMissingQuantities(products);
for (const auto& product : products) {
std::cout << product.name << ": " << product.quantity << " " << product.price << std::endl;
}
return 0;
}let products = [
{ name: "Wristwatch", quantity: null, price: 135 },
{ name: "WirelessEarbuds", quantity: null, price: 821 },
{ name: "GolfClubs", quantity: 779, price: 9319 },
{ name: "Printer", quantity: 849, price: 3051 },
];
products.forEach(product => {
if (product.quantity === null) {
product.quantity = 0;
}
});
products.forEach(product => {
console.log(`${product.name}: ${product.quantity} ${product.price}`);
});#include <stdio.h>
#define ROWS 4
typedef struct {
char* name;
int quantity;
int price;
} Product;
void fillMissingQuantities(Product products[]) {
for (int i = 0; i < ROWS; i++) {
if (products[i].quantity == -1) { // assume -1 as the place for 'None'
products[i].quantity = 0;
}
}
}
int main() {
Product products[ROWS] = {
{"Wristwatch", -1, 135},
{"WirelessEarbuds", -1, 821},
{"GolfClubs", 779, 9319},
{"Printer", 849, 3051}
};
fillMissingQuantities(products);
for (int i = 0; i < ROWS; i++) {
printf("%s: %d %d\n", products[i].name, products[i].quantity, products[i].price);
}
return 0;
}using System;
class Product {
public string Name { get; set; }
public int? Quantity { get; set; }
public int Price { get; set; }
}
class FillMissingData {
static void FillMissingQuantities(Product[] products) {
foreach (var product in products) {
if (!product.Quantity.HasValue) {
product.Quantity = 0;
}
}
}
static void Main() {
Product[] products = {
new Product { Name = "Wristwatch", Quantity = null, Price = 135 },
new Product { Name = "WirelessEarbuds", Quantity = null, Price = 821 },
new Product { Name = "GolfClubs", Quantity = 779, Price = 9319 },
new Product { Name = "Printer", Quantity = 849, Price = 3051 }
};
FillMissingQuantities(products);
foreach (var product in products) {
Console.WriteLine($"{product.Name}: {product.Quantity} {product.Price}");
}
}
}In Python, we use a class Product to structure product data. We iterate over a list of Product instances, replacing None with 0 in the quantity attributes if necessary. We finally print the updated values.
Time Complexity: O(n), driven by the number of products.
Space Complexity: O(1), since the modification is done in-place.
Approach 2: Use Built-In Functions or Libraries
This approach involves leveraging built-in functions or libraries available in programming languages, like pandas in Python or LINQ in C#, to perform the task of filling in missing values effectively and efficiently.
import pandas as pd
data = {
'name': ['Wristwatch', 'WirelessEarbuds', 'GolfClubs', 'Printer'],
'quantity': [None, None, 779, 849],
'price': [135, 821, 9319, 3051]
}
products = pd.DataFrame(data)
products['quantity'].fillna(0, inplace=True)
print(products)import java.util.Arrays;
import java.util.stream.Stream;
class Product {
String name;
Integer quantity;
Integer price;
Product(String name, Integer quantity, Integer price) {
this.name = name;
this.quantity = quantity;
this.price = price;
}
}
public class FillMissingData {
public static void fillMissingQuantities(Product[] products) {
Arrays.stream(products).forEach(product -> {
if (product.quantity == null) {
product.quantity = 0;
}
});
}
public static void main(String[] args) {
Product[] products = {
new Product("Wristwatch", null, 135),
new Product("WirelessEarbuds", null, 821),
new Product("GolfClubs", 779, 9319),
new Product("Printer", 849, 3051)
};
fillMissingQuantities(products);
Arrays.stream(products).forEach(p -> System.out.println(p.name + ": " + p.quantity + " " + p.price));
}
}#include <iostream>
#include <vector>
#include <algorithm>
struct Product {
std::string name;
int quantity;
int price;
};
void fillMissingQuantities(std::vector<Product>& products) {
std::for_each(products.begin(), products.end(), [](Product& p) {
if (p.quantity == -1) { // assuming -1 stands in for 'None'
p.quantity = 0;
}
});
}
int main() {
std::vector<Product> products = {
{"Wristwatch", -1, 135},
{"WirelessEarbuds", -1, 821},
{"GolfClubs", 779, 9319},
{"Printer", 849, 3051}
};
fillMissingQuantities(products);
for (const auto& product : products) {
std::cout << product.name << ": " << product.quantity << " " << product.price << std::endl;
}
return 0;
}let products = [
{ name: "Wristwatch", quantity: null, price: 135 },
{ name: "WirelessEarbuds", quantity: null, price: 821 },
{ name: "GolfClubs", quantity: 779, price: 9319 },
{ name: "Printer", quantity: 849, price: 3051 },
];
products = products.map(product => ({
...product,
quantity: product.quantity ?? 0
}));
console.log(products);#include <stdio.h>
#define ROWS 4
typedef struct {
char* name;
int quantity;
int price;
} Product;
void fillMissingQuantities(Product products[]) {
for (int i = 0; i < ROWS; i++) {
if (products[i].quantity == -1) { // assume -1 as the place for 'None'
products[i].quantity = 0;
}
}
}
int main() {
Product products[ROWS] = {
{"Wristwatch", -1, 135},
{"WirelessEarbuds", -1, 821},
{"GolfClubs", 779, 9319},
{"Printer", 849, 3051}
};
fillMissingQuantities(products);
for (int i = 0; i < ROWS; i++) {
printf("%s: %d %d\n", products[i].name, products[i].quantity, products[i].price);
}
return 0;
}using System;
using System.Linq;
class Product {
public string Name { get; set; }
public int? Quantity { get; set; }
public int Price { get; set; }
}
class FillMissingData {
static void FillMissingQuantities(Product[] products) {
products = products.Select(p =>
{
if (!p.Quantity.HasValue)
p.Quantity = 0;
return p;
}).ToArray();
}
static void Main() {
Product[] products = {
new Product { Name = "Wristwatch", Quantity = null, Price = 135 },
new Product { Name = "WirelessEarbuds", Quantity = null, Price = 821 },
new Product { Name = "GolfClubs", Quantity = 779, Price = 9319 },
new Product { Name = "Printer", Quantity = 849, Price = 3051 }
};
FillMissingQuantities(products);
foreach (var product in products) {
Console.WriteLine($"{product.Name}: {product.Quantity} {product.Price}");
}
}
}By employing Python's pandas library, we can use the fillna function to efficiently handle missing values in DataFrames, specifying inplace=True to maintain modifications.
Time Complexity: O(n), guided by the size of the DataFrame.
Space Complexity: O(1), as the DataFrame is updated in-place.
Complexity comparison
| Approach | Complexity |
|---|---|
| Iterate and Replace Using Conditional Logic | Time Complexity: O(n), driven by the number of products. |
| Use Built-In Functions or Libraries | Time Complexity: O(n), guided by the size of the DataFrame. |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterate and Replace Using Conditional Logic | O(n) | O(1) | Best for interviews and when you want full control over how missing values are handled |
| Use Built-In Functions or Libraries | O(n) | O(1) to O(n) | Useful in production environments where standard library utilities simplify data cleaning |
Frequently asked questions
Is Fill Missing Data easy or hard?
Fill Missing Data is generally classified as an easy problem. The solution relies on straightforward array traversal and conditional updates rather than advanced algorithms or data structures.
Fill Missing Data Python/Java solution
In Python, iterate through the list and replace missing values using conditional checks or built-in utilities. In Java, loop through the array and update elements directly while maintaining the last valid value. Both implementations run in O(n) time and require constant extra space.
How to solve Fill Missing Data in O(n)?
Perform a single linear scan through the array. For each element, check if it represents missing data. If it does, replace it using the defined rule (such as the last valid value encountered). Maintaining a variable that stores the most recent valid entry allows the entire operation to complete in O(n) time.
What is the best approach for Fill Missing Data?
The most reliable approach is iterating through the sequence and replacing missing entries using conditional logic. Track the last valid value or compute the replacement according to the problem rule while scanning the array. This method runs in O(n) time and uses O(1) extra space when updates are done in place.
Is Fill Missing Data asked at Google/Amazon/Meta?
Problems involving filling or propagating missing values appear in interviews at major tech companies, especially in data-processing or backend roles. Variations test your ability to iterate efficiently, maintain state during traversal, and handle edge cases in arrays or datasets.
What data structure is used in Fill Missing Data?
The problem primarily uses arrays or lists because the data must be scanned sequentially. A small number of variables are used to track the most recent valid value or replacement rule, so no complex data structures are required.
What is the time complexity of Fill Missing Data?
The standard solution processes each element exactly once, resulting in O(n) time complexity where n is the number of data points. Space complexity is typically O(1) when modifying the array directly, though some library-based implementations may use O(n) if they return a new structure.