basic/intermediate code Flashcards
Palindrome Check:
Write a program to check if a given string is a palindrome.
Normalize the String:
Convert to lowercase: “a man, a plan, a canal, panama”.
s = s.toLowerCase();
Remove non-alphanumeric characters: “amanaplanacanalpanama”.
s = s.replaceAll(“[^a-z0-9]”, “”);
Initialize Two Pointers:
left = 0 (pointing to ‘a’).
right = 20 (pointing to ‘a’).
int left = 0;
int right = s.length() - 1;
Check Characters:
Compare s.charAt(left) and s.charAt(right):
s.charAt(0) == s.charAt(20) (‘a’ == ‘a’) → Move pointers: left = 1, right = 19.
s.charAt(1) == s.charAt(19) (‘m’ == ‘m’) → Move pointers: left = 2, right = 18.
s.charAt(2) == s.charAt(18) (‘a’ == ‘a’) → Move pointers: left = 3, right = 17.
s.charAt(3) == s.charAt(17) (‘n’ == ‘n’) → Move pointers: left = 4, right = 16.
Continue this process…
Complete the Check:
Continue comparing until left meets or crosses right.
If all characters match, the string is a palindrome.
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
// Characters don’t match, so it’s not a palindrome
return false;
}
// Move the pointers
left++;
right–;
}
Result:
Since all characters matched, the function returns true.
return true;
Factorial Calculation:
Write a program to calculate the factorial of a given number using recursion and iteration.
Recursion:
Base Case: Handles the simplest case directly (n == 0 or n == 1).
if (n == 0 || n == 1) {
return 1;
}
Recursive Call: The function calls itself with a smaller argument (n - 1).
return n * factorial(n - 1);
Iteration:
Initialize Result: Set the initial result to 1.
int result = 1;
Iterate and Multiply: Use a loop to multiply the result by each integer from 2 up to n.
for (int i = 2; i <= n; i++) {
result *= i;
}
send back the result
return result;
Fibonacci Series:
Write a program to print the first ‘n’ numbers of the Fibonacci series.
Steps
Base Case: If n is 0, return 0; if n is 1, return 1.
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
}
Recursive Case: Return the sum of the two preceding numbers in the series
return fibonacci(n - 1) + fibonacci(n - 2);
Input: n = 10
Print Fibonacci Numbers:
fibonacci(0): 0
fibonacci(1): 1
fibonacci(2): fibonacci(1) + fibonacci(0) = 1 + 0 = 1
fibonacci(3): fibonacci(2) + fibonacci(1) = 1 + 1 = 2
fibonacci(4): fibonacci(3) + fibonacci(2) = 2 + 1 = 3
Prime Number Check:
Write a program to check if a given number is prime.
Handle Special Cases: If the number is less than or equal to 1, return false.
if (number <= 1) {
return false;
}
Check for Divisors: Loop from 2 to the square root of the number. If the number is divisible by any of these values, return false.
for (int i = 2; i <= Math.sqrt(number); i++) {
if (number % i == 0) {
return false; // Number is divisible by i, so it’s not prime
}
}
Return True: If no divisors are found, return true, indicating the number is prime.
return true;
29 is greater than 1
Loop from i = 2 to i <= sqrt(29) which is approximately 5.39. Thus, loop up to 5
Check divisibility:
29 % 2 != 0 (not divisible)
29 % 3 != 0 (not divisible)
29 % 4 != 0 (not divisible)
29 % 5 != 0 (not divisible)
No divisors were found in the loop, so 29 is a prime number. Return true.
Reverse a String:
Write a program to reverse a given string.
Convert String to Char Array:
char[] charArray = s.toCharArray();
Since strings in Java are immutable, we first convert the string to a char array, which allows us to modify the characters.
Initialize Pointers:
int left = 0;
int right = charArray.length - 1;
left starts at the beginning of the array (0).
right starts at the end of the array (charArray.length - 1).
Swap Characters:
char temp = charArray[left];
charArray[left] = charArray[right];
charArray[right] = temp;
We swap the characters at the left and right indices.
Temporary variable temp is used to hold the value at left during the swap.
Move Pointers:
left++;
right–;
Increment left to move it towards the center.
Decrement right to move it towards the center.
Continue Until Pointers Meet:
The loop continues until left is greater than or equal to right.
while (left < right)
Convert Char Array Back to String:
return new String(charArray);
After the loop, the char array is reversed. We convert it back to a string and return it.
Iterative:
Initialization: Create an empty StringBuilder.
StringBuilder reversed = new StringBuilder();
Iteration: Loop through the string in reverse order, appending each character to the StringBuilder.
for (int i = s.length() - 1; i >= 0; i–) {
reversed.append(s.charAt(i)); // Step 3: Build the reversed string
}
Efficiency: O(n) time complexity, where n is the length of the string.
return reversed.toString();
Stringbuilder method:
Initialize: Create a StringBuilder with the original string.
StringBuilder stringBuilder = new StringBuilder(s);
Reverse: Use the reverse() method.
stringBuilder.reverse();
Convert: Convert the StringBuilder back to a string.
return stringBuilder.toString();
Remove Duplicates from Array:
Write a program to remove duplicates from an array.
Initialization:
Set<Integer> set = new LinkedHashSet<>();
Create a HashSet or LinkedHashSet to hold unique elements.</Integer>
Iteration:
for (int num : array) {
set.add(num);
}
Iterate through the original array and add each element to the set. The set automatically handles duplicates by ensuring each element is unique.
Conversion:
set.toArray(new Integer[0])
or
int[] resultArray = new int[set.size()];
int i = 0;
for (int num : set) {
resultArray[i++] = num;
}
Convert the set back to an array. This involves iterating over the set and copying the elements into a new array.
Find Second Largest Element:
Write a program to find the second largest element in an array.
Handle Special Cases:
if (array == null || array.length < 2) {
return Integer.MIN_VALUE; // Not enough elements to determine the second largest
}
Check if the array is null or has fewer than 2 elements. If true, return Integer.MIN_VALUE as a sentinel value indicating an error.
Initialize Variables:
int firstLargest = Integer.MIN_VALUE;
int secondLargest = Integer.MIN_VALUE;
firstLargest is initialized to Integer.MIN_VALUE to ensure any number in the array will be larger.
secondLargest is also initialized to Integer.MIN_VALUE.
Iterate through the Array:
for (int num : array) {
For each element num in the array:
if (num > firstLargest) {
secondLargest = firstLargest;
firstLargest = num;
If num is greater than firstLargest, update secondLargest to be firstLargest and then update firstLargest to be num.
} else if (num > secondLargest && num != firstLargest) {
secondLargest = num;
}
Otherwise, if num is greater than secondLargest and is not equal to firstLargest, update secondLargest to be num.
Return the Result:
return secondLargest;
After iterating through the array, secondLargest will hold the second largest element.
If secondLargest is still Integer.MIN_VALUE, it means there was no valid second largest element (e.g., all elements were the same).
Anagram Check:
Write a program to check if two strings are anagrams of each other.
Normalize Strings:
str1 = str1.toLowerCase();
str2 = str2.toLowerCase();
Convert both strings to lowercase.
Early exit:
// If lengths are different, they cannot be anagrams
if (str1.length() != str2.length()) {
return false;
}
Count Frequencies:
int[] charCount = new int[26];
Use an integer array charCount of size 26 (for each letter of the alphabet) to store character frequencies.
Increment the count for each character in str1.
for (char c : str1.toCharArray()) {
charCount[c]++;
}
for (char c : s2.toCharArray()) {
if (–letterCount[c] < 0) {
return false;
}
}
Decrement the count for each character in str2.
If any count is negative after processing the second string, it means the second string had more of that character than the first, indicating the strings are not anagrams.
return true;
if we reached the end its an anagram
Sorting and Comparing::
Normalize Strings:
str1 = str1.toLowerCase();
str2 = str2.toLowerCase();
Convert both strings to lowercase to make the comparison case-insensitive.
In this example, we assume the strings contain only alphabetical characters. If the strings can contain spaces or punctuation, you might want to remove those using replaceAll(“[^a-zA-Z]”, “”).
Sort Strings:
char[] charArray1 = str1.toCharArray();
char[] charArray2 = str2.toCharArray();
Arrays.sort(charArray1);
Arrays.sort(charArray2);
Convert the strings to character arrays using toCharArray().
Sort the character arrays using Arrays.sort().
Compare Strings:
return Arrays.equals(charArray1, charArray2);
Use Arrays.equals() to compare the sorted character arrays.
If they are equal, the original strings are anagrams.
Time and space complexity
Approach 1: Sorting and Comparing
Time Complexity
Normalization: Converting strings to lowercase is O(n) where n is the length of the string.
Sorting: Sorting the characters of the string is O(n log n) using efficient sorting algorithms like Timsort, which is used by Arrays.sort().
Comparison: Comparing two arrays of length n is O(n).
Overall time complexity is dominated by the sorting step:
Time Complexity=O(nlogn)
Space Complexity
Normalization: O(n) for storing the lowercase versions of the strings.
Sorting: O(n) for the space used by the sorting algorithm.
Comparison: O(1) for the comparison step (assuming in-place sorting).
Overall space complexity:
Space Complexity=O(n)
Approach 2: Using Character Frequency
Time Complexity
Normalization: Converting strings to lowercase is O(n).
Counting Frequencies: Iterating through the strings to count frequencies is O(n).
Comparison: Comparing the frequency counts is O(1) since the length of the frequency array is fixed (26 for lowercase alphabets).
Overall time complexity:
Time Complexity=O(n)
Space Complexity
Normalization: O(n) for storing the lowercase versions of the strings.
Counting Frequencies: O(1) for the frequency array (fixed size of 26 for lowercase alphabets).
Overall space complexity:
Space Complexity=O(1)
Summary
Sorting and Comparing Approach:
Time Complexity: O(n log n)
Space Complexity: O(n)
Character Frequency Approach:
Time Complexity: O(n)
Space Complexity: O(1)
Recommendation
Sorting and Comparing Approach: Suitable for general-purpose use and straightforward to implement.
Character Frequency Approach: More efficient for large strings as it has linear time complexity and constant space complexity for character frequencies. Use this approach when dealing with large datasets or when performance is critical.
Sum of Digits:
Write a program to find the sum of the digits of a given number.
Initialize a Sum Variable:
int sum = 0; initializes the sum variable to 0.
Extract and Add Digits:
int digit = number % 10; extracts the last digit of the number.
sum += digit; adds the extracted digit to the sum.
Remove the Last Digit:
number /= 10; removes the last digit from the number by performing integer division by 10.
Continue Until the Number is Zero:
The while (number != 0) loop continues until the number is reduced to zero, ensuring all digits are processed.
This program efficiently calculates the sum of the digits of a given number by using basic arithmetic operations in a loop. The time complexity is O(d), where d is the number of digits in the number, and the space complexity is O(1).
Leap Year Check:
Write a program to check if a given year is a leap year.
Check Divisibility by 4:
if (year % 4 == 0): If the year is divisible by 4, proceed to the next checks.
Check Divisibility by 100:
if (year % 100 == 0): If the year is also divisible by 100, proceed to the next check.
Check Divisibility by 400:
if (year % 400 == 0): If the year is divisible by 400, it is a leap year.
else: If the year is divisible by 100 but not by 400, it is not a leap year.
Return True for Divisibility by 4 but Not by 100:
else: If the year is divisible by 4 but not by 100, it is a leap year.
Return False for Not Divisible by 4:
else: If the year is not divisible by 4, it is not a leap year.
Odd or Even:
Write a program to check if a given number is odd or even.
Main Method:
int number = 25; initializes the number to be checked.
boolean isEven = checkEven(number); calls the checkEven method to determine if the number is even.
An if statement is used to print whether the number is even or odd based on the result.
checkEven Method:
return number % 2 == 0; checks if the number is divisible by 2 and returns true if it is (indicating the number is even) and false if it isn’t (indicating the number is odd).
String Concatenation:
Write a program to concatenate two strings without using the + operator.
Concatenate Using concat:
str1.concat(str2); concatenates str2 to the end of str1.
return str1.concat(str2);
Initialize a StringBuilder:
StringBuilder stringBuilder = new StringBuilder();
This creates a new StringBuilder instance, which is an efficient way to handle string concatenations.
Append Strings:
stringBuilder.append(str1); appends the first string to the StringBuilder.
stringBuilder.append(str2); appends the second string to the StringBuilder.
Convert to String:
return stringBuilder.toString(); converts the StringBuilder content back to a string.
Vowel Count:
Write a program to count the number of vowels in a given string.
This method takes a string (str) as input and returns the number of vowels in it.
Initialize a Counter:
int count = 0;
It initializes a counter count to 0.
str = str.toLowerCase();
It converts the input string to lowercase using toLowerCase() to handle both uppercase and lowercase vowels uniformly.
for (int i = 0; i < str.length(); i++) {
It iterates through each character of the string using a for loop.
char ch = str.charAt(i);
converts string to char array
if (ch == ‘a’ || ch == ‘e’ || ch == ‘i’ || ch == ‘o’ || ch == ‘u’) {
count++;
}
Inside the loop, it checks if the current character (ch) is a vowel (one of ‘a’, ‘e’, ‘i’, ‘o’, ‘u’).
If the character is a vowel, it increments the counter count.
return count;
After the loop completes, it returns the count of vowels.
Largest of Three Numbers:
Write a program to find the largest of three numbers.
Compare Numbers: The if-else statements compare the three numbers to find the largest.
if (num1 >= num2 && num1 >= num3): Checks if num1 is greater than or equal to both num2 and num3.
else if (num2 >= num1 && num2 >= num3): Checks if num2 is greater than or equal to both num1 and num3.
else: If the above conditions are false, num3 is the largest.
Output the Result: The largest number is printed to the console.
Swapping Variables:
Write a program to swap two variables without using a third variable.
System.out.println(“Before swapping: a = “ + a + “, b = “ + b);
// Swapping using arithmetic operations
a = a + b; // a now becomes 15
b = a - b; // b now becomes 5 (original value of a)
a = a - b; // a now becomes 10 (original value of b)
System.out.println(“After swapping: a = “ + a + “, b = “ + b);
Initial Values: a = 5, b = 10
First Operation: a = a + b => a = 15
Second Operation: b = a - b => b = 5
Third Operation: a = a - b => a = 10
