Amazon Interview Question
Software Engineer / Developersi feel we refer to space complexity as O(n) only if the extra data structure used(as in this case a hash table)is proportionally dependent on the input string....
but in the hash table case its size isnt dependent on the input string....hence it is O(1) nt o(n)...ne thoughts on this?
well, seems easy...lets have a variable 'char c' and I store the character at the first index of the array at 'c'. Now if the character at next index is itself different from the value stored at 'c', voila, you have your first non repeated character, which is the one at first index.
now if the characters at subsequent indexes are same as 'c', they are all repeated. As soon as you find one which is different from the character stored at 'c', you have your answer.
public void displayRev(string str)
{
if (str.Length > 0)
displayRev(str.Substring(1, str.Length - 1));
else
return;
Console.Write(str[0]);
}
public void nonrepeat(string str)
{
char[] ch = str.ToCharArray();
int j=0;
bool flag=false;
for(int i=1;i<ch.Length;i++)
{
if(ch[i]==ch[j])
{
flag=true;
}
else if(flag==false)
{
Console.Write("First non repeating character is {0}",ch[j]);
break;
}
else if(flag==true)
{
if (ch[i] != ch[i + 1])
{
Console.Write("First non repeating character is {0}", ch[i]);
break;
}
else
j++;
continue;
}
j++;
}
}
How about something like this
char firstNonRepeat(char * a)
{
int minIndex = 0;
for(int i =0 ;i <26 ; i++)
{
int count = 0;
int firstIndex = -1;
for(int j =0 ; j < strlen(a) ;j++)
{
if(a[j] == 'a' + i)
{
count++;
if(count == 1)
firstIndex = j;
if(count > 1)
break;
}
}
if(count == 1 && minIndex > firstIndex)
minIndex = firstIndex;
}
return a[minIndex];
}
The run time is 26n which O(n) and it can be the case that we also need to check for other characters. We can then add everything to an array and check.
Python:
def first_non_repeating(string):
if len(string) == 0:
return None
elif len(string) == 1:
return string[0]
i = 1
previous = string[0]
continuity = 1
while i < len(string):
current = string[i]
if current == previous:
continuity += 1
else:
continuity = 1
if continuity == 1:
if i == 1:
return previous
elif i == len(string) - 1:
return current
elif string[i + 1] != current:
return current
previous = current
i += 1
if continuity > 1:
return None
@dream
- sepsun December 29, 2009I beg to contradict.
when you say the space complexity is O(1), what you are implying is essentially that the size of the hash table is constant irrespective of the word given, which is not the case. On the other hand, when you say that the space complexity is O(n), you would be implying that the size of the hash table would never exceed n elements(n being the no of characters in the string). In my opinion, O(n) better represents the space complexity of the hash table.
comments invited.