Implement Game Metadata Lookups

medium

Coding OOPReported Apr 2026

Approach 1: Linear Scan for Every Query

The most direct implementation keeps the records in a plain list and answers each lookup by walking through that list. No preprocessing is required, but every name lookups, genre lookups, and platform-count query scans the entire catalog.

For name and genre matching, normalize both the input and the stored value before comparing. For platform queries, convert each game's platform list into a set so repeated platforms are counted only once. To find the games on the largest number of unique platforms, first compute the maximum count, then use a second pass to collect every game with that count in input order.

Consider this small catalog:

games = [
  {"name": "Neon Drift", "platform": ["pc", "pc", "switch"], "genre": "Racing"},
  {"name": "Iron Vale",   "platform": ["xbox", "switch"],     "genre": "RPG"},
  {"name": "Mystic Path", "platform": ["switch"],             "genre": "Adventure"}
]

For get_genre("IRON VALE"), the scan checks Neon Drift, then Iron Vale, and returns "RPG". The unique platform counts are 2, 2, and 1, so the maximum is 2 and get_most_available_games() returns ["Neon Drift", "Iron Vale"].

def get_genre(input_game):    target = input_game.casefold()    for game in games:        if game["name"].casefold() == target:            return game["genre"]    return Nonedef get_games(input_genre):    target = input_genre.casefold()    result = []    for game in games:        if game["genre"].casefold() == target:            result.append(game["name"])    return resultdef get_most_available_games(games):    max_count = 0    for game in games:        max_count = max(max_count, len(set(game["platform"])))    return [        game["name"]        for game in games        if len(set(game["platform"])) == max_count    ]def get_available_games(number_of_platform):    return [        game["name"]        for game in games        if len(set(game["platform"])) == number_of_platform    ]

import java.util.*;public class GameCatalogLinear {    private final List<Map<String, Object>> games;    public GameCatalogLinear(List<Map<String, Object>> games) {        this.games = games;    }    private int uniquePlatformCount(Map<String, Object> game) {        Object platformValue = game.get("platform");        if (!(platformValue instanceof List<?>)) {            return 0;        }        return new HashSet<Object>((List<?>) platformValue).size();    }    public String getGenre(String inputGame) {        String target = inputGame.toLowerCase(Locale.ROOT);        for (Map<String, Object> game : games) {            String name = (String) game.get("name");            if (name.toLowerCase(Locale.ROOT).equals(target)) {                return (String) game.get("genre");            }        }        return null;    }    public List<String> getGames(String inputGenre) {        String target = inputGenre.toLowerCase(Locale.ROOT);        List<String> result = new ArrayList<>();        for (Map<String, Object> game : games) {            String genre = (String) game.get("genre");            if (genre.toLowerCase(Locale.ROOT).equals(target)) {                result.add((String) game.get("name"));            }        }        return result;    }    public List<String> getMostAvailableGames() {        int maxCount = 0;        for (Map<String, Object> game : games) {            maxCount = Math.max(maxCount, uniquePlatformCount(game));        }        List<String> result = new ArrayList<>();        for (Map<String, Object> game : games) {            if (uniquePlatformCount(game) == maxCount) {                result.add((String) game.get("name"));            }        }        return result;    }    public List<String> getAvailableGames(int requestedCount) {        List<String> result = new ArrayList<>();        for (Map<String, Object> game : games) {            if (uniquePlatformCount(game) == requestedCount) {                result.add((String) game.get("name"));            }        }        return result;    }}

Time & Space Complexity

Time complexity: $O(n)$ for name and genre queries, and $O(n + p)$ for platform-count queries — each query scans every game, and platform-count queries also inspect every platform entry, where p is the total number of platform strings across all games.
Space complexity: $O(1)$ auxiliary space beyond the output — no extra data structure is kept between queries.

Approach 2: Precomputed Case-Insensitive Indexes

The linear approach repeats two expensive operations: scanning all records and reconstructing platform sets. Since the catalog can have up to 100,000 records and 100,000 queries, we can instead build dictionaries once and make each query a direct lookup.

