#note
Use Sieve of Eratosthenes algorithm to find all prime numbers till n.
Use Sieve of Eratosthenes algorithm to find all prime numbers till n.
algorithm Sieve of Eratosthenes is
input: an integer n > 1.
output: all prime numbers from 2 through n.
let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
for i = 2, 3, 4, ..., not exceeding √n do
if A[i] is true
for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
set A[j] := false
return all i such that A[i] is true.
Time - O(nloglogn)
Example problem: https://leetcode.com/problems/closest-prime-numbers-in-range/description
Hey everyone! 👋
Its been a long break, but I'm finally back here. From now on, I'll start sharing posts based on the book “Cracking the Coding Interview.” 🚀
I'm not a pro at all this, but I'll do my best to share what I learn along the way. Hopefully it helps you too — and we can grow together step by step. 🙌
#crackingthecodinginterview
Its been a long break, but I'm finally back here. From now on, I'll start sharing posts based on the book “Cracking the Coding Interview.” 🚀
I'm not a pro at all this, but I'll do my best to share what I learn along the way. Hopefully it helps you too — and we can grow together step by step. 🙌
#crackingthecodinginterview
❤1🔥1
1.1. Is Unique: Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?
The easy way is to use a hashtable, but without it, one quick idea is using an array to store the count of characters:
I also learned another way using bit vectors.
It’s similar to the first idea, but instead of an array, it only uses one integer:
Both have the same space complexity, but the second one is more efficient because it only takes 4 bytes.
#crackingthecodinginterview
The easy way is to use a hashtable, but without it, one quick idea is using an array to store the count of characters:
public static boolean isUnique(String s) {
int[] arr = new int[128];
for (int i=0; i<s.length(); i++) {
int idx = s.charAt(i) - 'a';
if (arr[idx] == 1) return false;
arr[idx]++;
}
return true;
}
TC - O(c)
SC - O(1)I also learned another way using bit vectors.
It’s similar to the first idea, but instead of an array, it only uses one integer:
public static boolean isUnique2(String s) {
int bits = 0;
for (int i=0; i<s.length(); i++) {
int idx = s.charAt(i) - 'a';
if ((bits & (1 << idx)) > 0) {
return false;
}
bits |= (1 << idx);
}
return true;
}
TC - O(c)
SC - O(1)Both have the same space complexity, but the second one is more efficient because it only takes 4 bytes.
#crackingthecodinginterview
🔥2
1.4. Palindrome Permutation: Given a string, write a function to check if it is a permutation of a palindrome. A palindrome is a word or phrase that is the same forwards and backwards.
The first solution is with hashmap:
Let's revise bit vectors and here is the next solution:
For a string to be a palindrome permutation, all letters must appear even number of times, but at most one letter can appear odd number of times (the middle one). With XOR operator, each time a character appears we flip its bit:
Even occurrences ➡️ bit ends up as 0
Odd occurrences ➡️ bit ends up as 1
At the end:
If all bits are 0 ➡️ every letter appears even times.
If exactly one bit is 1 ➡️ only one letter appears odd times.
To check the latter case, we use bitmask. if there is one 1 bit in integer, like 00010000, we subtract 1 then it becomes 00001111. after applying AND operator it will be 0, that confirms exactly one bit was set.
#crackingthecodinginterview
The first solution is with hashmap:
public static boolean f1(String s) {
Map<Character, Integer> map = new HashMap<>();
int oddFrequencies = 0;
for (char ch : s.toCharArray()) {
if (!Character.isLetter(ch)) continue;
ch = Character.toLowerCase(ch);
map.put(ch, map.getOrDefault(ch, 0) + 1);
if (map.get(ch) % 2 != 0) oddFrequencies++;
else oddFrequencies--;
}
return oddFrequencies <= 1;
}
// TC - O(n)
// SC - O(n)Let's revise bit vectors and here is the next solution:
public static boolean f2(String s) {
int bits = 0;
for (char ch : s.toCharArray()) {
if (!Character.isLetter(ch)) continue;
int k = Character.toLowerCase(ch) - 'a';
bits ^= (1 << k);
}
return bits == 0 || (bits & (bits - 1)) == 0;
}
// TC - O(n)
// SC - O(1)For a string to be a palindrome permutation, all letters must appear even number of times, but at most one letter can appear odd number of times (the middle one). With XOR operator, each time a character appears we flip its bit:
Even occurrences ➡️ bit ends up as 0
Odd occurrences ➡️ bit ends up as 1
At the end:
If all bits are 0 ➡️ every letter appears even times.
If exactly one bit is 1 ➡️ only one letter appears odd times.
To check the latter case, we use bitmask. if there is one 1 bit in integer, like 00010000, we subtract 1 then it becomes 00001111. after applying AND operator it will be 0, that confirms exactly one bit was set.
#crackingthecodinginterview
⚡4
image_2025-12-16_00-53-41.png
21.3 KB
#N1679. Max Number of K-Sum Pairs
problem link
#solution
TC - O(n)
SC - O(n)
problem link
#solution
TC - O(n)
SC - O(n)
class Solution {
public int maxOperations(int[] nums, int k) {
int count = 0;
Map<Integer, Integer> map = new HashMap<>();
for(int n: nums){
if(map.containsKey(n)){
count++;
map.put(n, map.get(n) -1);
if(map.get(n)==0) map.remove(n);
}else if(n<k){
map.put(k-n, map.getOrDefault(k-n, 0) +1);
}
}
return count;
}
}