• ,

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

Вобщем-то простенькое тестовое задание на позицию Trainee Functional Developer, так сказать, для затравки. Я проходил собеседование 2 года назад, поэтому не думаю, что сделаю что-то страшное выложив задание.
]На выполнение отводился час (с рефакторингом, это обязательное условие).
Обязательно отпимизируйте код программы, но так, чтобы это не заняло много времени.
Оцениваться будет не только ответ, но и способ решения, и количество итераций для нахождения правильного решения.

Вобщем-то, у меня время вышло в 1мс (по количеству итераций я уже не помню) и это довольно просто сделать. Интереснее было оптимизировать алгоритм. Это заняло у меня 3/4 от времени выполнения. На собеседование в офис я попал, но не справился со вторым тестовым заданием во время.

Итак, само задание:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 х 99.

Find the largest palindrome made from the product of two 3-digit numbers.


Link для ленивых неангличан.

Заявки на конкурс принимаются до 08.02 до 01:00 по Киеву (Москва до 02:00).

Если поддержите плюсиками — запилю бложик отдельно для тестовых задачек, их у меня есть предостаточно. Думаю, будет интересно.

Свой вариант пока не выкладываю, дабы не сбивать ваш полет фантазии.">

Himeg
Torin
Javin
tonyloner

65 комментариев

maximuswork
Заводи свой блог. Такие вещи нужны для того, чтобы включить мозг. Хоть пока и не решил данную задачу.
imp
  • imp
  • +6
обязательно пили блог.
очень нужная вещь, думаю все джаворашовцы поддержат.
Himeg
Ну, в общем, вот:
public class PalindromicNumbers
{
    private static int candidate = 997799;

    public static void main(String[] args) throws Exception
    {
        long T = System.currentTimeMillis();
        int palindrome = 0;
        int first = 0;
        int second = 0;
        int start, step;
        int temp;
        while (palindrome == 0 && candidate > 99999)
        {
            if (candidate % 10 == 0)
            {
                start = 990;
                step = 10;
            }
            else if (candidate % 5 == 0)
            {
                start = 995;
                step = 5;
            }
            else if (candidate % 2 == 0)
            {
                start = 998;
                step = 2;
            }
            else
            {
                start = 999;
                step = 2;
            }

            for (int i = start; i >= Math.sqrt(candidate); i = i - step)
            {
                temp = candidate / i;
                if ((temp > 999)||(temp < 100)) break;
                if (candidate % i == 0)
                {
                    first = i;
                    second = candidate / i;
                    palindrome = candidate;
                    break;
                }
            }
            nextCandidate();
        }
        System.out.println(first + " times " + second + " equals " + palindrome);
        T = System.currentTimeMillis() - T;
        System.out.println(T + " ms wasted");
    }

    private static void nextCandidate()
    {
        if ((candidate - (candidate % 10)) % 100000 == 0) candidate = candidate - 11;
        else if ((candidate - (candidate % 100)) % 10000 == 0) candidate = candidate - 110;
        else candidate = candidate - 1100;
    }
}
Torin
а выхлоп какой? сколько мс на каком железе? и какое результативное число?
imp
результативное число для данной задачи — 906609
Torin
странно, а множители точно 3-х значные?
JuriMik
всё правильно
Himeg
  • Himeg
  • 0
  • Комментарий отредактирован 2017-02-01 14:41:29 пользователем Himeg
Ответ 906609. 0-1 мс на I7 8GB.
imp
  • imp
  • 0
  • Комментарий отредактирован 2017-02-01 14:04:12 пользователем imp
прокомментируйте алгоритм? :)
потестил ваш алгоритм, когда поставил candidate = 9999999;
алгоритм выдал 898896… то есть с нечетными числами он работать не умеет?
Himeg
Сначала у меня был вариант с перебором произведений чисел от 999 до 100 с нахождением максимального произведения и максимальной пары делителей. Ещё был метод isPalindrome. В нем на входе был int, далее он преобразовывался в строку, далее создавалась отраженная копия этой строки и если оригинал и копия были идентичны, то метод считал, что число является палиндромом. Но потом я все переделал, так как нашёл другой вариант, как мне показалось, более изящный и эффективный.

Итак, суть кода сводится к тому, что мы не множим трехзначные числа в попытках найти максимальный палиндром, а, наоборот, перебираем все палиндромы от 999999 до 100001 и проверяем, делится ли очередной палиндром на любое целое число от 100 до 999. Этим и занимается цикл while (palindrome == 0 && candidate > 99999).

Дополнительно, написан метод nextCandidate, который записывает в статическое поле candidate класса PalindromicNumbers очередной палиндром. Изначальное значение поля 997799, поскольку это ближайший палиндром к произведению 999*999. Метод nextCandidate не руководствуется ничем, кроме арифметики, и суть алгоритма сводится к следующему:

1. If ((candidate — (candidate % 10)) % 100000 == 0) candidate = candidate — 11;
если разность candidate и остатка от деления candidate на 10 делится на 100000 (это будут все шестизначные числа вида A0000F), то вычитаем из candidate 11. Пример: 900009. Вычитаем остаток от деления этого числа на 10 из этого же числа. Получаем 900009 — 9 = 900000, делится на 100000 без остатка, следовательно, 900009 — 11 = 899998.

2. Действует по тому же принципу, только для чисел вида AB00EF. Делим на 100, вычитаем из текущего числа и проверяем, делится ли результат на 10000. Если да, то пример: (990099 — 990099%100)%10000 = 0 => чтобы получить следущего кандидата в палиндромы, из 990099 (и любого такого числа) вычитаем 110. Получаем 899998.

3. И, наконец, ABCDEF. Нетрудно догадаться, что если ни одна из цифр числа не равна нулю, то, чтобы получить следующий палиндром, нужно из текущего вычесть 1100. Пример: 997799 — 1100 = 996699 => 995599 => 994499 и т.п.

В конечном итоге, код обрел дополнительные проверки для исключения бессмысленных итераций. Так, например, если кандидат в палиндромы делится на 10, то не имеет смысла проверять множители, не делящиеся на 10. То же с 5, один из множителей в любом случае будет кратен 5, поэтому итерация в цикле for проходит с шагом 5. В остальных случаях проверяется, четное число или нет, шаг 2. Для каждого варианта также устанавливается стартовый множитель. Ну и в самом цикле for не берутся в расчет все результаты деления кандидата в палиндромы на i, которые больше 1000 и меньше 100.

Дополнительно, минимальное значение, которое может принимать переменная i, ограничена квадратным корнем из кандидата в палиндромы: нет смысла проверять по два раза одни и те же множители.
Himeg
  • Himeg
  • 0
  • Комментарий отредактирован 2017-02-01 14:57:25 пользователем Himeg
Алгоритм не умеет работать с семизначными палиндромами, так как максимальное произведение двух трехзначных, по условию задачи, чисел не может иметь больше шести цифр.

PS хотя, можно переписать его так, чтобы пользователь вводил количество знаков у множителя. Но это будет уже решение в общем виде, т. е. немного другая задача. Сегодня вечером попробую)
imp
все равно подход отличный :)
а не считали насколько он сократил количество поиска по сравнению с обычным перебором?
Himeg
  • Himeg
  • 0
  • Комментарий отредактирован 2017-02-01 16:15:09 пользователем Himeg
Неа… только по времени можно оценить: обычный перебор выполнялся 5 мс против 0-1 мс у текущего варианта. Хотя, это в большей степени от метода зависит, потому что арифметическая проверка палиндрома гораздо эффективнее, чем разворот строки.
shcho_isle
  • shcho_isle
  • 0
  • Комментарий отредактирован 2017-02-06 10:59:00 пользователем shcho_isle