Build three structures during one pass over the game list:

A name index mapping a casefolded game name to its full record.
A genre index mapping a casefolded genre to a list of original game names, appended in input order.
A platform-count index mapping a unique platform count to a list of original game names, also appended in input order.

Also track the largest platform count seen so far. Because all lists are appended during the input-order pass, returned lists naturally preserve the required ordering. Original casing is preserved because we never store the modified name as the result value.

Using the earlier sample:

name_index contains keys like "neon drift", "iron vale", and "mystic path".
genre_index maps "racing" to ["Neon Drift"], "rpg" to ["Iron Vale"], and "adventure" to ["Mystic Path"].
The unique platform count for Neon Drift is 2 because the duplicate "pc" entry is removed by the set. Iron Vale also has 2 platforms, and Mystic Path has 1.
Therefore count_index contains {2: ["Neon Drift", "Iron Vale"], 1: ["Mystic Path"]}, and max_count is 2.

After preprocessing, get_games("RACING") is a single dictionary lookup, and get_most_available_games() simply returns the list stored under max_count.

_index_cache = {}def _build_indexes(games):    name_index = {}    genre_index = {}    count_index = {}    max_count = 0    for game in games:        original_name = game["name"]        genre = game["genre"]        name_index[original_name.casefold()] = game        genre_key = genre.casefold()        genre_index.setdefault(genre_key, []).append(original_name)        # Duplicates in the platform list must not affect the count.        unique_platforms = len(set(game["platform"]))        count_index.setdefault(unique_platforms, []).append(original_name)        if unique_platforms > max_count:            max_count = unique_platforms    return name_index, genre_index, count_index, max_countdef _get_indexes(games):    # Cache by object identity so repeat queries do not rebuild the indexes.    key = id(games)    if key not in _index_cache:        _index_cache[key] = _build_indexes(games)    return _index_cache[key]def get_genre(input_game):    name_index, _, _, _ = _get_indexes(games)    game = name_index.get(input_game.casefold())    if game is None:        return None    return game["genre"]def get_games(input_genre):    _, genre_index, _, _ = _get_indexes(games)    return genre_index.get(input_genre.casefold(), [])def get_most_available_games(games):    _, _, count_index, max_count = _get_indexes(games)    return count_index.get(max_count, [])def get_available_games(number_of_platform):    _, _, count_index, _ = _get_indexes(games)    return count_index.get(number_of_platform, [])

import java.util.*;public class GameCatalog {    private final Map<String, Map<String, Object>> nameIndex = new HashMap<>();    private final Map<String, List<String>> genreIndex = new HashMap<>();    private final Map<Integer, List<String>> countIndex = new HashMap<>();    private final int maxCount;    public GameCatalog(List<Map<String, Object>> games) {        int runningMax = 0;        for (Map<String, Object> game : games) {            String originalName = (String) game.get("name");            String genre = (String) game.get("genre");            List<?> platforms = (List<?>) game.get("platform");            String nameKey = originalName.toLowerCase(Locale.ROOT);            nameIndex.put(nameKey, game);            String genreKey = genre.toLowerCase(Locale.ROOT);            genreIndex                .computeIfAbsent(genreKey, ignored -> new ArrayList<>())                .add(originalName);            int uniqueCount = new HashSet<Object>(platforms).size();            countIndex                .computeIfAbsent(uniqueCount, ignored -> new ArrayList<>())                .add(originalName);            runningMax = Math.max(runningMax, uniqueCount);        }        this.maxCount = runningMax;    }    public String getGenre(String inputGame) {        Map<String, Object> game = nameIndex.get(inputGame.toLowerCase(Locale.ROOT));        return game == null ? null : (String) game.get("genre");    }    public List<String> getGames(String inputGenre) {        return genreIndex.getOrDefault(            inputGenre.toLowerCase(Locale.ROOT),            Collections.emptyList()        );    }    public List<String> getMostAvailableGames() {        return countIndex.getOrDefault(maxCount, Collections.emptyList());    }    public List<String> getAvailableGames(int requestedCount) {        return countIndex.getOrDefault(requestedCount, Collections.emptyList());    }}

