Machine Coding Problem

Price Comparison Engine

macoAllcommercenormalizationentity-matching
Commonly Asked By:GoogleAmazonPayPal

Requirements & System Scope

Functional Specifications (In-Scope)

  • Raw Data Ingestion: Aggregates real-time price feeds across diverse external retailers.
  • Smart Product Normalizer: Standardizes text, strips marketing fluff, and extracts brand metadata models.
  • Hybrid Entity Matcher: Employs exact barcode checks first, falling back to Jaccard word overlaps.
  • Real-time Staleness Evaluator: Purges prices that exceed configured maximum TTL limits.

Out-of-Scope Boundaries

  • Fulfillment Logistics Tracking: Excludes tracking carrier locations or warehouse inventory updates.
  • Voucher Coupon Scraping: Excludes scanning external voucher databases for local rebates.

Class Diagram & Entity Relationships

Entity structure of normalizers, matchers, and indexed stores:

Loading...
  • RetailerProduct: Raw ingestion model containing retailer-specific strings and pricing.
  • NormalizedProduct: Cleaned model mapping brand, model, and barcode.
  • PriceIndex: Master storage aggregating verified retailer prices per canonical product.

Design Patterns & SOLID Principles

  • Strategy Pattern: Encapsulates entity matching logic under separate matching strategies (Exact Barcode matching, Fuzzy Jaccard string comparison).
  • Factory Pattern: Utilizes Normalizer to construct cleaned NormalizedProduct entities from raw inputs.
  • Liskov Substitution Principle (LSP): Promotes interchangeable similarity algorithms (Levenshtein, Jaccard) to compute title scores.

Core Execution Workflows

Entity Matching & Best-Price Query Workflow

  1. Ingest Feed: Receive raw data payload (Title, Barcode, Price, Retailer).
  2. Execute Normalization: Convert title to lowercase, strip unlocked/refurbished/model annotations, and isolate brand strings.
  3. Search Entity Index:
    1. Query active database index for identical barcodes. If matched, select canonical product.
    2. Compute similarity overlap ratios across existing canonical titles. If Jaccard Index > 0.65, merge records.
    3. If no matches are identified, insert a new Canonical Product.
  4. Index Price Tally: Insert new RetailerPrice entry with current epoch timestamp. Remove stale matches.
  5. Serve Queries: Sort active price array ascending (lowest price first) and filter out entries that have expired.

Concurrency & Thread Safety Strategy

Securing write-heavy indices under high-volume feed ingestions:

  • Concurrent Skip List Map: Keeps sorted retailer prices thread-safe during high-frequency concurrent writes.
  • Sharded Locks: Locks matching catalog segments using brand-specific locks to facilitate concurrent matching of unrelated goods.

Complete Clean Code Blueprint

Production reference implementations demonstrating normalization cleanups, Jaccard matching, and price querying:

// ─── JAVA BLUEPRINT ──────────────────────────────────────────────────────────
import java.util.*;
import java.util.concurrent.*;

class RetailerProduct {
    private final String retailerId;
    private final String rawTitle;
    private final double price;
    private final String currency;
    private final String barcode; // UPC/GTIN
    private final String url;

    public RetailerProduct(String retailerId, String rawTitle, double price, String currency, String barcode, String url) {
        this.retailerId = retailerId;
        this.rawTitle = rawTitle;
        this.price = price;
        this.currency = currency;
        this.barcode = barcode;
        this.url = url;
    }

    public String getRetailerId() { return retailerId; }
    public String getRawTitle() { return rawTitle; }
    public double getPrice() { return price; }
    public String getCurrency() { return currency; }
    public String getBarcode() { return barcode; }
    public String getUrl() { return url; }
}

class NormalizedProduct {
    private final String canonicalId;
    private final String cleanedTitle;
    private final String brand;
    private final String model;
    private final String barcode;

    public NormalizedProduct(String canonicalId, String cleanedTitle, String brand, String model, String barcode) {
        this.canonicalId = canonicalId;
        this.cleanedTitle = cleanedTitle;
        this.brand = brand;
        this.model = model;
        this.barcode = barcode;
    }

