User Andrey
Andrey
26 уровень

Java String. Вопросы к собеседованию и ответы на них, ч.2

Статья из группы Архив info.javarush.ru
К сожалению статья не поместилась одним фрагментом, пришлось разбить её на две части. Начало смотрите тут Java String. Вопросы к собеседованию и ответы на них, ч.2 - 1

12. Напишите функцию для нахождения самого длинного палиндрома в данной строке

Строка может содержать в себе строки-палиндромы, и нахождение самого длинного палиндрома – это вопрос программирования. Ключевым моментом здесь является то, что из середины любого палиндрома, если мы пойдем направо и налево на 1 символ, это всегда будет одинаковый символ. К примеру, 12321, середина тут 3, и если мы продолжим движение с текущей позиции в обе стороны, мы получим 2, а затем 1. Мы используем подобную логику в нашей Java программе для нахождения самого длинного палиндрома. Однако если длина палиндрома четная, длина середины тоже четная, так что мы должны убедиться, что в нашей программе это так же предусмотрено, к примеру, 12333321, тут середина 33, и если мы продолжим движение в обе стороны, мы получим 3, 2 и 1. В нашей программе мы проходим по полученной строке с серединой на первом месте и проверяем левый и правый символ. Так же мы имеем две глобальные переменные для хранения начальной позиции палиндрома. Нам также необходимо проверить наличие уже найденного более длинного палиндрома, так как мы можем найти несколько палиндромов в данной строке. Ниже приведен пример программы, которая отлично работает во всех случаях. Мы можем усовершенствовать приведенный код, переместив цикл while в отдельный метод, но я оставил эту часть для вас . Пожалуйста, дайте мне знать, если у вас есть более удачная реализация, или программа не срабатывает в каком-то случае.

package com.journaldev.util;
 
public class LongestPalindromeFinder {
 
    public static void main(String[] args) {
        System.out.println(longestPalindromeString("1234"));
        System.out.println(longestPalindromeString("12321"));
        System.out.println(longestPalindromeString("9912321456"));
        System.out.println(longestPalindromeString("9912333321456"));
        System.out.println(longestPalindromeString("12145445499"));
    }
 
    public static String longestPalindromeString(String in) {
        char[] input = in.toCharArray();
        int longestPalindromeStart = 0;
        int longestPalindromeEnd = 0;
 
        for (int mid = 0; mid < input.length; mid++) {
            // для случая нечетного палиндрома как 12321, 3 будет серединой
            int left = mid-1;
            int right = mid+1;
            // нам необходимо двигаться влево и вправо на 1 позицию до конца
            while (left >= 0 && right < input.length) {
                // ниже проверка, является ли это палиндромом
                if (input[left] == input[right]) {
                    // обновление глобальных позиций, только если палиндром длиннее имеющегося
                    if (right - left > longestPalindromeEnd
                            - longestPalindromeStart) {
                        longestPalindromeStart = left;
                        longestPalindromeEnd = right;
                    }
                }
                left--;
                right++;
            }
            // для четного палиндрома у нас должна быть подобная логика с размером середины 2
            // для этого мы начнем на одну позицию правее
            left = mid-1;
            right = mid + 2;// к примеру, для 12333321 мы выбрали 33 в качестве середины
            while (left >= 0 && right < input.length)
            {
                if (input[left] == input[right]) {
                    if (right - left > longestPalindromeEnd
                            - longestPalindromeStart) {
                        longestPalindromeStart = left;
                        longestPalindromeEnd = right;
                    }
                }
                left--;
                right++;
            }
        }
        // теперь у нас есть позиции для самого длинного палиндрома
        return in.substring(longestPalindromeStart, longestPalindromeEnd + 1);
    }
}
Программа выведет следующее:

1
12321
12321
12333321
454454

13. Какие различия между String, StringBuffer и StringBuilder

Строка является неизменной и финализированной в Java, поэтому все наши манипуляции со строкой всегда будут создавать новую строку. Манипуляции со строками ресурсоемкие, поэтому Java обеспечивает два полезных класса для манипуляций со строками – StringBuffer и StringBuilder. StringBuffer и StringBuilder являются изменяемыми классами. Операции с StringBuffer потокобезопасны и синхронизированы, а методы StringBuilder не потокобезопасны. Поэтому когда несколько нитей работают с одной строкой, мы должны использовать StringBuffer, но в однопоточном окужении мы должны использовать StringBuilder. StringBuilder более производительный, чем StringBuffer, поскольку не обременен синронизацией.