Time & Space Complexity

Time complexity: $O(n + p)$ preprocessing, then $O(1)$ average time per query — each game and platform entry is processed once while building the indexes, and lookups are dictionary accesses. Returning a list of k games takes $O(k)$ output time.
Space complexity: $O(n)$ — every game record is stored in the name index, and each original game name appears in exactly one genre bucket and one platform-count bucket.

BackBack to problems

Implement Game Metadata Lookups

medium

Coding OOPReported Apr 2026

Approach 1: Linear Scan for Every Query

Consider this small catalog:

games = [
  {"name": "Neon Drift", "platform": ["pc", "pc", "switch"], "genre": "Racing"},
  {"name": "Iron Vale",   "platform": ["xbox", "switch"],     "genre": "RPG"},
  {"name": "Mystic Path", "platform": ["switch"],             "genre": "Adventure"}
]

def get_genre(input_game):    target = input_game.casefold()    for game in games:        if game["name"].casefold() == target:            return game["genre"]    return Nonedef get_games(input_genre):    target = input_genre.casefold()    result = []    for game in games:        if game["genre"].casefold() == target:            result.append(game["name"])    return resultdef get_most_available_games(games):    max_count = 0    for game in games:        max_count = max(max_count, len(set(game["platform"])))    return [        game["name"]        for game in games        if len(set(game["platform"])) == max_count    ]def get_available_games(number_of_platform):    return [        game["name"]        for game in games        if len(set(game["platform"])) == number_of_platform    ]

import java.util.*;public class GameCatalogLinear {    private final List<Map<String, Object>> games;    public GameCatalogLinear(List<Map<String, Object>> games) {        this.games = games;    }    private int uniquePlatformCount(Map<String, Object> game) {        Object platformValue = game.get("platform");        if (!(platformValue instanceof List<?>)) {            return 0;        }        return new HashSet<Object>((List<?>) platformValue).size();    }    public String getGenre(String inputGame) {        String target = inputGame.toLowerCase(Locale.ROOT);        for (Map<String, Object> game : games) {            String name = (String) game.get("name");            if (name.toLowerCase(Locale.ROOT).equals(target)) {                return (String) game.get("genre");            }        }        return null;    }    public List<String> getGames(String inputGenre) {        String target = inputGenre.toLowerCase(Locale.ROOT);        List<String> result = new ArrayList<>();        for (Map<String, Object> game : games) {            String genre = (String) game.get("genre");            if (genre.toLowerCase(Locale.ROOT).equals(target)) {                result.add((String) game.get("name"));            }        }        return result;    }    public List<String> getMostAvailableGames() {        int maxCount = 0;        for (Map<String, Object> game : games) {            maxCount = Math.max(maxCount, uniquePlatformCount(game));        }        List<String> result = new ArrayList<>();        for (Map<String, Object> game : games) {            if (uniquePlatformCount(game) == maxCount) {                result.add((String) game.get("name"));            }        }        return result;    }    public List<String> getAvailableGames(int requestedCount) {        List<String> result = new ArrayList<>();        for (Map<String, Object> game : games) {            if (uniquePlatformCount(game) == requestedCount) {                result.add((String) game.get("name"));            }        }        return result;    }}

Time & Space Complexity

Time complexity: $O(n)$ for name and genre queries, and $O(n + p)$ for platform-count queries — each query scans every game, and platform-count queries also inspect every platform entry, where p is the total number of platform strings across all games.
Space complexity: $O(1)$ auxiliary space beyond the output — no extra data structure is kept between queries.

Approach 2: Precomputed Case-Insensitive Indexes

Build three structures during one pass over the game list:

A name index mapping a casefolded game name to its full record.
A genre index mapping a casefolded genre to a list of original game names, appended in input order.
A platform-count index mapping a unique platform count to a list of original game names, also appended in input order.

Using the earlier sample:

