## Amazon Interview Question for Software Engineer / Developers

• 0

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

@dream
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.

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

amazon has come a full circle. now they have started asking routine questions. seems their question bank has dried down.
this Q is a directly lifted from programming interviews exposed "arrays and strings" chapter...

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

i 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?

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

That's awesome and I think thats the right answer.........

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

@dream
absolutely right.
the space complexity here is O(1) since we are using an array of 256 characters only which is a constant amount.

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

Just because the data is character, so we can use a array with 128 chars to take as the hash
table. Array[(int)char]

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

sepsun is right...coz hash entries exist only if the character exists in the input...array.Hence O(n)
but if the extra space used is an array(say 256) characters then mayb we can say it as O(1).What say?

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

sepsun is right...coz hash entries exist only if the character exists in the input...array.Hence O(n)
but if the extra space used is an array(say 256) characters then mayb we can say it as O(1).What say?i think the confusion is b/w the hash and the array(256 chars)

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

The hashtable implemented using an array would technically take O(1) space. (for the reasons described by dream).

But in this question, I guess the interviewer was looking for solution not involving a hash table which is the main issue.

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

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.

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

totally bs

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

total bs

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

Thats O(n^2) dude !!

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

If the string is sorted, you can do it without using a hashtable or any extra memory (in place) by comparing the cosecutive elements.. in O(n) time..

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

public void displayRev(string str)
{
if (str.Length > 0)
displayRev(str.Substring(1, str.Length - 1));
else
return;

Console.Write(str);
}
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++;
}

}

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

Pls ignore the first function displayrev()....

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

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.

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

maybe can use some dynamic hashing which keeps deleting nodes whenever a hash is collided....
or
can use bits of an int variable...or bit array.....

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

int main ()

``````{
printf("Test\n");
return 0;``````

}

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

``````int main () {
printf("Test\n");
return 0;``````

}

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

Use 1 bit per character. Assuming string is made of a-z chars.

``````char find_1st_nonrepeat( const char* str )
{
long result = 0;
for( int i=0; str[i]; ++i )
{
if( (( 1 << ( str[i] - 'a' ) ) & result) == 0 )
result = result | ( 1 << ( str[i] - 'a' ) );
else
return str[i];
}
return 0;
}``````

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

Python:

``````def first_non_repeating(string):
if len(string) == 0:
return None
elif len(string) == 1:
return string
i = 1
previous = string
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``````

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

Tested with these strings:
"aabbbccd"
"aaabccdd"
"abbccdd"
"aabbccdd"
"a"

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.