• ,

Тестовое задание "Image Comparison"

Привет всем, дорогие читатели и форумчане!

Отличная идея начать выставлять тестовые задания для тех, кто хочет себя попробовать перед собеседованием. Начал эту тему JuriMik и я вспомнил, что у меня тоже есть пара задач.
Здесь я выставлю только условие задания, в комментариях можно обсуждать алгоритм решения. Задание, как и водится, будет на английском.

  • ,

javarush.test.level20.lesson10.bonus01; не принимает. что делать?

C задачей разобрался. Оставлю несколько важных замечаний будущим поколениям:
1) обязательно удалите метод main перед сдачей;
2) внимательно читайте условие: я неправильно понял условие и программа долгое время не проходила проверку
(N — это максимально допустимое число Армстронга, а не последнее число, участвующее в переборе )
3) на счет этого я не на 100% уверен, но все таки — статические коллекции внесите в метод main и передавайте в нужные методы через конструктор.

Здравствуйте. Скажите пожалуйста — что еще можно исправить, чтобы сервер принимал решение?
Сейчас 2 000 000 000 обрабатывает за 30 секунд и быстрее уже едва ли получится сделать.
Уже видел на форуме несколько тем с обсуждением этой задачи, но ничего полезного для себя не увидел.
П.С. если вам будет лень разбираться с моим кодом, но у вас есть решение задачи ( не костылём ) — то скиньте пожалуйста в личку. Самому интересно как люди решили. Очень интересная задача. )
Спасибо.


    package com.javarush.test.level20.lesson10.bonus01;
    
    import java.util.Set;
    import java.util.TreeSet;
    
    /* Алгоритмы-числа
    Число S состоит из M чисел, например, S=370 и M(количество цифр)=3
    Реализовать логику метода getNumbers, который должен среди натуральных чисел меньше N (long)
    находить все числа, удовлетворяющие следующему критерию:
    число S равно сумме его цифр, возведенных в M степень
    getNumbers должен возвращать все такие числа в порядке возрастания
    
    Пример искомого числа:
    370 = 3*3*3 + 7*7*7 + 0*0*0
    8208 = 8*8*8*8 + 2*2*2*2 + 0*0*0*0 + 8*8*8*8
    
    На выполнение дается 10 секунд и 50 МБ памяти.
    */
    public class Solution
    {
        /*
        powers содержит массив степеней ( 0 -- 10 ) для всех чисел ( 0 -- 9 )
        narcissisticNumbers содержит список всех чисел, являющихся числами Армстронга
        maxSum - константа, содержащая максимальное значение для integer
        ( на случай, если степенная сумма числа превысит максимальное значение Integer.MAX_VALUE
        пример = powSum(1 999 999 999) = 31 381 059 610 ;
        */
        private static int[][] powers = new int[10][11]; // массив степеней
        private static Set<Integer> narcissisticNumbers = new TreeSet<>(); // множество set для автоматической сортировки полученных результатов
        private static int maxSum = Integer.MAX_VALUE - 1; // граница максимально возможного значения степенной суммы
    
        static // генерируем массив степеней
        {
            for (int ii = 0; ii < 10; ii++)
            {
                for (int jj = 0; jj < 11; jj++)
                {
                    powers[ii][jj] = (int) Math.pow(ii, jj);
                }
            }
        }
        /*
        Основной метод класса. перебираю числа. если каждая следующая цифра ( с конца к началу ).
        Если каждая следующая цифра меньше предыдущей - то число подходит и я обрабатываю его дальше.
        В powSum сохраняю значение степенной суммы подходящий чисел и далее проверяю - является ли данная
        степенная сумма числом Армстронга.
        */
    
        public static int[] getNumbers(int N)
        {
            int[] result = null;
            for (int ii = 1; ii <= N; ii++)
            {
                if (isFitting(ii))
                {
                    int powSum = powerSum(ii);
                    if (isNarcissistic(powSum)) narcissisticNumbers.add(powSum);
                }
            }
    
            int size = narcissisticNumbers.size();
            int[] result0 = new int[size];
            byte jj = 0;
            for (int x : narcissisticNumbers)
            {
                result0[jj] = x;
                jj++;
            }
            result = result0;
            return result;
        }
        /*
        Метод класса, который считает степенную сумму числа.
        power - длина числа, поданного на вход
        sum - значение степенной суммы
         */
        private static int powerSum(int number)
        {
            int power = (int) Math.log10(number) + 1;
            int sum = 0;
            while (number > 0)
            {
                sum += powers[number % 10][power];
                if (sum > maxSum)
                {
                    break;
                }
                number /= 10;
            }
            return sum;
        }
    
        /*
        Метод проверяет - является ли число, переданное в метод
        числом Армстронга. Считаем степенную сумму переданного числа и сравниваем
        полученную сумму с переданным числом.
        Совпадает --> true;
        Не совпадает --> false.
         */
        private static boolean isNarcissistic(int number)
        {
            int sum = powerSum(number);
            if (number != sum) return false;
            return true;
        }
        /*
        Метод проверяет число на предмет удовлетворения условию отсечения:
        135 --> подходит 1 < 3 < 5
        153 --> не подходит 1 < 5 > 3
         */
        private static boolean isFitting(int number)
        {
            int previousDigit = 9;
            int currentDigit;
            while (number > 0)
            {
                currentDigit = number % 10;
                if (currentDigit == 0)
                {
                } else
                {
                    if (currentDigit > previousDigit) return false;
                    previousDigit = currentDigit;
                }
                number /= 10;
            }
            return true;
        }
    
        public static void main(String[] args)
        {
            long date0 = System.currentTimeMillis();
            int[] result = getNumbers(2000000000);
            long date = System.currentTimeMillis();
            for (int x : result)
            {
                System.out.println(x);
            }
            System.out.println(narcissisticNumbers.size());
            System.out.println("==============================");
            System.out.println("program was working " + (date - date0) + " ms==");
            System.out.println("==============================");
    
        }
    
    }

  • ,

