Amazon Interview Question
SDE-3sCountry: United States
Interview Type: In-Person
static String findLargestRepeatedSubString(String s){
if(s == null)
throw new IllegalArgumentException("Provided String is null");
if(s.length() == 1){
return null;
}
String result = null;
for(int start = 0; start < s.length(); start++){
for(int end = start+1; end <= s.length(); end++) {
String subString = s.substring(start, end);
if(s.substring(end).contains(subString)){
if(result == null)
result = s.substring(start, end);
else if(subString.length() > result.length()){
result = subString;
}
}
}
}
return result;
}
string FindLongestRepSubstring(string s)
{
if(s == null)
return throw new ArgumentException("s");
HashTable<string, int> h = new HashTable<string, h>();
string longRepStr = null;
for(int i=0;i<s.Length; i++)
{
for(int = i+1; j<s.Length; j++)
{
string nextSubStr = s.substring(i, j);
if(h.ContainsKey(nextSubStr))
{
h[nextSubStr].Value++;
if(longRepStr == null)
{
longRepStr = nextSubStr;
}
else if(longRepStr.Length < nextSubStr.Length) //if(h[longRepStr].Value < h[nextSubStr].Value)
{
longRepStr = nextSubStr;
}
}
else
{
h[nextSubStr].Value = 1;
}
}
}
return longRepStr;
}
{
// Time - O(n^2), Space - O(n^2)
static String findLongestRepeatedSubString(String s) {
if(s==null || s.trim().length()==0)
return "";
int len = s.length();
int[][] matrix = new int[len][len];
int maxLen = 0;
int maxIndex = 0;
for(int i=0; i< len; i++) {
for(int j=i+1; j < len; j++) {
if(s.charAt(i)==s.charAt(j)) {
matrix[i][j] = ((i-1<0 || j-1<0)?0:matrix[i-1][j-1]) +1;
if(matrix[i][j]>maxLen) {
maxLen = matrix[i][j];
maxIndex = j;
}
}
}
}
return s.substring(maxIndex-maxLen+1,maxIndex+1);
}
}
- Cody March 09, 2017