14. Почему строка неизменная и финализированная в Java

Есть несколько преимуществ в неизменности строк:
  1. Строковый пул возможен только потому, что строка неизменна в Java, таким образом виртуальная машина сохраняет много места в памяти (heap space), поскольку разные строковые переменные указывают на одну переменную в пуле. Если бы строка не была неизмененяемой, тогда бы интернирование строк не было бы возможным, потому что если какая-либо переменная изменит значение, это отразится также и на остальных переменных, ссылающихся на эту строку.

  2. Если строка будет изменяемой, тогда это станет серьезной угрозой безопасности приложения. Например, имя пользователя базы данных и пароль передаются строкой для получения соединения с базой данных и в программировании сокетов реквизиты хоста и порта передаются строкой. Так как строка неизменяемая, её значение не может быть изменено, в противном случае любой хакер может изменить значение ссылки и вызвать проблемы в безопасности приложения.

  3. Так как строка неизменная, она безопасна для много поточности и один экземпляр строки может быть совместно использован различными нитями. Это позволяет избежать синхронизации для потокобезопасности, строки полностью потокобезопасны.

  4. Строки используются в Java classloader и неизменность обеспечивает правильность загрузки класса при помощи Classloader. К примеру, задумайтесь об экземпляре класса, когда вы пытаетесь загрузить java.sql.Connection класс, но значение ссылки изменено на myhacked.Connection класс, который может осуществить нежелательные вещи с вашей базой данных.

  5. Поскольку строка неизменная, её hashcode кэшируется в момент создания и нет необходимости рассчитывать его снова. Это делает строку отличным кандидатом для ключа в Map и его обработка будет быстрее, чем других ключей HashMap. Это причина, почему строка наиболее часто используемый объект, используемый в качестве ключа HashMap.

15. Как разделить строку на части?

Мы можем использовать метод split(String regex) для разделения строки на массив строк, используя в качестве разделителя регулярное выражение.

import java.util.Arrays;

public class JavaSplitString {
    public static void main(String[] args) {
        String line = "I am a java developer";
        String[] words = line.split(" ");
        String[] twoWords = line.split(" ", 2);
        System.out.println("String split with delimiter: "+Arrays.toString(words));
        System.out.println("String split into two: "+Arrays.toString(twoWords));
        //split string delimited with special characters
        String wordsWithNumbers = "I|am|a|java|developer";
        String[] numbers = wordsWithNumbers.split("\\|");
        System.out.println("String split with special character: "+Arrays.toString(numbers));
    }
}
Метод split(String regex, int numOfStrings) является перегруженным методом для разделения строки на заданное количество строк. Мы можем использовать обратную черту для использования специальных символов регулярных выражений в качестве обычных символов. Программа выведет следующее:

String split with delimiter: [I, am, a, java, developer]
String split into two: [I, am a java developer]
String split with special character: [I, am, a, java, developer]

16. Почему массив строк предпочтительнее строки для хранения пароля?

Строка неизменяемая в Java и хранится в пуле строк. С тех пор, как она была создана, она остается в пуле, пока не будет удалена сборщиком мусора, поэтому, когда мы думаем, что закончили работу с паролем, он остается доступным в памяти некоторое время, и нет способа избежать этого. Это риск безопасности, поскольку кто-либо, имеющий доступ к дампу памяти сможет найти пароль в виде чистого текста. Если мы используем массив символов для хранения пароля, мы можем очистить его после того, как закончим с ним работать. Таким образом, мы можем контролировать, как долго он находится в памяти, что позволяет избежать риска безопасности, свойственного строке.

17. Как вы проверите две строки на подобность в Java?

Есть два способа проверить, являются ли две строки эквивалентными – используя оператор “==”, или используя метод equals. Когда мы используем оператор “==”, он проверяет значение строки, как ссылки, но в программировании большую часть времени мы проверяем эквивалентность строки только для значения. Поэтому мы должны использовать метод equals для проверки двух строк на эквивалентность. Еще есть метод equalsIgnoreCase, который мы можем использовать для игнорирования регистра.

String s1 = "abc";
String s2 = "abc";
String s3= new String("abc");
System.out.println("s1 == s2 ? "+(s1==s2)); //true
System.out.println("s1 == s3 ? "+(s1==s3)); //false
System.out.println("s1 equals s3 ? "+(s1.equals(s3))); //true

18. Что такое пул строк?

