Festive biathlon

    Programmers' dayHappy programmer day, colleagues!

    I propose in honor of the holiday to stretch their brains and participate in biathlon.
    Sports: algorithms, SQL. For each of them there will be two tasks: simpler and more complicated.
    As a reward for the efforts, all participants are guaranteed improved blood circulation in the left hemisphere of the brain (:

    Algorithms Task number 1, warm-up


    Write a code that finds the number of sub- numbers of the number n into which this number is divisible without a remainder.

    For a number n, a sub-number is a number whose record is a substring of the number n. For example, if n equals 1938, then its sub-numbers will be: 1, 9, 3, 8, 19, 93, 38, 193 and 938. Without a remainder, 1938 is divided into four of these sub-numbers: 1, 3, 19 and 38. Accordingly, the result of the program should be the number 4.
    If the sub-numbers are repeated, each of them is considered. For example, 101 is divisible by 1, 1, and 01, which means the answer is 3.

    Since the task is not difficult, brevity or a non-standard approach are appreciated in solutions.

    Algorithms Problem number 2, more difficult


    The management of the financial pyramid decided to assign a numerical rating to each of the participants in the pyramid. If the participant has still not brought anyone into the pyramid, then his rating is 1. If the participant already has subordinates, then his rating is 1 + the sum of the ratings of his direct subordinates.
    Task: find the sum of the ratings of all participants in the financial pyramid.

    The initial data is presented as an array of n lines, where each line contains n characters. Each character is either '0' or '1'.
    The j-th character of the i-th line indicates whether the participant under number j is a direct subordinate of participant i.
    The jth character of the jth line is always '0'. The member tree never has cycles. Each participant is always a direct subordinate of at most one other participant. The member tree always has only one root member.

    Example raw data:

    "0110""0000""0001""0000"

    The root element in this case is participant 0. It has two subordinates: participants 1 and 2. 1 has no subordinates, 2 has a subordinate participant 3.
    3rd rating: 1.
    1st rating: 1.
    2nd rating: 1 + 1 = 2.
    Rating of the 0th: 1 + 1 + 2 = 4.

    The result of the code should be the sum of the ratings of all participants, in this case: 1 + 1 + 2 + 4 = 8.

    SQL Problem number 1, simpler


    Given: two (non-normalized) tables:
    Categories (Id, Name)
    Books (Id, CategoryId, Name)

    In the future, of course, you want to add a third table-binding table, Book_Category, but so far there may be several records in the Books table with the same value Name fields, but different CategoryId.

    Task: write a query that selects all books that are in the category with Id = 1, but which are not in the category with Id = 2.
    A small clarification: the DBMS you use does not know what subqueries are :)

    SQL Problem number 2, more difficult


    There is a table Players (Id, Name, Score), where Score is the number of player points. The more points, the higher the player’s place in the standings.
    Objective: write a query that selects players holding (dividing) 3rd place.

    UPD: Since the task turned out to be easier than expected, a restriction is introduced: you cannot use subqueries. For fun, try to get by with joins :)

    Example data:

    Players

    As you can see, Stepan and Svetlana share 1-2 places, and Vladimir and Valentin share 3-4, which the query should return.

    The script for creating the table and test data can be downloaded .

    In the end


    Those who do not have an account can send the solutions to me by mail: dmitrii.shevchenko@gmail.com . I do not promise invites (I do not have them), but in the commentary I will post the most interesting solutions.

    I hope you will like it :)

    Also popular now: