Amazon telephonic interview ques

1. Write an efficient algo to find longest recurring substring in a string e.g. in banana, it would be 'ana'


Ans : We can use suffix trees to implement this. I will post the exact solution soon

2. Write a function to find intersection of two strings. i.e. characters common to the strings.

For this, the most efficient solution would be to use 26 bits .. one for each character and put zero in all and then wen u encounter a character, just make the corresponding bit 1. For this, we ll need to traverse both the strings only once ands the extra memory that would be required would only be 26 bits :) O(n) solution

Inefficient O(n^2) Method of finding Largest Recurring Substring in a string

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
* @author Pragya Rawal
*/
public class LargestSubstring {
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter String : ");
try {
String input = br.readLine();
LargestSubstring str = new LargestSubstring();
String largestSubstr = str.getLargestSubstr(input);
if (largestSubstr != null) {
System.out.println("Largest Recurring substring is : "
+ largestSubstr);
}
} catch (IOException e) {
e.printStackTrace();
}

}

public String getLargestSubstr(String input) {
if (null == input || input.length() == 0) {
System.out.println("Invalid / Empty string ...");
return null;
} else {
int length = input.length();
int subStrLen = 0;
String longestSubStr = "";
String currentStr = "";
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
int k = i;
int l = j;
while ((k < length) && (l < length) &&(input.charAt(k) == input.charAt(l)) ) {
currentStr += input.charAt(k);
k++;
l++;
subStrLen++;
}
if (longestSubStr.length() < currentStr.length()) {
longestSubStr = currentStr;
}
currentStr = "";
}

}
return longestSubStr;
}

}
}