## N/A Interview Question for Nones

• 0

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

Normally u would use a set for that. But if you can restrict the range of characters to ASCII (vs. Unicode for example) you can use an array of booleans or a bit vector. Just mark every character as seen[S.charAt(I)] = true after checking seen[s.charAt(I)] ... I think you get the idea. This has time complexity O(n) and space complexity O(n).

Your solution is of space complexity O(1) but time complexity O(n^2). That square comes from contains that will loop from 0 to i, where i is looped from 0 to n. So n^2 / 2 to be exact...

edit:
no, it's not O(n^3) because substring(..).contains() is not nested (although a bit unnecessary copying...)

Comment hidden because of low score. Click to expand.
1
of 1 vote

If you are allowed to change the string you are given you can sort it and then looking for duplicates can be done in O(n); so the total is O(nlog(n)) for the sort;
If you cannot do that you must search the whole string for each letter you run across. Of course you can double the speed by only looking forward from where you are.
this will cost you O(n^2)

``````for(int i =0; i < len-1; i++)
{
for(int j = i+1; j < len; j++)
{
if(input[i] == input[j]) return false;
}
}
return true;``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

As per my analysis, I think that it would take O(n^3) where n is the size of string. Since outer loop runs O(n) time, then substring method O(n) and contains O(n). I think a better approach that runs in O(n^2) time, similar to your approach is that (Pseudo code)

``````for each char in string:
i <-- position of char in string
for j from i-1 to 0:
if charAt(i)==charAt(j)
return false;
return true;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class HelloWorld{
public static void main(String...args){
String s=args;
int a=0;
for(int i=0;i<s.length();++i){
int bit=1<<(s.charAt(i)-'a');
if((a | bit) == a){     // If there is no change after OR operation, then it's a repeatition.
System.out.println("Yes");
return;
}
a=a | bit;
}
System.out.println("No");
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be done in one loop i.e. 0(n) to determine if string has all unique characters without extra space complexity O(1).
int xor=0;
for(int i=0;i<str.length();i++){
xor=xor^(int)str.charAt(i);
}

return (xor==0);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

@smile.jain, your approach will not work. Consider the string str = "ABC", XOR of each character is not zero so your function will return false, but for given string ans is true as it contains all unique character.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Free hand code, O(n) space and time

boolean isUnique(String str){
Map<Character, Boolean > map = new HashMap<String, Boolean>;

for(Character c : str.toCharArray()){
if(map.ContainsKey(c)){
return false;
} else {
map.put(c);
}
return true;
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.