Common SDE and SDET Java Interview

FOR YOUR NEXT INTERVIEW

Lamhot Siagian
PhD Student • AI Engineer • Software Engineer • Software Testing • Interview Preparation
[Link]
[Link]
lamhotsiagian2025@[Link]
Founder of @[Link] (Helping 130K+ people improve their skills)
Instagram: [Link]

January 28, 2026

Contents

1 Numbers & Basics 1

1.1 1. Find Odd or Even . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 2. Check Prime Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 3. Fibonacci Series Up to N Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 4. Swap Two Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 5. Factorial of a Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.6 6. Reverse a Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.7 7. Armstrong Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.8 8. Count Digits in a Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.9 9. Palindrome Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.10 10. Sum of Digits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2 Strings 13
2.1 1. Reverse a String . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 2. Reverse Each Word in a Sentence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 3. Find Duplicate Characters in a String . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4 4. Count Occurrences of Each Word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5 5. Count Number of Words in a String . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6 6. All Permutations of a String . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.7 7. Check Palindrome String . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.8 8. Check Anagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.9 9. Count Vowels and Consonants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.10 10. Print Unique Characters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.11 11. Print Even Indexed Characters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.12 12. Remove Spaces from a String . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.13 13. Print Each Letter Twice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.14 14. Swap Two Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.15 15. Run-Length Encoding (aabbcccdd -> a2b2c3d2) . . . . . . . . . . . . . . . . . . . . 28
2.16 16. Separate Lowercase and Uppercase Letters . . . . . . . . . . . . . . . . . . . . . . . 29
2.17 17. Separate Alphabetic and Numeric Characters . . . . . . . . . . . . . . . . . . . . . . 30
2.18 18. Move All Zeros to the End (Digits Only) . . . . . . . . . . . . . . . . . . . . . . . . 31
2.19 19. Remove Zeros and Left-Pad with Zeros . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.20 20. Longest Substring Without Repeating Characters . . . . . . . . . . . . . . . . . . . 34

3 Arrays & Collections 36

3.1 1. Find Common Elements Between Two Arrays . . . . . . . . . . . . . . . . . . . . . . 36
3.2 2. Find First and Last Element of an ArrayList . . . . . . . . . . . . . . . . . . . . . . . 37
3.3 3. Sort an Array Without Using Built-in Methods . . . . . . . . . . . . . . . . . . . . . 38
3.4 4. Remove Duplicates from an Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

ii
CONTENTS iii

3.5 5. Remove Duplicates from an ArrayList . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3.6 6. Find Missing Number in 1..n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.7 7. Find Largest and Smallest Element in an Array . . . . . . . . . . . . . . . . . . . . . 43
3.8 8. Search Element in an Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.9 9. Sum Only Integers in a Mixed String Array . . . . . . . . . . . . . . . . . . . . . . . 45
3.10 10. Find Minimum and Maximum from an Array . . . . . . . . . . . . . . . . . . . . . . 46
3.11 11. Count Odd and Even Numbers in an Array . . . . . . . . . . . . . . . . . . . . . . . 47
3.12 12. Find Non-Repeated Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4 Java Fundamentals 50
4.1 1. Implement equals() and hashCode() . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

Notes 52
iv CONTENTS
 Chapter 1

Numbers & Basics

1.1 1. Find Odd or Even

Problem Statement
Given an integer n, print whether it is even or odd.

Example

Example: input 7 -> odd; input 10 -> even.

Brute-Force Solution
Use modulo: n mod 2. Time O(1).

1 import java . util . Scanner ;

2
3 public class P01 _OddEv en_Bru te {
4 public static void main ( String [] args ) {
5 Scanner sc = new Scanner ( System . in ) ;
6 System . out . print ( " Enter any number : " ) ;
7 int n = sc . nextInt () ;
8
9 if ( n % 2 == 0) {
10 System . out . println ( n + " is even . " ) ;
11 } else {
12 System . out . println ( n + " is odd . " ) ;
13 }
14 }
15 }

Best Solution
Use bitwise AND. This avoids modulo and is also O(1).

1 import java . util . Scanner ;

2
3 public class P01_OddEven_Best {
4 public static void main ( String [] args ) {

1
 2 CHAPTER 1. NUMBERS & BASICS

5 Scanner sc = new Scanner ( System . in ) ;

6 System . out . print ( " Enter any number : " ) ;
7 int n = sc . nextInt () ;
8
9 if ( ( n & 1) == 0 ) {
10 System . out . println ( n + " is even . " ) ;
11 } else {
12 System . out . println ( n + " is odd . " ) ;
13 }
14 }
15 }

1.2 2. Check Prime Number

Problem Statement
Given an integer n ≥ 0, determine if it is a prime number.

Example

Example: input 11 -> prime; input 12 -> not prime.

Brute-Force Solution
Try dividing by every integer from 2 to n − 1. Time O(n).

1 import java . util . Scanner ;

2

