Выпуск#34: ITренировка — актуальные вопросы и задачи от ведущих компаний

    Привет! Мы снова подготовили Вам подборку интересных вопросов и задачек с собеседований в ведущие IT-компании!



    Выпуски будут появляться каждую неделю — следите за обновлениями! Рубрика выходит при поддержке рекрутингового агентства Spice IT.

    На этой неделе мы собрали задачи с собеседований в индийскую компанию Snapdeal. Кстати, ответы на задачки из прошлого выпуска уже опубликованы.

    Вопросы


    1. Car Wheel Puzzle
    A car has 4 tyres and 1 spare tyre. Each tyre can travel a maximum distance of 20000 miles before wearing off. What is the maximum distance the car can travel before you are forced to buy a new tyre? You are allowed to change tyres (using the spare tyre) an unlimited number of times.

    Перевод
    Автомобиль имеет 4 шины и 1 запасную шину. Каждая шина может пройти максимальное расстояние в 20000 миль, прежде чем прийти в негодность. Какое максимальное расстояние может проехать автомобиль, прежде чем вы будете вынуждены купить новую шину? Вы можете менять шины (используя запасную шину) неограниченное количество раз.

    2. Completion of Task
    A man is allocated a task. He doubles the task done everyday. If the man completely does the task in 18 days, how many days did it take for the man to complete 25% of the task?

    Перевод
    Человеку дается задание. Каждый день он увеличивает свой прогресс в данном задании вдвое. Если человек полностью выполняет задание за 18 дней, то сколько дней ему потребовалось, чтобы выполнить 25% задания?

    Задачи


    1. Next greater number set digits
    Given a number n, find the smallest number that has same set of digits as n and is greater than n. If n is the greatest possible number with its set of digits, then print “not possible”.

    Input:
    The first line of input contains an integer T denoting the number of test cases.
    The first line of each test case is n,n is the number.

    Output:
    Print the greater number than n with same set of digits and if not possible then print «not possible» without double quote.

    Constraints:
    1 ≤ T ≤ 100
    1 ≤ n ≤ 100000


    Example:
    Input

    2
    143
    431


    Output
    314
    not possible

    Перевод
    Дано число n, найдите наименьшее число, которое имеет тот же набор цифр, что и n, и больше n. Если n — это и есть максимально возможное число с его набором цифр, то выведите “not possible”.

    Ввод:
    Первая строка входных данных содержит целое число T, обозначающее количество тестов.
    Первая строка каждого теста — n. n — это число.

    Вывод:
    Выведите большее число, чем n, с тем же набором цифр, и если это невозможно, то выведите «not possible».

    Ограничения:
    1 ≤ T ≤ 100
    1 ≤ n ≤ 100000


    Пример:
    Ввод

    2
    143
    431


    Вывод
    314
    not possible

    2. Coin Change
    Given a value N, find the number of ways to make change for N cents, if we have infinite supply of each of S = { S1, S2,…, Sm} valued coins. The order of coins doesn’t matter. For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

    Input:
    The first line contains an integer 'T' denoting the total number of test cases. In each test cases, the first line contains an integer 'M' denoting the size of array. The second line contains M space-separated integers A1, A2, ..., AN denoting the elements of the array. The third line contains an integer 'N' denoting the cents.

    Output:
    Print number of possible ways to make change for N cents.

    Constraints:
    1 ≤ T ≤ 50
    1 ≤ N ≤ 300
    1 ≤ A[i] ≤ 300


    Example:
    Input:

    2
    3
    1 2 3
    4
    4
    2 5 3 6
    10


    Output:
    4
    5


    Explanation:
    Testcase 1: The possiblities are as such: {1, 1, 1, 1}, {1, 1, 2}, {1, 3}, {2, 2}.

    Перевод
    Дано значение N, найдите количество способов разменять монету N, если у нас есть бесконечный набор каждой монеты таких номиналов S = { S1, S2, ...,., Sm}. Порядок монет не имеет значения. Например, для N = 4 и S = {1,2,3} существует четыре решения: {1,1,1,1},{1,1,2},{2,2},{1,3}. Так что вывести нужно 4. Для N = 10 и S = {2, 5, 3, 6}, существует пять решений: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} и {5,5}. Так вывести нужно 5.

    Ввод:
    Первая строка содержит целое число 'T', обозначающее общее количество тестов. В каждом тесте первая строка содержит целое число 'M', обозначающее размер массива. Вторая строка содержит M целых чисел, разделенных пробелами A1, A2,..., обозначающие элементы массива. Третья строка содержит целое число 'N', обозначающее сумму.

    Вывод:
    Выведите количество возможных способов размена суммы N.

    Ограничения:
    1 ≤ T ≤ 50
    1 ≤ N ≤ 300
    1 ≤ A [i] ≤ 300


    Пример:
    Ввод:

    2
    3
    1 2 3
    4
    4
    2 5 3 6
    10


    Вывод:
    4
    5


    Объяснение:
    Тест 1: возможности таковы: {1, 1, 1, 1}, {1, 1, 2}, {1, 3}, {2, 2}.

    3. Phone directory
    Given a list of contacts which exist in a phone directory and a query string str. The task is to implement search query for the phone directory. Run a search query for each prefix p of the query string str(i.e from index 1 to str length) that prints all the distinct recommended contacts which have the same prefix as our query (p) in lexicographical order. Please refer the explanation part for better understanding.

    NOTE: If there is no match between query and contacts, print «0».

    Input:
    The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains three lines. First line of each test case contains N i.e., number of contacts. Second line contains space separated all the contacts in the form of string. And third line contains query string.

    Output:
    For each test case, print each query result in new line. If there is no match between query and contacts, print «0».

    Constraints:
    1<=T<=100
    1<=N<=50
    1<=|contact[i].length|<=50
    1<=|query length|<=6


    Example:
    Input:

    1
    3
    spiceit spcicecite spiiceti
    spicpt


    Output:
    spiceit spcicecite spiiceti
    spiceit spcicecite spiiceti
    spiceit spiiceti
    spiceit
    0
    0


    Explanation:
    By running the query on contact list, we get,
    Suggestions based on "s" are:
    spiceit spcicecite spiiceti
    Suggestions based on "sp" are:
    spiceit spcicecite spiiceti
    Suggestions based on "spi" are:
    spiceit spiiceti
    Suggestions based on "spic" are:
    spiceit
    No Results Found for «spicp», So print «0».
    No Results Found for «spicpt», So print «0».

    Перевод
    Дан список контактов, которые есть в телефонном справочнике и строке запроса str. Задача состоит в том, чтобы реализовать поисковый запрос для телефонного справочника. Выполните поисковый запрос для каждого префикса p строки запроса str (т. е. от индекса 1 до длины str), который печатает все отдельные рекомендуемые контакты, имеющие тот же префикс, что и наш запрос (p) в лексикографическом порядке. Пожалуйста, обратитесь к пояснительной части для лучшего понимания.

    Примечание: если запрос и контакты не совпадают, выведите «0».

    Ввод:
    Первая строка входных данных содержит целое число T, обозначающее количество тестов. Затем следуют T тестов. Каждый тест содержит три строки. Первая строка каждого теста содержит N, т. е. количество контактов. Вторая строка содержит пробел, разделяющий все контакты в виде строки. А третья строка содержит строку запроса.

    Вывод:
    Для каждого теста выведите каждый результат запроса в новой строке. Если между запросом и контактами нет совпадения, выведите «0».

    Ограничения:
    1<=T<=100
    1<=N<=50
    1<=|contact[i].length|<=50
    1<=|длина запроса|<=6


    Пример:
    Ввод:

    1
    3
    spiceit spcicecite spiiceti
    spicpt


    Вывод:
    spiceit spcicecite spiiceti
    spiceit spcicecite spiiceti
    spiceit spiiceti
    spiceit
    0
    0


    Объяснение:
    Запустив запрос по списку контактов, мы получаем,
    Результаты поиска "s", таковы:
    spiceit spcicecite spiiceti
    Результаты поиска "sp", таковы:
    spiceit spcicecite spiiceti
    Результаты поиска "spi", таковы:
    spiceit spiiceti
    Результаты поиска "spic", таковы:
    spiceit
    Для «spicp» не найдено результатов, поэтому вывели «0».
    Для «spicpt» не найдено результатов, поэтому вывели «0».


    Ответы


    Вопрос 1
    Ответ: 25000 миль.
    Решение: нужно разделить срок службы запасного колеса на 4 равные части, т. е. 5000, и заменять его при каждом завершении дистанции в 5000 миль.

    Пусть четыре шины будут названы A, B, C и D, а запасная шина — S.

    5000 миль: заменить A на S. Остаток ресурса (A, B, C, D, S): 15000, 15000, 15000, 15000, 20000.
    10000 миль: верните A в исходное положение и замените B на S. Остаток ресурса (A, B, C, D, S): 15000, 10000, 10000, 10000, 15000.
    15000 миль: верните B в исходное положение и замените C на S. Остаток ресурса (A, B, C, D, S): 10000, 10000, 5000, 5000, 10000.
    20000 миль: верните C в исходное положение и замените D на S. Остаток ресурса (A, B, C, D, S): 5000, 5000, 5000, 0, 5000.
    25000 миль: каждая шина теперь полностью изношена.

    Вопрос 2
    Ответ: 16
    100% от задания = 18 дней
    Если он каждый день удваивает свой прогресс, то
    50% от задания = 17 дней
    25% от задания = 16 дней.

    Задача 1
    import java.io.*;
    
    class GFG {
    	public static void main (String[] args) {
    		//code
    		GFG gfg = new GFG();
    		int testCases, n, i;
    		String a;
    		char[] c;
    		Scanner sc = new Scanner(System.in);
    		
    		testCases = sc.nextInt();
    		
    		for(int t = 0; t < testCases; t++)
    		{
    		    a = sc.next();
    		    c = a.toCharArray();
    		    i = a.length() - 1;
    		    
    		    while(i > 0)
    		    {
    		        if(c[i-1] >= c[i])
    		        {
    		            i--;
    		        }
    		        else
    		        {
    		            break;
    		        }
    		    }
    		    
    		    if(i == 0)
    		    {
    		        System.out.println("not possible");
    		    }
    		    else
    		    {
    		        i--;
    		        
    		    
    		        int j = i + 1;
    		    
    		        for(int k = i + 2; k < a.length(); k++)
    		        {
    		            if(c[k] > c[i])
    		            {
    		                j = k;
    		            }
    		        }
    		        
    		        char v = c[i];
    		        c[i] = c[j];
    		        c[j] = v;
    		        i++;
    		        
    		        Arrays.sort(c, i, c.length);
    		    
    		    
    		    
    		    for(int k = 0; k < a.length(); k++)
    		    {
    		        System.out.print(c[k]);
    		    }
    		    System.out.println();		
    		        
    		    }
    		}
    		
    	}
    }

    Задача 2
    for _ in range(int(input())):
        n,ar,m=int(input()),list(map(int,input().split())),int(input())
        dp=[0]*(m+1)
        dp[0]=1
        for i in range(n):
            for j in range(ar[i],m+1):
                dp[j]+=dp[j-ar[i]]
        print(dp[m]) 

    Задача 3
    Идея состоит в том, чтобы использовать TRIE.
    Цикл для каждой подстроки, начиная с 0 до 1..n
    Поисковые предложения для этой подстроки.
    import java.util.*;
    import java.lang.*;
    import java.io.*;
    class trie
    {
      HashMap<Character,trie> child;;
      boolean isEnd;
      trie()
      {
        isEnd=false;
        child=new HashMap<>();
      }
      void add(String a,trie root)
      {
      trie cur=root;
      for (int i=0;i<a.length() ;++i ) {
        if(cur.child.containsKey(a.charAt(i)))
        cur=cur.child.get(a.charAt(i));
        else
        {cur.child.put(a.charAt(i),new trie());
          cur=cur.child.get(a.charAt(i));
        }
      }
      cur.isEnd=true;
      }
       void search(String a,trie root)
       {
         trie cur=root;
         for (int i=0; i<a.length();++i ) {
           char t=a.charAt(i);
           trie node=cur.child.get(t);
           if(node==null)
           {System.out.print("0");
         return;}
    
         cur=node;
         }
         print(cur,a);
       }
       void print(trie root,String prefix)
       {
           if(root.isEnd)
           {System.out.print(prefix+" ");
           }
         for(char i='a';i<='z';++i)
         {
           trie node=root.child.get(i);
           
           if(node!=null)
           print(node,prefix+i);
         }
       }
    }
    class phoneDict
     {
      static trie root;
      public static void fn(String a[],int n,String q)
      {
        for (String t :a ) {
          root.add(t,root);
        }
        for(int i=1;i<=q.length();++i)
        {root.search(q.substring(0,i),root);
          System.out.println();
        }
      }
     public static void main (String[] args)
      {
     Scanner ab=new Scanner(System.in);
     int t=ab.nextInt();
     while(t-->0)
     {
         root=new trie();
         int n=ab.nextInt();
         String arr[]=new String[n];
         for(int i=0;i<n;++i)
         arr[i]=ab.next();
          fn(arr,n,ab.next());
         //System.out.println();
     }
      }
    }
    Spice IT Recruitment
    ИТ-специализированное кадровое агентство
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 28

      0
      Каждый день он увеличивает свой прогресс в данном задании вдвое.

      В начале первого дня у него, естественно, 0%. За день он увеличивает прогресс вдвое. 0%×2=0%. И так далее.
      Хорошая ловушка.
        0
        Никакой ловушки. Он увеличивает прогресс вдвое, за предыдущий день, поэтому брать надо достигнутый прогресс на конец дня. А вообще тут не важно сколько он сделал за день…

        Ответ
        Считать надо с конца:
        18 дней: 100%
        17 дней: 100% / 2 = 50%
        16 дней: 50% / 2 = 25%
        Ответ: 16 дней
          0
          Он увеличивает прогресс вдвое, за предыдущий день…

          Именно так. Сколько он сделал за предыдущий первому? 0!
          …поэтому брать надо достигнутый прогресс на конец дня.

          Ага! Только этот фокус работает, если в первый день он сделал 100×2-18% всей работы. А этой информации в условии задачи нет.
          А вообще тут не важно сколько он сделал за день…

          Важно, с какой доли он начал. Если с нуля, то он никогда не кончит.
            0
            Именно так. Сколько он сделал за предыдущий первому? 0!

            С чего вы это взяли? По условию задачи он все таки делал какую-то работу и делал он ее с двукратным приростом, так что в 18-ый день он полностью (100%) ее закончил.
            Это (100%) опять же по условию задачи, ваш расчет (0%×2=0%) противоречит данному условию, оно бы никогда не выполнилось.

            Важно, с какой доли он начал. Если с нуля, то он никогда не кончит.

            Человеку дается задание...

            Логично предположить что начал он его с 0 и в первый день сделал какую то часть работы.
            Я не вижу здесь никакого подвоха…
              0
              Это (100%) опять же по условию задачи, ваш расчет (0%×2=0%) противоречит данному условию, оно бы никогда не выполнилось.

              Вот именно. Противоречивое условие задачи. Или каждый день вдвое, или задача выполнена на 100%.
              • НЛО прилетело и опубликовало эту надпись здесь
                  0
                  Убрать «каждый день».
                  С другой стороны, это же собеседование. Если испытуемый решил выпендриться, поговорить с ним. В том числе, попросить скорректировать условие задачи. Может быть он годится на что-то большее, чем «Чего изволите?».
                  • НЛО прилетело и опубликовало эту надпись здесь
                      0
                      Но про закономерность-то надо написать.
                      • НЛО прилетело и опубликовало эту надпись здесь
                          0
                          Здравствуйте! Давайте добавим такую оговорку про первый день, тогда условие задачи должно быть полным и не иметь противоречий:
                          Человеку дается задание. В первый день он выполняет некоторую часть задания. Каждый последующий день он увеличивает свой прогресс в данном задании вдвое. Если человек полностью выполняет задание за 18 дней, то сколько дней ему потребовалось, чтобы выполнить 25% задания?

                          Однако, в условии задачи сказано о том, что «человек полностью выполняет задание за 18 дней». Это значит, что все-таки такого случая, когда в первый день он выполнил 0% задания и каждый последующий день будет удваивать свой прогресс (0% х 2 = 0%) — быть не может.
                          • НЛО прилетело и опубликовало эту надпись здесь
                            0
                            Не будет, если сформулировать как-то так: выполнил за 18 дней, а за каждый предыдущий — в два раза меньше. Но тогда и задача исчезает.
                            • НЛО прилетело и опубликовало эту надпись здесь
          0
          1. Car Wheel Puzzle
          Ответ
          Меняя по очереди каждое колесо можно проехать 25000 миль.
          Посчитать можно например так: полный ресурс всех пяти колес делим на износ всех колеса-мест, получаем сколько будет износ на колесо-месте и умножаем на износ одной шины.
          (100000/80000)*20000=25000
          100000/80000=1,25 — эти 0,25 это то превышение нормального износа, через сколько надо менять очередное колесо (20000*0,25=5000)
          Какое-то замысловатое объяснение у меня получилось…
            0
            Все не так просто, поставьте в ваши рассуждения значение износа равное 10 миль. Нужно учитывать что вы «приехали», если любые 2 колеса достигли состояния износа.
              0
              Всё равно 1,25. Одно колесо достигнет износа через 20000, остальные ещё через 5000. Надо всего лишь чтобы каждое колесо проехало 5000 в багажнике.
                0
                Все нормально получается хоть с 10 милями:
                image
                Желтым — колесо в запасе. К концу пути все колеса имеют 100% износ.
                  0
                  Да, вы правы. У меня был другой ход мыслей (сильнее запутанный :) и я посчитал нулевую точку (милю)… невнимательность.
                  • НЛО прилетело и опубликовало эту надпись здесь
                      0
                      Нет, если проморгал, то максимум уже не получится. С другой стороны, если говорить о реальном мире, тогда вопрос: «Выйдет ли покрышка из строя проехав ровно свой ресурс?». Это риторический вопрос, предлагаю дальше не раздувать тему…
                      • НЛО прилетело и опубликовало эту надпись здесь
                          0
                          Что если менять колеса в два раза чаще? Решит ли это проблему водителя с пропуском очередной смены покрышек?

                          Это может уменьшить неоптимальность износа, все зависит от того, по какой причине он пропускает смену. Если у него, например, стоит какая то напоминалка и он одну из них пропустил, то минимизирует, а если он просто забыл, то это не поможет. Но если есть еще какой то запас, то после того как он вспомнил, он может скорректировать план по смене колес…
                          И можно еще придумать много если, и потом придумывать много сложных алгоритмов оптимизации, поэтому предлагаю лучше сделать все что бы не допустить такую забывчивость (а следовательно и не допустить усложнение кода, тестирование, потенциальные ошибки, трату ресурсов — мы же говорим о задачи для программиста). Сделаем напоминание и контроль за выполнением, а может и вообще сделаем замену колес за него.
                          P.S. Но это все таки уже другая задача…
                          • НЛО прилетело и опубликовало эту надпись здесь
                              0
                              Чувствую, я попал на собеседование… )
                              Нахождение алгоритмов задача программиста?

                              В том числе
                              задача найти алгоритм, с помощью которого можно корректировать поведение программы

                              Если ИИ знает какой ему предстоит путь и что он не сможет вовремя произвести замену, лучше сделать это заранее, тем самым он сможет скорректировать график замены позже, и «добить» недоезженный ресурс на более коротких отрезках пути.
                              По сути алгоритм тот же, необходимо тратить ресурс покрышек равномерно на всех, по очереди, период замены можно менять:
                              если не добили какой то из периодов и известно что потребуется проехать не больше чем этот остаток то:
                              добиваем этот период на тех же колесах, на которых недоездили тот период
                              в противном случае оставляем на потом и начинаем новый цикл:
                              до замены осталось = остаток ресурса покрышки с максимальном износом / 4
                              если произвели досрочную замену на первой итерации в цикле:
                              можно провести замены в цикле с той же периодичностью, что и эту
                              Таким образом недоезженные периоды будут все время уменьшаться, т.е. минимизироваться не оптимальный случай
                              • НЛО прилетело и опубликовало эту надпись здесь
                                • НЛО прилетело и опубликовало эту надпись здесь
                  • НЛО прилетело и опубликовало эту надпись здесь

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое