JuriMik
26 уровень
Харьков

Тестовое задания для Trainee

Пост из группы Архив info.javarush.ru
3745 участников
Вобщем-то простенькое тестовое задание на позицию Trainee Functional Developer, так сказать, для затравки. Я проходил собеседование 2 года назад, поэтому не думаю, что сделаю что-то страшное выложив задание. Link для ленивых неангличан. Заявки на конкурс принимаются до 08.02 до 01:00 по Киеву (Москва до 02:00). Если поддержите плюсиками - запилю бложик отдельно для тестовых задачек, их у меня есть предостаточно. Думаю, будет интересно. Свой вариант пока не выкладываю, дабы не сбивать ваш полет фантазии."> Himeg Torin Javin tonyloner
Комментарии (68)
  • популярные
  • новые
  • старые
Для того, что бы оставить комментарий вы должны авторизоваться
fatfaggy26 уровень, Киев
1 ноября 2017, 23:05
условие таково, что никаких вводных данных не требуется. поэтому, считаю, что мой вариант будет быстрее всего :)

public int findPalindrome() {
    return 906609;
}
ferasinka32 уровень, Санкт-Петербург
2 ноября 2017, 12:21
Не нужно использовать магические числа :)
private final int RESULT =906609;

public int findPalindrome() {
    return RESULT;
}
lichMax40 уровень, Санкт-Петербург
4 ноября 2017, 23:59
анти-паттерн, нужен коммент в коде для понимания
antonioplay35 уровень
12 февраля 2017, 13:37
public class Cat {
public static void main(String[] args) throws IOException {
BufferedReader r=new BufferedReader(new InputStreamReader(System.in));
int x=Integer.parseInt(r.readLine());
r.close();
for (int i=x;i>0;i--){
if (Check(i)) {
System.out.print(i);
break;
}
}

}
static boolean Check(int x){
String str=x+"";
for (int i=0;i<str.length()/2;i++) {
if (str.charAt(i) != str.charAt(str.length()-(i+1))) return false;
}
return true;
}

}
Javin7 уровень, Stockholm
11 февраля 2017, 11:50
Похоже, что не угасший интерес, а некие обстоятельства непреодолимой силы не позволили автору темы подвести итоги конкурса. Жаль!
Алгоритм уважаемого Himegа даёт, похоже, наибольшее быстродействие. Но лично для меня, к сожалению, он так и остался вне понимания.
Осталось загадкой и то, что никто пока не использовал возможности многопоточности. Хотя некоторые участники, предполагаю, разбираются и в ней. Почему же они не стали применять эту технологию? Ведь практически у всех в персональных компьютерах стоят многоядерные микропроцессоры и от параллельных вычислений, полагаю, можно получить прирост в быстродействии.
JuriMik26 уровень, Харьков
12 февраля 2017, 22:44
отсутствие свободного времени. В будни работа — на выходных в квартире одно повесить, другое прибить, третье перетянуть нужно :)
LuxTux37 уровень
9 февраля 2017, 01:08
Решение похоже на многие здесь, однако стоит обратить внимание на отрезки цикла. А именно: 1) поиск второго множителя начинается не с 999, а с i (если мы проверили 999 * 998, зачем проверять 998 * 999); 2) если мы нашли палиндром, то ни 1-му, ни 2-му множителю нет смысла опускаться ниже значения 2-го множителя палиндрома (для этого в ограничениях циклов используется переменная secondNumber).

Железо: Intel Pentium B950 2.1Ghz, 4 Gb RAM, Windows 7 Ultimate (ноут 5 лет). Время: 1-3 мс

public static void main(String[] args) {
        long start = new Date().getTime();
        int palindrome = 0;
        int firstNUmber = 0;
        int secondNumber = 100;
        for (int i = 999; i >= secondNumber; i--) {
            for (int j = i; j >= secondNumber; j--) {
                int temp = i * j;
                if (isPalindrome(temp) && temp > palindrome) {
                    palindrome = temp;
                    firstNUmber = i;
                    secondNumber = j;
                    break;
                }
            }
        }
        long timeSpent = new Date().getTime() - start;
        System.out.println("palindrome: " + palindrome + " (" + firstNUmber +" * " + secondNumber +
                "). Time spent = " + timeSpent + " ms.");
    }

    private static boolean isPalindrome (int numberToCheck) {
        int a = numberToCheck % 10;
        int b = (numberToCheck % 100) / 10;
        int c = (numberToCheck % 1000) / 100;
        return numberToCheck/1000 == a*100 + b*10 + c;
}
astraboomer22 уровень
8 февраля 2017, 11:12
Со своим результатом по быстродействию я, конечно, не пройду. Но умею искать макс. палиндромы размерностью от 3 до 18 (возвращает -1, если не укладывается в этот диапазон). Поиск 10-значного палиндрома у меня занимает 59с.
public static long MaxPolindrom(int bit){
        if (bit < 3 || bit > 18) return -1;
        long maxPoli =0;
        long start = (long) Math.pow(10, bit);
        int halfBit = bit / 2;
        long nBit = (long) Math.sqrt(start);
        long[] digits = new long[bit];

         l:for (long i = start - 1; i > 0; i--)
        {
            int symFlag = 0;

            for (int k = 0; k < digits.length; k++)
                digits[k] = (i % (long) Math.pow(10, k + 1)) / (long) Math.pow(10, k);

            for (int j = 0; j < halfBit; j++)
            {
                if (digits[j] == digits[bit - 1 - j])
                    symFlag++;
                else
                   continue l;
            }
            if (symFlag == halfBit)
            {
                for (long j = nBit - 1; j > 0; j--)
                {
                    if ((i % j) == 0 && i / j < nBit)
                    {
                        maxPoli = i;
                        return maxPoli;
                    }
                }
            }
        }
        return maxPoli;
    }