Как подсказывает название, пул строк – это набор строк, который хранится в памяти Java heap. Мы знаем, что String это специальный класс в Java, и мы можем создавать объекты этого класса, используя оператор new точно так же, как и создавать объекты, предоставляя значение строки в двойных кавычках. Диаграмма ниже объясняет, как пул строк размещается в памяти Java heap и что происходит, когда мы используем различные способы создания строк. Java String. Вопросы к собеседованию и ответы на них, ч.2 - 2Пул строк возможен исключительно благодаря неизменяемости строк в Java и реализации идеи интернирования строк. Пул строк также является примером паттерна Приспособленец (Flyweight). Пул строк помогает экономить большой объем памяти, но с другой стороны создание строки занимает больше времени. Когда мы используем двойные кавычки для создания строки, сначала ищется строка в пуле с таким же значением, если находится, то просто возвращается ссылка, иначе создается новая строка в пуле, а затем возвращается ссылка. Тем не менее, когда мы используем оператор new, мы принуждаем класс String создать новый объект строки, а затем мы можем использовать метод intern() для того, чтобы поместить строку в пул, или получить из пула ссылку на другой объектString с таким же значением. Ниже приведен пример, показывающий работу пула строк.

public class StringPool {
    public static void main(String[] args) {
        String s1 = "Cat";
        String s2 = "Cat";
        String s3 = new String("Cat");
         
        System.out.println("s1 == s2 :"+(s1==s2));
        System.out.println("s1 == s3 :"+(s1==s3));
    }
}
Программа выведет следующее:

s1 == s2 :true
s1 == s3 :false

19. Что делает метод intern()?

Когда метод intern() вызван, если пул строк уже содержит строку, эквивалентную к нашему объекту, что подтверждается методом equals(Object), тогда возвращается ссылка на строку из пула. В противном случае объект строки добавляется в пул и ссылка на этот объект возвращается. Этот метод всегда возвращает строку, которая имеет то же значение, что что и текущая строка, но гарантирует что это будет строка из пула уникальных строк. Ниже приведен пример работы метода intern():

public class StringPool {
    public static void main(String[] args) {
        String a = "string a";
        String b = new String("string a");
        String c = b.intern();

        System.out.println(a == b);
        System.out.println(b == c);
        System.out.println(a == c);
    }
}
Программа выведет следующее:
false
false
true

20. Являются ли строки потокобезопасными в Java?

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

21. Почему строка является популярным ключем в HashMap в Java?

Поскольку строки неизменны, их хэшкод кэшируется в момент создания, и не требует повторного пересчета. Это делает строки отличным кандидатом для ключа в Map и они обрабатываются быстрее, чем другие объекты-ключи HashMap. Вот почему строки преимущественно используются в качестве ключей HashMap. Надеюсь, что вопросы, перечисленные в этой статье помогут вам на собеседованиях, пожалуйста, дайте мне знать, если я что-то пропустил. Ссылка на оригинальную статью Автор: Pankaj Kumar
Комментарии (33)
ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
Владимир Уровень 25, Минск, Беларусь
3 апреля 2022
Спасибо, хорошая статья для закрепления лекций 10 уровня по String. За оригинал статьи отдельная благодарность. P.S. да, диаграмму в вопросе №18 исправьте
Anonymous #2854449 Уровень 18, Москва, Russian Federation
23 февраля 2022
я на 10 уровне, половина из статьи непонятна, зачем они ее добавили сюда))
🦔 Виктор Уровень 20, Москва, Россия Expert
5 декабря 2020
Как и в случае первой части, еле дочитал до конца. Не знаю, кто додумался подкинуть эти ссылки в течении 10 уровней, нечего здесь пока ловить. Просто как сборник примеров по стрингам — ок, спасибо за труды. Во всех остальных случаях: есть вопрос, есть ответ, но нет доступного объяснения. -- tlgrm: @LetsCodeIt | @SefoNotasi
Vyacheslav Уровень 20, Москва
29 июня 2020
В 14 пункте нет ни слова о том ПОЧЕМУ String - immutable.
Nadezhda Ermolaeva Уровень 1, Санкт-Петербург
1 февраля 2020
public static void main(String[] args) { Scanner sc = new Scanner(System.in); String A = sc.nextLine(); sc.close(); int maxLength = 1; int position_start = 0; int position_end = 0; for (int n = 1; n <= A.length() ; n++) { for (int i = 0; i <= A.length() - n; i++) { String subs = A.substring(i,i + n); if(subs.equals(new StringBuilder(subs).reverse().toString())) { maxLength = n; position_start = i; position_end = i + n; break; } } } System.out.println("Polindrome length = " + maxLength); System.out.println(A.substring(position_start, position_end)); }
Кирилл Уровень 0, Гомель
7 ноября 2019
В задаче на нахождение самого длинного(четного) палиндрома нет проверки на то,что в центре находится палиндром.Т.е. для варианта 121221 выдает самый динный палиндром 121221.
Иван Уровень 2, Днепр
4 августа 2019
Я думаю лучше двигаться по строке и находить чётный (1) или не чётный (2) палиндром, а потом уже находить его длину (3) и сравнивать (4) с предыдущим палиндромом.