name_index contains keys like "neon drift", "iron vale", and "mystic path".
genre_index maps "racing" to ["Neon Drift"], "rpg" to ["Iron Vale"], and "adventure" to ["Mystic Path"].
The unique platform count for Neon Drift is 2 because the duplicate "pc" entry is removed by the set. Iron Vale also has 2 platforms, and Mystic Path has 1.
Therefore count_index contains {2: ["Neon Drift", "Iron Vale"], 1: ["Mystic Path"]}, and max_count is 2.

After preprocessing, get_games("RACING") is a single dictionary lookup, and get_most_available_games() simply returns the list stored under max_count.

_index_cache = {}def _build_indexes(games):    name_index = {}    genre_index = {}    count_index = {}    max_count = 0    for game in games:        original_name = game["name"]        genre = game["genre"]        name_index[original_name.casefold()] = game        genre_key = genre.casefold()        genre_index.setdefault(genre_key, []).append(original_name)        # Duplicates in the platform list must not affect the count.        unique_platforms = len(set(game["platform"]))        count_index.setdefault(unique_platforms, []).append(original_name)        if unique_platforms > max_count:            max_count = unique_platforms    return name_index, genre_index, count_index, max_countdef _get_indexes(games):    # Cache by object identity so repeat queries do not rebuild the indexes.    key = id(games)    if key not in _index_cache:        _index_cache[key] = _build_indexes(games)    return _index_cache[key]def get_genre(input_game):    name_index, _, _, _ = _get_indexes(games)    game = name_index.get(input_game.casefold())    if game is None:        return None    return game["genre"]def get_games(input_genre):    _, genre_index, _, _ = _get_indexes(games)    return genre_index.get(input_genre.casefold(), [])def get_most_available_games(games):    _, _, count_index, max_count = _get_indexes(games)    return count_index.get(max_count, [])def get_available_games(number_of_platform):    _, _, count_index, _ = _get_indexes(games)    return count_index.get(number_of_platform, [])

import java.util.*;public class GameCatalog {    private final Map<String, Map<String, Object>> nameIndex = new HashMap<>();    private final Map<String, List<String>> genreIndex = new HashMap<>();    private final Map<Integer, List<String>> countIndex = new HashMap<>();    private final int maxCount;    public GameCatalog(List<Map<String, Object>> games) {        int runningMax = 0;        for (Map<String, Object> game : games) {            String originalName = (String) game.get("name");            String genre = (String) game.get("genre");            List<?> platforms = (List<?>) game.get("platform");            String nameKey = originalName.toLowerCase(Locale.ROOT);            nameIndex.put(nameKey, game);            String genreKey = genre.toLowerCase(Locale.ROOT);            genreIndex                .computeIfAbsent(genreKey, ignored -> new ArrayList<>())                .add(originalName);            int uniqueCount = new HashSet<Object>(platforms).size();            countIndex                .computeIfAbsent(uniqueCount, ignored -> new ArrayList<>())                .add(originalName);            runningMax = Math.max(runningMax, uniqueCount);        }        this.maxCount = runningMax;    }    public String getGenre(String inputGame) {        Map<String, Object> game = nameIndex.get(inputGame.toLowerCase(Locale.ROOT));        return game == null ? null : (String) game.get("genre");    }    public List<String> getGames(String inputGenre) {        return genreIndex.getOrDefault(            inputGenre.toLowerCase(Locale.ROOT),            Collections.emptyList()        );    }    public List<String> getMostAvailableGames() {        return countIndex.getOrDefault(maxCount, Collections.emptyList());    }    public List<String> getAvailableGames(int requestedCount) {        return countIndex.getOrDefault(requestedCount, Collections.emptyList());    }}

Time & Space Complexity

Time complexity: $O(n + p)$ preprocessing, then $O(1)$ average time per query — each game and platform entry is processed once while building the indexes, and lookups are dictionary accesses. Returning a list of k games takes $O(k)$ output time.
Space complexity: $O(n)$ — every game record is stored in the name index, and each original game name appears in exactly one genre bucket and one platform-count bucket.