    public String getCanonicalId() { return canonicalId; }
    public String getCleanedTitle() { return cleanedTitle; }
    public String getBrand() { return brand; }
    public String getModel() { return model; }
    public String getBarcode() { return barcode; }
}

class RetailerPrice {
    private final String retailerId;
    private final double price;
    private final String currency;
    private final String url;
    private final long lastUpdated;

    public RetailerPrice(String retailerId, double price, String currency, String url) {
        this.retailerId = retailerId;
        this.price = price;
        this.currency = currency;
        this.url = url;
        this.lastUpdated = System.currentTimeMillis();
    }

    public String getRetailerId() { return retailerId; }
    public double getPrice() { return price; }
    public String getCurrency() { return currency; }
    public String getUrl() { return url; }
    public long getLastUpdated() { return lastUpdated; }

    public boolean isStale(long maxAgeMs) {
        return (System.currentTimeMillis() - lastUpdated) > maxAgeMs;
    }
}

class Normalizer {
    public NormalizedProduct normalize(String rawTitle, String barcode) {
        String cleaned = rawTitle.toLowerCase()
            .replaceAll("(?i)\\b(unlocked|model|refurbished|oem)\\b.*", "")
            .trim();
        
        String brand = "Generic";
        if (cleaned.contains("apple") || cleaned.contains("iphone")) {
            brand = "Apple";
        } else if (cleaned.contains("samsung") || cleaned.contains("galaxy")) {
            brand = "Samsung";
        } else if (cleaned.contains("sony")) {
            brand = "Sony";
        }

        String model = cleaned;
        if (cleaned.startsWith(brand.toLowerCase())) {
            model = cleaned.substring(brand.length()).trim();
        }

        String canonicalId = "CAN-" + UUID.randomUUID().toString().substring(0, 8).toUpperCase();
        return new NormalizedProduct(canonicalId, cleaned, brand, model, barcode);
    }
}

class EntityMatcher {
    public double calculateJaccard(String s1, String s2) {
        if (s1 == null || s2 == null) return 0.0;
        Set<String> words1 = new HashSet<>(Arrays.asList(s1.toLowerCase().split("\\s+")));
        Set<String> words2 = new HashSet<>(Arrays.asList(s2.toLowerCase().split("\\s+")));
        
        Set<String> intersection = new HashSet<>(words1);
        intersection.retainAll(words2);
        
        Set<String> union = new HashSet<>(words1);
        union.addAll(words2);
        
        if (union.isEmpty()) return 0.0;
        return (double) intersection.size() / union.size();
    }

    public NormalizedProduct match(RetailerProduct rawProduct, Collection<NormalizedProduct> catalog) {
        if (rawProduct.getBarcode() != null && !rawProduct.getBarcode().isEmpty()) {
            for (NormalizedProduct np : catalog) {
                if (rawProduct.getBarcode().equals(np.getBarcode())) {
                    return np;
                }
            }
        }
        
        double bestSim = 0.0;
        NormalizedProduct bestMatch = null;
        String rawCleaned = rawProduct.getRawTitle().toLowerCase()
            .replaceAll("(?i)\\b(unlocked|model|refurbished|oem)\\b.*", "").trim();

        for (NormalizedProduct np : catalog) {
            double sim = calculateJaccard(rawCleaned, np.getCleanedTitle());
            if (sim > 0.65 && sim > bestSim) {
                bestSim = sim;
                bestMatch = np;
            }
        }
        return bestMatch;
    }
}

class PriceIndex {
    private final Map<String, List<RetailerPrice>> prices = new ConcurrentHashMap<>();

    public void addPrice(String canonicalId, RetailerPrice price) {
        prices.computeIfAbsent(canonicalId, k -> new CopyOnWriteArrayList<>()).add(price);
    }

    public List<RetailerPrice> getPrices(String canonicalId) {
        return prices.getOrDefault(canonicalId, Collections.emptyList());
    }
}

class BestPriceService {
    private final PriceIndex priceIndex;
    private final long maxAgeMs;

    public BestPriceService(PriceIndex priceIndex, long maxAgeHours) {
        this.priceIndex = priceIndex;
        this.maxAgeMs = maxAgeHours * 60 * 60 * 1000L;
    }

