Clash Royale CLAN TAG

Why does 'Cracking The Coding Interview' advices to create an array chars[128]?

As far as I know, there are 65,535 chars in the Java language.
Meanwhile, Unicode 11.0, contains a repertoire of 137,439 signs.
I'm reading Cracking The Coding Interview and can't understand the internals of the present solution.

Why does the book advice to create an array chars[128] in a case if String represents Unicode if there can be 137,439 Unicode signs?

I'm not familiar with encoding, could you explain me it in details?

Is Unique: Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

SOLUTION

You should first ask your interviewer if the string is an ASCII string or a Unicode string. Asking this question
will show an eye for detail and a solid foundation in computer science. We'll assume for simplicity the character
set is ASCII. If this assumption is not valid, we would need to increase the storage size.
One solution is to create an array of boolean values, where the flag at index i indicates whether character
i in the alphabet is contained in the string. The second time you see this character you can immediately
return false.
We can also immediately return false if the string length exceeds the number of unique characters in the
alphabet. After all, you can't form a string of 280 unique characters out of a 128-character alphabet.
I It's also okay to assume 256 characters. This would be the case in extended ASCII. You should
clarify your assumptions with your interviewer.
The code below implements this algorithm.

boolean isUniqueChars(String str) {
if (str.length() > 128) return false;
boolean char_set = new boolean[128];
for (int i= 0; i < str.length(); i++) {
int val= str.charAt(i);
if (char_set[val]) { //Already found this char in string
return false;
}
char_set[val] = true;
}
return true;
}


1 Answer
1

The answer provided by the book advises the reader to ask if the characters are in Unicode or ASCII to demonstrate some insight.

However the writer proceeded with assuming ASCII is used which is 128 characters so this is why a 128 array size is used.

It also mentions that extended-ASCII could be assumed which is 256 characters. In this case a 255 size array should be used .

The writer also mentions that in case of Unicode the array size should be increased but does not really specify the size.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.