Skip to content

Commit 6df191c

Browse files
MichaelVandiMichaelVandi
committed
Added a bunch of questions from Cracking the coding interview from my prep session recentrly
1 parent 09f5ec7 commit 6df191c

25 files changed

Lines changed: 1153 additions & 1 deletion

‎CrackingTheCodingInterview/ArraysAndStrings/URLify.java‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
import java.util.*;
2+
public class MyClass {
3+
public static void main(String args[]) {
4+
String str = "Mr John Smith ";
5+
System.out.println(URLify2(str.toCharArray(), 13));
6+
7+
}
8+
/*
9+
Approach 1: Using regex
10+
*/
11+
public static String URLify(String url) {
12+
return url.replaceAll("[ ]+", "%20");
13+
}
14+
/*
15+
Approach 2: Using true length
16+
*/
17+
public static String URLify2(char[] url, int trueLength) {
18+
int spaceCount = 0;
19+
int index;
20+
int i = 0;
21+
for (i = 0; i < trueLength; i++) {
22+
// Count the number of spaces
23+
if (url[i] == ' ') {
24+
spaceCount++;
25+
}
26+
}
27+
index = trueLength + spaceCount * 2;
28+
System.out.println("Index : " + index);
29+
if (trueLength < url.length) {
30+
url[trueLength] = '\0'; // Mark the end of the array
31+
System.out.println("yes");
32+
System.out.println(Arrays.toString(url));
33+
}
34+
for (i = trueLength - 1; i >= 0; i--) {
35+
if (url[i] == ' ') {
36+
// Replace the 3 consecutive characters backwards with %20
37+
url[index - 1] = '0';
38+
url[index - 2] = '2';
39+
url[index - 3] = '%';
40+
// Update the new index
41+
index = index - 3;
42+
43+
System.out.println("New Index: " + index);
44+
System.out.println(Arrays.toString(url));
45+
} else {
46+
// Move the prev character one place up
47+
url[index - 1] = url[i];
48+
// Update the index
49+
System.out.println("New Index: " + index);
50+
System.out.println(Arrays.toString(url));
51+
index--;
52+
}
53+
}
54+
return new String(url);
55+
}
56+
57+
58+
}

‎CrackingTheCodingInterview/ArraysAndStrings/check_permutation.java‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
/**These are mostly my own solutions, sometimes I put the solutions in the book too, but you get the idea */
2+
import java.util.*;
3+
public class MyClass {
4+
public static void main(String args[]) {
5+
System.out.println(checkPermutation2("abc", "bac"));
6+
}
7+
/*
8+
Sorting approach
9+
Time: O(n log n)
10+
*/
11+
public static boolean checkPermutation(String a, String b) {
12+
// if one is a permutation of the other, they have the same characters
13+
// you can sort them and check for equality
14+
// you can count the occurence of each character
15+
String nA = sort(a);
16+
String nB = sort(b);
17+
return nA.equals(nB);
18+
19+
}
20+
/*
21+
Count each occurence approach O(n)
22+
*/
23+
public static boolean checkPermutation2(String a, String b) {
24+
Map<Character, Integer> map = new HashMap<>();
25+
for (int i = 0; i < a.length(); i++) {
26+
char current = a.charAt(i);
27+
// Increment this character's occurences or put 1 if it's the first occurent
28+
map.put(current, map.getOrDefault(current, 0) + 1);
29+
}
30+
// Now go through b and make sure it's the same or subtract one
31+
for (int i = 0; i < b.length(); i++) {
32+
char current = b.charAt(i);
33+
if (!map.containsKey(current)) {
34+
return false;
35+
}
36+
// if it's there subtract it
37+
map.put(current, map.get(current) - 1);
38+
}
39+
for (char ch : map.keySet()) {
40+
if (map.get(ch) != 0) {
41+
// Something went wrong return false
42+
return false;
43+
}
44+
}
45+
return true;
46+
}
47+
public static String sort(String s) {
48+
char[] array = s.toCharArray();
49+
Arrays.sort(array);
50+
return new String(array);
51+
}
52+
53+
}

