Бинарный поиск

Одним из основных алгоритмов поиска является бинарный поиск. Он работает только с отсортированными данными, за счет этого достигается большая скорость поиска: O(logN). Принцип работы алгоритма прост: находим середину массива данных, проверяем, больше, меньше и равно искомое значение значению в середине. Если равно, значит нашли. Если искомое больше, значит дальше ищем только в правой половине, если меньше - в левой. Т.е. с каждой итерацией количество данных для поиска делится надвое.

public class Binary {
    public static void main(String[] args) {
        int[] arr = { 1,12,23,34,55,61,67,88,89,101 };
        System.out.println(rank(55, arr));
    }
    
    public static int rank(int val, int[] arr) {
        return rank(val, arr, 0, arr.length-1);
    }
    
    private static int rank(int val, int[] arr, int lo, int hi) {
        if (lo > hi) return -1;
        
        int mid = lo + (hi - lo) / 2;
        
        if (val < arr[mid]) {
            return rank(val, arr, lo, mid - 1);
        } else if (val > arr[mid]) {
            return rank(val, arr, mid + 1, hi);
        } else {
            return mid;
        }
    }
}

Как проверить, является ли число простым

Простые числа являются элементарными строительными блоками натуральных чисел. Простые числа применяются, например, в криптографии. За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичных цифр назначена премия в 150 000 и 250 000 долларов США, говорится в Википедии.

/**
 * Является ли число простым?
 */
public static boolean isPrime(int N) {
    if (N < 2) return false;
    for (int i = 2; i*i <= N; i++)
        if (N % i == 0) return false;
    return true;
}

Умножение матриц

Умножение матриц - одна из основных операций над матрицами. Принцип умножения матриц хорошо описан в Википедии

В двумерном массиве arr[m][n], по соглашению, первое значение - количество строк, второе - столбцов.

Применение умножения матриц можно найти, например,при программировании поведения объектов в трехмерном пространстве.

public class MatrixMultiplection {
    public static void main(String[] args) {
        int[][] mA = 
            {{33,34,12},
             {33,19,10},
             {12,14,17},
             {84,24,51},
             {43,71,21}};
        
        int[][] mB = 
            {{10,11,34,55},
             {33,45,17,81},
             {45,63,12,16}};

        
        int m = mA.length;
        int n = mB[0].length;
        int o = mB.length;
        int[][] res = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < o; k++) {
                    res[i][j] += mA[i][k] * mB[k][j]; 
                }
            }
        }
        
        for (int i = 0; i < res.length; i++) {
            for (int j = 0; j < res[0].length; j++) {
                System.out.format("%6d ", res[i][j]);
            }
            System.out.println();
        }
    }
}
/**
  Output:   
  1992   2649   1844   4761 
  1407   1848   1565   3514 
  1347   1833    850   2066 
  3927   5217   3876   7380 
  3718   4991   2921   8452
 */

Данный алгоритм имеет сложность O(n³). Алгоритм Копперсмита — Винограда может делать это за O(n^2.3727).

Выстраиваем элементы массива в обратном порядке

import java.util.Arrays;
/**
 * Меняет порядок элементов массива на обратный за n/2
 */
public class ReverseElements {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9,10,11};
        for (int i = 0; arr.length/2 > i; i++) {
            int tmp = arr[i];
            arr[i] = arr[arr.length - i - 1];
            arr[arr.length - i - 1] = tmp;
        }
        System.out.println(Arrays.toString(arr));
        
    }
}

Наибольший общий делитель

/**
 * Алгоритм Евклида. Наибольший общий делитель
 * */
public class GratestCommonDivisor {
    public static void main(String[] args) {
        System.out.println(gcd(30000, 1701));
    }
    
    public static int gcd(int a, int b) {
        if (b == 0) return a;
        int x = a % b;
        return gcd(b, x);
    }
}

Вызываем метод

Всё ли в порядке в коде?

public void go()
{
    ripper(10,11,15,-1);
}