Онлайн тесты на работу.

Добрый день. Вообщем решил создать такую тему. Многие конторы при устройстве на работу используют онлайн тестирование. При том условия на англ. языке и вот сегодня я писал такой тест — www.hackerrank.com/
Рекомендую всем попробовать. Тем более что JavaRush свои задачи в паблик не приветствует, а там можно рейтинг потом работодателю показать. Но да ладно, не об этом сейчас.
Вообщем у меня было 4 теста, на 90 минут. Решать все не обязательно и написано что лучше решить несколько но качественно. И я бы хотел их обсудить, т.к. не понял как их можно было решить лучше)))))
Задача 1. Написать такое — static int result(int[] arr){}
Дается массив, в котором найти разницу между самым большим элементом и самым маленьким, при том индекс самого маленького должен быть меньше индекса самого большого.
Я решал наверно как все подумали — первый for ищет самый большой элемент и индекс.
Потом второй for ищет самый маленький элемент в элементах до indexMax.
И просто вывожу разницу. И вот это решение не самое оптимальное, набрало всего 3 теста из 10.
Какие есть предложения решить ее лучше? сейчас вот думаю может можно было как то в один фор вложить, но как, если последовательность после max элемента не должна участвовать… или возможно что нибудь типа public static synchronized и т.д. тоже дают плюсы по тестам, не проверял кроме public

Задача 2. написать String[] result(String S, String T){}
Дается две строки. (На javarush похожая была с файлами) Строка T это строка S без некоторых слов. Вернуть массив слов которых не хватает в Т.
Решал так split(t)=" " — результат в set;
split(s)=" ", for и если !set.contains(s[i]) то добавляем в ArrayListresult;
потом return result.toArray(new String[0]);
5 теста из 10;
Сначала result был Set — было 3 теста из 10;
У кого еще какие замечания и предложения есть?

Задача 3. я не решал но если кому интересно — дан текст String[] и найти все домены в тексте и вывести на экран. Типа «ляляля www.xyz.ru лялл ялл ww2.abc.com/sfsflj&dsf?dsfslj/index.html ляляля» вывести «xyz.ru;abc.com»

4-ая С бинарными деревьями, не читал, жаль времени было

level36.lesson08.bonus01

подскажите с деревом. вроде работает