У меня способ который перебирает множители занял 7659 итераций.
А способ от Himeg: 1104 итерации.
Torin
  • Torin
  • 0
  • Комментарий отредактирован 2017-02-01 11:53:35 пользователем Torin
Плюсую, ждем блога!
И для всех участвующих — не смотрите чужие решения! это в наших же интересах сначала решить по своему, выложить код, а потом ознакомиться с другими решениями.

JuriMik , ты писал что это тестовое задание, а где ты его выполнял? дома или непосредственно в компании? за компом или на бумаге? :) и если за компом, то следили ли за процессом написания, или ты просто выкатил свой результат?
Torin
  • Torin
  • 0
  • Комментарий отредактирован 2017-02-01 13:32:47 пользователем Torin
Да и еще, было бы неплохо назвать валидный максимальный палиндром, что бы было на что ровняться. Просто число, которые мы должны получить. Например у меня получился 580085. Честно говоря. не ожидал что задание вызовет у меня затруднения. Может конечно дело в том что я делаю его на работе, одним глазом работая, другим набирая код… но в любом случае, почувствовал себя слабым в некоторых местах, хм.
imp
должно быть 906609
Torin
опачки :D
JuriMik
Выполнял дома, за мной никто не следил. Просто в письме написал потрачено времени на решение столько-то, на рефакторинг столько-то.
И да, правильно 906609 ;)
Torin
так-с, ладно. Тогда буду думать дальше
Javin
Если поддержите плюсиками — запилю бложик отдельно для тестовых задачек, их у меня есть предостаточно. Думаю, будет интересно.
JuriMik , неплохая идея. Однако, если такой блог создавать на местной площадке, то неплохо было бы узнать мнение на этот счёт и её собственников: ведь если не будет стыковки с учебным материалом по уровням сложности, то такой блог, полагаю, даже сократит количество начинающих на этом ресурсе.

Может создадите отдельную тему для всестороннего обсуждения Вашего предложения по блогу? Думаю, что у многих найдутся дельные предложения. «Что быстро рождается, то быстро и умирает», и примеров подобных начатых блогов в Интернете и брошенных — превеликое множество…
JuriMik
  • JuriMik
  • 0
  • Комментарий отредактирован 2017-02-01 14:36:59 пользователем JuriMik
А можно еще создать отдельную тему для для всестороннего обсуждения темы про всестороннее обсуждение темы моего предложения по блогу :-D
Я не вижу причин оттока обучающихся из-за разбора двух-трёх задачек с тестовых заданий от IT-компаний в месяц.
Torin
Я бы заподозрил приток обучающихся благодаря наличию тестовых заданий. По сути JuriMik с позиции опыта занимается благотворительностью. Он получил этот опыт в боях и фейспалмах, а мы имеем возможность в тепличной обстановке провести тестдрайв реальных задач
Javin
Привык мыслить масштабно :), с чем и попадаю часто впросак. Раз такие очень скромные планы, то налёта элитарности у этого ресурса, думаю, не появится, и Torin, пожалуй, прав в том, что можно ожидать даже приток новичков, интересующихся реальными тестовыми заданиями при приёме на работу.
JuriMik
лол, что значит «Масштабно»?
Javin
Масштабно — большими размерами и количеством. Т.е. почти как Собакевич из «Мертвых душ» у Гоголя:«У меня когда свинина — всю свинью давай на стол, баранина — всего барана тащи, гусь — всего гуся!». О мере и скромности часто забываю в жизни, а от этого часто и страдаю.
JuriMik
ну ок.
Torin
А я не совсем понял про элитарность. Если я правильно понимаю это слово, то оно подразумевает узкий Круг людей, объединенных определенными привелегиями и обладающих закрытостью. Эта концепция не вяжется с

А)
Привык мыслить масштабно

Б) концепцией монетизации курсов, где выгодно именно большое кол-во обучающихся и максимальная доступность курсов.

