## Amazon Interview Question for Software Analysts

• 0

Country: United States
Interview Type: Phone Interview

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

is it biggest palindrome?

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

Use a suffix tree.

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

It's a typical suffix trie problem.

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

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.

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

One possible solution is

#1

1> Find all the palindromes in the stream.
2> For each palindrome in the list
if(hash.containsKey(palidrome)){
} else {
}
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

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

suffix array shoudl be used

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

why not answer will be anana ? than ana ? was there a condition that overlap is limited to one character?

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

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);

// 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));

}

}

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

``````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);
}``````

}

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

``````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);
}

}``````

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

``````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)
}
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));
}

}``````

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

``````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)
}
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));
}

}``````

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

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)
}
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));
}

}

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

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)
}
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));
}

}

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.