Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
Here is the code.
This is how it works
1) Iterate till the end of unique character window, saving the index of each char in array.
Lets say unique window starts at "x" and stops at "y"
and character at index "z" is repeated at "y" + 1
2) Reset the index in array for characters from "x" to "z" including "z"
3) Again start the procedure from "y". Note that we don't reset the indices for characters between "z" and "y" as we already know they are unique
int find_longest_unique_str(char *str)
{
int array[256], i, size, index, temp_size;
char *fast, *start, *slow, c, *temp, *dup;
for (i = 0; i < 256; i++)
array[i] = -1;
slow = start = str;
size = temp_size = index = 0;
while (*slow) {
fast = slow;
while (*fast) {
c = *fast;
if (array[c] == -1)
/* store the index */
array[c] = fast - str;
else
break;
fast++;
}
temp_size = fast - start;
if (temp_size > size) {
size = temp_size;
index = start - str;
}
/* pointer to duplicate char */
dup = str + array[c];
/* Reset values from "start" to "dup" including dup */
for (temp = start; temp <= dup; temp++) {
c = *temp;
array[c] = -1;
}
/* Again start from where we stopped; now we know that
* the characters between 'dup' and 'fast' are unique */
slow = fast;
start = dup + 1;
}
printf("size of longest unique string = %d\n", size);
return index;
}
private int longestSubString()
{
int start=0,len=1;
Set<Integer> subIndex = new HashSet<Integer>();
int[] v = new int[256];
for(int i=0; i<256; i++)
v[i]=-1;
for(int i=0; i<s.length() && start<s.length(); i++)
{
if(v[s.charAt(i)]<start)
{
v[s.charAt(i)]=i;
}
else
{
start=v[s.charAt(i)]+1;
v[s.charAt(i)]=i;
}
if(i-start+1>len)
{
len = i-start+1;
subIndex.clear();
subIndex.add(start);
}
else if(i-start+1==len)
{
subIndex.add(start);
}
}
System.out.print("Longest Substrings without repeating characters is : ");
Iterator<Integer> it = subIndex.iterator();
while(it.hasNext())
{
int l = it.next();
System.out.println();
for(int i=l; i<l+len; i++)
System.out.print(s.charAt(i));
}
return len;
}
The first one is more focused on using less memory. The second adds an array to record non-unique chars. Both utilize indexing to keep track of the longest unique string:
public class UniqueAscii {
private static int RAND_WORD_LENGTH = 100;
public static void main(String[] args) {
// iterate through random string
// add char to list of known chars
//
// String testString = "abcdefghijklmnopbrstuvcxyza";
String testString = "abcdefghijklmnopbrstuv";
char[] randomString = testString.toCharArray();
//char[] randomString = randomAsciiString(RAND_WORD_LENGTH);
System.out.println(randomString);
// char[] longest = longestUniqueCharsLowMemory(randomString);
char[] longest = longestUniqueCharsSpeed(randomString);
System.out.print("LONGEST: ");
System.out.println(longest);
}
public static char[] longestUniqueCharsLowMemory(char[] charString) {
int sIndex = 0, eIndex = 0;
int startIndex = 0, endIndex = 0;
for (int i=1; i<charString.length; i++) {
for (int j=startIndex; j<=endIndex; j++) {
if (charString[i] == charString[j]) {
startIndex = j;
}
}
endIndex = i;
if ((endIndex - startIndex) > (eIndex - sIndex)) {
sIndex = startIndex;
eIndex = endIndex;
System.out.print("current longest: ");
System.out.println(subChar(charString, startIndex, endIndex));
}
}
return subChar(charString, sIndex, eIndex);
}
public static char[] longestUniqueCharsSpeed(char[] charString) {
int[] asciiCharsIndexes = new int[256];
for (int i=0; i<asciiCharsIndexes.length; i++)
asciiCharsIndexes[i] = -1;
asciiCharsIndexes[(int)charString[0]] = 0;
int sIndex = 0, eIndex = 0;
int startIndex = 0, endIndex = 0;
for (int i=1; i<charString.length; i++) {
if (asciiCharsIndexes[(int)charString[i]] == -1)
asciiCharsIndexes[(int)charString[i]] = i;
else {
int lastMatchIndex = asciiCharsIndexes[(int)charString[i]];
for (int j=lastMatchIndex; j>=startIndex; j--)
asciiCharsIndexes[(int)charString[j]] = -1;
startIndex = lastMatchIndex + 1;
}
endIndex = i;
if ((endIndex - startIndex) > (eIndex - sIndex)) {
sIndex = startIndex;
eIndex = endIndex;
System.out.print("current longest: ");
System.out.println(subChar(charString, startIndex, endIndex));
}
}
return subChar(charString, sIndex, eIndex);
}
public static char[] subChar(char[] cArray, int start, int end) {
char[] rVal = new char[end-start+1];
int index = 0;
for (int i=start; i<=end; i++)
rVal[index++] = cArray[i];
return rVal;
}
public static char[] randomAsciiString(final int stringLength) {
char[] randomString = new char[stringLength];
int i=0;
int c;
do {
c = (int)(Math.random()*255);
randomString[i] = (char)c;
//System.out.print(c + "=" + randomString[i] + " ");
i++;
}
while (i < stringLength);
return randomString;
}
}
c++ version(look "for strings with a-z. Can be easily extended for entire ASCII table" below) works correctly for you case
in function longestUniqueCharsLowMemory, in if clause put startIndex=j+1, and it wrks fine... as you want to start from the next position, jth position is already matched and you should exclude this.
public static char[] findLongestUnique(char[] charString){
int sIndex=0;int eIndex=0;
int startIndex=0;int endIndex=0;
for(int i=0;i<charString.length;i++){
for(int j=startIndex;j<=endIndex;j++){
if(charString[i]==charString[j])startIndex=j+1;
}
endIndex=i;
if(endIndex-startIndex>eIndex-sIndex){
sIndex=startIndex;
eIndex=endIndex;
}
}
return subChar(charString,sIndex,eIndex);
}
wrks fine
I glanced through the code and after discounting for the main() and randomAsciiString() methods, the remaining code still seems too long even if it works. It might be good exercise to try rewriting or optimizing for shorter code here. Even if you get to do this on a computer during an interview, the more code you write the higher the chance there's some bug and also the harder it is for the interviewer to agree with your solution.
#include<iostream>
using namespace std;
//given an ASCII string, return the longest substring with unique characters.
//Ex. dabcade => bcade
int maxcount=0;
char a[10] = "dabcade";
int sting[10];
bool check(char k,int j,int from) //checks if that character is already present. Iterates from the poisition i
{
bool returnval = true;
for(int i=from;i<j;i++){
if(a[i]==k){
returnval = false;
}
}
return returnval;
}
int main()
{
int position;
for(int i=0;i<strlen(a);i++){
sting[i] = int(a[i]- int('a'));
}
int count = 0;
for(int i=0;i<strlen(a);i++){
for(int j=i;j<strlen(a);j++){
if(check(a[j],j,i)){
count++;
if(maxcount<count){
maxcount = count;
position = j;
}
}
else
break;
}count=0;
}
cout<<"the longest increasing string with unique characters is:\n";
for(int i=(position-maxcount)+1;i<=position;i++){
cout<<a[i];
}
cout<<endl;
}
Here is my Python version.
def longest_unique_substring (str):
longest = ""
charset = []
current = 0
marked = current + 1
while current < len(str):
if str[current] in charset:
if len(longest) < len(charset):
longest = "".join(charset)
charset = []
current = marked
marked = marked + 1
else:
charset.append(str[current])
current = current + 1
if len(longest) < len(charset):
longest = "".join(charset)
return longest
#include<stdio.h>
#include<conio.h>
#include<iostream.h>
int main()
{
char *start,*end,*p,*q,*str="abcabhyuiopqp";
int a[26],i,len=0,maxLen=0;
for(i=0;i<26;i++)
a[i]=0;
start=str;
end=str;
while(*str)
{
if(++a[*str-97]>1||*(str+1)=='\0')
{
len=str-start;
if(maxLen<len)
{
maxLen=len;
p=start;
q=str-1;
}
start=str;
for(i=0;i<26;i++)
a[i]=0;
}
str++;
}
cout<<"\n";
while(maxLen--)
{
cout<<*p++;
}
getch();
return 0;
}
for strings with a-z. Can be easily extended for entire ASCII table
string noDuplicatesLongestSub(const string &strData)
{
vector<int> vIndexTable(26, -1);
size_t nMaxSubIndex = 0;
size_t nMaxSubLen = 0;
size_t nCurSubIndex = 0;
size_t nCurSubLen = 0;
size_t nLen = strData.length();
for (size_t nIdx = 0; nIdx < nLen; ++nIdx)
{
size_t nTableIndex = strData[nIdx] - 'a';
bool bCheckSub = true;
if (vIndexTable.at(nTableIndex) == -1 ||
(vIndexTable.at(nTableIndex) != -1 && vIndexTable.at(nTableIndex) < nCurSubIndex))
{
vIndexTable.at(nTableIndex) = nIdx;
++nCurSubLen;
bCheckSub = false;
}
if (bCheckSub || nIdx == nLen - 1)
{
if (nCurSubLen > nMaxSubLen)
{
nMaxSubLen = nCurSubLen;
nMaxSubIndex = nCurSubIndex;
}
nCurSubLen = nIdx - vIndexTable.at(nTableIndex);
nCurSubIndex = vIndexTable.at(nTableIndex) + 1;
vIndexTable.at(nTableIndex) = nIdx;
}
}
return strData.substr(nMaxSubIndex, nMaxSubLen);
};
Here is the super cool python solution : Please Verify
Input is assumed to be a valid alphabet. Logic can be extended to any number of character-set
DP Solution :
len[i] = maximum length of the string if we have ith character as the last character in our substring
len[i] = min{currentindex[c] - previndex[c],len[i-1]+1}
len[i] = 0 if i<0
Runtime : O(n)
Python implementation :
import sys
alphabets = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
lengtharr = []
def calcLength(inptstr) :
indexarr = dict()
strlen = 0
global alphabets
global lengtharr
for element in alphabets :
indexarr[element] = 0
for element in inptstr :
strlen += 1
dplen = 0
for i in range(0,strlen):
char = inptstr[i]
currentindex = i+1
previousindex = indexarr[char]
lengtharr.append(min(currentindex-previousindex,dplen + 1))
dplen = lengtharr[i]
indexarr[char] = i + 1
def printLongestSubString(inptstr):
global lengtharr
maxlength = 0
maxindex = 0
for i in range(0,len(lengtharr)) :
if(lengtharr[i] >= maxlength):
maxlength = lengtharr[i]
maxindex = i
print "Largest Substring : ",inptstr[(maxindex+1)-maxlength:maxindex+1]
if __name__ == '__main__' :
calcLength(sys.argv[1])
printLongestSubString(sys.argv[1])
Runtime: O(1)
public static String maxUniqueSubstring(String str) {
HashMap<Character, Integer> chars = new HashMap<>();
for (int i = 0; i < str.length(); i++) {
if (chars.containsKey(str.charAt(i))) {
int k = (i > str.length() - chars.get(str.charAt(i)) ? i : chars.get(str.charAt(i)) + 1);
String s0 = maxUniqueSubstring(str.substring(0, k));
String s1 = maxUniqueSubstring(str.substring(k));
return (s0.length() < s1.length() ? s1 : s0);
}
chars.put(str.charAt(i), i);
}
return str;
}
public class Problem7 {
//given an ASCII string, return the longest substring with
//unique characters. Ex: dabcade => Ans: bcade.
public static void main (String [] args){
char[] a = "dabcade".toCharArray();
String[] strs ;
String temp="";
boolean flag =true;
//int j =0;
for (int j =0; j<a.length-1 && flag;j++)
{
flag=false;
//temp="";
for (int i = j ; i<a.length;i++)
{
char c =a[i];
//System.out.println(c);
//System.out.println(temp);
if(temp.indexOf(c)>=0)
{
//strs[i]=temp;
System.out.println(temp);
temp="";
flag=true;
break;
}
else
{
temp=temp +c;
//System.out.println("jjj" + temp);
}
}
if(!flag)
{
System.out.println(temp);
}
}
}
}
def longest_unique_substring(data):
tempset = set()
current_substring = ''
longest_substring = ''
for char in data:
if char not in tempset:
current_substring+=char
else:
# Reset tempset
tempset = set()
if len(current_substring) > len(longest_substring):
longest_substring = current_substring
current_substring = ''
if len(current_substring) > len(longest_substring):
longest_substring = current_substring
return longest_substring
public class UniqueLongestString {
public static void main(String args[])
{
String abc = "abcdegfdrikm";
int arrays[] = new int[26];
int start = 0, length = 0, storeLength =0;
for(int iCount = 0; iCount < abc.length(); iCount++)
{
arrays[(abc.charAt(iCount))-97]= arrays[(abc.charAt(iCount))-97] + 1;
if(arrays[(abc.charAt(iCount))-97] > 1)
{
System.out.println("value is: " + abc.charAt(iCount) + ":" + iCount);
start = getStart(abc, iCount) + 1;
System.out.println("start is: " + start);
iCount = start;
if(length < storeLength)
storeLength = length;
else length=0;
arrays= new int[26];
}
length++;
}
System.out.println(length);
}
public static int getStart(String pass, int count)
{
for(int icnt=count-1; icnt>=0; icnt--)
{
if(pass.charAt(icnt) == pass.charAt(count))
return icnt;
}
return 0;
}
}
public class UniqueLongestString {
public static void main(String args[])
{
String abc = "abcdegfdrikm";
int arrays[] = new int[26];
int start = 0, length = 0, storeLength =0;
for(int iCount = 0; iCount < abc.length(); iCount++)
{
arrays[(abc.charAt(iCount))-97]= arrays[(abc.charAt(iCount))-97] + 1;
if(arrays[(abc.charAt(iCount))-97] > 1)
{
System.out.println("value is: " + abc.charAt(iCount) + ":" + iCount);
start = getStart(abc, iCount) + 1;
System.out.println("start is: " + start);
iCount = start;
if(length < storeLength)
storeLength = length;
else length=0;
arrays= new int[26];
}
length++;
}
System.out.println(length);
}
public static int getStart(String pass, int count)
{
for(int icnt=count-1; icnt>=0; icnt--)
{
if(pass.charAt(icnt) == pass.charAt(count))
return icnt;
}
return 0;
}}
package test20;
public class LongestSubString1 {
private static String SOURCE="abcd";
public static void main(String[] args) {
longestNonRepeatingSubString(SOURCE.toCharArray());
}
private static void longestNonRepeatingSubString(char[] chars)
{
int max=0;
int cur=0;
int start=0;
int end=0;
int cstart=0;
int cend=0;
int[] array=new int[256];
for(int i=0;i<chars.length;i++)
{
if(array[chars[i]]==0||array[chars[i]]-1<i-cur)
{
cur++;
cend=i;
}
else
{
if(max<cur)
{
max=cur;
start=cstart;
end=cend;
}
cur=i-array[chars[i]]+1;
cstart=array[chars[i]];
cend=i;
}
array[chars[i]]=i+1;
}
if(max<cur)
{
max=cur;
start=cstart;
end=cend;
}
System.out.println(String.valueOf(chars).substring(start,end+1));
}
}
//given an ASCII string, return the longest substring with unique characters. Ex: dabcade => Ans: bcade.
#include<stdio.h>
int main()
{
char str[81];
scanf("%s",str);
int pl=0,ph=0,cl=0,ch=0,pcnt=0,ccnt=0,i,j,A[26];
for(i=0;i<26;i++)
{
A[i]=0;
}
for(i=0;str[i]!='\0';i++)
{
if(A[str[i]-97]>0)
{
//printf("%d ",ccnt);
if(ccnt>pcnt)
{
//printf("%d",ccnt);
pcnt=ccnt;
pl=cl;
ph=ch-1;
}
for(j=cl;str[j]!=str[i];j++)
{
// printf("cnt %d ",ccnt);
A[str[j]-97]--;
cl++;
ccnt--;
}
A[str[j]-97]--;
cl++;
//ch++;
ccnt--;
i--;
}
else
{
//printf("%d ",ccnt);
A[str[i]-97]++;
ccnt++;
ch++;
}
}
if(ccnt>pcnt)
{
// printf("%d",ccnt);
pcnt=ccnt;
pl=cl;
ph=ch-1;
}
for(i=pl;i<=ph;i++)
{
printf("%c",str[i]);
}
return 0;
}
/*
timecomplexity:O(n*maxcnt) maxcnt=maxsubstring length
space complexity: O(1)
input:dabcade
output:bcade
*/
//given an ASCII string, return the longest substring with unique characters. Ex: dabcade => Ans: bcade.
#include<stdio.h>
int main()
{
char str[81];
scanf("%s",str);
int pl=0,ph=0,cl=0,ch=0,pcnt=0,ccnt=0,i,j,A[26];
for(i=0;i<26;i++)
{
A[i]=0;
}
for(i=0;str[i]!='\0';i++)
{
if(A[str[i]-97]>0)
{
//printf("%d ",ccnt);
if(ccnt>pcnt)
{
//printf("%d",ccnt);
pcnt=ccnt;
pl=cl;
ph=ch-1;
}
for(j=cl;str[j]!=str[i];j++)
{
// printf("cnt %d ",ccnt);
A[str[j]-97]--;
cl++;
ccnt--;
}
A[str[j]-97]--;
cl++;
//ch++;
ccnt--;
i--;
}
else
{
//printf("%d ",ccnt);
A[str[i]-97]++;
ccnt++;
ch++;
}
}
if(ccnt>pcnt)
{
// printf("%d",ccnt);
pcnt=ccnt;
pl=cl;
ph=ch-1;
}
for(i=pl;i<=ph;i++)
{
printf("%c",str[i]);
}
return 0;
}
/*
timecomplexity:O(n*maxcnt) maxcnt=maxsubstring length
space complexity: O(1)
input:dabcade
output:bcade
*/
String longestSubstring(String str)
{
char [] strArr = str.toCharArray();
char [] retArr = new char[str.length()];
String returnVal = "";
int longestSize = 0;
for(int i = 0; i < str.length(); i++)
{
HashMap map = new HashMap();
int currSize = 0;
if(longestSize >= str.length()-i)
break;
for(int j = i; j < str.length()-i; j++)
{
int val = 0;
if(map.get(strArr[j]) != null)
{
val = map.get(strArr[j]);
}
if(val != 0)
break;
retArr[j-i] = strArr[j];
currSize++;
map.put(strArr[j], val++);
}
if(currSize > longestSize)
{
longestSize = currSize;
retArr[longestSize] = '\0';
returnVal = new String(retArr);
}
}
return returnVal;
}
Have a "seen" and "arr" arrays, seen just monitors if the character has been seen before, arr keeps track of the first occurance of characters.
Every time we detect a repeat of the character, we reset the seen array, and set to begin searching from the next index of the first occurance of the repeated character.
for example:
dabcade
>the arr['a']=1 when we encounter 'a' again at i=3, we reset i=arr['a']+1=2, and start the search again. This works even for multiple repeated characters.
>In the end we check if the "currLen>maxLen", because i would have popped of after reaching the length of the string and there is a possibility the last run would have produced the longest length( like in this case).
#include<stdio.h>
#include<string.h>
void longSub(char str[])
{
int arr[256];
int seen[256];
int i;
int len=strlen(str);
for(i=0;i<256;i++)
{arr[i]=-1;seen[i]=-1;}
int j,maxLen=0,currLen=0,maxStart,currSt,temp;
int chFlag=0;
i=0;
while(i<len)
{
if(!chFlag) {currSt=i;chFlag=1;}
if(seen[str[i]]==-1)
{
arr[str[i]]=i;
currLen=currLen+1;
seen[str[i]]=1;
printf("%d , %c, %d, %d \n",i,str[i],seen[str[i]],arr[str[i]]);
i++;
}
else
{
printf("Repeat Detected\n");
chFlag=0;
if(currLen>=maxLen)
{maxLen=currLen;maxStart=currSt;}
i=arr[str[i]]+1;
for(j=0;j<256;j++) seen[j]=-1;
currLen=0;
}
}
if(currLen>=maxLen)
{maxLen=currLen;maxStart=currSt;}
for(i=maxStart;i<maxStart+maxLen;i++)
printf("%c",str[i]);
printf("\n");
}
int main()
{
char str[]="abcdefebcabcdef";
longSub(str);
return 0;
}
Here is a simpler C impl
I wonder if something here is long
void longestUnique(char* input, int len)
{
if (!input) return;
int indexArray[256];
int start = 0;
int end = 0;
int longeststart = 0;
int longestend = 0;
for (int i = 0; i < 256; i++ )
indexArray[i] = -1;
for (int i = 0; i < len; i++)
{
char current = input[i];
int lastpos = indexArray[current];
indexArray[current] = i;
// this character repeated and substring
// formed by adding it is larger than last (lagest) substring
if( lastpos > -1 && lastpos >= start)
{
start = lastpos + 1;
}
end = i;
if( (end - start) > (longestend - longeststart) )
{
longeststart = start;
longestend = end;
}
}
cout << "largest substring = starts " ;
for(int i = longeststart; i <= longestend; i++)
cout<< input[i];
cout<< endl;
}
import javax.swing.JOptionPane;
public class LongestSubString {
public static void main(String []args)
{
new LongestSubString().displayLongestSubString(JOptionPane.showInputDialog("Enter input String :"));
}
public void displayLongestSubString(String main)
{
StringBuffer sub = new StringBuffer();
StringBuffer max = sub;
for(int i = 0;i < main.length();i++)
{
int []bool = new int[256];
for(int k = 0;k < 256;k++)
bool[k] = 0;
for(int j = i;j < main.length();j++)
{
if(bool[main.charAt(j)] == 0)
{
sub.append(main.charAt(j));
bool[main.charAt(j)]++;
}
else
{
break;
}
}
if(sub.length() > max.length())
max = sub;
sub = new StringBuffer();
}
System.out.println("Longest sub string : " + max);
}
}
1. Use a boolean/integer array to check if character is already present in the substring .
2. Append if its the first occurence , if not , break and check for max length !
Code is not as clean as I would have liked.....but this will solve it in O(n) time.
void copy(char max[], char *source, char *dest)
{
int j=0;
for(char *i = source; i != dest; i++)
max[j++] = *i;
max[j] = '\0';
cout << max << endl;
}
int main()
{
set<char> myset;
set<char>::iterator it;
char str[] = "bbbbb";
char *tmp, *hold;
tmp = hold = str;
char max[10];
int crnt_len=0;
while(*tmp != '\0'){
it = myset.find(*tmp);
if( it != myset.end()){
if(tmp - hold > crnt_len){
crnt_len = tmp-hold;
copy(max, hold, tmp);
}
do{
myset.erase(*hold);
hold++;
}
while(*hold != *tmp);
myset.erase(*hold);
hold++;
}
myset.insert(*tmp);
tmp++;
}
if(tmp - hold > crnt_len){
crnt_len = tmp-hold;
copy(max, hold, tmp);
}
cout << max << endl;
return 0;
}
tmp pointer starts from the first character and continues till it encounters a repeated character. Here hold pointer marks the beginning of the current max string. When you find a repeated character, you increment your hold pointer, store the string seen till now (as max) and erase the corresponding character from set.
Easier way is to use an array of 256 elements to check for repetition. Sorry if the code looks messy.
In other words, hold and tmp shall traverse once. Hence O(N)
This is what I told in an interview ..
- bharat November 16, 2012maintain an array of 256 Nodes.
typedef struct _Node {
bool flag;
int position;
}Node;
while traversing the string,
if flag == false
then make flag=true; and fill the position of that character in the string.
when ever u encounter the repeated character, calculate the length of the unique_character_substring and start traversing string from the previous position of that repeated charater +1 and make visited array[256] flags as false.