Исходя из данных соображений, я бы отнес к элитарности людей, уже устроившихся работать по нашему направлению, ибо они обладают всеми описанными качествами:

1) их действительно мало тут.
2) их по сути ничего тут уже не держит. Обычно люди, получив Профит идут дальше, это как школа — всего лишь этап.
3) обладают тем, чего нет у большинства учащихся тут — работой по профилю.

Мое мнение «масштабное» — личные достижения человека определяют его элитарность и круг общения. Как-то так.
Javin
Узость элитарного круга компенсируется широтой знаний его участников.
Roman_kh
  • Roman_kh
  • 0
  • Комментарий отредактирован 2017-02-01 13:51:02 пользователем Roman_kh
Классная идея с блогом для тестовых задач. У меня тоже есть одна. У тебя не хвататет рейтинга для блога. Я могу создать блог, будешь там модератором
JuriMik
  • JuriMik
  • +1
  • Комментарий отредактирован 2017-02-01 14:54:25 пользователем JuriMik
Не стоит. Я лучше в твой блог по паттернам пару статеек закину. Есть что сказать )
Можешь там модера дать, ты вроде ищещь?
Roman_kh
да, могу вполне. Напиши мне в ЛС когда нужно будет — сделаю.
А вот круче было бы сделать отдельный блог для тестовых заданий! Давай сделаем!
Torin
Если я правильно понял задание, нужно найти максимальный палиндром, образованный перемножением двух трехзначных чисел, по аналогии с:

9009 = 91 х 99.

Я выкатываю первую версию своего кода, однако оставляю за собой право на правки до 08.02.
Но если вдруг окажется, что все норм, то #на_конкурс.

import shine.sol.*;
import java.util.*;

class Main{
    static final int MAX_VALUE = 999;
    static int num1 = MAX_VALUE;
    static int num2 = MAX_VALUE;
    static boolean switcher = false;
    static String maxPalindrome;
    
    public static void main(String[] args){
        long st = System.currentTimeMillis();
        findPalindrome();
        long delta = System.currentTimeMillis() - st;
        System.out.println("Числовой палиндром: " + maxPalindrome + " = " + num1 + " x " + num2);
        System.out.println("Времени затрачено: " + delta + " мс");
    }
    
    public static void findPalindrome() {       
        for (num1 = Main.MAX_VALUE; num1 > 100; num1--) {
            for (num2 = Main.MAX_VALUE; num2 > 100; num2--) {
                int tmp = num1 * num2;                
                if (tmp < 100000) {
                    break;
                }
                if (isPalindrome(tmp)) {                    
                    return;
                }
            }            
        }
    }
    
    public static boolean isPalindrome(int i) {
        String initial = Integer.toString(i);        
        String p1 = initial.substring(0, initial.length() / 2);
        StringBuilder p2 = new StringBuilder();        
        for (int ii = initial.length() - 1; ii > initial.length() / 2 - 1; ii--) {
            p2.append(initial.charAt(ii));
        }        
        if (p1.equals(p2.toString())) {            
            maxPalindrome = initial;            
            return true;
        } else {
            return false;
        }
    }
    
}


intel core i5 6200U @ 2.30 Ghz (ноут)

2-5 мс.

Вывод:

Torin
Это не я писал, это уборщица пока меня не было за компом наговнокодила. Исправляю.....
Torin
  • Torin
  • +1
  • Комментарий отредактирован 2017-02-01 18:02:05 пользователем Torin
Есть большие подозрения, что по скорости я не выиграю, но по крайней мере за этот код мне уже не стыдно.
#НА_КОНКУРС_v_2

class Main{
    
    static int num1 = 999;
    static int num2 = 999;
    static boolean switcher = false;
    static int maxPalindrome;
    static int n1;
    static int n2;    
    