public void ripper(short... args)
{
    System.out.print(args.length);
} 

Ответ

Не скомпилируется
В метод ripper мы передаем int, ожидается short

Объявление массива

Скомпилируется ли?

Object hobject = new Short[4];

Ответ

Да
Каждый массив - это объект

Конструкторы

Что выведет программа?

class Test {
    public static void main(String[] args) {
        Devil dev = new Boast(1);
    }
}

class Boast extends Devil 
{
    public Boast(){System.out.print("boast ");}
    public Boast(int i)
    {}
}

class Devil
{
    public Devil(){System.out.print("devil ");}
    public Devil(int i)
    {}  
}

Ответ

devil
При создании объекта, всегда вызываются конструкторы по умолчанию у родителей, начиная с самого старшего.
Если в конструкторе вызывается конструктор родителя, то конструктор по умолчанию родителя не вызывается

Статические поля

Что выведет программа?

class T1 extends T {}

class T2 extends T {}

class T {
    public static int i;
}

public class Test {
    public static void main(String[] args) {
        T1.i = 5;
        T2.i = 3;
        System.out.format("%d = %d", T1.i, T2.i);
    }
}

Ответ

3 = 3
Статические поля родительских классов являются общими для наследников

Integer

Что выведет программа?

Integer i1 = Integer.valueOf(11);
Integer i2 = Integer.valueOf(11);
System.out.println(i1 == i2);
        
Integer i3 = Integer.valueOf(10000);
Integer i4 = Integer.valueOf(10000);
System.out.println(i3 == i4);

Ответ

true
false
Класс Integer содержит пул предопределенных объектов (-128...127)

Вызов методов из конструктора

Что выведет программа?

public class Parent {
    Parent() {
        test();
    }
    
    public static void main(String[] args) {
        new Child();
    }
 
    protected void test() {
     System.out.println("Hello from Parent");
    }
}

class Child extends Parent {
    private final String someString;
    Child() {
        someString = "some Text";
    }
    protected void test() {
        System.out.println("Hello from Child");
        System.out.println(someString);
    }
}

Ответ

Hello from Child
null
Если в конструкторе базового класса вызвать метод, который переопределен в дочернем, то при создании дочернего класса в конструкторе базового будет вызван метод дочернего класса, хотя очередь инициализации этого класса еще не настала. Это может привести к ошибкам. Например, вызванный метод может использовать переменные, которые еще не были инициализированы. Надо стараться избегать вызова методов в конструкторах. Можно смело вызывать только методы, помеченные в текущем классе как final или private, т.к. они не переопределяются.

Значение переменных внутри метода

Что выведет программа?

class Test {
    public static void main(String[] args) {
        String s = "old";
        print(s, s = "new");
    }
    
    static void print(String s1, String s2) {
        System.out.println(s1 + " " + s2);
    }
}

Ответ

old new
Внутри вызова метода значения присваиваются разным переменным

Finally

Какое значение вернет метод?

private static int foo() {
    int a = 1;
    int b = 2;
    try  {
        return a + b;
    } finally {
        a = 10;
        b = 20;
        return a + b;
    }
}

Ответ

30
Блок finally должен выполняться всегда, даже если в try есть return. Return внутри finally перебивает предыдущий return.

Операции с числами

Что выведет программа?

int x = 4;
System.out.println("value is " + ((x > 4) ? 99.99 : 9));

Ответ

value is 9.0
При выполнении сравнения между разными типами, типы приводятся к одному, если это возвожно

Сколько объектов в коллекции?

Что выведет программа?

public class Animal {
    private final String type;
    Animal(String type) {
       this.type = type; 
    }
    
    public boolean equals(Animal animal) {
        return type.equals(animal.type);
    }
    
    public int hashCode() {
        return type.hashCode();
    }

    
    public static void main(String[] args) {
        Set set = new HashSet();
        set.add(new Animal("Dog"));
        set.add(new Animal("Cat"));
        set.add(new Animal("Cat"));
        System.out.println(set.size());
    }
}

