4
\$\begingroup\$

I am currently reviewing CTCI(Cracking the Coding Interview)

The question is asking me to implement an algorithm which checks whether the characters in a string are all unique however they do not want me to use any auxillary data structures

My Algorithm is relatively straight forward, Two nested loops one starting at 0(i) and another at 1(i+1)

If the condition finds two characters that are equal then I print duplicate characters have been found.

 public static void checkUnique(String s)
{


    for(int i = 0; i<s.length(); ++i)
    {
        for(int j = i +1; j<s.length(); ++j)
        {
            if(s.charAt(i) == s.charAt(j))
            {
                System.out.println("Duplicates found");
            }
        }
    }


}

My question

  1. Is this an optimal algorithm, my second approach was to sort, and find a pair which contains the same characters.
  2. Obviously a hashmap would be beneficial here, but questions does not really want me to use it.

I have refactored the code and hopefully now it is correct.

Is there any way of reducing it to an O(N) runtime. What if we keep track of the Unicode code's for each char character. I doubt O(N^2) is the best we can do here.

\$\endgroup\$
13
  • \$\begingroup\$ Your implementation Is O(n^2) indeed. The sort approach would get you to O(n * log(n)). You can get to O(n) using a hashset. You can also do it in O(n) using an array of bools of size 256, which would effectively emulate a hashset for 1-byte characters. Not sure from what you wrote if you should not use data structures from standard library or if you are even asked to not implement them on your own... \$\endgroup\$
    – slepic
    Jul 22 '20 at 13:29
  • \$\begingroup\$ Oh actually, your implementation Is O(n) but that's because It's flawed. It just does not do what you claim it does. That makes your question off topic here. Please test your code before posting the next time. \$\endgroup\$
    – slepic
    Jul 22 '20 at 13:37
  • \$\begingroup\$ How so, I have tested the inputs "abcdefghijklmnopqrstuvwxyz", it worked, similarly if included duplicate characters it still worked. Am i missing something here \$\endgroup\$ Jul 22 '20 at 13:44
  • 2
    \$\begingroup\$ Love the question, but I voted to close since this is not working code. Please update the question with working code (include tests!!) so that after we can vote to re-open \$\endgroup\$
    – konijn
    Jul 22 '20 at 14:08
  • 1
    \$\begingroup\$ For those in the VTC queue, the edit should fix the question. \$\endgroup\$
    – pacmaninbw
    Jul 22 '20 at 15:43
5
\$\begingroup\$

A way to optimize it would be to return as soon as you have found a duplicate, unless the question specifically asks you to list all duplicates.

You could refactor it to something like that:

public static boolean checkUnique(String s) {
    int len = s.length();
    for (int i = 0; i < len; i++) {
        int c = s.codePointAt(i);
        int next = s.indexOf(c, i + 1);
        if (next > i) {
             return false;
        }
    }
    return true;
}

It isn't more efficient as your solution, but I doubt there is an algorithm that can do it better.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Early return sure. But lastIndexOf can only decrease performance. Further there Is also no point to use i++ over ++i, why you even mention it? \$\endgroup\$
    – slepic
    Jul 23 '20 at 3:24
  • \$\begingroup\$ lastIndexOf can decrease performance compared to what? I mentioned i++ because I find that easier to read. \$\endgroup\$ Jul 23 '20 at 5:05
  • \$\begingroup\$ Compared to scanning only those characters that can change the result. In every iteration you're going to scan one more character then you need to (unless you find a duplicate). But that's miniscule anyway. And for i++ being easier to read, that's just subjective. Either be explicit about that being your personal opinion or don't include it in your answer at all, as the answer should not be opinion based. \$\endgroup\$
    – slepic
    Jul 23 '20 at 5:21
  • \$\begingroup\$ Ok, I changed both in my answer. \$\endgroup\$ Jul 23 '20 at 7:13
1
\$\begingroup\$

If I were your interviewer, I'd not hire you, because of that piece of code.

The one absolute showstopper is that your method prints to System.out instead of returning a boolean.

Even if no one told you explicitly, from a professional developer we expect that algorithms just compute something and give the results to their callers (by means of a boolean return value), and not write it to the user. But your solution mixes the algorithm with text output.

Otherwise, your solution is okay, given the condition that no additional data structure is to be used (by the way, that's a strange condition, not representative for professional development).

\$\endgroup\$
7
  • \$\begingroup\$ What if I told you the solution in the book uses an int as a bitset to store occurrences? Would that count as an auxiliary data structure? stackoverflow.com/questions/19484406/… \$\endgroup\$
    – spyr03
    Jul 22 '20 at 15:48
  • 1
    \$\begingroup\$ @spyr03 Even with ASCII, the int need to be at least of the 128-bit variant, and in 2020, ASCII is simply outdated. With Unicode, you'd need an unlimited-length-integer (or at least some 200kbit), and that surely is an auxiliary data structure. And don't fall into the trap of operating on the UTF-8 representation bytes, that one will give wrong results. \$\endgroup\$ Jul 22 '20 at 15:58
  • 1
    \$\begingroup\$ So much this, you stole my answer ;) \$\endgroup\$
    – konijn
    Jul 22 '20 at 16:13
  • \$\begingroup\$ Yea, I forgot to remove this. The Print was for testing purposes. My bad. \$\endgroup\$ Jul 22 '20 at 16:23
  • \$\begingroup\$ "...given the condition that no additional data structure is to be used (by the way, that's a strange condition, not representative for professional development)." - hardly, if the professional development environment is for embedded or high-performance computing. If I'm working on some wearable device and I've got 16KB to use for everything, I will be bending over backwards to avoid allocating additional data structures. Granted, that might not be the case on Windows or web servers or even in mobile phones nowadays, but even so. \$\endgroup\$ Jul 23 '20 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.