0

I'm reading Cracking the Coding Interview, and there's the question, "Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?"

Assuming ASCII strings, an obvious solution is to store whether a character has been used before in an array of 256 booleans. A more space efficient solution is to instead use a bit vector. My understanding is that would be implemented something like this: an array of integers, where each bit of an integer is either a true or false value. So, let's say we have 32 bit integers. Then we need an array of 8 such integers to get 32*8 = 256 booleans stored in bits. These will be stored in only 256 bits. On the other hand, if a boolean is stored in n bits, we will need n * 256 bits to store the array.

Here's where I'm confused. The book says that using a bit vector decreases space by a factor of 8. This would only be true if n=8, but I don't think booleans are stored in 2 bytes in Java (the language the book uses), so that is not correct. So, what am I doing wrong/why does using a bit vector decrease space by a factor of 8?

EDIT: I know that there are 8 bits in a byte, the above was just a dumb mistake. Question is answered by comments, as well as an explanation for my confusion.

EnriqueC
  • 67
  • 8
  • 4
    A byte is 8 bits long, boolean is stored in a byte, hence the factor 8. – Maurice Perry Dec 19 '19 at 06:54
  • @ElliottFrisch For ASCII strings at least, there are only 128 characters in the ASCII standard so you could just use two 64-bit `long`s, if arrays are not allowed. – kaya3 Dec 19 '19 at 07:05
  • As @MauricePerry points out, the question is flawed; you said *"if a boolean is stored in n bits"*, then *"This would only be true if n=8"* which it is, because booleans are stored in one byte which takes 8 bits of memory. I don't know how you got from n=8 bits to 2 bytes. – kaya3 Dec 19 '19 at 07:09
  • Yes that was a dumb mistake, I recognize that there are 8 bits in a byte must've just been a lapse in thinking. However, I researched the question before of how many bytes are in a java boolean and was confused because if you google "how many bytes are java booleans" the google suggested result is "9 bytes", but looking into it further shows that that's actually just 1 byte of payload and 8 bytes of header. I suppose this space usage is optimized in an array of booleans? This was very unclear to me though, hence the question – EnriqueC Dec 19 '19 at 07:12
  • That Google result is to [this](https://stackoverflow.com/a/17716385/12299000) Stack Overflow answer, which is talking about the size of a `Boolean` object, not a `boolean` array component. Generally, a `boolean` array stores one `boolean` per byte since that's the smallest addressable unit of memory. – kaya3 Dec 19 '19 at 07:17
  • 1
    Ahhh thank you so much @kaya3!!! I was still left a little unsure before you wrote that. I've barely ever used Java, hence my confusion. – EnriqueC Dec 19 '19 at 07:25

0 Answers0