    public List<RetailerPrice> getBestPrices(String canonicalId) {
        List<RetailerPrice> activePrices = new ArrayList<>();
        for (RetailerPrice rp : priceIndex.getPrices(canonicalId)) {
            if (!rp.isStale(maxAgeMs)) {
                activePrices.add(rp);
            }
        }
        activePrices.sort(Comparator.comparingDouble(RetailerPrice::getPrice));
        return activePrices;
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("=== JAVA PRICE COMPARISON ENGINE SIMULATION ===");
        EntityMatcher matcher = new EntityMatcher();
        PriceIndex priceIndex = new PriceIndex();
        
        List<NormalizedProduct> catalog = new CopyOnWriteArrayList<>();

        NormalizedProduct np1 = new NormalizedProduct("CAN-IPHONE15", "apple iphone 15 pro 128gb", "Apple", "iphone 15 pro 128gb", "195949018442");
        catalog.add(np1);

        priceIndex.addPrice("CAN-IPHONE15", new RetailerPrice("Amazon", 999.00, "USD", "http://amazon.com/iphone15"));
        priceIndex.addPrice("CAN-IPHONE15", new RetailerPrice("Walmart", 979.99, "USD", "http://walmart.com/iphone15"));

        System.out.println("Ingesting raw product feeds...");
        
        RetailerProduct feed1 = new RetailerProduct("BestBuy", "Apple iPhone 15 Pro (128GB) Unlocked Model", 989.00, "USD", "195949018442", "http://bestbuy.com/iphone15");
        NormalizedProduct matched1 = matcher.match(feed1, catalog);
        if (matched1 != null) {
            System.out.println("✅ Matched [Exact Barcode]: " + feed1.getRawTitle() + " -> " + matched1.getCanonicalId());
            priceIndex.addPrice(matched1.getCanonicalId(), new RetailerPrice(feed1.getRetailerId(), feed1.getPrice(), feed1.getCurrency(), feed1.getUrl()));
        }

        RetailerProduct feed2 = new RetailerProduct("Target", "Apple iPhone 15 Pro Space Gray 128GB", 995.00, "USD", "", "http://target.com/iphone15");
        NormalizedProduct matched2 = matcher.match(feed2, catalog);
        if (matched2 != null) {
            System.out.println("✅ Matched [Fuzzy Title]: " + feed2.getRawTitle() + " -> " + matched2.getCanonicalId());
            priceIndex.addPrice(matched2.getCanonicalId(), new RetailerPrice(feed2.getRetailerId(), feed2.getPrice(), feed2.getCurrency(), feed2.getUrl()));
        }

        BestPriceService bestPriceService = new BestPriceService(priceIndex, 24);
        List<RetailerPrice> bestPrices = bestPriceService.getBestPrices("CAN-IPHONE15");
        
        System.out.println("\nBest Prices for Apple iPhone 15 Pro 128GB (Ascending):");
        for (RetailerPrice rp : bestPrices) {
            System.out.println(" - " + rp.getRetailerId() + ": $" + rp.getPrice() + " (URL: " + rp.getUrl() + ")");
        }

        System.out.println("=== END OF JAVA SIMULATION ===");
    }
}

Interactive Simulator

❖Price Comparison & Entity Normalizer Simulator

Clean marketing strings, match products using barcodes, calculate Jaccard similarities, and purge stale feeds.

📥 Ingest Retailer Pricing Feed

📜 Processing & Matching Engine Logs

🔄 Comparison engine initialized.

📂 Canonical Index Catalog

Brand: Apple
Model: iphone 15 pro 128gb
UPC Barcode: 195949018442

📊 Retailer Prices Array

Max Age: 24h
WalmartBest Price
Age: 0 hours ago
$979.99
Amazon
Age: 0 hours ago
$999.00

💬Review

Help Us Improve

How helpful was this walkthrough?

Click a star to rate. We actively use this feedback to refine and update our system design content.

Placeholder
Optional but highly appreciated!

Discussion

Share your thoughts, ask questions, or help others.

Loading comments...