Ingredient Quantity Parser — Problem Statement & Solution Guide

StringsMediumMixed

TimeO(n)

SpaceO(k)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Strings and solve the Ingredient Quantity Parser problem optimally.

TopicStrings

PatternMixed

TimeO(n)

SpaceO(k)

Problem Description

Given a single line string that encodes several ingredient‑quantity pairs, parse the string and return a mapping from each ingredient to its associated quantity. Each pair is formatted as <ingredient>:<quantity> and pairs are separated by commas. Ingredient names consist only of lowercase English letters (a‑z) and are non‑empty. Quantities are non‑empty sequences of alphanumeric characters (digits and optional unit letters). The input string contains no leading or trailing commas, and there are no extra whitespace characters. Your function should output a dictionary (or map) where keys are ingredient names and values are the exact quantity strings as they appear in the input.

DSA Pattern Breakdown

"Ingredient Quantity Parser"

medium

WHY DOES IT MATTER?

Efficient string tokenization is a foundational pattern for any text‑driven protocol, configuration file, or log‑parsing task; mastering it prevents hidden quadratic costs in real‑world pipelines.

OPTIMIZATION CHALLENGE

The key insight is to avoid repeated splitting or substring creation; by scanning character‑by‑character and building tokens on the fly, you keep the algorithm linear and memory usage proportional only to the output size.

REAL-WORLD CONNECTION

Think of a network router parsing a CSV‑style routing table: each line must be read once and inserted into a routing hash table, mirroring the ingredient‑quantity map creation.

When coding under pressure, write a tiny state machine with clear enum states (READ_INGREDIENT, READ_QUANTITY) and use index pointers instead of calling split() inside loops; this eliminates hidden O(n²) behavior.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(k)

Core Theory — Why This Approach?

The problem reduces to tokenizing a delimited string and aggregating the results into a hash map. A linear scan that identifies delimiters (',' and ':') yields each ingredient and its quantity in O(n) time, where n is the length of the input. Naïve approaches that repeatedly split the string using high‑overhead library calls or that scan the string multiple times incur O(n²) time because each split creates new substrings and traverses the remaining characters again. The optimal paradigm is a single-pass deterministic finite automaton (DFA) that switches states between reading an ingredient, expecting a colon, reading a quantity, and handling commas, thereby guaranteeing linear time and constant auxiliary space aside from the output map.

Interview Questions on This Problem

Q1How would you modify the parser to handle duplicate ingredients where the last occurrence should overwrite the previous one?

During the linear scan, simply insert each (ingredient, quantity) pair into the hash map; if the key already exists, the new value overwrites the old one, which naturally satisfies the "last occurrence wins" rule.

Q2If quantities could be arbitrarily large integers, how would you store them without overflow in a language like Java?

Parse the quantity as a string and store it as a BigInteger (or equivalent arbitrary‑precision type) in the map, avoiding any intermediate numeric conversion that could overflow.

Q3Describe how you would extend the solution to support nested structures like "sauce:tomato{2},spice:pepper{1}" where braces denote sub‑quantities.

First, treat the outer delimiter parsing unchanged, then when reading a quantity, detect an opening brace and recursively parse the substring inside the braces using the same state machine, building a nested map or object to represent sub‑quantities.

Examples

Example 1

Input

flour:200g,sugar:100g,eggs:2

Output

{"flour":"200g","sugar":"100g","eggs":"2"}

Explanation: The string is split at commas yielding three tokens: 'flour:200g', 'sugar:100g', and 'eggs:2'. Each token is then split at the colon. The left part becomes the key and the right part becomes the value, producing the map {flour→200g, sugar→100g, eggs→2}.

Example 2

Input

milk:1L,coffee:3tbsp,cream:250ml

Output

{"milk":"1L","coffee":"3tbsp","cream":"250ml"}

Explanation: Splitting on commas gives three pairs. Further splitting each pair on ':' extracts the ingredient and its quantity, resulting in the dictionary {milk→1L, coffee→3tbsp, cream→250ml}.

Example 3

Input

tomato:5,lettuce:1head,bacon:200g,cheese:150g

Output

{"tomato":"5","lettuce":"1head","bacon":"200g","cheese":"150g"}

Explanation: The input contains four comma‑separated pairs. After separating each pair by the colon, we map 'tomato' to '5', 'lettuce' to '1head', 'bacon' to '200g', and 'cheese' to '150g', yielding the final map.

