Amazon Interview Question SDE1s
Country: India
You are over thinking this. "abcdefghi" is composed of the constituent words, "abc", "def" "ghi", and "abcdef".
Try This...
public static void main(String[] args) {
ArrayList<String>list = new ArrayList<>();
list.add( "rat");
list.add( "cat");
list.add( "abcxyz");
list.add( "abc");
list.add( "xyz");
list.add( "ratcatabc");
list.add( "xyzcatratabc" );
Map<String, Integer> map = new HashMap<String, Integer>();
for(int i=0; i<list.size()-1; i++){
String s = list.get(i);
for(int j=0; j < list.size(); j++){
if(i==j){
continue;
}
if(list.get(j).contains(s)){
Integer v = map.get(list.get(j));
if(v == null){
map.put(list.get(j), 0);
}else{
map.put(list.get(j), v+1);
}
}
}
}
System.out.println(map);
}
static string findMaxSubStr(List<string> list)
{
int chosenStringNumberOfSubstrings = 0;
string chosenString = list[0];
foreach (string evaluatingStr in list)
{
int evaluatingStrNumberOfSubstrings = 0;
foreach (string str in list)
{
if (evaluatingStr.Contains(str))
{
evaluatingStrNumberOfSubstrings++;
}
}
if (evaluatingStrNumberOfSubstrings > chosenStringNumberOfSubstrings)
{
chosenString = evaluatingStr;
chosenStringNumberOfSubstrings = evaluatingStrNumberOfSubstrings;
}
}
return chosenString;
}
import java.util.List;
import java.util.ArrayList;
public class WordsInWords {
public static void main(String[] args) {
List<String> list = new ArrayList<String>(10);
list.add("cat");list.add("abcxyz");list.add("abc");list.add("xyz");list.add("ratcatabc");list.add("xyzcatratabc");
// /*alternate list*/ list.add("rat");list.add("cat");list.add("dog");list.add("xyz");
String mostWords = null;
int max = 0;
for (int i=0; i < list.size(); i++) {
String s = list.get(i);
int count = 0;
for (int j=0; j < list.size(); j++) {
if (i==j) {
continue;
}
if(s.contains(list.get(j))) {
count++;
}
}
if (count > 0) {
max = count;
mostWords = s;
}
}
System.out.println("" + (mostWords != null ? mostWords : "No words contain another."));
}
}
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
public class test4 {
public static void main(String[] args) {
List<String> list = new ArrayList<String>(10);
HashMap<Integer, String> list2 = new HashMap<Integer, String>();
list.add("cat");
list.add("abcxyz");
list.add("abc");
list.add("xyzcatratabc");
list.add("xyz");
list.add("ratcatabc");
for (int i = 0; i < list.size(); i++) {
String s = list.get(i);
int count = 0;
for (int j = 0; j < list.size(); j++) {
if (i == j) {
continue;
}
if (s.contains(list.get(j))) {
count++;
}
}
list2.put(count, s);
}
int maxValueInMap = (Collections.max(list2.keySet()));
System.out.println("Teh max value is is :" + list2.get(maxValueInMap));
}
}
I am really confused by the question here. If you already knew that all strings in the given array are either unique or constructed by concatenating other smaller strings already in the array, wouldn't the longest string be simply the string with maximum length? (And by construction of the problem it should contain other smaller strings from that array. Until unless I am totally missing something.
Anyway here is the sweet Python implementation.
array_of_strings = ["rat", "cat", "abc", "xyz", "abcxyz", "ratcatabc", "xyzcatratabc"]
max_len = 0
index = 0
for idx in range(len(array_of_strings)):
lenword = len(array_of_strings[idx])
if lenword > max_len:
max_len = lenword
index = idx
else:
continue
my_word = array_of_strings[index]
# Check for other strings it contains
for word in array_of_strings:
if ((word in my_word) and (word != my_word)):
print word
Optimal Java solution, with length checking and using arrays (for reduced memory footprint). I'm assuming that it's not overly complex like referring to Tree structures, etc.
public class MaxSubstrings {
public static void main(String[] args) {
String[] strs = {"rat", "cat", "abc", "xyz", "abcxyz", "ratcatabc", "xyzcatratabc", "abcx"};
int[] strSizes = new int[strs.length];
int[] strCounts = new int[strs.length];
for(int i=0, len=strs.length; i<len; i++)
{
strSizes[i] = strs[i].length();
strCounts[i] = 0;
}
for(int i=0, len=strs.length, wordLength=strs[i].length(); i<len; i++)
{
for(int j=0; j<len; j++)
{
if(i==j || wordLength > strs[j].length())
continue;
if(strs[j].contains(strs[i]))
strCounts[j]++;
}
}
int indexMaxCount = -1, maxCount = 0;
for(int i=0, len=strs.length; i<len; i++)
if(strCounts[i] > maxCount)
{
maxCount = strCounts[i];
indexMaxCount = i;
}
System.out.println(strs[indexMaxCount]);
}
}
It should be simple. Use strstr() to find if string contained in rest of strings and keep track for every string, how many other strings find in it.
i.e.
for (next=0;next<n,next++)
{
outStr=strArray[next];
i=0;
for i=0;i<n;i++
{
while (NULL != (outStr = strstr(outstr,strArray[next])))
{
count[next]++;
}
}
}
Print the string with index having highest count.
private static String FindBest(string [] list)
{
var array = new int[list.Length];
var max = 0; int result = 0;
for (int i = 0; i < list.Length; ++i)
{
for (int j = 0; j < list.Length; ++j)
{
if (list[i].Contains(list[j]))
{
array[i] += 1;
if (max < array[i])
{
max = array[i];
result = i;
}
}
}
}
return list[result];
}
A similar but different case when you need to count the string with maximum occurrences of smaller string.
array_of_strings = ["rat", "cat", "abc", "xyz", "abcxyz", "ratcatabc", "cat", "xyzxyzxyzxyzabcabc"]
max_occurences = 0
my_word = ''
for i in range(len(array_of_strings)): # This is a simple for loop
counter = 0
for j in range(i):
word_1 = array_of_strings[i]
word_2 = array_of_strings[j]
if (word_2 in word_1) and (word_2 != word_1):
counter += word_1.count(word_2)
if counter > max_occurences:
max_occurences = counter
my_word = word_1
print word_1, max_occurences
//career cup problum
#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
char a[5][20];
static int i,j,count[5]={0},k,max;
printf("Enter 5 strings:\n");
for(i=0;i<5;i++)
{
gets(a[i]);
}
for(j=0;j<5;j++)
{
for(i=0;i<5;i++)
{
if(strstr(a[j],a[i])!=NULL)
count[j]++;
}
max=count[0];
if(max<count[j])
{ max=count[j];
k=j;
}
}
//for(i=0;i<5;i++)
//{
// printf("%d",count[i]);
//}
printf("THE STRING CONTAINING MAX . NO OF OTHER IS GIVEN BY:");
puts(a[k]);
getch();
}
}
public class MaxStrings {
static String s1[] = {"rat", "cat", "abc", "xyz", "abcxyz", "xyzcatratabc"};
static int length = s1.length;
static int count[] = new int[length];
static String findMaxStrings(){
int max = 0, position = -1;
for(int i = 0; i < length; i++){
for(int j = 0 ; j < length; j++){
if(i!=j)
if(s1[i].contains(s1[j])){
count[i]=count[i]+1;
}
if(max < count[i]){
max = count[i];
position = i;
}
}
}
if(position == -1)
return "all strings are unique";
else
return s1[position];
}
public static void main(String args[]){
if(s1.length >0)
System.out.print(findMaxStrings());
else
System.out.print("no strings");
}
}
public static void main(String[] args) {
String max = "";
int maxNum = 0;
String []str = {"rat", "xyzcatratabc", "cat", "xyz",
"abcxyz", "ratcatabc", "abc"};
HashMap<String, Integer> map = new HashMap<String, Integer>();
int length = str.length;
for(int i=length-1;i>=0;i--){
for(int j=0;j<length-1;j++){
if(i==j)
break;
if(str[i].contains(str[j])){
if(map.get(str[i])!=null){
int temp = map.get(str[i])+1;
if(temp>maxNum){
max = str[i];
maxNum = temp;
}
map.put(str[i], temp);
}
else{
map.put(str[i], 1);
}
}
else
if(str[j].contains(str[i])){
if(map.get(str[j])!=null){
map.put(str[j], map.get(str[j])+1);
}
else{
map.put(str[j], 1);
}
}
}
}
System.out.println(map);
System.out.println("'"+max+"' is the String which made with '"+maxNum+"' other strings.");
}
int max=0;
int i,j,index,no=0;
char *p[5]={{"abc"},{"def"},{"abcdefghi"},{"lop"},{"abcdeflopabcdefghi"}};
for(i=0;i<5;i++)
{
char * temp=p[i];
for (j=0;j<5;j++)
{
if (j!=i)
{
if((strstr(temp,p[j]))!=NULL)
{
no+=1;
}
}
}
if(no>max)
{
index=i;
max=no;
}
}
printf("%d Index element",index) ;
getchar();
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
*
*/
/**
* @author Srikanth.BG
*
*/
public class RepeatString {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
List<String> listStr = new ArrayList<String>();
listStr.add("rat");
listStr.add("cat");
listStr.add("abc");
listStr.add("xyz");
listStr.add("abcxyz");
listStr.add("ratcatabc");
listStr.add("xyzcatratabc");
listStr.add("abcx");
Collections.sort(listStr, new ListSizeComparator());
//System.out.println(listStr.toString());
String bigStr = "";
int repeatations = 0;
String biggestString = "";
for(int i=listStr.size()-1;i>=0;i--)
{
bigStr = listStr.get(i);
int loopRepeat = 0;
for(int j=i-1;j>=0;j--)
{
if(bigStr.contains(listStr.get(j)))
{
loopRepeat++;
}
}
if(loopRepeat > repeatations)
{
repeatations = loopRepeat;
biggestString = bigStr;
}
}
System.out.println(biggestString + " " + repeatations);
}
}
import java.util.ArrayList;
import java.util.HashMap;
public class test {
public static void main (String[] args) {
int max = 0;
String longestString;
ArrayList<String> strings = new ArrayList<String>();
strings.add("rat");
strings.add("cat");
strings.add("xyz");
strings.add("abcxyz");
strings.add("ratcatabc");
strings.add("xyzcatratabc");
longestString = strings.get(0);
for (int i = 0; i < strings.size(); i++) {
int count = 0;
String currString = strings.get(i);
for (int j = 0; j < strings.size(); j++) {
if (i != j) {
String s = strings.get(j);
if (currString.contains(s)) {
count++;
if (count >= max) {
max = count;
longestString = currString;
}
}
}
}
}
System.out.println(longestString);
}
}
C++ version with O(n^2) time.
#include <iostream>
#include <vector>
std::string find_max_composite(const std::vector<std::string>& words) {
std::string max_str;
size_t max_count = 0;
for (size_t i = 0; i < words.size(); i++) {
size_t count = 0;
for (size_t j = 0; j < words.size(); j++) {
// Don't compare the same word
if (j == i)
continue;
// A string is only composed of other strings if it's longer
if (words[i].size() > words[j].size()) {
if (words[i].find(words[j]) != std::string::npos)
count++;
}
}
if (count > max_count) {
max_count = count;
max_str = words[i];
}
}
return max_str;
}
int main() {
std::vector<std::string> words { "rat", "cat", "abc", "xyz", "abcxyz",
"ratcatabc", "xyzcatratabc" };
std::cout << find_max_composite(words);
return 0;
}
public class MaxNumString {
public static void main(String[] args) {
String[] strs = { "rat", "cat", "xyz", "abcxyz", "ratcatabc",
"xyzcatratabc" };
System.out.println(maxNumStr(strs));
}
public static String maxNumStr(String[] strs) {
int[] matches = new int[strs.length];
for (int j = 0; j < strs.length; j++) {
for (int k = 0; k < strs.length; k++) {
if (j == k)
continue;
if (strs[k].indexOf(strs[j]) != -1) {
matches[k] += 1;
}
}
}
int max = 0;
int p = 0;
for (int i = 0; i < matches.length; i++) {
if (max < matches[i]) {
max = matches[i];
p = i;
}
}
return strs[p];
}
}
public class MaxNumString {
public static void main(String[] args) {
String[] strs = { "rat", "cat", "xyz", "abcxyz", "ratcatabc",
"xyzcatratabc" };
System.out.println(maxNumStr(strs));
}
public static String maxNumStr(String[] strs) {
int[] matches = new int[strs.length];
for (int j = 0; j < strs.length; j++) {
for (int k = 0; k < strs.length; k++) {
if (j == k)
continue;
if (strs[k].indexOf(strs[j]) != -1) {
matches[k] += 1;
}
}
}
int max = 0;
int p = 0;
for (int i = 0; i < matches.length; i++) {
if (max < matches[i]) {
max = matches[i];
p = i;
}
}
return strs[p];
}
}
This isn't too bad, we can use the time-saving feature of java that the String class has, the .contains(CharSequence s) method, lovely little bugger isn't it?
We create an array of ints to track each associated strings "score", the number of other strings it contains.
then it's just a few for loops and we are done.
Let's take a look:
public String find_best(String[] strings){
int[] scores = new int[strings.length];
for(int i = 0; i < strings.length; i++){
for (int j = 0; j < strings.length; j++){
if(j == i) continue; //skip the string from counting itself
if(strings[i].contains(strings[j])) scores[i]++;
}
}
int max = 0;
for(int i = 0; i < scores.length; i++){
if(scores[i] > scores[max]) max = i; //a basic find-max array run through in O(n)
}
return strings[max];
}
This isn't the most terribly efficient process, unfortunately. String.contains is O(n), if I recall correctly. That means we have n lookups of n-1 elements, O(n^2) total, and for each of those, O(m) is the time for the contains lookup. m may or may not be greater than n, that is arbitrary, our runtime in this case, i believe, is O(m*(n^2)), which could be O(n^3) depending on the value of m. We can mitigate time by telling the loops to ignore attempts to compare strings to those of larger size (since they can't contain a string larger than themselves), but it won't do much.
Brute force answer. Anyone know a more efficient method?
The previous solutions are wrong. We need a recursive procedure which tests different combinations. E.g. we have words "abc", "def", "ghi", "abcdef" and "abcdefghi". What score does "abcdefghi" have? Either we put it as "abc", "def", "ghi" or as "abcdef", "ghi". We can't say it has score 4 because it should be composed of the constituent words.
You should ask the interviewer a few questions: What if a word appears repeatedly? Does it count for 1 or more? Is it even allowed to use one word twice?
I would insert all strings into a trie structure. Than, for each word, I would follow this pseudocode, which tries to use the shortest string but backtracks if it does not lead to a solution:
- galli October 11, 2013boolean backtrack(int i, int found) Node n = root while n has child word[i] and i < word.length n = child word[i] i = i + 1 if n.isEndOfWord if i == word.length maxFound = Math.max(maxFound, found) return true else if backtrack(i, found + 1) return true return n has child word[i]