String problem in java

How to solve the string rotation problem in Java with a trick

Many candidates are rejected or down-leveled due to poor performance in their System Design Interview. Stand out in System Design Interviews and get hired in 2023 with this popular free course.

Problem statement

One of the interesting string algorithm-based coding questions is how do you find if a given string is the rotation of another given string? For example, if the two given strings are “Java” and “aJav,” then they are rotations of each other because it seems the string is rotated from the last “a.” However, “Java” and “Jaav” are not rotations of each other.

You need to write a function in Java that accepts two string inputs and returns true if they are rotations of each other and false otherwise. This question might seem difficult, but there is a nice trick to solve this problem, which we’ll go over in this shot.

Things to consider

Like all other programming interview questions, you should ask some general questions before jumping into the solution, e.g., are the given strings in ASCII or Unicode? Since ASCII and Unicode are different encoding schemes, it will affect the solution. For this question, we’ll assume that the given strings are in ASCII format.

Another good question to ask while dealing with string interview questions is about case sensitivity. Does your solution need to consider the case or not?

For example, if the case is not considered, then ‘a’ and ‘A’ will be treated equally. Hence, ‘java’ and ‘aJav’ will be rotations of each other.

Here, we can assume the solution is case-sensitive.

Similarly, you can ask whether you can use additional data structures or not, how big the string will be, whether both strings can fit in memory or not, etc.

These questions show your attention to detail, which is very valuable when working with real-life production systems.

Источник

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

К сожалению статья не поместилась одним фрагментом, пришлось разбить её на две части. Начало смотрите тут

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 и реализации идеи интернирования строк. Пул строк также является примером паттерна Приспособленец (Flyweight). Пул строк помогает экономить большой объем памяти, но с другой стороны создание строки занимает больше времени. Когда мы используем двойные кавычки для создания строки, сначала ищется строка в пуле с таким же значением, если находится, то просто возвращается ссылка, иначе создается новая строка в пуле, а затем возвращается ссылка. Тем не менее, когда мы используем оператор new, мы принуждаем класс String создать новый объект строки, а затем мы можем использовать метод intern() для того, чтобы поместить строку в пул, или получить из пула ссылку на другой объект String с таким же значением. Ниже приведен пример, показывающий работу пула строк.

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

Источник