Amazon Interview Question Software Analysts
Country: United States
Interview Type: Phone Interview
I came up with something different. Want to know if it is also accepted solution:
string findLCSSubstr(string str){
string result = "", maxResult = "";
for(int i=0; i<str.length();i++){
result = str.substr(i,1);
while(str.find(result, i+1,str.size()-1) != string::npos){
i++;
result+=str.substr(i,1);
}
result.erase(result.end());
if(result.size()>maxResult.size()){
maxResult = result;
}
}
cout<<maxResult<<endl;
}
Time Complexity: O(nk) where n represents number of repeating substrings and K represents average length of the substrings.
One possible solution is
#1
1> Find all the palindromes in the stream.
2> For each palindrome in the list
if(hash.containsKey(palidrome)){
hash.add(palindrome, hash.getValue(palindrome) + 1);
} else {
hash.add(Key, 1);
}
3> Find the max count in the hash and print that key.
#2,
Prefix Array calculation in KMP algorithm could be used
As each prefix array is the suffix of the current string, the value will give the solution in minimum time and space complexity
package com.interview.multithreaded;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;
public class SearchASubStringInword {
public static void main(String[] args) {
// TODO Auto-generated method stub
String s = "banana";
Set<String> set = new HashSet<>();
ArrayList<String> arrlist = new ArrayList<>();
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j < s.length() + 1; j++) {
String temp = s.substring(i, j);
if (!set.add(temp)) {
arrlist.add(temp);
// System.out.println(temp);
}
}
}
Collections.sort(arrlist, new Comparator<String>() {
public int compare(String o1, String o2) {
// TODO Auto-generated method stub
return o2.length() - o1.length();
}
});
System.out.println(arrlist.get(0));
}
}
package topcoder.sort;
public class Test {
public static void main(String[] args) {
String a = "banana";
String max = "";
int size = a.length();
for(int i=1; i<size; i++){
char pivot = a.charAt(i);
int startIndex = 0;
int endIndex = 0;
for(int j=1; j <= i && j <= size -1 - i; j++){
System.out.println("i = " + i + " j = " + j);
char leftChar = a.charAt(i-j);
char rightChar = a.charAt(i+j);
if(leftChar == rightChar ){
startIndex = i - j;
endIndex = i + j;
}
else{
break;
}
}
String temp = a.substring(startIndex, endIndex + 1);
if(max.length() < temp.length()){
max = temp;
}
}
System.out.println(max);
}
}
package topcoder.sort;
public class Test {
public static void main(String[] args) {
String a = "banana";
String max = "";
int size = a.length();
for(int i=1; i<size; i++){
char pivot = a.charAt(i);
int startIndex = 0;
int endIndex = 0;
for(int j=1; j <= i && j <= size -1 - i; j++){
System.out.println("i = " + i + " j = " + j);
char leftChar = a.charAt(i-j);
char rightChar = a.charAt(i+j);
if(leftChar == rightChar ){
startIndex = i - j;
endIndex = i + j;
}
else{
break;
}
}
String temp = a.substring(startIndex, endIndex + 1);
if(max.length() < temp.length()){
max = temp;
}
}
System.out.println(max);
}
}
import java.util.*;
public class repeatedStringinString {
public static void main(String[] args) {
String test = "banana";
Map<String, Integer> map = new HashMap<String, Integer>();
List<String> list = new ArrayList<String>();
for (int i = 0; i < test.length(); i++) {
for (int j = i + 1; j < test.length(); j++) {
String temp = test.substring(i, j + 1);
if (map.get(temp) != null)
map.put(temp, map.get(temp) + 1);
else
map.put(temp, 1);
}
}
for (Map.Entry<String, Integer> entry : map.entrySet()) {
if (entry.getValue() >= 2)
list.add(entry.getKey());
}
System.out.println(list);
Collections.sort(list, new Comparator<String>() {
public int compare(String o1, String o2) {
return o2.length() - o1.length();
}
});
System.out.println(list.get(0));
}
}
import java.util.*;
public class repeatedStringinString {
public static void main(String[] args) {
String test = "banana";
Map<String, Integer> map = new HashMap<String, Integer>();
List<String> list = new ArrayList<String>();
for (int i = 0; i < test.length(); i++) {
for (int j = i + 1; j < test.length(); j++) {
String temp = test.substring(i, j + 1);
if (map.get(temp) != null)
map.put(temp, map.get(temp) + 1);
else
map.put(temp, 1);
}
}
for (Map.Entry<String, Integer> entry : map.entrySet()) {
if (entry.getValue() >= 2)
list.add(entry.getKey());
}
System.out.println(list);
Collections.sort(list, new Comparator<String>() {
public int compare(String o1, String o2) {
return o2.length() - o1.length();
}
});
System.out.println(list.get(0));
}
}
import java.util.*;
public class repeatedStringinString {
public static void main(String[] args) {
String test = "banana";
Map<String, Integer> map = new HashMap<String, Integer>();
List<String> list = new ArrayList<String>();
for (int i = 0; i < test.length(); i++) {
for (int j = i + 1; j < test.length(); j++) {
String temp = test.substring(i, j + 1);
if (map.get(temp) != null)
map.put(temp, map.get(temp) + 1);
else
map.put(temp, 1);
}
}
for (Map.Entry<String, Integer> entry : map.entrySet()) {
if (entry.getValue() >= 2)
list.add(entry.getKey());
}
System.out.println(list);
Collections.sort(list, new Comparator<String>() {
public int compare(String o1, String o2) {
return o2.length() - o1.length();
}
});
System.out.println(list.get(0));
}
}
import java.util.*;
public class repeatedStringinString {
public static void main(String[] args) {
String test = "banana";
Map<String, Integer> map = new HashMap<String, Integer>();
List<String> list = new ArrayList<String>();
for (int i = 0; i < test.length(); i++) {
for (int j = i + 1; j < test.length(); j++) {
String temp = test.substring(i, j + 1);
if (map.get(temp) != null)
map.put(temp, map.get(temp) + 1);
else
map.put(temp, 1);
}
}
for (Map.Entry<String, Integer> entry : map.entrySet()) {
if (entry.getValue() >= 2)
list.add(entry.getKey());
}
System.out.println(list);
Collections.sort(list, new Comparator<String>() {
public int compare(String o1, String o2) {
return o2.length() - o1.length();
}
});
System.out.println(list.get(0));
}
}
is it biggest palindrome?
- Anonymous July 05, 2016