Constraints

1 <= number of pairs <= 10^4
Total length of the input string <= 10^5 characters
Ingredient names contain only lowercase letters and are at most 20 characters long
Quantity strings contain only digits and optional unit letters and are at most 10 characters long
The input string is well‑formed: each pair contains exactly one ':' and pairs are separated by a single ','

Optimal Approach & Strategy

Perform a single pass with two pointers, building ingredient and quantity strings on the fly and inserting them directly into a hash map.

Brute Force Approach

Repeatedly call split(',') then split(':') on each segment, creating many intermediate strings and traversing the input multiple times.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

function parseIngredients(s){
    const map={};
    if(!s) return map;
    const pairs=s.split(',');
    for(const p of pairs){
        const idx=p.indexOf(':');
        if(idx===-1) continue; // malformed
        const ing=p.substring(0,idx);
        const qty=p.substring(idx+1);
        map[ing]=qty; // last wins
    }
    return map;
}

// Driver (same as template)
const readline=require('readline');
const rl=readline.createInterface({input:process.stdin,output:process.stdout});
let input='';
rl.on('line',line=>{input+=line;});
rl.on('close',()=>{console.log(JSON.stringify(parseIngredients(input.trim())));});

#include <bits/stdc++.h>
using namespace std;

unordered_map<string,string> parseIngredients(const string& s){
    unordered_map<string,string> mp;
    size_t i=0,n=s.size();
    while(i<n){
        // parse ingredient
        size_t start=i;
        while(i<n && s[i]!=':') i++;
        if(i==n) break; // malformed
        string ing=s.substr(start,i-start);
        i++; // skip ':'
        // parse quantity
        start=i;
        while(i<n && s[i]!=',') i++;
        string qty=s.substr(start,i-start);
        mp[ing]=qty; // last occurrence wins
        if(i<n && s[i]==',') i++; // skip ','
    }
    return mp;
}

int main(){
    string line; getline(cin,line);
    auto res=parseIngredients(line);
    cout<<"{";
    bool first=true;
    for(const auto& kv:res){
        if(!first) cout<<","; first=false;
        cout<<"\""<<kv.first<<"\":\""<<kv.second<<"\"";
    }
    cout<<"}"<<"\n";
    return 0;
}

import java.util.*;

public class Main {
    public static Map<String,String> parseIngredients(String s){
        Map<String,String> map=new LinkedHashMap<>();
        if(s==null||s.isEmpty()) return map;
        String[] pairs=s.split(",");
        for(String p:pairs){
            int idx=p.indexOf(':');
            if(idx==-1) continue;
            String ing=p.substring(0,idx);
            String qty=p.substring(idx+1);
            map.put(ing,qty);
        }
        return map;
    }
    public static void main(String[] args) throws Exception{
        java.io.BufferedReader br=new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
        String line=br.readLine();
        Map<String,String> res=parseIngredients(line==null?"":line.trim());
        StringBuilder sb=new StringBuilder();
        sb.append('{');
        boolean first=true;
        for(Map.Entry<String,String> e:res.entrySet()){
            if(!first) sb.append(',');
            first=false;
            sb.append('"').append(e.getKey()).append('"').append(':').append('"').append(e.getValue()).append('"');
        }
        sb.append('}');
        System.out.println(sb.toString());
    }
}

def parse_ingredients(s):
    result={}
    if not s:
        return result
    for pair in s.split(','):
        if ':' not in pair:
            continue
        ing, qty = pair.split(':',1)
        result[ing]=qty
    return result

if __name__=="__main__":
    import sys, json
    line=sys.stdin.read().strip()
    print(json.dumps(parse_ingredients(line)))

function parseIngredients(s){
    const map={};
    if(!s) return map;
    const pairs=s.split(',');
    for(const p of pairs){
        const idx=p.indexOf(':');
        if(idx===-1) continue; // malformed
        const ing=p.substring(0,idx);
        const qty=p.substring(idx+1);
        map[ing]=qty; // last wins
    }
    return map;
}

// Driver (same as template)
const readline=require('readline');
const rl=readline.createInterface({input:process.stdin,output:process.stdout});
let input='';
rl.on('line',line=>{input+=line;});
rl.on('close',()=>{console.log(JSON.stringify(parseIngredients(input.trim())));});

Asked in Top Tech Interviews

PhonePe

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.