Mid-Term Exam

March 16, 2018

At many colleges and universities, Spring Break is approaching soon, and that means mid-term exams are also imminent. Here are two questions suitable for a mid-term exam for not-too-advanced students:

First: You are given two strings, say “aet6ukm” and “123678”; neither is necessarily sorted. You are to find the first character in the first string that also appears in the second string, and return the index of the character in the second string. For the two strings above, the character “6” appears in the first string and also in the second string, at index position 3 (counting from zero), so your program should return 3.

Second: You are given a list of recipes, where each recipe is a list with a name in the first position of the list and a list of ingredients in the remaining positions of the list; for instance, (“Pasta” “Spaghetti” “Tomato sauce” “Basil”) is a simple recipe for pasta. Your program should return a list of all ingredients that are used in more than one recipe, with a list of recipe names attached to each ingredient.

Your task is to answer the two mid-term exam questions given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

6 Responses to “Mid-Term Exam”

  1. Paul said

    In Python.

    from collections import defaultdict
    
    def first(s1, s2):
        D = {val:pos for pos, val in reversed(list(enumerate(s2)))}
        return next((pos for pos, val in enumerate(s1) if val in D), False)
    
    print(first("aet6ukm", "1236786"))  # -> 3
    print(first("aet9ukm", "1236786"))  # -> False
    
    def second(recipes):
        D = defaultdict(list)
        for meal, *ingredients in recipes:
            for i in ingredients:
                D[i].append(meal)
        return [(ingredient, meals) for ingredient, meals in D.items()
                if len(meals) > 1]
    
    recipes = [("a", 1, 2, 3), ("b", 2, 4, 6), ("c", 3, 6, 7), ("d", 4, 5),
               ("e", 5, 7, 9), ("f", 6, 7, 8), ("g", 8, 9)]
    
    print(second(recipes))
    # [(2, ['a', 'b']), (3, ['a', 'c']), (4, ['b', 'd']), (6, ['b', 'c', 'f']),
    # (7, ['c', 'e', 'f']), (5, ['d', 'e']), (9, ['e', 'g']), (8, ['f', 'g'])]
    
  2. Globules said

    A Haskell version.

    import Data.Function (on)
    import Data.List (findIndex, groupBy, sort)
    import Data.Tuple (swap)
    
    first :: Eq a => [a] -> [a] -> Maybe Int
    first xs ys = findIndex (`elem` ys) xs
    
    --------------------------------------------------------------------------------
    
    -- For lists of length > 1: unpair . pair = id
    
    pair :: [a] -> [(a, a)]
    pair (x:xs) = map ((,) x) xs
    pair _      = []
    
    unpair :: [(a, a)] -> [a]
    unpair xs@(x:_) = fst x : map snd xs
    unpair _        = []
    
    second :: Ord a => [[a]] -> [[a]]
    second = filter ((> 2) . length)
           . map unpair
           . groupBy ((==) `on` fst)
           . sort
           . map swap
           . concatMap pair
    
    --------------------------------------------------------------------------------
    
    main :: IO ()
    main = do
      print $ first "aet6ukm" "123678"
      print $ first "aet9ukm" "123678"
      putStrLn ""
      mapM_ print $ second [ ["a", "1", "2", "3"]
                           , ["b", "2", "4", "6"]
                           , ["c", "3", "6", "7"]
                           , ["d", "4", "5"]
                           , ["e", "5", "7", "9"]
                           , ["f", "6", "7", "8"]
                           , ["g", "8", "9"]
                           ]
    
    $ ./midterm
    Just 3
    Nothing
    
    ["2","a","b"]
    ["3","a","c"]
    ["4","b","d"]
    ["5","d","e"]
    ["6","b","c","f"]
    ["7","c","e","f"]
    ["8","f","g"]
    ["9","e","g"]
    
  3. ad said

    Kotlin version

    fun main(args: Array<String>) {
    val recipes = listOf(listOf("a", 1, 2, 3),
    listOf("b", 2, 4, 6), listOf("c", 3, 6, 7), listOf("d", 4, 5),
    listOf("e", 5, 7, 9),
    listOf("f", 6, 7, 8),
    listOf("g", 8, 9) )

    val commonIngredients = recipes.map {
    l -> Pair(l.take(1)[0], l.drop(1))
    } . flatMap {
    p -> p.second.map { ingredient -> Pair(ingredient, p.first) }
    } . groupBy {
    it.first
    } . filter {
    it.value.size > 1
    } . mapValues {
    it.value.map { p -> p.second }
    }

    println(commonIngredients)

    }

  4. ad said
    fun main(args: Array<String>) {
        val recipes = listOf(listOf("a", 1, 2, 3),
                listOf("b", 2, 4, 6), listOf("c", 3, 6, 7), listOf("d", 4, 5),
                listOf("e", 5, 7, 9),
                listOf("f", 6, 7, 8),
                listOf("g", 8, 9) )
    
       val commonIngredients = recipes.map {
            l -> Pair(l.take(1)[0], l.drop(1))
        } . flatMap {
            p -> p.second.map { ingredient -> Pair(ingredient, p.first) }
        } . groupBy {
            it.first
        } . filter {
            it.value.size > 1
        } . mapValues {
           it.value.map { p -> p.second }
        }
    
        println(commonIngredients)
    
    }
    
  5. Daniel said

    Here’s a solution to the first problem in C.

    /* first.c */
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    // Finds the first character in s1 that's also in
    // s2, and returns the index in s2.
    // Returns the index of the null character in s2
    // on failure.
    size_t find_first_char(char* s1, char* s2) {
      size_t s1_len = strlen(s1);
      size_t s2_len = strlen(s2);
      size_t index_lookup[256];
      for (size_t i = 0; i < 256; ++i) {
        index_lookup[i] = s2_len;
      }
      for (size_t i = 0; i < s2_len; ++i) {
        unsigned char c = s2[i];
        if (index_lookup[c] < s2_len) continue;
        index_lookup[c] = i;
      }
      for (size_t i = 0; i < s1_len; ++i) {
        unsigned char c = s1[i];
        size_t index = index_lookup[c];
        if (index < s2_len) return index;
      }
      return s2_len;
    }
    
    static char usage[] = "Usage: first STRING1 STRING2";
    #define PRINT_USAGE_AND_EXIT(stream) \
      do {                               \
        fprintf(stream, "%s\n", usage);  \
        exit(EXIT_FAILURE);              \
      } while (0)
    
    int main(int argc, char* argv[]) {
      if (argc != 3) PRINT_USAGE_AND_EXIT(stderr);
      size_t index = find_first_char(argv[1], argv[2]);
      printf("%zu\n", index);
      return EXIT_SUCCESS;
    }
    

    Example Usage:

    $ ./first aet6ukm 123678
    3
    
  6. Daniel said

    Here’s a solution to the second problem in C++11.

    /* second.cpp */
    
    #include <cstdlib>
    #include <iostream>
    #include <unordered_map>
    #include <vector>
    
    using std::cout;
    using std::endl;
    using std::move;
    using std::pair;
    using std::string;
    using std::unordered_map;
    using std::vector;
    
    void find_ingredients(
        const vector<vector<string>>& recipes,
        vector<pair<string,vector<string>>>* output) {
      unordered_map<string, vector<string>> recipe_lookup;
      for (const auto& recipe : recipes) {
        const string& name = recipe[0];
        for (size_t i = 1; i < recipe.size(); ++i) {
          const string& ingredient = recipe[i];
          if (recipe_lookup.find(ingredient) == recipe_lookup.end()) {
            recipe_lookup.insert({ingredient, vector<string>()});
          }
          recipe_lookup[ingredient].push_back(name);
        }
      }
      for (const auto& x : recipe_lookup) {
        const vector<string>& recipes = x.second;
        if (recipes.size() > 1) {
          output->push_back(move(x));
        }
      }
    }
    
    int main() {
      const vector<vector<string>> recipes {
        {"a", "1", "2", "3"},
        {"b", "2", "4", "6"},
        {"c", "3", "6", "7"},
        {"d", "4", "5"},
        {"e", "5", "7", "9"},
        {"f", "6", "7", "8"},
        {"g", "8", "9"}
      };
      vector<pair<string,vector<string>>> ingredient_recipes;
      find_ingredients(recipes, &ingredient_recipes);
      for (const auto& x : ingredient_recipes) {
        const string& ingredient = x.first;
        const vector<string>& recipes = x.second;
        cout << ingredient << " [";
        for (size_t i = 0; i < recipes.size(); ++i) {
          if (i > 0) cout << ", ";
          cout << recipes[i];
        }
        cout << "]" << endl;
      }
      return EXIT_SUCCESS;
    }
    

    Output:

    5 [d, e]
    7 [c, e, f]
    9 [e, g]
    6 [b, c, f]
    8 [f, g]
    4 [b, d]
    3 [a, c]
    2 [a, b]
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: