Here are the top 20 string programming and coding interview questions, along with their answers in Java, designed for experienced Java developers:
1. Reverse a String
Question: Write a Java program to reverse a string without using the StringBuilder or StringBuffer classes.
Answer:
javapublic static String reverseString(String input) {
char[] chars = input.toCharArray();
int left = 0, right = chars.length - 1;
while (left < right) {
char temp = chars[left];
chars[left] = chars[right];
chars[right] = temp;
left++;
right--;
}
return new String(chars);
}2. Check for Palindrome
Question: Write a Java function to check if a string is a palindrome (reads the same forwards and backwards).
Answer:
javapublic static boolean isPalindrome(String str) {
str = str.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
int left = 0, right = str.length() - 1;
while (left < right) {
if (str.charAt(left) != str.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}3. Count Occurrences of a Character
Question: How would you count the number of occurrences of a specific character in a string in Java?
Answer:
javapublic static int countOccurrences(String str, char target) {
int count = 0;
for (char c : str.toCharArray()) {
if (c == target) {
count++;
}
}
return count;
}4. Anagram Check
Question: Write a Java program to check if two strings are anagrams of each other.
Answer:
javapublic static boolean areAnagrams(String str1, String str2) {
if (str1.length() != str2.length()) {
return false;
}
char[] chars1 = str1.toCharArray();
char[] chars2 = str2.toCharArray();
Arrays.sort(chars1);
Arrays.sort(chars2);
return Arrays.equals(chars1, chars2);
}5. Check for Unique Characters
Question: Write a Java program to determine if a string has all unique characters.
Answer:
javapublic static boolean hasUniqueCharacters(String str) {
Set<Character> seen = new HashSet<>();
for (char c : str.toCharArray()) {
if (seen.contains(c)) {
return false;
}
seen.add(c);
}
return true;
}6. Longest Substring Without Repeating Characters
Question: Find the length of the longest substring without repeating characters in a given string.
Answer:
javapublic static int lengthOfLongestSubstring(String s) {
int maxLength = 0;
int start = 0;
Map<Character, Integer> charIndexMap = new HashMap<>();
for (int end = 0; end < s.length(); end++) {
if (charIndexMap.containsKey(s.charAt(end))) {
start = Math.max(start, charIndexMap.get(s.charAt(end) + 1));
}
charIndexMap.put(s.charAt(end), end);
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}7. Reverse Words in a String
Question: Write a Java program to reverse the words in a given string.
Answer:
javapublic static String reverseWords(String s) {
String[] words = s.trim().split("\\s+");
StringBuilder reversed = new StringBuilder();
for (int i = words.length - 1; i >= 0; i--) {
reversed.append(words[i]).append(" ");
}
return reversed.toString().trim();
}8. String to Integer (atoi)
Question: Implement the atoi function, which converts a string to an integer.
Answer:
javapublic static int atoi(String str) {
str = str.trim();
if (str.isEmpty()) {
return 0;
}
int sign = 1;
int index = 0;
if (str.charAt(0) == '-' || str.charAt(0) == '+') {
sign = str.charAt(0) == '-' ? -1 : 1;
index++;
}
long result = 0;
while (index < str.length() && Character.isDigit(str.charAt(index))) {
result = result * 10 + (str.charAt(index) - '0');
if (result * sign > Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
if (result * sign < Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
}
index++;
}
return (int) (result * sign);
}9. Implement strStr()
Question: Implement the strStr() function, which finds the first occurrence of a substring in a string.
Answer:
javapublic static int strStr(String haystack, String needle) {
if (needle.isEmpty()) {
return 0;
}
for (int i = 0; i <= haystack.length() - needle.length(); i++) {
if (haystack.substring(i, i + needle.length()).equals(needle)) {
return i;
}
}
return -1;
}10. Valid Palindrome II
Question: Given a non-empty string, write a function to check if it can be made a palindrome by removing at most one character.
Answer:
javapublic static boolean validPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
}
left++;
right--;
}
return true;
}
private static boolean isPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}11. Longest Common Prefix
Question: Write a function to find the longest common prefix among an array of strings.
Answer:
javapublic static String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
while (strs[i].indexOf(prefix) != 0) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) {
return "";
}
}
}
return prefix;
}12. Valid Parentheses
Question: Write a Java function to determine if a string of parentheses is valid.
Answer:
javapublic static boolean isValidParentheses(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
stack.pop();
} else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {
stack.pop();
} else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
stack.pop();
} else {
return false;
}
}
return stack.isEmpty();
}13. Implement Regular Expression Matching
Question: Implement regular expression matching with support for '.' and '*'.
Answer:
javapublic static boolean isMatch(String s, String p) {
if (p.isEmpty()) {
return s.isEmpty();
}
boolean firstMatch = !s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
if (p.length() >= 2 && p.charAt(1) == '*') {
return (isMatch(s, p.substring(2)) || (firstMatch && isMatch(s.substring(1), p)));
} else {
return firstMatch && isMatch(s.substring(1), p.substring(1));
}
}14. Find All Anagrams in a String
Question: Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Answer:
javapublic static List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
int[] pCount = new int[26];
int[] sCount = new int[26];
for (char c : p.toCharArray()) {
pCount[c - 'a']++;
}
for (int i = 0; i < s.length(); i++) {
sCount[s.charAt(i) - 'a']++;
if (i >= p.length()) {
sCount[s.charAt(i - p.length()) - 'a']--;
}
if (Arrays.equals(pCount, sCount)) {
result.add(i - p.length() + 1);
}
}
return result;
}15. Implement strStr() with KMP Algorithm
Question: Implement strStr() using the Knuth-Morris-Pratt (KMP) string-searching algorithm.
Answer:
javapublic static int strStrKMP(String haystack, String needle) {
if (needle.isEmpty()) {
return 0;
}
int[] prefixArray = buildPrefixArray(needle);
int i = 0, j = 0;
while (i < haystack.length()) {
if (haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
}
if (j == needle.length()) {
return i - j;
}
if (i < haystack.length() && haystack.charAt(i) != needle.charAt(j)) {
if (j != 0) {
j = prefixArray[j - 1];
} else {
i++;
}
}
}
return -1;
}
private static int[] buildPrefixArray(String pattern) {
int[] prefixArray = new int[pattern.length()];
int length = 0;
int i = 1;
while (i < pattern.length()) {
if (pattern.charAt(i) == pattern.charAt(length)) {
length++;
prefixArray[i] = length;
i++;
} else {
if (length != 0) {
length = prefixArray[length - 1];
} else {
prefixArray[i] = 0;
i++;
}
}
}
return prefixArray;
}16. Generate All Subsets of a String
Question: Write a Java function to generate all subsets of a string.
Answer:
javapublic static List<String> generateSubsets(String s) {
List<String> subsets = new ArrayList<>();
generateSubsetsHelper(s, 0, "", subsets);
return subsets;
}
private static void generateSubsetsHelper(String s, int index, String current, List<String> subsets) {
if (index == s.length()) {
subsets.add(current);
return;
}
generateSubsetsHelper(s, index + 1, current, subsets); // Exclude current character
generateSubsetsHelper(s, index + 1, current + s.charAt(index), subsets); // Include current character
}17. Minimum Window Substring
Question: Given two strings s and t, return the minimum window in s that contains all characters from t.
Answer:
javapublic static String minWindow(String s, String t) {
int[] tCount = new int[128];
for (char c : t.toCharArray()) {
tCount[c]++;
}
int left = 0, minLen = Integer.MAX_VALUE, minStart = 0, count = t.length();
for (int right = 0; right < s.length(); right++) {
if (tCount[s.charAt(right)] > 0) {
count--;
}
tCount[s.charAt(right)]--;
while (count == 0) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minStart = left;
}
tCount[s.charAt(left)]++;
if (tCount[s.charAt(left)] > 0) {
count++;
}
left++;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
}18. Group Anagrams
Question: Given an array of strings, group anagrams together.
Answer:
javapublic static List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> anagramGroups = new HashMap<>();
for (String str : strs) {
char[] charArray = str.toCharArray();
Arrays.sort(charArray);
String sortedStr = new String(charArray);
anagramGroups.computeIfAbsent(sortedStr, k -> new ArrayList<>()).add(str);
}
return new ArrayList<>(anagramGroups.values());
}19. Count and Say
Question: The count-and-say sequence is a series of strings where each string is the result of "saying" the previous string. Write a function to generate the nth string in the count-and-say sequence.
Answer:
javapublic static String countAndSay(int n) {
if (n == 1) {
return "1";
}
String previous = countAndSay(n - 1);
StringBuilder result = new StringBuilder();
char currentChar = previous.charAt(0);
int count = 1;
for (int i = 1; i < previous.length(); i++) {
if (previous.charAt(i) == currentChar) {
count++;
} else {
result.append(count).append(currentChar);
currentChar = previous.charAt(i);
count = 1;
}
}
result.append(count).append(currentChar);
return result.toString();
}20. Regular Expression Matching (Dynamic Programming)
Question: Implement regular expression matching with support for '.' and '*'. Use dynamic programming to optimize the solution.
Answer:
javapublic static boolean isMatchDP(String s, String p) {
int m = s.length(), n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 1; i <= n; i++) {
if (p.charAt(i - 1) == '*') {
dp[0][i] = dp[0][i - 2];
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '.') {
dp[i][j] = dp[i - 1][j - 1];
} else if (p.charAt(j - 1) == '*') {
dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.'));
}
}
}
return dp[m][n];
}These string-related interview questions and answers cover a range of topics and challenges that experienced Java developers might encounter during technical interviews. Make sure to understand the underlying concepts, practice coding, and adapt your solutions to different scenarios to excel in coding interviews.
Comments
Post a Comment