Привет! Мы снова подготовили Вам подборку интересных вопросов и задачек с собеседований в ведущие IT-компании!
![](https://habrastorage.org/r/w1560/webt/gb/xj/ul/gbxjuldvtuid-ptlc_qift9a6he.png)
Выпуски будут появляться каждую неделю — следите за обновлениями! Рубрика выходит при поддержке рекрутингового агентства Spice IT.
На этой неделе мы собрали задачи с собеседований в индийскую компанию Snapdeal. Кстати, ответы на задачки из прошлого выпуска уже опубликованы.
1. Car Wheel Puzzle
2. Completion of Task
1. Next greater number set digits
2. Coin Change
3. Phone directory
![](https://habrastorage.org/webt/gb/xj/ul/gbxjuldvtuid-ptlc_qift9a6he.png)
Выпуски будут появляться каждую неделю — следите за обновлениями! Рубрика выходит при поддержке рекрутингового агентства 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».
Ограничения:
Пример:
Ввод
Вывод
Ввод:
Первая строка входных данных содержит целое число 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: возможности таковы: {1, 1, 1, 1}, {1, 1, 2}, {1, 3}, {2, 2}.
Ввод:
Первая строка содержит целое число '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».
Ограничения:
Пример:
Ввод:
Вывод:
Объяснение:
Запустив запрос по списку контактов, мы получаем,
Результаты поиска "s", таковы:
Результаты поиска "sp", таковы:
Результаты поиска "spi", таковы:
Результаты поиска "spic", таковы:
Для «spicp» не найдено результатов, поэтому вывели «0».
Для «spicpt» не найдено результатов, поэтому вывели «0».
Примечание: если запрос и контакты не совпадают, выведите «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 миль: каждая шина теперь полностью изношена.
Решение: нужно разделить срок службы запасного колеса на 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 дней.
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
Поисковые предложения для этой подстроки.
Цикл для каждой подстроки, начиная с 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();
}
}
}