private static String longestPalindromeString(String str){
        char[] input = str.toCharArray();
        int start = 0, end = 0, stepBack, stepForward;
        for(int i = 1; i < str.length(); i++){
            if(input[i - 1] == input[i]){                           // 1
                stepBack = i - 1;
            } else if(i - 2 > 0 && input[i - 2] == input[i]){       // 2
                stepBack = i - 2;
            } else
                continue;

            stepForward = i;
            while (stepForward < str.length() &&
                    stepBack >= 0 &&
                    input[stepBack] == input[stepForward]) {        //3
                stepBack--;
                stepForward++;
            }

            if(end - start < stepForward - ++stepBack){             // 4
                start = stepBack;
                end = stepForward;
            }
        }
        return str.substring(start, end);
    }
Alejandro_Kolio Уровень 31, Санкт-Петербург, Россия
30 марта 2019
Можно попробовать сделать это проще, средствами Java8, например 1. Определяем, палиндром ли строка с которой работаем сейчас? 2. Далее в стриме проверям длинну палинромов и возвращаем самый длинный. Я сделал так:

@Slf4j
public class Main {
  private final static String PUNCTUATION = "[. ,\\/#!$%\\^&\\*;:{}=\\-_`~()]";

  public static void main(String[] args) {
    List<String> palindromes = Arrays.asList(
            "A but tuba.",
            "A man, a plan, a cat, a ham, a yak, a yam, a hat, a canal-Panama!   ",
            "A slut nixes sex in Tulsa.",
            "12345678987654321");

    final Main main = new Main();
    final String longestPalindrome = main.longestPalindrome(palindromes);
  }

  private String longestPalindrome(@NonNull List<String> values) {
    Optional<String> palindrome = values
            .stream()
            .filter(this::isPalindrome)
            .collect(toList())
            .stream()
            .max(Comparator.comparingInt(String::length));

    if (palindrome.isPresent()) {
      log.info("The longest palindrome in this list: {}", palindrome.get());
      return palindrome.get();
    } else {
      return palindrome.orElse("no palindromes found");
    }
  }

  private boolean isPalindrome(@NonNull String value) {
    final String clean = value.replaceAll(PUNCTUATION, "").trim().toLowerCase();
    final StringBuilder reverse = new StringBuilder(clean).reverse();
    return (reverse.toString()).equals(clean);
  }
Alejandro_Kolio Уровень 31, Санкт-Петербург, Россия
30 марта 2019
Можно попробовать сделать это проще, средствами Java8 например 1. Сначал надо определить палиндром ли эта строка с которой мы работаем сейчас или нет. 2. Далее уже будем работать со списком всех палиндромов в стриме и найдем самый длинный из них. Я сделал так:

@Slf4j
public class Main {
  public static void main(String[] args) {
    List<String> palindromes = Arrays.asList(
            "A but tuba.",
            "A man, a plan, a cat, a ham, a yak, a yam, a hat, a canal-Panama!",
            "A slut nixes sex in Tulsa.",
            "12345678987654321");

    Main main = new Main();
    final String longestPalindrome = main.longestPalindrome(palindromes);
  }

  private String longestPalindrome(@NonNull List<String> values) {
    Optional<String> palindrome = values
            .stream()
            .filter(this::isPalindrome)
            .collect(toSet())
            .stream()
            .max(Comparator.comparingInt(String::length));
    if (palindrome.isPresent()) {
      log.info("The longest palindrome in this list: {}", palindrome.get());
      return palindrome.get();
    } else {
      return palindrome.orElse("no palindromes found");
    }
  }

  private boolean isPalindrome(String text) {
    String clean = text.replaceAll("[, .!?-]+", "").toLowerCase();
    int length = clean.length();
    int forward = 0;
    int backward = length - 1;
    while (backward > forward) {
      char forwardChar = clean.charAt(forward++);
      char backwardChar = clean.charAt(backward--);
      if (forwardChar != backwardChar)
        return false;
    }
    return true;
  }
}