Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
      • 17
      • 18
        Graph Representation
      • 19

  • Podcast search

    After playing with pairs (guest, views) of Lex Fridman’s podcasts, Anna loses the guest information from some of the pairs and is left with only views for those podcasts. She wants you to help her restore that information. There is one more issue with her list as well. She wrote the information about the views a month ago, while yours is fresh. So, the views in her list might be lower than yours. But you decide to give your best guess for each of the questions Anna asks you.


    The first line of the input contains a single integer n (1 ≤ n ≤ ) - the number of podcasts you’ve kept as a list of pairs.
    The next 2n lines contain pairs of guests and views. First comes the name of the guest, then the number of views that the podcast obtained. The list of guests is ordered by views in increasing order.
    The following line contains a single integer q (1 ≤ q ≤ n) - the number of podcasts Anna lost recently.
    The next line contains q integers separated by a space - the view counts of each podcast Anna lost in her list.


    For each of the q questions, the program should print the name of the podcast guest that got views greater or equal to the given number. If there are several such podcasts print the guest name that had minimum number of views


    5 Mark Zuckerberg 3800000 Kanye West 4000000 Vitalik Buterin 4500000 Joe Rogan 6200000 Elon Musk 6400000 3 6300000 3800000 6100000
    Elon Musk Mark Zuckerberg Joe Rogan


    Time limit: 3 seconds

    Memory limit: 512 MB

    Output limit: 25 MB

    To check your solution you need to sign in
    Sign in to continue