3 public class P02_Prime_Brute {

4 static boolean isPrime ( int n ) {
5 if ( n < 2) return false ;
6 for ( int d = 2; d <= n - 1; d ++) {
7 if ( n % d == 0) return false ;
8 }
9 return true ;
10 }
11
12 public static void main ( String [] args ) {
13 Scanner sc = new Scanner ( System . in ) ;
14 System . out . print ( " Enter a number : " ) ;
15 int n = sc . nextInt () ;
16 System . out . println ( n + ( isPrime ( n ) ? " is a prime number . " : " is not
a prime number . " ) ) ;
17 }
18 }

Best Solution
√ √
Only test divisors up to n (and skip even divisors after checking 2). Time O( n).
 1.3. 3. FIBONACCI SERIES UP TO N TERMS 3

1 import java . util . Scanner ;

2
3 public class P02_Prime_Best {
4 static boolean isPrime ( int n ) {
5 if ( n < 2) return false ;
6 if ( n == 2) return true ;
7 if ( n % 2 == 0) return false ;
8 for ( int d = 3; ( long ) d * d <= n ; d += 2) {
9 if ( n % d == 0) return false ;
10 }
11 return true ;
12 }
13

14 public static void main ( String [] args ) {

15 Scanner sc = new Scanner ( System . in ) ;
16 System . out . print ( " Enter a number : " ) ;
17 int n = sc . nextInt () ;
18 System . out . println ( n + ( isPrime ( n ) ? " is a prime number . " : " is not
a prime number . " ) ) ;
19 }
20 }

1.3 3. Fibonacci Series Up to N Terms

Problem Statement
Print the Fibonacci series for n terms (starting from 0, 1).

Example

Example: n=7 -> 0 1 1 2 3 5 8

Brute-Force Solution
Recursive definition is simple but slow: F (n) = F (n − 1) + F (n − 2) with exponential time.

1 import java . util . Scanner ;

2

3 public class P 0 3_ F i bo n a cc i _ Br u t e {
4 static long fib ( int n ) {
5 if ( n <= 1) return n ;
6 return fib ( n - 1) + fib ( n - 2) ;
7 }
8

9 public static void main ( String [] args ) {

10 Scanner sc = new Scanner ( System . in ) ;
11 System . out . print ( " Enter number of terms : " ) ;
12 int n = sc . nextInt () ;
13
14 for ( int i = 0; i < n ; i ++) {
15 System . out . print ( fib ( i ) + ( i + 1 < n ? " " : " " ) ) ;
 4 CHAPTER 1. NUMBERS & BASICS

16 }
17 System . out . println () ;
18 }
19 }

Best Solution
Iterate with two pointers. Time O(n), space O(1).

1 import java . util . Scanner ;

2
3 public class P 03_ Fi bo na cc i_ Be st {
4 public static void main ( String [] args ) {
5 Scanner sc = new Scanner ( System . in ) ;
6 System . out . print ( " Enter number of terms : " ) ;
7 int n = sc . nextInt () ;
8
9 long a = 0 , b = 1;
10 for ( int i = 0; i < n ; i ++) {
11 System . out . print ( a + ( i + 1 < n ? " " : " " ) ) ;
12 long next = a + b ;
13 a = b;
14 b = next ;
15 }
16 System . out . println () ;
17 }
18 }

1.4 4. Swap Two Numbers

Problem Statement
Swap two integers a and b.

Example

Example: a=5, b=10 -> after swap a=10, b=5.

Brute-Force Solution
Use a third temporary variable. Time O(1).

1 public class P04_Swap_Brute {

2 public static void main ( String [] args ) {
3 int a = 5;
4 int b = 10;
5
6 System . out . println ( " Before swapping : a = " + a + " , b = " + b ) ;
7 int temp = a ;
8 a = b;
 1.5. 5. FACTORIAL OF A NUMBER 5

9 b = temp ;
10 System . out . println ( " After swapping : a=" + a + ", b=" + b);
11 }
12 }

Best Solution
Swap without a third variable using XOR (avoids overflow). Time O(1).

1 public class P04_Swap_Best {

2 public static void main ( String [] args ) {
3 int a = 5;
4 int b = 10;
5
6 System . out . println ( " Before swapping : a = " + a + " , b = " + b ) ;
7 a = a ^ b;
8 b = a ^ b;
9 a = a ^ b;
10 System . out . println ( " After swapping : a = " + a + " , b = " + b ) ;
11 }
12 }

1.5 5. Factorial of a Number

Problem Statement
Compute n! = 1 · 2 · . . . · n.

Example

Example: 5! = 120.

Brute-Force Solution
Recursive factorial. Time O(n), but uses stack frames.

1 import java . util . Scanner ;

2
3 public class P 0 5_ F a ct o r ia l _ Br u t e {
4 static long fact ( int n ) {
5 if ( n < 0) throw new I l l e g a l A r g u m e n t E x c e p t i o n ( " n must be >= 0 " ) ;
6 if ( n == 0) return 1;
7 return n * fact ( n - 1) ;
8 }
9
10 public static void main ( String [] args ) {
11 Scanner sc = new Scanner ( System . in ) ;
12 System . out . print ( " Enter n : " ) ;
13 int n = sc . nextInt () ;
14 System . out . println ( n + " ! = " + fact ( n ) ) ;
 6 CHAPTER 1. NUMBERS & BASICS

15 }
16 }

Best Solution
Iterative factorial using BigInteger for large values. Time O(n), safer for bigger n.

1 import java . math . BigInteger ;

2 import java . util . Scanner ;
3
4 public class P 05_ Fa ct or ia l_ Be st {
5 static BigInteger fact ( int n ) {
6 if ( n < 0) throw new I l l e g a l A r g u m e n t E x c e p t i o n ( " n must be >= 0 " ) ;
7 BigInteger res = BigInteger . ONE ;
8 for ( int i = 2; i <= n ; i ++) {
9 res = res . multiply ( BigInteger . valueOf ( i ) ) ;
10 }
11 return res ;
12 }
13
14 public static void main ( String [] args ) {
15 Scanner sc = new Scanner ( System . in ) ;
16 System . out . print ( " Enter n : " ) ;
17 int n = sc . nextInt () ;
18 System . out . println ( n + " ! = " + fact ( n ) ) ;
19 }
20 }

1.6 6. Reverse a Number

Problem Statement
Given an integer n, output its digits reversed (e.g., 15786 → 68751).

Example

Example: input 15786 -> 68751.

Brute-Force Solution
Convert to string and reverse it. Time O(k) where k is number of digits.

1 import java . util . Scanner ;

2
3 public class P 0 6 _ R e v e r s e N u m b e r _ B r u t e {
4 public static void main ( String [] args ) {
5 Scanner sc = new Scanner ( System . in ) ;
6 System . out . print ( " Enter any number : " ) ;
7 long n = sc . nextLong () ;
8
 1.7. 7. ARMSTRONG NUMBER 7

9 String s = Long . toString ( Math . abs ( n ) ) ;

10 String reversed = new StringBuilder ( s ) . reverse () . toString () ;
11 if ( n < 0) reversed = " -" + reversed ;
12
13 System . out . println ( " Reverse : " + reversed ) ;
14 }
15 }

Best Solution
Reverse using math (mod/div). Time O(k), no string conversion.

1 import java . util . Scanner ;

2

3 public class P 0 6 _ R e v e r s e N u m b e r _ B e s t {
4 static long reverse ( long n ) {
5 long x = Math . abs ( n ) ;
6 long rev = 0;
7 while ( x > 0) {
8 rev = rev * 10 + ( x % 10) ;
9 x /= 10;
10 }
11 return n < 0 ? - rev : rev ;
12 }
13
14 public static void main ( String [] args ) {
15 Scanner sc = new Scanner ( System . in ) ;
16 System . out . print ( " Enter any number : " ) ;
17 long n = sc . nextLong () ;
18 System . out . println ( " Reverse : " + reverse ( n ) ) ;
19 }
20 }

1.7 7. Armstrong Number

Problem Statement
Check whether a number is an Armstrong number (e.g., 153 = 13 + 53 + 33 ).

Example

Example: 153 -> Armstrong; 154 -> Not Armstrong.

Brute-Force Solution
Convert to string, get digits, sum digitk . Time O(k).

1 import java . util . Scanner ;

2
3 public class P 0 7_ A r ms t r on g _ Br u t e {
 8 CHAPTER 1. NUMBERS & BASICS

4 static boolean isArmstrong ( int n ) {

5 String s = Integer . toString ( Math . abs ( n ) ) ;
6 int k = s . length () ;
7 int sum = 0;
8 for ( char ch : s . toCharArray () ) {
9 int d = ch - ’0 ’;
10 sum += Math . pow (d , k ) ;
11 }
12 return sum == Math . abs ( n ) ;
13 }
14
15 public static void main ( String [] args ) {
16 Scanner sc = new Scanner ( System . in ) ;
17 System . out . print ( " Enter a number : " ) ;
18 int n = sc . nextInt () ;
19 System . out . println ( isArmstrong ( n ) ? " Armstrong " : " Not Armstrong " ) ;
20 }
21 }

Best Solution
Use math (no string). Precompute powers for digits 0..9. Time O(k).

1 import java . util . Scanner ;

2

3 public class P 07_ Ar ms tr on g_ Be st {

4 static boolean isArmstrong ( int n ) {
5 int x = Math . abs ( n ) ;
6 int k = ( x == 0) ? 1 : ( int ) Math . floor ( Math . log10 ( x ) ) + 1;
7
8 int [] pow = new int [10];
9 for ( int d = 0; d <= 9; d ++) {
10 pow [ d ] = ( int ) Math . round ( Math . pow (d , k ) ) ;
11 }
12
13 int sum = 0;
14 int t = x ;
15 if ( t == 0) sum = pow [0];
16 while ( t > 0) {
17 sum += pow [ t % 10];
18 t /= 10;
19 }
20 return sum == x ;
21 }
22
23 public static void main ( String [] args ) {
24 Scanner sc = new Scanner ( System . in ) ;
25 System . out . print ( " Enter a number : " ) ;
26 int n = sc . nextInt () ;
27 System . out . println ( isArmstrong ( n ) ? " Armstrong " : " Not Armstrong " ) ;
28 }
29 }
 1.8. 8. COUNT DIGITS IN A NUMBER 9

1.8 8. Count Digits in a Number

Problem Statement
Given an integer n, count how many digits it has.

Example

Example: 1005 -> 4 digits.

Brute-Force Solution
Convert to string and take length. Time O(k).

1 import java . util . Scanner ;

2
3 public class P 0 8 _ C o u n t D i g i t s _ B r u t e {
4 public static void main ( String [] args ) {
5 Scanner sc = new Scanner ( System . in ) ;
6 System . out . print ( " Enter a number : " ) ;
7 long n = sc . nextLong () ;
8 String s = Long . toString ( Math . abs ( n ) ) ;
9 System . out . println ( " Digits : " + s . length () ) ;
10 }
11 }

Best Solution
Count by dividing by 10. Time O(k), no string conversion.

1 import java . util . Scanner ;

2
3 public class P 0 8 _ C o u n t D i g i t s _ B e s t {
4 static int countDigits ( long n ) {
5 long x = Math . abs ( n ) ;
6 if ( x == 0) return 1;
7 int count = 0;
8 while ( x > 0) {
9 count ++;
10 x /= 10;
11 }
12 return count ;
13 }
14
15 public static void main ( String [] args ) {
16 Scanner sc = new Scanner ( System . in ) ;
17 System . out . print ( " Enter a number : " ) ;
18 long n = sc . nextLong () ;
19 System . out . println ( " Digits : " + countDigits ( n ) ) ;
20 }
21 }
 10 CHAPTER 1. NUMBERS & BASICS

1.9 9. Palindrome Number

Problem Statement
Given an integer n, determine if it reads the same forward and backward (palindrome).

Example

Example: 121 -> Palindrome; 123 -> Not.

Brute-Force Solution
Convert to string and compare with reversed string. Time O(k).

1 import java . util . Scanner ;

2

3 public class P 0 9 _ P a l i n d r o m e N u m b e r _ B r u t e {
4 static boolean isPalindrome ( long n ) {
5 String s = Long . toString ( Math . abs ( n ) ) ;
6 String r = new StringBuilder ( s ) . reverse () . toString () ;
7 return s . equals ( r ) ;
8 }
9
10 public static void main ( String [] args ) {
11 Scanner sc = new Scanner ( System . in ) ;
12 System . out . print ( " Enter number : " ) ;
13 long n = sc . nextLong () ;
14 System . out . println ( isPalindrome ( n ) ? " Palindrome " : " Not Palindrome " ) ;
15 }
16 }

Best Solution
Reverse digits using math and compare. Time O(k).

1 import java . util . Scanner ;

2
3 public class P 0 9 _ P a l i n d r o m e N u m be r _ B e s t {
4 static boolean isPalindrome ( long n ) {
5 long x = Math . abs ( n ) ;
6 long original = x ;
7 long rev = 0;
8 while ( x > 0) {
9 rev = rev * 10 + ( x % 10) ;
10 x /= 10;
11 }
12 return original == rev ;
13 }
14
15 public static void main ( String [] args ) {
16 Scanner sc = new Scanner ( System . in ) ;
17 System . out . print ( " Enter number : " ) ;
18 long n = sc . nextLong () ;
 1.10. 10. SUM OF DIGITS 11

19 System . out . println ( isPalindrome ( n ) ? " Palindrome " : " Not Palindrome " ) ;
20 }
21 }

1.10 10. Sum of Digits

Problem Statement
Given an integer n, compute the sum of its digits (e.g., 1234 → 10).

Example

Example: 15786 -> 1+5+7+8+6 = 27.

Brute-Force Solution
Convert to string and sum characters. Time O(k).

1 import java . util . Scanner ;

2
3 public class P 1 0_ S u mD i g it s _ Br u t e {
4 static int sumDigits ( long n ) {
5 String s = Long . toString ( Math . abs ( n ) ) ;
6 int sum = 0;
7 for ( char ch : s . toCharArray () ) sum += ( ch - ’0 ’) ;
8 return sum ;
9 }
10
11 public static void main ( String [] args ) {
12 Scanner sc = new Scanner ( System . in ) ;
13 System . out . print ( " Enter number : " ) ;
14 long n = sc . nextLong () ;
15 System . out . println ( " Sum of digits : " + sumDigits ( n ) ) ;
16 }
17 }

Best Solution
Use modulo/division. Time O(k), no string conversion.

1 import java . util . Scanner ;

2
3 public class P 10_ Su mD ig it s_ Be st {
4 static int sumDigits ( long n ) {
5 long x = Math . abs ( n ) ;
6 int sum = 0;
7 while ( x > 0) {
8 sum += ( int ) ( x % 10) ;
9 x /= 10;
10 }
 12 CHAPTER 1. NUMBERS & BASICS

11 return sum ;
12 }
13
14 public static void main ( String [] args ) {
15 Scanner sc = new Scanner ( System . in ) ;
16 System . out . print ( " Enter number : " ) ;
17 long n = sc . nextLong () ;
18 System . out . println ( " Sum of digits : " + sumDigits ( n ) ) ;
19 }
20 }
 Chapter 2

Strings

2.1 1. Reverse a String

Problem Statement
Given a string s, print its reverse.

Example

Example: Automation -> noitamotuA.

Brute-Force Solution
Build reversed string by concatenation in a loop (can be O(n2 ) due to repeated allocations).

1 import java . util . Scanner ;

2
3 public class S 0 1 _ R e v e r s e S t r i n g _ B r u t e {
4 public static void main ( String [] args ) {
5 Scanner sc = new Scanner ( System . in ) ;
6 System . out . print ( " Enter a string : " ) ;
7 String input = sc . nextLine () ;
8
9 String reversed = " " ;
10 for ( int i = 0; i < input . length () ; i ++) {
11 reversed = input . charAt ( i ) + reversed ;
12 }
13 System . out . println ( " Reversed String is : " + reversed ) ;
14 }
15 }

Best Solution
Use StringBuilder which is linear time O(n).

1 import java . util . Scanner ;

2
3 public class S 0 1 _ R e v e r s e S t r i n g _ B e s t {
4 public static void main ( String [] args ) {

13
 14 CHAPTER 2. STRINGS

5 Scanner sc = new Scanner ( System . in ) ;

6 System . out . print ( " Enter a string : " ) ;
7 String input = sc . nextLine () ;
8
9 String reversed = new StringBuilder ( input ) . reverse () . toString () ;
10 System . out . println ( " Reversed String is : " + reversed ) ;
11 }
12 }

2.2 2. Reverse Each Word in a Sentence

Problem Statement
Given a sentence, reverse each word while keeping word order.

Example

Example: "Java is good" -> "avaJ si doog".

Brute-Force Solution
Split by spaces, reverse each word using a nested loop. Time O(n).

1 public class S 0 2 _ R e v e r s e E a c h W o rd _ B r u t e {
2 static String reverseWord ( String w ) {
3 String r = " " ;
4 for ( int i = 0; i < w . length () ; i ++) {
5 r = w . charAt ( i ) + r ;
6 }
7 return r ;
8 }
9
10 static String reverseEachWord ( String s ) {
11 String [] words = s . split ( " " ) ;
12 String out = " " ;
13 for ( String w : words ) out += reverseWord ( w ) + " " ;
14 return out . trim () ;
15 }
16

17 public static void main ( String [] args ) {

18 String input = " Java is good programming languages " ;
19 System . out . println ( input ) ;
20 System . out . println ( reverseEachWord ( input ) ) ;
21 }
22 }

Best Solution
Scan characters and reverse each word using a builder to avoid many string allocations.
 2.3. 3. FIND DUPLICATE CHARACTERS IN A STRING 15

1 public class S 0 2 _ R e v e r s e E a c h W o r d _ B e s t {
2 static String reverseEachWord ( String s ) {
3 StringBuilder out = new StringBuilder ( s . length () ) ;
4 int i = 0;
5 while ( i < s . length () ) {
6 // copy spaces
7 while ( i < s . length () && s . charAt ( i ) == ’ ’) {
8 out . append ( ’ ’) ;
9 i ++;
10 }
11 // reverse next word
12 int start = i ;
13 while ( i < s . length () && s . charAt ( i ) != ’ ’) i ++;
14 for ( int j = i - 1; j >= start ; j - -) out . append ( s . charAt ( j ) ) ;
15 }
16 return out . toString () ;
17 }
18
19 public static void main ( String [] args ) {
20 String input = " Java is good programming languages " ;
21 System . out . println ( input ) ;
22 System . out . println ( reverseEachWord ( input ) ) ;
23 }
24 }

2.3 3. Find Duplicate Characters in a String

Problem Statement
Given a string, print characters that appear more than once and their counts.

Example

Example: ’aabbc’ -> a->2, b->2.

Brute-Force Solution
For each character, count with a nested loop. Time O(n2 ).

1 import java . util . HashSet ;

2 import java . util . Set ;
3
4 public class S 0 3 _ D u p l i c a t e C h a r s _ B r u t e {
5 public static void main ( String [] args ) {
6 String s = " Learn Java Programming " ;
7 s = s . replace ( " " , " " ) ;
8 Set < Character > printed = new HashSet < >() ;
9
10 for ( int i = 0; i < s . length () ; i ++) {
11 char c = s . charAt ( i ) ;
12 if ( printed . contains ( c ) ) continue ;
13
 16 CHAPTER 2. STRINGS

14 int count = 0;
15 for ( int j = 0; j < s . length () ; j ++) {
16 if ( s . charAt ( j ) == c ) count ++;
17 }
18
19 if ( count > 1) {
20 System . out . println ( c + " -> " + count ) ;
21 printed . add ( c ) ;
22 }
23 }
24 }
25 }

Best Solution

Use a frequency map. Time O(n).

1 import java . util . HashMap ;

2 import java . util . Map ;
3
4 public class S 0 3 _ D u p l i c a t e C h a r s _ B e s t {
5 public static void main ( String [] args ) {
6 String s = " Learn Java Programming " ;
7 s = s . replace ( " " , " " ) ;
8
9 Map < Character , Integer > freq = new HashMap < >() ;
10 for ( char c : s . toCharArray () ) {
11 freq . put (c , freq . getOrDefault (c , 0) + 1) ;
12 }
13
14 for ( Map . Entry < Character , Integer > e : freq . entrySet () ) {
15 if ( e . getValue () > 1) {
16 System . out . println ( e . getKey () + " -> " + e . getValue () ) ;
17 }
18 }
19 }
20 }

2.4 4. Count Occurrences of Each Word

Problem Statement
Given a sentence, count how many times each word appears.

Example

Example output: {Java=1, Automation=2, Test=1}.

 2.4. 4. COUNT OCCURRENCES OF EACH WORD 17

Brute-Force Solution

For each word, count it by scanning all words. Time O(m2 ) where m is number of words.

1 import java . util . Arrays ;

2
3 public class S 0 4_ W o rd C o un t _ Br u t e {
4 public static void main ( String [] args ) {
5 String s = " Test Automation Java Automation " ;
6 String [] words = s . split ( " \\ s + " ) ;
7

8 boolean [] used = new boolean [ words . length ];

9
10 for ( int i = 0; i < words . length ; i ++) {
11 if ( used [ i ]) continue ;
12 int count = 1;
13 for ( int j = i + 1; j < words . length ; j ++) {
14 if ( words [ i ]. equals ( words [ j ]) ) {
15 count ++;
16 used [ j ] = true ;
17 }
18 }
19 System . out . println ( words [ i ] + " -> " + count ) ;
20 }
21 }
22 }

Best Solution

Use a HashMap. Time O(m).

1 import java . util . HashMap ;

2 import java . util . Map ;
3
4 public class S 04_ Wo rd Co un t_ Be st {
5 public static void main ( String [] args ) {
6 String s = " Test Automation Java Automation " ;
7 String [] words = s . split ( " \\ s + " ) ;
8

9 Map < String , Integer > count = new HashMap < >() ;
10 for ( String w : words ) {
11 count . put (w , count . getOrDefault (w , 0) + 1) ;
12 }
13
14 System . out . println ( count ) ;
15 }
16 }
 18 CHAPTER 2. STRINGS

2.5 5. Count Number of Words in a String

Problem Statement
Given a string, count the number of words (words are separated by spaces).

Example

Example: "Welcome to Java World" -> 4.

Brute-Force Solution
Split by whitespace and count tokens. Time O(n) (but regex can be heavier).

1 public class S 0 5 _ C o u n t W o r d s _ B r u t e {
2 public static void main ( String [] args ) {
3 String s = " Welcome to Java World " ;
4 String [] words = s . trim () . split ( " \\ s + " ) ;
5 System . out . println ( " Number of words : " + ( s . trim () . isEmpty () ? 0 :
words . length ) ) ;
6 }
7 }

Best Solution
Scan characters and count transitions from space to non-space. Time O(n), no regex.

1 public class S 0 5_ C o un t W or d s _B e s t {
2 static int countWords ( String s ) {
3 int count = 0;
4 boolean inWord = false ;
5 for ( int i = 0; i < s . length () ; i ++) {
6 char c = s . charAt ( i ) ;
7 if ( c != ’ ’ && ! inWord ) {
8 count ++;
9 inWord = true ;
10 } else if ( c == ’ ’) {
11 inWord = false ;
12 }
13 }
14 return count ;
15 }
16
17 public static void main ( String [] args ) {
18 String s = " Welcome to Java World " ;
19 System . out . println ( " Number of words : " + countWords ( s ) ) ;
20 }
21 }
 2.6. 6. ALL PERMUTATIONS OF A STRING 19

2.6 6. All Permutations of a String

Problem Statement
Print all permutations of a string (e.g., abc → abc, acb, bac, bca, cab, cba).

Example

abc, acb, bac, bca, cab, cba.

Brute-Force Solution
Simple recursion using substring concatenation. Works but creates many substrings.

1 public class S 0 6 _ P e r m u t a t i o n s _ B r u t e {
2 static void permute ( String s , String prefix ) {
3 if ( s . length () == 0) {
4 System . out . println ( prefix ) ;
5 return ;
6 }
7 for ( int i = 0; i < s . length () ; i ++) {
8 String rem = s . substring (0 , i ) + s . substring ( i + 1) ;
9 permute ( rem , prefix + s . charAt ( i ) ) ;
10 }
11 }
12
13 public static void main ( String [] args ) {
14 permute ( " abc " , " " ) ;
15 }
16 }

Best Solution
Use a char array and swap in-place (avoids substring overhead).

1 public class S 0 6 _ P e r m u t a t i o n s _ B e s t {
2 static void permute ( char [] a , int idx ) {
3 if ( idx == a . length ) {
4 System . out . println ( new String ( a ) ) ;
5 return ;
6 }
7 for ( int i = idx ; i < a . length ; i ++) {
8 swap (a , idx , i ) ;
9 permute (a , idx + 1) ;
10 swap (a , idx , i ) ;
11 }
12 }
13
14 static void swap ( char [] a , int i , int j ) {
15 char t = a [ i ]; a [ i ] = a [ j ]; a [ j ] = t ;
16 }
17
18 public static void main ( String [] args ) {
 20 CHAPTER 2. STRINGS

19 permute ( " abc " . toCharArray () , 0) ;

20 }
21 }

2.7 7. Check Palindrome String

Problem Statement
Given a string, determine if it is a palindrome.

Example

madam -> true.

Brute-Force Solution
Reverse the string and compare. Time O(n), extra space O(n).

1 public class S 0 7 _ P a l i n d r o m e S t r i n g _ B r u t e {
2 static boolean isPalindrome ( String s ) {
3 String r = new StringBuilder ( s ) . reverse () . toString () ;
4 return s . equals ( r ) ;
5 }
6
7 public static void main ( String [] args ) {
8 System . out . println ( isPalindrome ( " madam " ) ) ; // true
9 System . out . println ( isPalindrome ( " hello " ) ) ; // false
10 }
11 }

Best Solution
Two pointers from both ends. Time O(n), space O(1).

1 public class S 0 7 _ P a l i n d r o m e S t r in g _ B e s t {
2 static boolean isPalindrome ( String s ) {
3 int i = 0 , j = s . length () - 1;
4 while ( i < j ) {
5 if ( s . charAt ( i ) != s . charAt ( j ) ) return false ;
6 i ++; j - -;
7 }
8 return true ;
9 }
10
11 public static void main ( String [] args ) {
12 System . out . println ( isPalindrome ( " madam " ) ) ; // true
13 System . out . println ( isPalindrome ( " hello " ) ) ; // false
14 }
15 }
 2.8. 8. CHECK ANAGRAMS 21

2.8 8. Check Anagrams

Problem Statement
Given two strings, determine if they are anagrams (same characters with same frequencies).

Example

listen vs silent -> true.

Brute-Force Solution
Sort both strings and compare. Time O(n log n).

1 import java . util . Arrays ;

2
3 public class S 08_ An ag ra ms _B ru te {
4 static boolean areAnagrams ( String a , String b ) {
5 if ( a . length () != b . length () ) return false ;
6 char [] x = a . toCharArray () ;
7 char [] y = b . toCharArray () ;
8 Arrays . sort ( x ) ;
9 Arrays . sort ( y ) ;
10 return Arrays . equals (x , y ) ;
11 }
12
13 public static void main ( String [] args ) {
14 System . out . println ( areAnagrams ( " listen " , " silent " ) ) ; // true
15 }
16 }

Best Solution
Count character frequencies (ASCII). Time O(n).

1 public class S08 _Anagr ams_Be st {

2 static boolean areAnagrams ( String a , String b ) {
3 if ( a . length () != b . length () ) return false ;
4 int [] freq = new int [256];
5 for ( int i = 0; i < a . length () ; i ++) {
6 freq [ a . charAt ( i ) ]++;
7 freq [ b . charAt ( i ) ] - -;
8 }
9 for ( int v : freq ) if ( v != 0) return false ;
10 return true ;
11 }
12
13 public static void main ( String [] args ) {
14 System . out . println ( areAnagrams ( " listen " , " silent " ) ) ; // true
15 System . out . println ( areAnagrams ( " hello " , " world " ) ) ; // false
 22 CHAPTER 2. STRINGS

16 }
17 }

2.9 9. Count Vowels and Consonants

Problem Statement
Given a string, count how many vowels and consonants it contains (letters only).

Example

Hello World -> Vowels=3, Consonants=7.

Brute-Force Solution
Check each letter against a vowel list. Time O(n).

1 public class S 0 9 _ V o w e l s C o n s o n a n t s _ B r u t e {
2 static void count ( String s ) {
3 int v = 0 , c = 0;
4 s = s . toLowerCase () ;
5 for ( char ch : s . toCharArray () ) {
6 if ( ch >= ’a ’ && ch <= ’z ’) {
7 if ( ch == ’a ’ || ch == ’e ’ || ch == ’i ’ || ch == ’o ’ || ch == ’u ’) v ++;
8 else c ++;
9 }
10 }
11 System . out . println ( " Vowels : " + v ) ;
12 System . out . println ( " Consonants : " + c ) ;
13 }
14
15 public static void main ( String [] args ) {
16 count ( " Hello World " ) ;
17 }
18 }

Best Solution
Same one-pass scan; just written cleanly with a helper for readability. Time O(n).

1 public class S 0 9 _ V o w e l s C o n s o n a nt s _ B e s t {
2 static boolean isVowel ( char ch ) {
3 return ch == ’a ’ || ch == ’e ’ || ch == ’i ’ || ch == ’o ’ || ch == ’u ’;
4 }
5
6 static void count ( String s ) {
7 int v = 0 , c = 0;
8 s = s . toLowerCase () ;
9 for ( int i = 0; i < s . length () ; i ++) {
10 char ch = s . charAt ( i ) ;
 2.10. 10. PRINT UNIQUE CHARACTERS 23

11 if ( ch < ’a ’ || ch > ’z ’) continue ;

12 if ( isVowel ( ch ) ) v ++; else c ++;
13 }
14 System . out . println ( " Vowels : " + v ) ;
15 System . out . println ( " Consonants : " + c ) ;
16 }
17

18 public static void main ( String [] args ) {

19 count ( " Hello World " ) ;
20 }
21 }

2.10 10. Print Unique Characters

Problem Statement
Given a string, print each character only once (first occurrence order).

Example

Example: Java Automation -> J a v A u t o m i n (spaces are also chars).

Brute-Force Solution
For each char, check whether it appeared earlier (nested loop). Time O(n2 ).

1 public class S 1 0 _ U n i q u e C h a r s _ B r u t e {
2 static void printUnique ( String s ) {
3 for ( int i = 0; i < s . length () ; i ++) {
4 char c = s . charAt ( i ) ;
5 boolean seenBefore = false ;
6 for ( int j = 0; j < i ; j ++) {
7 if ( s . charAt ( j ) == c ) { seenBefore = true ; break ; }
8 }
9 if (! seenBefore ) System . out . print ( c + " " ) ;
10 }
11 System . out . println () ;
12 }
13
14 public static void main ( String [] args ) {
15 printUnique ( " Java Automation " ) ;
16 }
17 }

Best Solution
Use a boolean array (ASCII). Time O(n).

1 public class S 1 0 _ U n i q u e C h a r s _ B e s t {
2 static void printUnique ( String s ) {
 24 CHAPTER 2. STRINGS

3 boolean [] seen = new boolean [256];

4 for ( int i = 0; i < s . length () ; i ++) {
5 char c = s . charAt ( i ) ;
6 if (! seen [ c ]) {
7 seen [ c ] = true ;
8 System . out . print ( c + " " ) ;
9 }
10 }
11 System . out . println () ;
12 }
13
14 public static void main ( String [] args ) {
15 printUnique ( " Java Automation " ) ;
16 }
17 }

2.11 11. Print Even Indexed Characters

Problem Statement
Given a string s, print the characters at even indices (0,2,4,...).

Example

Automation -> Atmto.

Brute-Force Solution
Loop all indices and check i mod 2 == 0. Time O(n).

1 public class S 1 1 _ E v e n I n d e x e d _ B r u t e {
2 public static void main ( String [] args ) {
3 String s = " Automation " ;
4 for ( int i = 0; i < s . length () ; i ++) {
5 if ( i % 2 == 0) System . out . print ( s . charAt ( i ) ) ;
6 }
7 System . out . println () ;
8 }
9 }

Best Solution
Step by 2 directly. Time O(n) but fewer operations.

1 public class S 1 1 _ E v e n I n d e x e d _ B e s t {
2 public static void main ( String [] args ) {
3 String s = " Automation " ;
4 for ( int i = 0; i < s . length () ; i += 2) {
5 System . out . print ( s . charAt ( i ) ) ;
6 }
 2.12. 12. REMOVE SPACES FROM A STRING 25

7 System . out . println () ;

8 }
9 }

2.12 12. Remove Spaces from a String

Problem Statement
Given a string, remove all space characters.

Example

Welcome to Java World -> WelcometoJavaWorld.

Brute-Force Solution

Use replaceAll with a regex. Simple but regex adds overhead.

1 public class S 1 2 _ R e m o v e S p a c e s _ B r u t e {
2 public static void main ( String [] args ) {
3 String s = " Welcome to Java World " ;
4 System . out . println ( s . replaceAll ( " \\ s + " , " " ) ) ;
5 }
6 }

Best Solution

Scan once and build output with StringBuilder. Time O(n).

1 public class S 1 2 _ R e m o v e S p a c e s _ B e s t {
2 static String removeSpaces ( String s ) {
3 StringBuilder out = new StringBuilder ( s . length () ) ;
4 for ( int i = 0; i < s . length () ; i ++) {
5 char c = s . charAt ( i ) ;
6 if ( c != ’ ’) out . append ( c ) ;
7 }
8 return out . toString () ;
9 }
10
11 public static void main ( String [] args ) {
12 String s = " Welcome to Java World " ;
13 System . out . println ( removeSpaces ( s ) ) ;
14 }
15 }
 26 CHAPTER 2. STRINGS

2.13 13. Print Each Letter Twice

Problem Statement
Given a string, output a new string where each character is repeated twice (hello → hheelllloo).

Example

hello -> hheelllloo.

Brute-Force Solution

Concatenate into a string in a loop (can be O(n2 )).

1 public class S 1 3 _ D o u b l e C h a r s _ B r u t e {
2 static String doubleChars ( String s ) {
3 String out = " " ;
4 for ( int i = 0; i < s . length () ; i ++) {
5 out += " " + s . charAt ( i ) + s . charAt ( i ) ;
6 }
7 return out ;
8 }
9
10 public static void main ( String [] args ) {
11 System . out . println ( doubleChars ( " hello " ) ) ;
12 }
13 }

Best Solution

Use StringBuilder with capacity 2n. Time O(n).

1 public class S 1 3 _ D o u b l e C h a r s _ B e s t {
2 static String doubleChars ( String s ) {
3 StringBuilder out = new StringBuilder ( s . length () * 2) ;
4 for ( int i = 0; i < s . length () ; i ++) {
5 char c = s . charAt ( i ) ;
6 out . append ( c ) . append ( c ) ;
7 }
8 return out . toString () ;
9 }
10
11 public static void main ( String [] args ) {
12 System . out . println ( doubleChars ( " hello " ) ) ;
13 }
14 }
 2.14. 14. SWAP TWO STRINGS 27

2.14 14. Swap Two Strings

Problem Statement
Swap two strings str1 and str2.

Example

Hello, World -> swap -> World, Hello.

Brute-Force Solution

Swap using a temporary variable. Time O(1).

1 public class S 1 4 _ S w a p S t r i n g s _ B r u t e {
2 public static void main ( String [] args ) {
3 String str1 = " Hello " ;
4 String str2 = " World " ;
5

6 System . out . println ( " Before : str1 = " + str1 + " , str2 = " + str2 ) ;
7 String temp = str1 ;
8 str1 = str2 ;
9 str2 = temp ;
10 System . out . println ( " After : str1 = " + str1 + " , str2 = " + str2 ) ;
11 }
12 }

Best Solution

Swap without a third variable by concatenation + substring. Time O(n) due to string copies.

1 public class S 1 4 _ S w a p S t r i n g s _ B e s t {
2 public static void main ( String [] args ) {
3 String str1 = " Hello " ;
4 String str2 = " World " ;
5
6 System . out . println ( " Before : str1 = " + str1 + " , str2 = " + str2 ) ;
7
8 str1 = str1 + str2 ; // " HelloWorld "
9 str2 = str1 . substring (0 , str1 . length () - str2 . length () ) ; // " Hello "
10 str1 = str1 . substring ( str2 . length () ) ; // " World "
11
12 System . out . println ( " After : str1 = " + str1 + " , str2 = " + str2 ) ;
13 }
14 }
 28 CHAPTER 2. STRINGS

2.15 15. Run-Length Encoding (aabbcccdd -> a2b2c3d2)

Problem Statement
Given a string like aabbcccdd, produce a2b2c3d2 (character followed by its consecutive count).

Example

aabbcccdd -> a2b2c3d2.

Brute-Force Solution
Brute-force by counting each character’s run with nested checks (or repeatedly scanning).

1 public class S15_RLE_Brute {

2 static String encode ( String s ) {
3 String out = " " ;
4 int i = 0;
5 while ( i < s . length () ) {
6 char c = s . charAt ( i ) ;
7 int count = 0;
8 // scan run
9 while ( i < s . length () && s . charAt ( i ) == c ) {
10 count ++;
11 i ++;
12 }
13 out += " " + c + count ; // concatenation can make it O ( n ^2)
14 }
15 return out ;
16 }
17
18 public static void main ( String [] args ) {
19 System . out . println ( encode ( " aabbcccdd " ) ) ;
20 }
21 }

Best Solution
One pass with StringBuilder. Time O(n).

1 public class S15_RLE_Best {

2 static String encode ( String s ) {
3 if ( s . isEmpty () ) return " " ;
4 StringBuilder out = new StringBuilder () ;
5 int count = 1;
6

7 for ( int i = 0; i < s . length () ; i ++) {

8 if ( i + 1 < s . length () && s . charAt ( i ) == s . charAt ( i + 1) ) {
9 count ++;
10 } else {
11 out . append ( s . charAt ( i ) ) . append ( count ) ;
12 count = 1;
13 }
 2.16. 16. SEPARATE LOWERCASE AND UPPERCASE LETTERS 29

14 }
15 return out . toString () ;
16 }
17
18 public static void main ( String [] args ) {
19 System . out . println ( encode ( " aabbcccdd " ) ) ;
20 }
21 }

2.16 16. Separate Lowercase and Uppercase Letters

Problem Statement
Given a string, output two strings: (1) all lowercase letters, (2) all uppercase letters.

Example

Input: aBACbcEDed -> Lowercase: abced; Uppercase: BACED (depending on order).

Brute-Force Solution
Two passes: first collect lowercase, then uppercase. Time O(n).

1 public class S 1 6 _ S e p a r a t e C a s e _ B r u t e {
2 static String lowerOnly ( String s ) {
3 String out = " " ;
4 for ( int i = 0; i < s . length () ; i ++) {
5 char c = s . charAt ( i ) ;
6 if ( Character . isLowerCase ( c ) ) out += c ;
7 }
8 return out ;
9 }
10

11 static String upperOnly ( String s ) {

12 String out = " " ;
13 for ( int i = 0; i < s . length () ; i ++) {
14 char c = s . charAt ( i ) ;
15 if ( Character . isUpperCase ( c ) ) out += c ;
16 }
17 return out ;
18 }
19
20 public static void main ( String [] args ) {
21 String s = " aBACbcEDed " ;
22 System . out . println ( " Lowercase : " + lowerOnly ( s ) ) ;
23 System . out . println ( " Uppercase : " + upperOnly ( s ) ) ;
24 }
25 }
 30 CHAPTER 2. STRINGS

Best Solution
One pass with two builders. Time O(n), fewer allocations.

1 public class S 1 6 _ S e p a r a t e C a s e _ B e s t {
2 static void separate ( String s ) {
3 StringBuilder lower = new StringBuilder () ;
4 StringBuilder upper = new StringBuilder () ;
5
6 for ( int i = 0; i < s . length () ; i ++) {
7 char c = s . charAt ( i ) ;
8 if ( Character . isLowerCase ( c ) ) lower . append ( c ) ;
9 else if ( Character . isUpperCase ( c ) ) upper . append ( c ) ;
10 }
11
12 System . out . println ( " Lowercase : " + lower ) ;
13 System . out . println ( " Uppercase : " + upper ) ;
14 }
15
16 public static void main ( String [] args ) {
17 separate ( " aBACbcEDed " ) ;
18 }
19 }

2.17 17. Separate Alphabetic and Numeric Characters

Problem Statement
Given a string like Subbu123raj, output alphabetic part Subburaj and numeric part 123.

Example

Subbu123raj -> Subburaj and 123.

Brute-Force Solution
Use two passes: one for letters, one for digits. Time O(n).

1 public class S 1 7 _ S e p a r a t e A l p h a N u m e r i c _ B r u t e {
2 static String letters ( String s ) {
3 String out = " " ;
4 for ( int i = 0; i < s . length () ; i ++) {
5 char c = s . charAt ( i ) ;
6 if ( Character . isLetter ( c ) ) out += c ;
7 }
8 return out ;
9 }
10
11 static String digits ( String s ) {
12 String out = " " ;
13 for ( int i = 0; i < s . length () ; i ++) {
14 char c = s . charAt ( i ) ;
 2.18. 18. MOVE ALL ZEROS TO THE END (DIGITS ONLY) 31

15 if ( Character . isDigit ( c ) ) out += c ;

16 }
17 return out ;
18 }
19
20 public static void main ( String [] args ) {
21 String s = " Subbu123raj " ;
22 System . out . println ( " Alpha : " + letters ( s ) ) ;
23 System . out . println ( " Numeric : " + digits ( s ) ) ;
24 }
25 }

Best Solution
One pass using two builders. Time O(n).

1 public class S 1 7 _ S e p a r a t e A l p h a N u m e r i c _ B e s t {
2 static void separate ( String s ) {
3 StringBuilder alpha = new StringBuilder () ;
4 StringBuilder numeric = new StringBuilder () ;
5 for ( int i = 0; i < s . length () ; i ++) {
6 char c = s . charAt ( i ) ;
7 if ( Character . isLetter ( c ) ) alpha . append ( c ) ;
8 else if ( Character . isDigit ( c ) ) numeric . append ( c ) ;
9 }
10 System . out . println ( " Alpha : " + alpha ) ;
11 System . out . println ( " Numeric : " + numeric ) ;
12 }
13

14 public static void main ( String [] args ) {

15 separate ( " Subbu123raj " ) ;
16 }
17 }

2.18 18. Move All Zeros to the End (Digits Only)

Problem Statement
Given a digit string (e.g., 32400121200), move all 0 digits to the end while preserving the order
of non-zero digits.

Example
32400121200 -> 32412120000.

Brute-Force Solution
Brute-force by repeatedly swapping adjacent zeros to the right (bubble-like). Time O(n2 ).

1 public class S 1 8 _ M o v e Z e r o s E n d _ B r u t e {
 32 CHAPTER 2. STRINGS

2 static String moveZeros ( String s ) {

3 char [] a = s . toCharArray () ;
4 // bubble zeros to the right
5 for ( int pass = 0; pass < a . length ; pass ++) {
6 for ( int i = 0; i + 1 < a . length ; i ++) {
7 if ( a [ i ] == ’0 ’ && a [ i + 1] != ’0 ’) {
8 char t = a [ i ]; a [ i ] = a [ i + 1]; a [ i + 1] = t ;
9 }
10 }
11 }
12 return new String ( a ) ;
13 }
14

15 public static void main ( String [] args ) {

16 System . out . println ( moveZeros ( " 32400121200 " ) ) ; // 32412120000
17 }
18 }

Best Solution

Stable partition in one pass: build non-zeros then append zeros. Time O(n).

1 public class S 1 8 _ M o v e Z e r o s E n d _ B e s t {
2 static String moveZeros ( String s ) {
3 StringBuilder nonZero = new StringBuilder ( s . length () ) ;
4 int zeros = 0;
5
6 for ( int i = 0; i < s . length () ; i ++) {
7 char c = s . charAt ( i ) ;
8 if ( c == ’0 ’) zeros ++;
9 else nonZero . append ( c ) ;
10 }
11 for ( int i = 0; i < zeros ; i ++) nonZero . append ( ’0 ’) ;
12 return nonZero . toString () ;
13 }
14
15 public static void main ( String [] args ) {
16 System . out . println ( moveZeros ( " 32400121200 " ) ) ; // 32412120000
17 }
18 }

2.19 19. Remove Zeros and Left-Pad with Zeros

Problem Statement
Given a digit string 32400121200, remove all internal zeros to form 3241212, then left-pad with
zeros to match the original length, producing 00003241212.
 2.19. 19. REMOVE ZEROS AND LEFT-PAD WITH ZEROS 33

Example
32400121200 -> 00003241212.

Brute-Force Solution

Brute-force: remove zeros, then pad in a loop. Time O(n).

1 public class S 1 9 _ R e m o v e Z e r o s P a d L e f t _ B r u t e {
2 static String transform ( String s ) {
3 String noZeros = " " ;
4 for ( int i = 0; i < s . length () ; i ++) {
5 char c = s . charAt ( i ) ;
6 if ( c != ’0 ’) noZeros += c ; // can be O ( n ^2) due to concatenation
7 }
8 while ( noZeros . length () < s . length () ) {
9 noZeros = " 0 " + noZeros ;
10 }
11 return noZeros ;
12 }
13
14 public static void main ( String [] args ) {
15 System . out . println ( transform ( " 32400121200 " ) ) ; // 00003241212
16 }
17 }

Best Solution

Use builders for linear time. Time O(n).

1 public class S 1 9 _ R e m o v e Z e r o s P a d L e f t _ B e s t {
2 static String transform ( String s ) {
3 StringBuilder digits = new StringBuilder ( s . length () ) ;
4 for ( int i = 0; i < s . length () ; i ++) {
5 char c = s . charAt ( i ) ;
6 if ( c != ’0 ’) digits . append ( c ) ;
7 }
8
9 int pad = s . length () - digits . length () ;
10 StringBuilder out = new StringBuilder ( s . length () ) ;
11 for ( int i = 0; i < pad ; i ++) out . append ( ’0 ’) ;
12 out . append ( digits ) ;
13 return out . toString () ;
14 }
15
16 public static void main ( String [] args ) {
17 System . out . println ( transform ( " 32400121200 " ) ) ; // 00003241212
18 }
19 }
 34 CHAPTER 2. STRINGS

2.20 20. Longest Substring Without Repeating Characters

Problem Statement
Given a string s, return the length of the longest substring without repeating characters.

Example

abcabcbb -> 3; bbbbb -> 1; pwwkew -> 3; empty -> 0.

Brute-Force Solution
Try every start index and extend until a repeat occurs. Worst-case O(n2 ).

1 import java . util . HashSet ;

2

3 public class S 2 0 _ L o n g e s t U n i q u e S u b s t r i n g _ B r u t e {
4 static int l e n g t h O f L o n g e s t S u b s t r i n g ( String s ) {
5 int best = 0;
6 for ( int i = 0; i < s . length () ; i ++) {
7 HashSet < Character > seen = new HashSet < >() ;
8 for ( int j = i ; j < s . length () ; j ++) {
9 char c = s . charAt ( j ) ;
10 if ( seen . contains ( c ) ) break ;
11 seen . add ( c ) ;
12 best = Math . max ( best , j - i + 1) ;
13 }
14 }
15 return best ;
16 }
17
18 public static void main ( String [] args ) {
19 System . out . println ( l e n g t h O f L o n g e s t S u b s t r i n g ( " abcabcbb " ) ) ; // 3
20 System . out . println ( l e n g t h O f L o n g e s t S u b s t r i n g ( " bbbbb " ) ) ; // 1
21 System . out . println ( l e n g t h O f L o n g e s t S u b s t r i n g ( " pwwkew " ) ) ; // 3
22 System . out . println ( l e n g t h O f L o n g e s t S u b s t r i n g ( " " ) ) ; // 0
23 }
24 }

Best Solution
Sliding window with last-seen index. Time O(n).

1 import java . util . Arrays ;

2
3 public class S 2 0 _ L o n g e s t U n i q u e S u b s t r i n g _ B e s t {
4 static int l e n g t h O f L o n g e s t S u b s t r i n g ( String s ) {
5 int [] last = new int [256];
6 Arrays . fill ( last , -1) ;
7
8 int best = 0;
9 int left = 0;
10 for ( int right = 0; right < s . length () ; right ++) {
 2.20. 20. LONGEST SUBSTRING WITHOUT REPEATING CHARACTERS 35

11 char c = s . charAt ( right ) ;

12 int prev = last [ c ];
13 if ( prev >= left ) left = prev + 1;
14 last [ c ] = right ;
15 best = Math . max ( best , right - left + 1) ;
16 }
17 return best ;
18 }
19
20 public static void main ( String [] args ) {
21 System . out . println ( l e n g t h O f L o n g e s t S u b s t r i n g ( " abcabcbb " ) ) ; // 3
22 System . out . println ( l e n g t h O f L o n g e s t S u b s t r i n g ( " bbbbb " ) ) ; // 1
23 System . out . println ( l e n g t h O f L o n g e s t S u b s t r i n g ( " pwwkew " ) ) ; // 3
24 System . out . println ( l e n g t h O f L o n g e s t S u b s t r i n g ( " " ) ) ; // 0
25 }
26 }
 Chapter 3

Arrays & Collections

3.1 1. Find Common Elements Between Two Arrays

Problem Statement
Given two integer arrays, return the set of common elements.

Example

array1={1,2,3,4,5}, array2={4,5,6,7,8} -> [4,5].

Brute-Force Solution
Brute-force: for each element in array1, scan array2. Time O(nm).

1 import java . util . HashSet ;

2 import java . util . Set ;
3
4 public class A 0 1 _ C o m m o n E l e m e n t s _ B r u t e {
5 static Set < Integer > common ( int [] a , int [] b ) {
6 Set < Integer > res = new HashSet < >() ;
7 for ( int x : a ) {
8 for ( int y : b ) {
9 if ( x == y ) {
10 res . add ( x ) ;
11 break ;
12 }
13 }
14 }
15 return res ;
16 }
17
18 public static void main ( String [] args ) {
19 int [] a = {1 ,2 ,3 ,4 ,5};
20 int [] b = {4 ,5 ,6 ,7 ,8};
21 System . out . println ( common (a , b ) ) ; // [4 , 5]
22 }
23 }

36
 3.2. 2. FIND FIRST AND LAST ELEMENT OF AN ARRAYLIST 37

Best Solution
Best: put one array in a set, then scan the other. Time O(n + m).

1 import java . util . HashSet ;

2 import java . util . Set ;
3
4 public class A 0 1 _ C o m m o n E l e m e n t s _ B e s t {
5 static Set < Integer > common ( int [] a , int [] b ) {
6 Set < Integer > set = new HashSet < >() ;
7 for ( int x : a ) set . add ( x ) ;
8
9 Set < Integer > res = new HashSet < >() ;
10 for ( int y : b ) if ( set . contains ( y ) ) res . add ( y ) ;
11 return res ;
12 }
13
14 public static void main ( String [] args ) {
15 int [] a = {1 ,2 ,3 ,4 ,5};
16 int [] b = {4 ,5 ,6 ,7 ,8};
17 System . out . println ( common (a , b ) ) ; // [4 , 5]
18 }
19 }

3.2 2. Find First and Last Element of an ArrayList

Problem Statement
Given an ArrayList, print its first and last elements.

Example

Output: First element: Apple; Last element: Elderberry (per PDF example).

Brute-Force Solution
Brute-force: loop to the last element. Time O(n).

1 import java . util . ArrayList ;

2
3 public class A 0 2_ F i rs t L as t _ Br u t e {
4 public static void main ( String [] args ) {
5 ArrayList < String > list = new ArrayList < >() ;
6 list . add ( " Apple " ) ;
7 list . add ( " Banana " ) ;
8 list . add ( " Cherry " ) ;
9
10 if ( list . isEmpty () ) {
11 System . out . println ( " Empty list " ) ;
12 return ;
13 }
14
 38 CHAPTER 3. ARRAYS & COLLECTIONS

15 String first = list . get (0) ;

16 String last = null ;
17 for ( String s : list ) last = s ;
18
19 System . out . println ( " First : " + first ) ;
20 System . out . println ( " Last : " + last ) ;
21 }
22 }

Best Solution
Best: direct indexing with size()-1. Time O(1).

1 import java . util . ArrayList ;

2
3 public class A 02_ Fi rs tL as t_ Be st {
4 public static void main ( String [] args ) {
5 ArrayList < String > list = new ArrayList < >() ;
6 list . add ( " Apple " ) ;
7 list . add ( " Banana " ) ;
8 list . add ( " Cherry " ) ;
9
10 if ( list . isEmpty () ) {
11 System . out . println ( " Empty list " ) ;
12 return ;
13 }
14
15 System . out . println ( " First : " + list . get (0) ) ;
16 System . out . println ( " Last : " + list . get ( list . size () - 1) ) ;
17 }
18 }

3.3 3. Sort an Array Without Using Built-in Methods

Problem Statement
Sort an integer array without using built-in sort.

Example

Input: {5,2,9,1,6} -> 1 2 5 6 9.

Brute-Force Solution
Bubble sort. Time O(n2 ).

1 public class A03_Sort_Brute {

2 static void bubbleSort ( int [] a ) {
3 for ( int pass = 0; pass < a . length ; pass ++) {
4 for ( int i = 0; i + 1 < a . length ; i ++) {
 3.4. 4. REMOVE DUPLICATES FROM AN ARRAY 39

5 if ( a [ i ] > a [ i + 1]) {
6 int t = a [ i ]; a [ i ] = a [ i + 1]; a [ i + 1] = t ;
7 }
8 }
9 }
10 }
11

12 public static void main ( String [] args ) {

13 int [] a = {5 ,2 ,9 ,1 ,6};
14 bubbleSort ( a ) ;
15 for ( int x : a ) System . out . print ( x + " " ) ;
16 System . out . println () ;
17 }
18 }

Best Solution

Selection sort (still O(n2 ), but fewer swaps).

1 public class A03_Sort_Best {

2 static void selectionSort ( int [] a ) {
3 for ( int i = 0; i < a . length - 1; i ++) {
4 int min = i ;
5 for ( int j = i + 1; j < a . length ; j ++) {
6 if ( a [ j ] < a [ min ]) min = j ;
7 }
8 int t = a [ i ]; a [ i ] = a [ min ]; a [ min ] = t ;
9 }
10 }
11
12 public static void main ( String [] args ) {
13 int [] a = {5 ,2 ,9 ,1 ,6};
14 selectionSort ( a ) ;
15 for ( int x : a ) System . out . print ( x + " " ) ;
16 System . out . println () ;
17 }
18 }

3.4 4. Remove Duplicates from an Array

Problem Statement
Given an integer array, remove duplicates.

Example

Example -> duplicates removed.

 40 CHAPTER 3. ARRAYS & COLLECTIONS

Brute-Force Solution
Brute-force: nested loop and build a unique list manually. Time O(n2 ).

1 import java . util . ArrayList ;

2 import java . util . List ;
3
4 public class A 0 4 _ R e m o v e D u p A r r a y _ B r u t e {
5 static int [] unique ( int [] a ) {
6 List < Integer > res = new ArrayList < >() ;
7 for ( int x : a ) {
8 boolean exists = false ;
9 for ( int y : res ) {
10 if ( x == y ) { exists = true ; break ; }
11 }
12 if (! exists ) res . add ( x ) ;
13 }
14 int [] out = new int [ res . size () ];
15 for ( int i = 0; i < res . size () ; i ++) out [ i ] = res . get ( i ) ;
16 return out ;
17 }
18
19 public static void main ( String [] args ) {
20 int [] a = {5 ,2 ,9 ,1 ,6 ,2 ,5};
21 int [] u = unique ( a ) ;
22 for ( int x : u ) System . out . print ( x + " " ) ;
23 System . out . println () ;
24 }
25 }

Best Solution
Best: use LinkedHashSet to preserve insertion order. Time O(n).

1 import java . util . LinkedHashSet ;

2 import java . util . Set ;
3
4 public class A 0 4 _ R e m o v e D u p A r r a y _ B e s t {
5 static int [] unique ( int [] a ) {
6 Set < Integer > set = new LinkedHashSet < >() ;
7 for ( int x : a ) set . add ( x ) ;
8

9 int [] out = new int [ set . size () ];

10 int i = 0;
11 for ( int x : set ) out [ i ++] = x ;
12 return out ;
13 }
14

15 public static void main ( String [] args ) {

16 int [] a = {5 ,2 ,9 ,1 ,6 ,2 ,5};
17 int [] u = unique ( a ) ;
18 for ( int x : u ) System . out . print ( x + " " ) ;
19 System . out . println () ;
20 }
21 }
 3.5. 5. REMOVE DUPLICATES FROM AN ARRAYLIST 41

3.5 5. Remove Duplicates from an ArrayList

Problem Statement
Given an ArrayList<Integer>, remove duplicate values.

Example

Example: [5,2,9,1,6,2,5] -> [5,2,9,1,6].

Brute-Force Solution
Brute-force: nested loops. Time O(n2 ).

1 import java . util . ArrayList ;

2

3 public class A 0 5 _ R e m o v e D u p L i s t _ B r u t e {
4 static ArrayList < Integer > unique ( ArrayList < Integer > list ) {
5 ArrayList < Integer > res = new ArrayList < >() ;
6 for ( int x : list ) {
7 boolean exists = false ;
8 for ( int y : res ) {
9 if ( x == y ) { exists = true ; break ; }
10 }
11 if (! exists ) res . add ( x ) ;
12 }
13 return res ;
14 }
15
16 public static void main ( String [] args ) {
17 ArrayList < Integer > list = new ArrayList < >() ;
18 int [] a = {5 ,2 ,9 ,1 ,6 ,2 ,5};
19 for ( int x : a ) list . add ( x ) ;
20

21 System . out . println ( unique ( list ) ) ;

22 }
23 }

Best Solution
Best: LinkedHashSet keeps insertion order. Time O(n).

1 import java . util . ArrayList ;

2 import java . util . LinkedHashSet ;
3 import java . util . Set ;
4
5 public class A 0 5 _ R e m o v e D u p L i s t _ B e s t {
6 static ArrayList < Integer > unique ( ArrayList < Integer > list ) {
 42 CHAPTER 3. ARRAYS & COLLECTIONS

7 Set < Integer > set = new LinkedHashSet < >( list ) ;
8 return new ArrayList < >( set ) ;
9 }
10
11 public static void main ( String [] args ) {
12 ArrayList < Integer > list = new ArrayList < >() ;
13 int [] a = {5 ,2 ,9 ,1 ,6 ,2 ,5};
14 for ( int x : a ) list . add ( x ) ;
15
16 System . out . println ( unique ( list ) ) ;
17 }
18 }

3.6 6. Find Missing Number in 1..n

Problem Statement
Given an array containing numbers from 1 to n with one missing number, find the missing one.

Example

{1,2,4,5,6} -> missing 3.

Brute-Force Solution
Brute-force: for each number 1..n, scan array to see if present. Time O(n2 ).

1 public class A 0 6 _ M i s s i n g N u m b e r _ B r u t e {
2 static int missing ( int [] a ) {
3 int n = a . length + 1;
4 for ( int x = 1; x <= n ; x ++) {
5 boolean found = false ;
6 for ( int v : a ) {
7 if ( v == x ) { found = true ; break ; }
8 }
9 if (! found ) return x ;
10 }
11 return -1;
12 }
13
14 public static void main ( String [] args ) {
15 int [] a = {1 ,2 ,4 ,5 ,6};
16 System . out . println ( missing ( a ) ) ; // 3
17 }
18 }

Best Solution
Best: sum formula (or XOR). Time O(n).
 3.7. 7. FIND LARGEST AND SMALLEST ELEMENT IN AN ARRAY 43

1 public class A 0 6 _ M i s s i n g N u m b e r _ B e s t {
2 static int missing ( int [] a ) {
3 int n = a . length + 1;
4 long total = ( long ) n * ( n + 1) / 2;
5 long sum = 0;
6 for ( int v : a ) sum += v ;
7 return ( int ) ( total - sum ) ;
8 }
9
10 public static void main ( String [] args ) {
11 int [] a = {1 ,2 ,4 ,5 ,6};
12 System . out . println ( missing ( a ) ) ; // 3
13 }
14 }

3.7 7. Find Largest and Smallest Element in an Array

Problem Statement
Given an integer array, find the smallest and largest values.

Example

Smallest=1, Largest=9.

Brute-Force Solution
Brute-force: sort the array and take first/last. Time O(n log n).

1 import java . util . Arrays ;

2
3 public class A07_MinMax_Brute {
4 static int [] minMax ( int [] a ) {
5 int [] b = Arrays . copyOf (a , a . length ) ;
6 Arrays . sort ( b ) ;
7 return new int []{ b [0] , b [ b . length - 1]};
8 }
9
10 public static void main ( String [] args ) {
11 int [] a = {5 ,2 ,9 ,1 ,6 ,3};
12 int [] r = minMax ( a ) ;
13 System . out . println ( " Smallest : " + r [0]) ;
14 System . out . println ( " Largest : " + r [1]) ;
15 }
16 }

Best Solution
Best: one pass. Time O(n), space O(1).
 44 CHAPTER 3. ARRAYS & COLLECTIONS

1 public class A07_MinMax_Best {

2 static int [] minMax ( int [] a ) {
3 if ( a == null || a . length == 0) throw new I l l e g a l A r g u m e n t E x c e p t i o n ( "
Empty array " ) ;
4 int min = a [0] , max = a [0];
5 for ( int v : a ) {
6 if ( v < min ) min = v ;
7 if ( v > max ) max = v ;
8 }
9 return new int []{ min , max };
10 }
11
12 public static void main ( String [] args ) {
13 int [] a = {5 ,2 ,9 ,1 ,6 ,3};
14 int [] r = minMax ( a ) ;
15 System . out . println ( " Smallest : " + r [0]) ;
16 System . out . println ( " Largest : " + r [1]) ;
17 }
18 }

3.8 8. Search Element in an Array

Problem Statement
Given an integer array and a target, return the index of the target or -1 if not found.

Example

Linear search output: target 6 at index 4 (original array).

Brute-Force Solution
Linear search. Time O(n).

1 public class A08_Search_Brute {

2 static int linearSearch ( int [] a , int target ) {
3 for ( int i = 0; i < a . length ; i ++) if ( a [ i ] == target ) return i ;
4 return -1;
5 }
6
7 public static void main ( String [] args ) {
8 int [] a = {5 ,2 ,9 ,1 ,6 ,3};
9 System . out . println ( linearSearch (a , 6) ) ; // 4
10 System . out . println ( linearSearch (a , 10) ) ; // -1
11 }
12 }

Best Solution
If the array is sorted, use binary search. Time O(log n).
 3.9. 9. SUM ONLY INTEGERS IN A MIXED STRING ARRAY 45

1 import java . util . Arrays ;

2
3 public class A08_Search_Best {
4 static int binarySearch ( int [] sorted , int target ) {
5 int lo = 0 , hi = sorted . length - 1;
6 while ( lo <= hi ) {
7 int mid = lo + ( hi - lo ) / 2;
8 if ( sorted [ mid ] == target ) return mid ;
9 if ( sorted [ mid ] < target ) lo = mid + 1;
10 else hi = mid - 1;
11 }
12 return -1;
13 }
14
15 public static void main ( String [] args ) {
16 int [] a = {5 ,2 ,9 ,1 ,6 ,3};
17 Arrays . sort ( a ) ; // must be sorted for binary search
18 System . out . println ( Arrays . toString ( a ) ) ;
19 System . out . println ( binarySearch (a , 6) ) ;
20 }
21 }

3.9 9. Sum Only Integers in a Mixed String Array

Problem Statement
Given a string array containing integers and non-integers, sum only the integer values.

Example

{"5","2","9","a","1","6","#","3"} -> 26.

Brute-Force Solution
Brute-force: check each string with a regex before parsing. Time O(nk).

1 public class A 0 9 _ S u m I n t e g e r s _ B r u t e {
2 static boolean isInteger ( String s ) {
3 return s . matches ( " -?\\ d + " ) ;
4 }
5
6 static int sum ( String [] a ) {
7 int sum = 0;
8 for ( String x : a ) {
9 if ( isInteger ( x ) ) sum += Integer . parseInt ( x ) ;
10 }
11 return sum ;
12 }
13
14 public static void main ( String [] args ) {
15 String [] a = { " 5 " ," 2 " ," 9 " ," a " ," 1 " ," 6 " ," # " ," 3 " };
 46 CHAPTER 3. ARRAYS & COLLECTIONS

16 System . out . println ( sum ( a ) ) ; // 26

17 }
18 }

Best Solution
Best: try/catch parsing (simple and common in interviews).

1 public class A 0 9 _ S u m I n t e g e r s _ B e s t {
2 static int sum ( String [] a ) {
3 int sum = 0;
4 for ( String x : a ) {
5 try {
6 sum += Integer . parseInt ( x ) ;
7 } catch ( N u m b e r F o r m a t E x c e p t i o n ignored ) {
8 // ignore non - integers
9 }
10 }
11 return sum ;
12 }
13
14 public static void main ( String [] args ) {
15 String [] a = { " 5 " ," 2 " ," 9 " ," a " ," 1 " ," 6 " ," # " ," 3 " };
16 System . out . println ( sum ( a ) ) ; // 26
17 }
18 }

3.10 10. Find Minimum and Maximum from an Array

Problem Statement
Find the minimum and maximum values in an array.

Example

Minimum=1, Maximum=9.

Brute-Force Solution
Brute-force: sort and take ends. Time O(n log n).

1 import java . util . Arrays ;

2

3 public class A10_MinMax_Brute {

4 public static void main ( String [] args ) {
5 int [] a = {5 ,2 ,9 ,1 ,6 ,3};
6 Arrays . sort ( a ) ;
7 System . out . println ( " Minimum value : " + a [0]) ;
8 System . out . println ( " Maximum value : " + a [ a . length - 1]) ;
9 }
 3.11. 11. COUNT ODD AND EVEN NUMBERS IN AN ARRAY 47

10 }

Best Solution
Best: one pass. Time O(n).

1 public class A10_MinMax_Best {

2 static int min ( int [] a ) {
3 int m = a [0];
4 for ( int i = 1; i < a . length ; i ++) if ( a [ i ] < m ) m = a [ i ];
5 return m ;
6 }
7
8 static int max ( int [] a ) {
9 int m = a [0];
10 for ( int i = 1; i < a . length ; i ++) if ( a [ i ] > m ) m = a [ i ];
11 return m ;
12 }
13
14 public static void main ( String [] args ) {
15 int [] a = {5 ,2 ,9 ,1 ,6 ,3};
16 System . out . println ( " Minimum value : " + min ( a ) ) ;
17 System . out . println ( " Maximum value : " + max ( a ) ) ;
18 }
19 }

3.11 11. Count Odd and Even Numbers in an Array

Problem Statement
Given an array of integers, count how many are odd and how many are even.

Example

Input {1..9} -> Even=4, Odd=5.

Brute-Force Solution
Use modulo check. Time O(n).

1 public class A 1 1 _ C o u n t O d d E v e n _ B r u t e {
2 static int [] count ( int [] a ) {
3 int odd = 0 , even = 0;
4 for ( int x : a ) {
5 if ( x % 2 == 0) even ++;
6 else odd ++;
7 }
8 return new int []{ odd , even };
9 }
10
 48 CHAPTER 3. ARRAYS & COLLECTIONS

11 public static void main ( String [] args ) {

12 int [] a = {1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9};
13 int [] r = count ( a ) ;
14 System . out . println ( " Odd : " + r [0]) ;
15 System . out . println ( " Even : " + r [1]) ;
16 }
17 }

Best Solution
Use bitwise AND to check parity. Time O(n).

1 public class A 1 1 _ C o u n t O d d E v e n _ B e s t {
2 static int [] count ( int [] a ) {
3 int odd = 0 , even = 0;
4 for ( int x : a ) {
5 if ( ( x & 1) == 0 ) even ++;
6 else odd ++;
7 }
8 return new int []{ odd , even };
9 }
10
11 public static void main ( String [] args ) {
12 int [] a = {1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9};
13 int [] r = count ( a ) ;
14 System . out . println ( " Odd : " + r [0]) ;
15 System . out . println ( " Even : " + r [1]) ;
16 }
17 }

3.12 12. Find Non-Repeated Elements

Problem Statement
Given an array where some elements repeat, return elements that appear exactly once (example:
[1,1,2,2,3,4,5,5,6,6] -> [3,4]).

Example

[1,1,2,2,3,4,5,5,6,6] -> [3,4].

Brute-Force Solution
Brute-force: for each element count occurrences with a nested loop. Time O(n2 ).

1 import java . util . ArrayList ;

2 import java . util . List ;
3
4 public class A 1 2 _ N o n R e p e a t e d _ B r u t e {
5 static List < Integer > nonRepeated ( int [] a ) {
 3.12. 12. FIND NON-REPEATED ELEMENTS 49

6 List < Integer > res = new ArrayList < >() ;

7 for ( int i = 0; i < a . length ; i ++) {
8 int count = 0;
9 for ( int j = 0; j < a . length ; j ++) {
10 if ( a [ i ] == a [ j ]) count ++;
11 }
12 if ( count == 1) res . add ( a [ i ]) ;
13 }
14 return res ;
15 }
16
17 public static void main ( String [] args ) {
18 int [] a = {1 ,1 ,2 ,2 ,3 ,4 ,5 ,5 ,6 ,6};
19 System . out . println ( nonRepeated ( a ) ) ; // [3 , 4]
20 }
21 }

Best Solution
Best: count with a HashMap. Time O(n).

1 import java . util . ArrayList ;

2 import java . util . HashMap ;
3 import java . util . List ;
4 import java . util . Map ;
5
6 public class A 1 2 _ N o n R e p e a t e d _ B e s t {
7 static List < Integer > nonRepeated ( int [] a ) {
8 Map < Integer , Integer > freq = new HashMap < >() ;
9 for ( int x : a ) freq . put (x , freq . getOrDefault (x , 0) + 1) ;
10
11 List < Integer > res = new ArrayList < >() ;
12 for ( int x : a ) {
13 if ( freq . get ( x ) == 1) res . add ( x ) ;
14 }
15 return res ;
16 }
17
18 public static void main ( String [] args ) {
19 int [] a = {1 ,1 ,2 ,2 ,3 ,4 ,5 ,5 ,6 ,6};
20 System . out . println ( nonRepeated ( a ) ) ; // [3 , 4]
21 }
22 }
 Chapter 4

Java Fundamentals

4.1 1. Implement equals() and hashCode()

Problem Statement
Create a class (e.g., Student) and implement equals() and hashCode() correctly so that logically
equal objects compare equal and work in hash-based collections.

Example

Expected: Student(1, Alice) equals Student(1, Alice) -> true.

Brute-Force Solution
Brute-force (wrong approach): rely on default [Link], which compares references.

1 import java . util . HashSet ;

2 import java . util . Set ;
3
4 public class J 0 1 _ E q u a l s H a s h C o d e _ B r u t e {
5 static class Student {
6 int id ;
7 String name ;
8
9 Student ( int id , String name ) {
10 this . id = id ;
11 this . name = name ;
12 }
13 }
14
15 public static void main ( String [] args ) {
16 Student a = new Student (1 , " Alice " ) ;
17 Student b = new Student (1 , " Alice " ) ;
18
19 // false because default equals compares references
20 System . out . println ( a . equals ( b ) ) ;
21
22 Set < Student > set = new HashSet < >() ;
23 set . add ( a ) ;
24 set . add ( b ) ;

50
 4.1. 1. IMPLEMENT EQUALS() AND HASHCODE() 51

25 // size =2 ( duplicate not removed )

26 System . out . println ( " Set size : " + set . size () ) ;
27 }
28 }

Best Solution
Best: override both methods using all identity fields.

1 import java . util . HashSet ;

2 import java . util . Objects ;
3 import java . util . Set ;
4
5 public class J 0 1 _ E q u a l s H a s h C o d e _ B e s t {
6 static class Student {
7 private final int id ;
8 private final String name ;
9
10 Student ( int id , String name ) {
11 this . id = id ;
12 this . name = name ;
13 }
14
15 @Override
16 public boolean equals ( Object o ) {
17 if ( this == o ) return true ;
18 if ( o == null || getClass () != o . getClass () ) return false ;
19 Student that = ( Student ) o ;
20 return id == that . id && Objects . equals ( name , that . name ) ;
21 }
22
23 @Override
24 public int hashCode () {
25 return Objects . hash ( id , name ) ;
26 }
27 }
28
29 public static void main ( String [] args ) {
30 Student a = new Student (1 , " Alice " ) ;
31 Student b = new Student (1 , " Alice " ) ;
32
33 System . out . println ( a . equals ( b ) ) ; // true
34
35 Set < Student > set = new HashSet < >() ;
36 set . add ( a ) ;
37 set . add ( b ) ;
38 System . out . println ( " Set size : " + set . size () ) ; // 1
39 }
40 }
Notes

• All code snippets are standalone Java classes. Copy a snippet into a file named exactly as its public
class to compile and run.

• Brute-force solutions favor simplicity and directness. Best solutions favor efficiency and clean
implementation.

52