KnyazVova30 уровень, Днепр
7 февраля 2017, 20:33
public class StringLogic {

    public static void main(String[] args) {

        maxPolindrom(999);
    }


    public static void maxPolindrom(int i) {
        Long T = System.currentTimeMillis();
        boolean flag = false;
        int result;
        String tmp;
        StringBuilder str;
        result = i * i;
        int fortmp =0;
        do {
            result--;
            tmp = result + "";
            str = new StringBuilder(tmp);
            if (tmp.equals(str.reverse().toString())) {
                for (int z = 999; z > 100; z--) {
                    for (int z1 = 999; z1 > 100; z1--) {
                        fortmp = z * z1;
                        if (fortmp == result) {
                            System.out.println(z + " " + z1+" Result: "+result);
                            System.out.println(T = System.currentTimeMillis() - T);
                            flag = true;
                            return;
                        }
                    }
                }
            }
        }while (!flag) ;

            }
        }
Вот такое решение но у меня железо слабое — 180 мс показывает.
skylurker33 уровень
6 февраля 2017, 23:44
Пилите, Шура, пилите! Будет у нас тут свой явовский DailyProgrammer, с JavaDoc и дженериками.

Процесс поиска решения:

1. Ищем правильный ответ, чтобы было на чём проверять различные подходы. Одновременно это нечто вроде Proof of concept идеи под названием «Я могу это решить».
function isPalindrome(number){
	return number.toString().split('').reverse().join('') == number.toString();
}

// debugging
/*
console.log(isPalindrome(580085));
console.log(isPalindrome(8));
console.log(isPalindrome(2345));
*/

function getPalindrome(){
	var palindromes = [];
	for (var i = 999; i > 500; i--){
		for (var j = 999; j > 500; j--){
			if (isPalindrome(i * j))
				palindromes.push(i * j);
		}
	}

	// debugging
	// console.log(palindromes);

	return palindromes.sort().pop();
}

console.log(getPalindrome());


Получаем 906609.

2. Переводим с JS на Java, чтобы было грязное, но рабочее решение. 33ms.
isPalindrome(int number) преобразует число в строку и проверяет, является ли строка палиндромом.
getPalindrome() перебирает произведения трёхзначных чисел, отыскивает среди них палиндромы, заносит в список, после чего выбирает из списка максимальное значение.
public static boolean isPalindrome(int number){
    String s = String.valueOf(number);
    int slength = s.length();
    for (int i = 0; i < slength / 2; i++)
    {
        if (s.charAt(i) != s.charAt(slength - i - 1))
            return false;
    }
    return true;
}