    public static void main(String[] args){
        long st = System.currentTimeMillis();
        findPalindrome();
        long delta = System.currentTimeMillis() - st;
        System.out.println("Числовой палиндром: " + maxPalindrome + " = " + n1 + " x " + n2);
        System.out.println("Времени затрачено: " + delta + " мс");
    }
    
    public static void findPalindrome() {       
        for (num1 = 999; num1 > 100; num1--) {
            for (num2 = 999; num2 > 100; num2--) {               
                int tmp = num1 * num2;                 
                if (isPalindrome(tmp)) {
                    if (maxPalindrome < tmp) {
                        maxPalindrome = tmp;
                        n1 = num1;
                        n2 = num2;
                    }
                }                
            }            
        }
    }
    
    public static boolean isPalindrome(int i) {
        int a = i % 10;
        if (a == 0) {
            return false;
        }        
        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;
        }
    }    
}


intel core i5 6200U @ 2.30 Ghz (ноут)

7 мс.
Himeg
int a = i % 10;
        if (a == 0) {
            return false;
        }  
Вот логично, кстати. Жаль, что я до этого не додумался.
Torin
Экономия на самом деле копеечная. Я еще немного подумаю, а потом начну вникать в твой алгоритм. Судя по всему ты к успеху пришел:)
Himeg
Экономия да, но дело не в ней, а в лишней проверке. Код мог бы бы быть как минимум компактнее, следовательно, читабельнее. К тому же, до 8 числа еще вагон времени. Придут люди с алгоритмом Манакера и капец)))))
Java-boy
Написал свой алгоритм. В итоге он оказался почти таким-же как твой :<
Только вот количество итераций как по мне все таки великовато.
Буду думать дальше)
Torin
У дураков мысли сходятся :D
imp
  • imp
  • 0
интересно, что напишет ТС про то как он делал тест и что от него ждали )

с одной стороны был явный намек на интерес к умению рефакторинга, с другой стороны вполне могли ждать реализации алгоритма Манакера, но его надо знать =\
JuriMik
  • JuriMik
  • 0
  • Комментарий отредактирован 2017-02-01 20:27:50 пользователем JuriMik
Так я ж написал. Основное требование — это минимальное количество итераций. И, соответственно, время работы.

Указанный тобой алгоритм мне кажется сюда не очень подходит ;-)
imp
поэтому и хочется посмотреть, как решал ты :)
Javin
Вывод в консоль количество произведенных итераций делать?
JuriMik
я не делал, смысла нет. Это можно оценить, когда видишь код
Torin
  • Torin
  • 0
  • Комментарий отредактирован 2017-02-02 10:23:19 пользователем Torin
Вот появилась мысль, но не пойму насколько она легитимна :) мысль из серии хитрожопости:

В моем решении слишком много вычислений проводится в методе findPalindrome(). Мне кажется сам процесс перебора и умножения мало относится к задаче «найти наибольший палиндром». Можно ли вычисления сделать предварительными? я могу загнать данные в TreeMap с ключем равным произведению, которое будет записано в стринге (которую потом просто распарсю). Таким образом палиндром будет проверяться по ключам TreeMap. Я не знаю насколько быстро происходит изъятие из TreeMap, но я бы избавился от вложенного цикла и от операции умножения. Я думаю это окупится процентов на 150%
Torin
  • Torin
  • 0
  • Комментарий отредактирован 2017-02-02 11:42:28 пользователем Torin
Я думаю это окупится процентов на 150%
Ошибался. Конечно findPalindrome() теперь отрабатывает за 1 мс:

public static void findPalindrome() {       
        for (Map.Entry<Integer, String> entry : results.entrySet()) {
            int key = entry.getKey();
            if (isPalindrome(key)) {
                String[] pairNums = entry.getValue().split("x");                
                n1 = Integer.parseInt(pairNums[0]);
                n2 = Integer.parseInt(pairNums[1]);
                maxPalindrome = key;
                break;
            }
        }
    }


Но на заполнение карты тратится 713 мс

