Cracking The Coding Interview Answers(Solutions) by Seunghun Lee

Chapter 1 - Cracking The Coding Interview Answers(Solutions) by Seunghun Lee

1.1
String hasUniqueCharacters(String[] words) {
    // compare the character with the entire sentence to find if they exist twice
    for(int i=0; i< words.length; i++) {
      for(int j=0; j<words.length && j!=i ; j++) {
        if(words[i] == words[j]) {
          return false
        }
      }
    }
  return sentence.toString();
1.2
  // sort two arrays of spells in increasing order
  // run for loop to see if there is any charater that doesn't match.
  // we can tell by then.
1.3
/* in for loop of charadter array, when we find unicode '%20',
     replace it with charcter '%20'.
/*

1.4
public boolean canbePalindrome() {
	

Spacebar 
for(i =0; i< words.length ; i++) {
	if (words[i] != '  ' ) {
	if(wordsMap.containsKey(words[i].toLowerCase()) {
	wordsMap.put(words[i].toLowerCase(), num + 1);
	} else {
wordsMap.put(words[i].toLowerCase(), 1);
}
}
}

int oddChars =0;

// for loop - check all key, values in the map. 
// iterate through wordsMap from char a to z, A to Z
for (Map.Entry<Char, int> char : wordsMap.entrySet()) {
	if( (char.getValue %2) != 0) {
 		 oddChars++ ;
	}
}

// palindrome can't have more than one odd character. 
if ( oddChars >1 ) {
	return false;
}

return true;

}

runtime: O(N+M)
WordsMap input for loop O(N)
WordsMap O(M) iteration.


Input : Tact Coa
False

1.5
public class oneInsertAway(Str str1, Str str2) {
  int count = 0;
  int longerStringLength =0;
  if( str1.length >= str2.length) {
  	longerStringLength = str1.length
  }
  else {
  	longStringLength = str2.length
  }

  if( |str1.length - str2.length| <=1 ) {
    for(int i,j =0; i,j<longerStringLength; i++, j++;) {
      // e.g) ' ', a or ' ' , ' '
      if( ( str1[i] == null || str2[j] == null) {
      	if(count ==1 || count ==0) {
      	  return true;
        }
        return false;
      }
      if(count >=2) {
        return false;
      }
      // e.g ) ab, ba
      if(str1[i] != str2[j] ) {
        count++;
        if( (str1[i] == str2[j+1]) && (str1[i+1] == str2[j]) ) {
          count++;
          i = i+2;
          j = j+2;
        }
      }
    }
    return true;
  }
}
1.6

public String oneInsertAway(String sentence) {
  Map<String, Long> charCount = new HashMap<>();
  String compressed;
  for (char charachter : sentence.toLowerCase().toCharArray()) {
      String charAsString = Character.toString(charachter);
      if (charCount.containsKey(charAsString)) {
          long val = charCount.get(charAsString) + 1;
          charCount.put(charAsString, val);
      } else {
          charCount.put(charAsString, 1);
      }
  }
  for (String key : charCount.keySet()) {
      compressed +=(key + charCount.get(key));
  }
  System.out.println(charCount);
  if(sentence.length > 2*charCount.size()) {
    return compressed;
  }
  return sentence;
}

1.7
public int[][] 90Rotate(int[][] array) {
	int[][] result = new int[array.length][array[0].length];	
	for(int row =0; row< array.length; row++) {
		for(int col =0; col < array[0].length-1; col++) {
			result[row][col] = array[col][array.length-1-row];
		}
	}
	return result
}

1.8
public int[][] zeroMatrix(int[][] array) {
	int[][] result = new int[array.length][array[0].length];	
	int[] zeroLocations = new int[array.length*array[0].length];
	for(int row =0; row< array.length; row++) {
		for(int col =0; col < array[0].length-1; col++) {
			if(array[row][col] == 0 ) {
				zeroLocations
				for(int row2=0; row2<array.length; row2++) {
					result[row2][col] =0;
				}
				for(int col2=0; col2<array[0].length-1; col2++) {
					result[row][col2] =0;
				}				
			}
			else {
				result[row][col] = array[row][col];
			}
		}
	}
	return result
}
1.9
public Boolean isRotation(String str1, String str2) {
		// first find overlapping part
		twoStr1s = str1 + st1;
		return twoStr1s.isSubstring(str2);
}

2.1
// put values into key, value map and delete node whenever head.next.data is in the map.
Node deleteDuplicatesNode(Node head) {
	Node n = head;
  HashMap newmap = new HashMap();
	
	while (n.next != null) {
		if (newmap.containsKey(n.next.data) {
			n.next = n.next.next;
		}
		else {
			newmap.put(n.next.data, 'exist');
			n.next = n.next.next;
		}
	}
	return null
}

// make headCurrent, headSecond. one start. one iterate. 
when found the duplicate, remove all duplicates. when the head == null, 
set two heads as headSecond.next. start over the process.

2.2
Node KthToLast (Node head, int k) {
	Node n = head;
  HashMap newmap = new HashMap();
	int nodecounter = 0;
	while (n.next != null) {
			newmap.put(nodecounter, n.next );
			n.next = n.next.next;
			nodecounter++;
	}
	return newmap.get(newmap.size() - k);
}

2.3

Node deleteNode(Node middle) {
	Node n = middle;
	middle.data = middle.next.data;
	middle.next = middle.next.next;
	return null;
}

2.4



H.W ) 1-5,6,8,9,  1,2,3,4.










# References
1.5
aple
apple

a
aa

a
aaa

''
A

A
A

 ab
 ba
 One Away: There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away.
						
EXAMPLE
pale, pIe -> true pales. pale -> true pale. bale -> true pale. bake -> false Hints: #23, #97, #130 

1.6
assertEquals(7, charCount.get("e"), 0);  

1.9
waterbottle 
erbottlewat
-erbottle

waterbottlewater
waterbottlewat
apple
pleap
-ple

app
ppa
-pp is 

find the overlapping part 

DiffOverlap
OverlapDiff

DiffOVerlapDiffOverlap
OverlapDiff
DiffOverlapDiff

2.2
Node deleteNode(Node head, int d) {
	Node n = head;
	if(n.data == d) {
		return head.next;
	}
	while (n.next != null) {
		if (n.next.data == d) {
			n.next = n.next.next;
			return head;
		}
		n = n.next;
	}
	return head;

}