Cracking the coding Interview: Unique Character (Working of if block)

Question

I want to understand the working of if block from the below code. For example: if my string is rock, then the ASCII would be char_set[r] = 114 char_set[o] = 111,char_set[c] = 99,char_set[k] = 107. So for the first time when char_set[r] = 114 will come to if block then what is going to be checked? Since char_set is boolean type so it could be either true or false but according to my understanding initially char_set[r] = 114 is not set to either true or false. So how can we check if it is either true or false inside the if block. I have looked at the previous related questions but my question was different and couldn't find anything. This question is taken from the book Cracking the coding interview.

public boolean isuniqueChars2(String str) {

       if (str.length() > 128) 
        return false;

    boolean[] char_set = new boolean[256];
    for (int i = 1; i < str.length(); i++)
    {
        int val = str.charAt(i);
        if (char_set[val]) {
            return false;
      }
        char_set[val] = true;
    }
    return true;
}

How can char_set[r] = 114 when char_set is a boolean[]? — aioobe
– aioobe, Commented Jun 16, 2015 at 21:48
In Java, you are not using ASCII. charAt can return 0 to 65535, which is a Unicode/UTF-16 code unit.Please take some time later to understand that. — Tom Blodget
– Tom Blodget, Commented Jun 16, 2015 at 23:11

user3707125 · Accepted Answer · 2015-06-16 21:49:26Z

1

Arrays are initialized with default values upon creation. Default value for boolean type is false.

answered Jun 16, 2015 at 21:49

user3707125

3,48916 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Jashaszun Over a year ago

What does this have to do with the question?

user3707125 Over a year ago

@Jashaszun, I assume that it answers it, I understood char_set[r] = 114 notation as char_set[r] "is the same as" char_set[114], and concluded that the author does not know about default value for array items.

Jashaszun Over a year ago

But the default value for booleans is false, which is intended for this sample of code. Whether or not the asker understands this is irrelevant, since there's no problem with this.

user3707125 Over a year ago

@Jashaszun, "So for the first time when char_set[r] = 114 will come to if block then what is going to be checked?", do you still think that the problem is not in understanding the default value?

Jashaszun Over a year ago

I believe that the misunderstanding is in the usage of characters for indexing into the boolean array, not in the default value of booleans.

Jashaszun · Accepted Answer · 2015-06-16 21:52:17Z

0

What char_set does is for every ASCII value, it stores a boolean value for whether you've seen that character before or not.

So essentially, it is saying this (in somewhat pseudocode):

for (every character in the string) {
    int val = str.charAt(i); //get the current character;
    if (char_set[val]) // if (we've seen the current character already)
        return false; // not made of unique characters
    char_set[val] = true; //store that we've seen the current character;
}
return true; // we got through all the characters, so it must now be unique.

What is really happening is that if your input string is rock, then char_set['r'] is true, and so is char_set['o'], char_set['c'], and char_set['k'].

answered Jun 16, 2015 at 21:52

Jashaszun

9,2503 gold badges31 silver badges58 bronze badges

Comments

John Bollinger · Accepted Answer · 2015-06-16 22:06:14Z

The elements of char_set are booleans. They are all initialized to the default value for that type (false), when you create the array. The values of some of those elements may be tested in

        if (char_set[val]) //...

(yielding one of the two possible values of type boolean, whichever was most recently set) and may be set to true in

        char_set[val] = true;

in each case, val is the index of the element involved, not the value to set or read.

Note, however, that this code has at least two significant problems:

String.charAt() returns values of type char, whose numeric range goes up to 65535. Therefore, the code presented can easily generate an ArrayIndexOutOfBoundsException.
Strings are indexed starting from 0, so the first character in the string is not included in the analysis. In a general sense, this could be intentional, but in an "analyze this code" sense it is important to recognize.

Collectives™ on Stack Overflow

Cracking the coding Interview: Unique Character (Working of if block)

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related