Amazon Interview Question for Software Engineer / Developers






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

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

- sepsun December 29, 2009 | Flag Reply
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...

- Anonymous December 23, 2009 | Flag Reply
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?

- dream December 23, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Kunal Gaind December 24, 2009 | Flag
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.

- P December 23, 2009 | Flag Reply
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]

- yhu December 25, 2009 | Flag Reply
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?

- Anonymous December 29, 2009 | Flag Reply
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)

- Anonymous December 29, 2009 | Flag Reply
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.

- sgt January 09, 2010 | Flag Reply
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.

- bhas January 14, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

totally bs

- Anonymous January 19, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

total bs

- Anonymous January 19, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thats O(n^2) dude !!

- TestCoder January 27, 2010 | Flag
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..

- sharath January 27, 2010 | Flag Reply
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[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++;
}

}

- Rohan January 29, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Rohan January 29, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Ram January 30, 2010 | Flag Reply
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.....

- Yoda February 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int main ()

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

}

- test March 16, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Anonymous March 16, 2010 | Flag Reply
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;
}

- AbhijeetP July 11, 2011 | Flag Reply
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[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

- Will.Conrardy March 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Will.Conrardy March 07, 2015 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More