Ответ

3
Метод equals должен принимать объекты типа Object, а у нас - Animal. Из-за этого не произошло перезаписи метода и использовался метод equals класса Object. Что бы такого не просходило, надо всегда использовать аннотацию @Override в тех местах, где мы хотим переопределить метод.

Конкатенация

Что выведет программа?

System.out.println(1 + 2 + 3 + "" + 4 + 5 + 6);

Ответ

6456
Т.к. операции выполняются слева направо, то сначала выполнится сложение, затем конкатенация

Объявление констант

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

package com.effectivejava.science;

public class PhysicalConstants {
    private PhysicalConstants() { } // Prevents instantiation
    public static final double AVOGADROS_NUMBER = 6.02214199e23;
    public static final double BOLTZMANN_CONSTANT = 1.3806503e-23;
    public static final double ELECTRON_MASS = 9.10938188e-31;
}


// Use of static import to avoid qualifying constants
import static com.effectivejava.science.PhysicalConstants.*;

public class Test {
    double atoms(double mols) {
        return AVOGADROS_NUMBER * mols;
    }
    // Many more uses of PhysicalConstants justify static import
}

Пример написания hashCode и equals

public class HashCodeTest {
    boolean boolVar = true;
    byte byteVar = 123;
    short shortVar = 12345;
    char charVar = 12;
    int intVar = 1234567890;
    long longVar = 1234567890123456789L;
    float floatVar = 12345.0F;
    double doubleVar = 123456789012.8D;
    int[] arrayVar = {1,2,3,4,5,6,7};
    String objectVar = "String";
    Object nullVar = null;
    
    public static void main(String[] args) {
        HashCodeTest hct = new HashCodeTest();
        HashCodeTest hct2 = new HashCodeTest();
        System.out.format("%s%n%s", hct.hashCode(), hct.equals(hct2));
    }
    
    @Override
    public int hashCode() {
        int result = 17;
        //compute int hash-code for every field
        result = 31 * result + (boolVar?1:0);
        result = 31 * result + (int) byteVar;
        result = 31 * result + (int) shortVar;
        result = 31 * result + (int) charVar;
        result = 31 * result + intVar;
        result = 31 * result + (int) (longVar ^ (longVar >>> 32));
        result = 31 * result + Float.floatToIntBits(floatVar);
        result = 31 * result + (int) (Double.doubleToLongBits(doubleVar) ^ 
            (Double.doubleToLongBits(doubleVar) >>> 32));
        result = 31 * result + 0; //for nullVar
        result = 31 * result + objectVar.hashCode();
        result = 31 * result + Arrays.hashCode(arrayVar);
        return result;
    }
    
    @Override
    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        }
        if (obj instanceof HashCodeTest) {
            HashCodeTest hct = (HashCodeTest) obj;
            return boolVar == hct.boolVar && 
                   byteVar == hct.byteVar && 
                   shortVar == hct.shortVar && 
                   charVar == hct.charVar && 
                   intVar == hct.intVar && 
                   longVar == hct.longVar && 
                   floatVar ==  hct.floatVar && 
                   doubleVar == hct.doubleVar && 
                   Arrays.equals(arrayVar, hct.arrayVar) && 
                   objectVar.equals(hct.objectVar);
        }
        return false;
    }
}

/**
 * Output: 
 * -1172080207
 * true
 */

Паттерн Комманда(Command). Пример кода

public class Steps {
    public void goSouth() {
        System.out.println("step to south");
    }
    
    public void goNorth() {
        System.out.println("step to north");
    }
    
    public void goEast() {
        System.out.println("step to east");
    }
    
    public void goWest() {
        System.out.println("step to west");
    }
}

public abstract class StepsCommand implements Command {
    protected Steps steps = new Steps();
}

public interface Command {
    void execute();
}

public class GoEastCommand extends StepsCommand {
    @Override
    public void execute() {
        steps.goEast();
    }
}