/* Разбираемся в красно-черном дереве
Дана реализация красно-черного дерева.
Некоторые методы сломаны. Разберитесь в коде и исправьте ошибки.
Метод main не участвует в тестировании.
Все модификатры правильные.
Имена переменных и методов не изменяйте.
*/


public class RedBlackTree {
    protected Node current;
    private Node parent;
    private Node grand;
    private Node great;
    private Node header;

    private static final Node EMPTY = new Node(0);

    static {
        EMPTY.left = EMPTY;
        EMPTY.right = EMPTY;
    }

    public RedBlackTree() {
        header = EMPTY;
        header.left = new Node(Integer.MIN_VALUE);
        header.right = EMPTY;
    }

    public boolean isEmpty() {
        return header.right == EMPTY;
    }

    public void clear() {

        header.right = EMPTY;
    }

    public void insert(int item) {
        current = grand = parent = header;
        EMPTY.element = 0;
        while (current.element != item) {
            great = grand;
            grand = parent;
            parent = current;
            current = item > current.element ? current.right : current.left;

            if(current.right.color == Color.RED && current.left.color == Color.RED){
                reorient(item);
            }

            if(current.element == 0){
                Node uncle;
                if(grand.left.equals(parent)){
                    uncle = grand.right;
                }else{
                    uncle = grand.left;
                }
                if (parent.color == Color.RED && uncle.color == Color.BLACK) {

                    reorient(item);
                }else {
                    break;
                }
            }

        }

        if (current != EMPTY) {
            return;
        }

        current = new Node(item, EMPTY, EMPTY);

        if (item < parent.element) {
            parent.left = current;
        } else {
            parent.right = current;
        }

        reorient(item);
    }

    protected void reorient(int item) {
        current.color = Color.RED;
        current.left.color = Color.BLACK;
        current.right.color = Color.BLACK;

        if (parent.color == Color.RED) {
            grand.color = Color.RED;
            if (item < grand.element != item < parent.element) {
                parent = rotate(item, grand);
            }
            current = rotate(item, great);
            current.color = Color.BLACK;
        }

        header.right.color = Color.BLACK;
    }

    private Node rotate(int item, Node parent) {
        if (item < parent.element) {
            Node node = parent.left;
            Node resultNode = item < node.element ? rotateWithRightNode(node) : rotateWithLeftNode(node);
            parent.left = resultNode;
            return parent.left;
        } else {
            Node node = parent.right;
            Node resultNode = item < node.element ? rotateWithRightNode(node) : rotateWithLeftNode(node);
            parent.right = resultNode;
            return parent.right;
        }
    }

    private Node rotateWithLeftNode(Node element) {
        Node right = element.right;
        element.right = right.left;
        right.left = element;
        return right;
    }

    private Node rotateWithRightNode(Node element) {
        Node left = element.left;
        element.left = left.right;
        left.right = element;
        return left;
    }

    public static enum Color {
        BLACK,
        RED
    }

    public static class Node {
        private int element;
        private Node left;
        private Node right;
        private Color color;

        public Node(int element) {
            this(element, null, null);
        }

        public Node(int element, Node left, Node right) {
            this.left = left;
            this.right = right;
            this.element = element;
            this.color = Color.BLACK;
        }
    }
}

level05.lesson12.bonus03

Все прекрасно работает, но может я не уловил суть задания? Что не так, Господа?

package com.javarush.test.level05.lesson12.bonus03;

import java.io.BufferedReader;
import java.io.InputStreamReader;

/* Задача по алгоритмам
Написать программу, которая:
1. вводит с консоли число N > 0
2. потом вводит N чисел с консоли
3. выводит на экран максимальное из введенных N чисел.
*/

public class Solution
{
    public static void main(String[] args) throws Exception
    {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int maximum = 0;

        //напишите здесь ваш код
        int N = Integer.parseInt(reader.readLine());
        if(N > 0)
        {
             int a[] = new int[N];

             for(int i = 0; i < N; i++)
             {
                a[i] = Integer.parseInt(reader.readLine());
             }


              for(int i = 0; i < a.length; i++)
              {
                   if(a[i] > maximum)
                    maximum = a[i];
              }

        }


        System.out.println(maximum);
    }
}