static {
        long a = System.currentTimeMillis();
        for (num1 = 999; num1 > 100; num1--) {
            for (num2 = 999; num2 > 100; num2--) {
                results.put(num1 * num2, Integer.toString(num1) + "x" + Integer.toString(num2));
            }
        }
        long r = System.currentTimeMillis() - a;
        System.out.println("Map Заполняется за " + r + " мс.");
    }


Вообще не кошерно, даже чувствуется притормаживание перед выводом в консоль :(

ЗЫ блин как же не удобно без спойлеров! так бы код можно было под спойлер засунуть, а из-за их отсутствия растягивается на 100 метров…
rembrand87
  • rembrand87
  • 0
  • Комментарий отредактирован 2017-02-02 13:25:54 пользователем rembrand87
НЛО прилетело и опубликовало эту надпись здесь
Torin
не работал? )) я так подозреваю 580085? ))
rembrand87
Ага )))
Уже потом посмотрел, как кто реализовал и дошло.
Javin
  • Javin
  • +1
  • Комментарий отредактирован 2017-02-02 18:26:26 пользователем Javin
НА КОНКУРС

/**
 * ПОИСК НАИБОЛЬШЕГО ПАЛИНДРОМА ДЛЯ ПРОИЗВЕДЕНИЯ ТРЕХЗНАЧНЫХ ДЕСЯТИЧНЫХ ЧИСЕЛ
 * @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"

            palindrome = Integer.parseInt(builder.toString());                             // 987789

            builderRevers.delete(0, NUMBER_OF_DECIMAL_SIGN);                               // полная очистка
            builder.delete(0, NUMBER_OF_DECIMAL_SIGN * 2);                                 // полная очистка

            for (int j = maxNumberOfDecimalSign; j >= centralNumber ; j--) {               // 999; 500

                if (palindrome % j == 0 &&  palindrome / j <= maxNumberOfDecimalSign) {
                    System.out.println("Наибольший палиндром для произведения " + NUMBER_OF_DECIMAL_SIGN +
                            "-значных десятичных чисел: "+ j + " * " + palindrome / j + " = " + palindrome);
                    break marker;
                }
            }

        }

        long timeSpent = System.nanoTime();

        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

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

Примечание
Пусть для палиндрома 178871 найдено одно из трехзначных чисел 707, то второе вычисляется как 178871 / 707 = 253. И после отыскания числа в диапазоне от 999 до 500 уже не имеет смысл поиск другого числа, т. е. 253, в диапазоне от 100 до 499, так оно элементарно вычисляется. Поэтому centralNumber = maxNumberOfDecimalSign/2 + 1, и в нашем случае равно 500.

P.S.
Буду благодарен за конструктивную критику моего кода, ведь я здесь, чтобы учиться.

P.S.S.
Теперь же с интересом ознакомлюсь с чужими вариантами решения задачи.
tonyloner
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
JuriMik
  • JuriMik
  • 0
  • Комментарий отредактирован 2017-02-03 21:21:53 пользователем JuriMik
Неплохо. Я похожее решение высылал.
Torin
Пффф. Я глянул на это решение, затем на свое. Заменил это

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 мс! инициализация переменных столько жрет??!
Torin
Или вообще так, почти всегда 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;
        }
    }
imp
а вот это очень интересный момент, в наносекундах тестил?
Torin
на моем ноуте не имеет смысла. Протестил 15 раз, в итоге разброс от 0 до 15 мс
Javin
НА КОНКУРС. Номинация «Экстрим».

/**
 * ПОИСК НАИБОЛЬШЕГО ПАЛИНДРОМА ДЛЯ ПРОИЗВЕДЕНИЯ ТРЕХЗНАЧНЫХ ДЕСЯТИЧНЫХ ЧИСЕЛ
 * @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, так оно элементарно вычисляется.
skylurker
Пилите, Шура, пилите! Будет у нас тут свой явовский 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);
            }
        }

        System.out.println(Collections.max(list));
    }


3. Убираем список, он не нужен. 24ms.

    public static void getPalindrome2(){
        int max = 0;

        for (int i = 999; i > 500; i--)
        {
            for (int j = 999; j > 500; j--)
            {
                if (isPalindrome(i * j) && (i * j > max) )
                    max = i * j;
            }
        }
        System.out.println(max);
    }


4. Пробуем другой подход. 3ms.
Генерируем палиндромы.
Самое большое число, получающееся при умножении двух трёхзначных чисел, есть
999 * 999 = 998001
Следовательно, самое большое число-палиндром из рассматриваемых нами — это 997799.
String number = new StringBuilder().append(i).reverse().insert(0, i).toString();

Берём 997 (append i), разворачиваем (reverse) — получили 799, вставляем перед ним 997 (insert).
Проверяем, является ли данный палиндром требуемым произведением (isDivisible()).


    /* If the given number is a product of two 3-digit numbers */
    public static boolean isDivisible(int number){
        for (int i = 999; i > 99; i--)
        {
            if ( (number % i == 0) && ( number / i > 99 ) && ( number / i < 999 ))
            {
               // System.out.println("number: " + number + " i: " + i + " number/i: " + number/i);
                return true;
            }
        }
        return false;
    }

    // 999 * 999 = 998001 => start search with 997799

    public static void getPalindrome3(){

        for (int i = 997; i > 500 ; i--)
        {
            String number = new StringBuilder().append(i).reverse().insert(0, i).toString();

            if (isDivisible(Integer.parseInt(number))) {
                System.out.println(number + " is divisible");
                return;
            }
        }
    }