public class GoNorthCommand extends StepsCommand {
    @Override
    public void execute() {
        steps.goNorth();
    }
}

public class GoSouthCommand extends StepsCommand {
    @Override
    public void execute() {
        steps.goSouth();
    }
}

public class GoWestCommand extends StepsCommand {
    @Override
    public void execute() {
        steps.goWest();
    }
}

public class Navigator {
    private final List<StepsCommand> steps = new LinkedList<>();
    private final List<StepsCommand> path = new LinkedList<>();
    
    public Navigator registerStep(StepsCommand step) {
        steps.add(step);
        return this;
    }
    
    public void go() {
        for(StepsCommand step : steps) {
            step.execute();
            ((LinkedList)path).addFirst(step);
        }
        steps.clear();
    }
    
    public void goBack() {
        for(StepsCommand step : path) {
            step.execute();
        }
        path.clear();
    }
}

public class Client {
    public static void main(String[] args) {
        Navigator navigator = 
            new Navigator().registerStep(new GoEastCommand())
                           .registerStep(new GoNorthCommand())
                           .registerStep(new GoNorthCommand())
                           .registerStep(new GoSouthCommand());
        System.out.println("go");
        navigator.go();
        System.out.println("go back");
        navigator.goBack();
    }
}
/**
 * Output:
 * go
 * step to east
 * step to north
 * step to north
 * step to south
 * go back
 * step to south
 * step to north
 * step to north
 * step to east
 */

Паттерн Цепочка обязанностей(Chain of responsibility). Пример кода

public class HouseProject {
    private final Set steps = new HashSet();
    
    public HouseProject(Steps... steps) {
        this.steps.addAll(Arrays.asList(steps));
    }
    
    public enum Steps {
        CREATE_BASEMENT,
        ADD_FLOOR,
        CREATE_ROOF,
        BUILD_FENCE
    }
    public Set getSteps() {
        return steps;
    }
}

public abstract class Builder {
    protected Builder nextBuilder;
    private final HouseProject.Steps step;
    
    public Builder(HouseProject.Steps step) {
        this.step = step;
    }
    
    public abstract void buildImpl();
    
    public void build(HouseProject project) {
        if (project.getSteps().contains(step)) {
            buildImpl();
        }
        if (nextBuilder != null) {
            nextBuilder.build(project);
        }
    }
    
    public Builder setNext(Builder builder) {
        nextBuilder = builder;
        return builder;
    }
}

public class BasementBuilder extends Builder {
    public BasementBuilder() {
        super(HouseProject.Steps.CREATE_BASEMENT);
    }

    @Override
    public void buildImpl() {
        System.out.println("Building basement");
    }
}

public class FloorBuilder extends Builder {
    public FloorBuilder() {
        super(HouseProject.Steps.ADD_FLOOR);
    }

    @Override
    public void buildImpl() {
        System.out.println("Building floor");
    }
}

public class RoofBuilder extends Builder {
    public RoofBuilder() {
        super(HouseProject.Steps.CREATE_ROOF);
    }

    @Override
    public void buildImpl() {
        System.out.println("Building roof");
    }
}

public class FecneBuilder extends Builder {
    public FecneBuilder() {
        super(HouseProject.Steps.BUILD_FENCE);
    }

    @Override
    public void buildImpl() {
        System.out.println("Building fence");
    }
}

public class Client {
    public static void main(String[] args) {
        Builder firstBuilder, lastBuilder;
        firstBuilder = lastBuilder = new BasementBuilder();
        lastBuilder = lastBuilder.setNext(new FloorBuilder())
                                 .setNext(new RoofBuilder())
                                 .setNext(new FecneBuilder());
        
        HouseProject hp = new HouseProject(
            HouseProject.Steps.CREATE_BASEMENT,
            HouseProject.Steps.ADD_FLOOR,
            HouseProject.Steps.CREATE_ROOF
        );
        
        firstBuilder.build(hp);
    }
}

/**
 * Output:
 * Building basement
 * Building floor
 * Building roof
 */