‎CrackingTheCodingInterview/ArraysAndStrings/is_unique.java‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
public class MyClass {
2+
public static void main(String args[]) {
3+
System.out.println(hasUniqueCharsOptimized("abc"));
4+
}
5+
/*
6+
Time: O(n) -> check if the "contains" method in a string runs in O(n) time,
7+
in that case it will be O(n^2)
8+
Space: O(1)
9+
*/
10+
public static boolean hasUniqueChars(String s) {
11+
// Approach: Go through s, at every index.
12+
// Check the left and right sides to see if the same char is present
13+
// We may only need to check the left side even
14+
if (s.length() == 0 || s == null) {
15+
return true;
16+
}
17+
for (int i = 0; i < s.length(); i++) {
18+
String current = String.valueOf(s.charAt(i));
19+
String leftSide = s.substring(0, i);
20+
if (leftSide.contains(current)) {
21+
// We've seen this before, return false
22+
return false;
23+
}
24+
}
25+
// If we did not see a repeating character
26+
return true;
27+
}
28+
29+
// Alternatively, each character has a unique asc code. We can create an array of all possible
30+
// asc codes and enter true or false when we see a character
31+
public static boolean hasUniqueCharsOptimized(String s) {
32+
boolean[] contains = new boolean[128]; // Assuming alpha numeric only
33+
// You can also do 26 and convert the letter to it's alphabetical number
34+
for (int i = 0; i < s.length(); i++) {
35+
int value = s.charAt(i);
36+
if (contains[value]) {
37+
return false;
38+
}
39+
// Else, put this value in the contains array
40+
contains[value] = true;
41+
}
42+
// If we did not see a repeating character
43+
return true;
44+
}
45+
46+
}

‎CrackingTheCodingInterview/ArraysAndStrings/oneAway.java‎

Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,104 @@
1+
import java.util.*;
2+
public class MyClass {
3+
public static void main(String args[]) {
4+
System.out.println(oneAway("bakes", "bale"));
5+
System.out.println(oneAwayOptimized("bakes", "bale"));
6+
7+
}
8+
public static boolean oneAway(String a, String b) {
9+
if (a.length() == b.length()) {
10+
return isOneReplacementAway(a, b);
11+
} else if (a.length() - 1 == b.length()) {
12+
return isOneEditOrDeleteAway(a, b);
13+
} else if (b.length() - 1 == a.length()) {
14+
return isOneEditOrDeleteAway(b, a);
15+
}
16+
// return false if the two strings have more than one character difference, etc.
17+
return false;
18+
}
19+
public static boolean isOneReplacementAway(String a, String b) {
20+
// The differ by only one character
21+
boolean differenceFound = false;
22+
for (int i = 0; i < a.length(); i++) {
23+
// check for only one difference
24+
if (a.charAt(i) != b.charAt(i)) {
25+
// The first differnce will get a pass
26+
if (differenceFound) {
27+
return false;
28+
}
29+
differenceFound = true;
30+
}
31+
}
32+
return true;
33+
}
34+
public static boolean isOneEditOrDeleteAway(String a, String b) {
35+
// Assuming a is the longer string
36+
int index1 = 0;
37+
int index2 = 0;
38+
while (index1 < a.length() && index2 < b.length()) {
39+
// Compare their characters to make sure they are at least one edit or delete away
40+
if (a.charAt(index1) != b.charAt(index2)) {
41+
// They are different, move the longer string one place up
42+
// if indices 1 and 2 are the same, it means this is the first edit or delete
43+
// instance that we have come across, so it gets a pass. if indices 1 and 2
44+
// are different, then we have more than one edit or delete instances
45+
if (index1 != index2) {
46+
return false;
47+
}
48+
index1 += 1;
49+
} else {
50+
// If they are the same, move on to check the i + 1th characters in both strings
51+
index1 += 1;
52+
index2 += 1;
53+
}
54+
}
55+
return true;
56+
}
57+
/*
58+
59+
The following is the optimized function that merges all 3 conditions to one function
60+
*/
61+
62+
63+
public static boolean oneAwayOptimized(String a, String b) {
64+
// Check that the lengths of the strings differ by at most 1
65+
if (Math.abs(a.length() - b.length()) > 1) return false;
66+
67+
// Determine which string is longer or shorter
68+
String longer = (a.length() > b.length()) ? a : b;
69+
String shorter = (a.length() < b.length()) ? a : b;
70+
71+
// Now check for all 3 conditions in one function
72+
int indexLong = 0;
73+
int indexShort = 0;
74+
boolean differenceFound = false;
75+
76+
while (indexLong < longer.length() && indexShort < shorter.length()) {
77+
if (longer.charAt(indexLong) != shorter.charAt(indexShort)) {
78+
// Check if we have more than one replace (first condition)
79+
if (differenceFound) {
80+
return false;
81+
}
82+
differenceFound = true;
83+
// Now check for the delete and edit case
84+
if (longer.length() == shorter.length()) {
85+
// Move the shorter pointer forward
86+
indexShort += 1;
87+
indexLong += 1;
88+
// We're always moving the longer pointer at the end of the loop
89+
} else {
90+
// The lengths are different, move the longer one
91+
indexLong += 1;
92+
}
93+
} else {
94+
// The characters are the same, move the shorter pointer
95+
indexShort += 1;
96+
indexLong += 1;
97+
98+
}
99+
}
100+
return true;
101+
102+
}
103+
104+
}

