Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
3 Cards in this Set
- Front
- Back
|
Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?
|
Details to confirm: * Is the string an ASCII string or Unicode. * Suppose for simplicity maximum length string =128 characters. - Create a 128 length boolean array. - Loop through the string getting the char value at the specified index i and using it like the index in the boolean array. - If this value is TRUE, it means it is the second time you see this character, so you can immediately return FALSE. - After that, do the value TRUE. - When the loop finishes, return TRUE The time complexity = O(n) = O(128) = O(1) The space complexity is O(1) |
|
|
Given two strings, write a method to decide if one is a permutation of the other. |
Details to confirm: * Is comparison case sensitive ? * Is whitespace significant ? We just need to compare the sorted versions of the strings. It's clean, simple and easy to understand but it's NOT optimal. (Use toCharArray() and java.util.Arrays.sort) Details to confirm: * Suppose for simplicity maximum length string =128 characters. - If the strings don't have the same length, return FALSE. - Create a 128 length int array. - Loop through the first string and count the number of each char storing it in the int array (intArray[str1.charAt(i)]++) - Loop through the second string, but this time decrease by 1 each occurrence of the char (intArray[str1.charAt(i)]--). After that, immediately check if the number is negative. In this case return FALSE. - When the second loop finishes, return TRUE. The time complexity = O(S1 + S2) = O(256) = O(1)The space complexity is O(1) |
|
|
Write a method to replace all spaces in a string with '%20'. You may assume that the string has sufficient space at the end to hold the additional characters and that you are given the "true" length of the string. (Note: if implementing in Java, please use a character array so that you can perform this operation in place) |
Approach: Working backward Details to confirm or assume: * Assume string has sufficient free space at the end. * Because immutability of String in Java, we will use a char array. At the end, suppose we have a function called charArrayToString. - Convert the String to a char array (str.toCharArray) - Get the findLastCharacter going backward in a for loop. Adding one to the result we'll get the trueLength. - The algorithm employs a two-scan approach. In the first scan, we count the number of spaces using trueLength. The index would be index = trueLength + spaceCount * 2 - In the second pass, which is done in reverse order, we actually edit the string. When we see a space, we replace it with %20. If there is no space, then we copy the original character. |