public static void getPalindrome(){
    ArrayList<Integer> list = new ArrayList<Integer>();
    for (int i = 999; i > 500; i--)
    {
        for (int j = 999; j > 500; j--)
        {
            if (isPalindrome(i * j))
                list.add(i * j);
        }
Javin7 уровень, Stockholm
4 февраля 2017, 01:43
НА КОНКУРС. Номинация «Экстрим».
/**
 * ПОИСК НАИБОЛЬШЕГО ПАЛИНДРОМА ДЛЯ ПРОИЗВЕДЕНИЯ ТРЕХЗНАЧНЫХ ДЕСЯТИЧНЫХ ЧИСЕЛ
 * @author Javin
 */

public class maxPalindrome {

      public static void main(String[] args) {

        int palindrome = 0, a = 9, b = 9, c = 9, m = -1;

        long startTime = System.nanoTime();

        marker:
        for (; a > -1; a--) {

            for (; b > -1 ; b--) {

                for (; c > -1; c--) {

                    palindrome =  100001 * a + 10010 * b + 1100 * c; // abccba

                    for (int j = 999; j >= 500 ; j--) {              // см. Примечание

                        if (palindrome % j == 0 &&  palindrome / j <= 999) {
                            m = j;
                            break marker;
                        }

                    }

                }

                c = 9;
            }

            b = 9;

        }

        long timeSpent = System.nanoTime();

        System.out.println("Наибольший палиндром для произведения трёхзначных десятичных чисел: "+ m +
                " * " + palindrome / m + " = " + palindrome);
        System.out.printf("\nВремя поиска палиндрома составило: %d наносекунд\n", timeSpent - startTime );

    }
}

Intel Core i7-2600 CPU @ 3.4 GHz x 4, RAM 16 GB, Linux

Наибольший палиндром для произведения 3-значных десятичных чисел: 993 * 913 = 906609

Время поиска палиндрома составило: 563039 наносекунд

Примечание
Пусть для палиндрома 178871 найдено одно из трехзначных чисел 707, то второе вычисляется как 178871 / 707 = 253. И после отыскания числа в диапазоне от 999 до 500 уже не имеет смысл поиск другого числа, т. е. 253, в диапазоне от 100 до 499, так оно элементарно вычисляется.
tonyloner37 уровень, Москва
3 февраля 2017, 16:36
public class Palindrome {
    public static void main(String[] args) {
        long startTime = new Date().getTime();
        int result = 0;
        int num1 = 0;
        int num2 = 0;
        for(int i = 999; i >= 100; i--) {
            for(int j = i; j >= 100; j--) {
                int value = i*j;
                if(value < result) {
                    break;
                }
                if(isPalindrome(value)) {
                    result = value;
                    num1 = i;
                    num2 = j;
                    break;
                }
            }
        }
        System.out.println("Result: " + result + " = " + num1 + "x" + num2);
        System.out.println("Time: " + (new Date().getTime() - startTime) + "ms");
    }

    public static boolean isPalindrome(int value) {
        int a = value % 10;
        int b = (value % 100) / 10;
        int c = (value % 1000) / 100;
        if (value/1000 == a*100 + b*10 + c)
            return true;
        return false;
    }
}


Result: 906609 = 993x913
Time: 1ms
Intel® Core(TM) i3 CPU @ 2.93GHz, RAM 8 GB, Linux
JuriMik26 уровень, Харьков
3 февраля 2017, 21:21
Неплохо. Я похожее решение высылал.
Torin27 уровень
4 февраля 2017, 01:51
Пффф. Я глянул на это решение, затем на свое. Заменил это

int b = (i % 100) / 10;
        int c = (i % 1000) / 100;
        int tempNum1 = i / 1000;
        int tempNum2 = a * 100 + (b * 10) + c;
        if (tempNum1 == tempNum2) {
            return true;
        } else {
            return false;
        }


На вот это

int b = (i % 100) / 10;
        int c = (i % 1000) / 100;
        if (i / 1000 == a * 100 + (b * 10) + c) {
            return true;
        } else {
            return false;
        }


и получил 0-4 мс! инициализация переменных столько жрет??!
Torin27 уровень
4 февраля 2017, 01:55
Или вообще так, почти всегда 0 мс:

public static boolean isPalindrome(int i) {
        if (i / 1000 == (i % 10) * 100 + ((i % 100) / 10 * 10) + (i % 1000) / 100) {
            return true;
        } else {
            return false;
        }
    }
imp31 уровень, Москва
4 февраля 2017, 14:01
а вот это очень интересный момент, в наносекундах тестил?
Torin27 уровень
4 февраля 2017, 17:55
на моем ноуте не имеет смысла. Протестил 15 раз, в итоге разброс от 0 до 15 мс
Javin7 уровень, Stockholm
2 февраля 2017, 18:26
НА КОНКУРС

/**
 * ПОИСК НАИБОЛЬШЕГО ПАЛИНДРОМА ДЛЯ ПРОИЗВЕДЕНИЯ ТРЕХЗНАЧНЫХ ДЕСЯТИЧНЫХ ЧИСЕЛ
 * @author Javin
 */

public class maxPalindrome {

    public static final int NUMBER_OF_DECIMAL_SIGN = 3; //начиная с 5 десятичных знаков, переменная
                                                        //palindrome станет больше Integer.MAX_VALUE
                                                        //и произойдет аварийное завершение программы

    public static void main(String[] args) {

        int palindrome, maxNumberOfDecimalSign, minNumberOfDecimalSign, centralNumber;
        StringBuilder builder = new StringBuilder();
        StringBuilder builderRevers = new StringBuilder();

/*Добавлено для универсальности кода при иных значениях NUMBER_OF_DECIMAL_SIGN*/

        for (int i = 1; i <= NUMBER_OF_DECIMAL_SIGN; i++) {                                 // "999"
            builder.append(9);
        }

        maxNumberOfDecimalSign = Integer.parseInt(builder.toString());                      // 999
        centralNumber = maxNumberOfDecimalSign/2 + 1;                                  // 500 см.Примеч.

        builder.delete(0, NUMBER_OF_DECIMAL_SIGN);

        builder.append(1); // "1"

        for (int i = 1; i <= NUMBER_OF_DECIMAL_SIGN - 1; i++) {                             // "100"
            builder.append(0);
        }

        minNumberOfDecimalSign = Integer.parseInt(builder.toString());                     // 100
        builder.delete(0, NUMBER_OF_DECIMAL_SIGN);

/*Основная часть*/
        long startTime = System.nanoTime();

        marker:
        for (int i = maxNumberOfDecimalSign; i >= minNumberOfDecimalSign ; i--) {          // 999; 100

            builder.append(i);                                                             // "987"
            builder.append(builderRevers.append(i).reverse());                             // "987789&