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