Добились улучшения производительности примерно на один порядок.

5. Смотрим чужие решения.
а) Замена внутреннего цикла в первых двух (js не считаем) способах на
for (int j = i; j > 500; j--)

(вариант tonyloner ) снижает время выполнения приблизительно на 10ms.
б) Замена метода isPalindrome на его же вариант снижает время работы примерно на 23 и 17ms соответственно.
в) Замена обоих даёт результаты примерно в 7 и 5ms против 33 и 24ms соответственно.

Мне понравился вариант Javin (Номинация «Экстрим»), хотя вечером «под пиво» его читать сложнее, чем остальные. Которые я обязательно прочитаю. Вдумчиво. Завтра.

P.S. main, просто на всякий:

    public static void main(String[] args)
    {
        long startTime = System.currentTimeMillis();
        getPalindrome();
        long endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime + " ms");

        startTime = System.currentTimeMillis();
        getPalindrome2();
        endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime + " ms");

        startTime = System.currentTimeMillis();
        getPalindrome3();
        endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime + " ms");
        
    }

Характеристики железа не даю, так как мне интересны не конкретные значения времени работы, а их приблизительные соотношения.
KnyazVova
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 мс показывает.
astraboomer
Со своим результатом по быстродействию я, конечно, не пройду. Но умею искать макс. палиндромы размерностью от 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;
    }
LuxTux
Решение похоже на многие здесь, однако стоит обратить внимание на отрезки цикла. А именно: 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;
}
Javin
Похоже, что не угасший интерес, а некие обстоятельства непреодолимой силы не позволили автору темы подвести итоги конкурса. Жаль!
Алгоритм уважаемого Himegа даёт, похоже, наибольшее быстродействие. Но лично для меня, к сожалению, он так и остался вне понимания.
Осталось загадкой и то, что никто пока не использовал возможности многопоточности. Хотя некоторые участники, предполагаю, разбираются и в ней. Почему же они не стали применять эту технологию? Ведь практически у всех в персональных компьютерах стоят многоядерные микропроцессоры и от параллельных вычислений, полагаю, можно получить прирост в быстродействии.
JuriMik
отсутствие свободного времени. В будни работа — на выходных в квартире одно повесить, другое прибить, третье перетянуть нужно :)
antonioplay
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;
}

}
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.