‎CrackingTheCodingInterview/ArraysAndStrings/palindrome_ permutaion.java‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
import java.util.*;
2+
public class MyClass {
3+
public static void main(String args[]) {
4+
String str = "Mr John Smith ";
5+
System.out.println(isPermutationOfPalindrome("Tact Coa"));
6+
7+
}
8+
public static boolean isPermutationOfPalindrome(String s) {
9+
s = s.toLowerCase();
10+
Map<Character, Integer> map = new HashMap<>();
11+
for (int i = 0; i < s.length(); i++) {
12+
char current = s.charAt(i);
13+
// update it's occurence in the map
14+
if (current == ' ') {
15+
continue;
16+
}
17+
map.put(current, map.getOrDefault(current, 0) + 1);
18+
19+
}
20+
// Check that no character has more than 1 odd occurence
21+
boolean foundOdd = false;
22+
for (char c : map.keySet()) {
23+
System.out.println(c + " -> " + map.get(c));
24+
if (map.get(c) % 2 == 1) {
25+
// it has an odd occurence
26+
// If we've foundOdd before we return false;
27+
if (foundOdd) {
28+
return false;
29+
}
30+
// otherwise we havent found odd before, set to true
31+
foundOdd = true;
32+
}
33+
}
34+
return true;
35+
}
36+
37+
38+
}

‎CrackingTheCodingInterview/ArraysAndStrings/rotate_matrix.java‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
public class rotate_matrix {
2+
3+
}
4+
import java.util.*;
5+
public class MyClass {
6+
public static void main(String args[]) {
7+
8+
int[][] matrix = new int[][] {
9+
{1, 2, 3},
10+
{4, 5, 6},
11+
{7, 8, 9}
12+
};
13+
int[][] ans = rotateMatrix(matrix);
14+
for (int[] row: ans) {
15+
System.out.println(Arrays.toString(row));
16+
}
17+
18+
19+
}
20+
public static int[][] rotateMatrix(int[][] matrix) {
21+
// Step 1: Transpose matrix
22+
for (int i = 0; i < matrix.length; i++) {
23+
for (int j = i; j < matrix[i].length; j++) {
24+
int temp = matrix[i][j];
25+
matrix[i][j] = matrix[j][i];
26+
matrix[j][i] = temp;
27+
}
28+
}
29+
30+
// Step 2: Flip horizontally
31+
for (int[] row : matrix) {
32+
int left = 0;
33+
int right = row.length - 1;
34+
while (left < right) {
35+
int temp = row[left];
36+
row[left] = row[right];
37+
row[right] = temp;
38+
left++;
39+
right--;
40+
}
41+
}
42+
return matrix;
43+
44+
}
45+
46+
}

‎CrackingTheCodingInterview/ArraysAndStrings/string_compression.java‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
import java.util.*;
2+
public class MyClass {
3+
public static void main(String args[]) {
4+
System.out.println(compress("aabcccccaaa"));
5+
6+
}
7+
public static String compress(String s) {
8+
// TODO: Check for edge cases
9+
int count = 0;
10+
StringBuilder sb = new StringBuilder();
11+
for (int i = 0; i < s.length(); i++) {
12+
// System.out.println("Current : " + s.charAt(i));
13+
count += 1;
14+
// We get the current character
15+
char thisChar = s.charAt(i);
16+
// System.out.println(i + " : " + thisChar + " : " + count);
17+
if (i == s.length() - 1 || s.charAt(i) != s.charAt(i + 1)) {
18+
// reset
19+
// System.out.println("should append " + i + " : " + s.charAt(i) + " : " + count);
20+
sb.append(s.charAt(i));
21+
sb.append(count);
22+
count = 0;
23+
24+
}
25+
26+
}
27+
28+
29+
return sb.toString().length() < s.length() ? sb.toString() : s;
30+
}
31+
32+
}public class string_compression {
33+
34+
}

0 commit comments

Comments
 (0)