Samsung Interview Question
Network EngineersCountry: India
Interview Type: In-Person
I would go for a map with key={string} value={set}
I am choosing this case assuming i have small number of keys so the map cost will be small for lookup.
also, in any DS like LL, Tr(i)e etc, the cost of storing a pointer is high when data is small.
Trie might end up optimizing this as well, but given there are too many children per node, the ptr cost i think might become high.
/*This code Needs some modification anybody who got the logic can try it.. and it does work for "a" and "aa", but doesn't work for input "ac" */
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class StringChallenge {
public static void main(String[] args) {
// TODO Auto-generated method stub
String[] input = { "aabb", "aafd", "acff", "aacg", "acfg" };
List<String> lst = new ArrayList<String>();
for (String str : input) {
lst.add(str);
}
System.out.println("enter your option: ");
Scanner in = new Scanner(System.in);
String expt = in.nextLine();
char[] inp = expt.toCharArray();
for (int i = 0; i < inp.length; i++) {
while (lst.get(i).contains(expt)) {
System.out.println(lst.get(i) + " ");
lst.remove(i);
continue;
}
}
}
}
import java.util.Scanner;
public class CheckSubString {
public static void main(String[] args) {
String[] str={"aabd","adbd","bfdbd","abcd","absbd"};
Scanner sc=new Scanner(System.in);
String input=sc.nextLine();
for(int i=0;i<str.length;i++){
System.out.println(str[i].substring(0,input.length()));
if(str[i].substring(0,input.length()).equals(input))
System.out.println(str[i]);
else
continue;
}
}
}
import java.util.Scanner;
public class CheckSubString {
public static void main(String[] args) {
String[] str={"aabd","adbd","bfdbd","abcd","absbd"};
Scanner sc=new Scanner(System.in);
String input=sc.nextLine();
for(int i=0;i<str.length;i++){
if(str[i].substring(0,input.length()).equals(input))
System.out.println(str[i]);
else
continue;
}
}
}
package com.example.itext;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* Hello world!
*
*/
public class App implements IExample
{
public static void main( String[] args )
{
String[] strArr = {"aBB","aaCC","aBc","aaaVBF","bbaa","bAAA","aaaHHHH","d"};
List<String> strArrayList = new ArrayList<String>();
for(String str:strArr){
strArrayList.add(str);
}
Collections.sort(strArrayList);
String inputString = "d";
StringBuilder strb = new StringBuilder("");
for(String listElm: strArrayList){
if(inputString.charAt(0)== listElm.charAt(0)){
if(listElm.startsWith(inputString))
strb.append(listElm).append(" ");
}else{
continue;
}
}
System.out.println("strb: " + strb);
}
}
/*here is the code in C*/
#include<stdio.h>
#include<string.h>
int main()
{
int i;
char strin[][10] = {"abc","aab","aacf","gffg","saas","dddd","lkll","dfgfd","dfgdete","aafgdgr"};
char str[5];
printf("Enter the string to be searched\n");
scanf("%s",str);
for(i = 0;i<10;i++){
if(strncmp(strin[i],str,strlen(str)) == 0)
printf("%s\n",strin[i]);
}
return 0;
}
I think you should build trie from these strings, so when you go from root to nodes, all strings that would be under current node - will be answers. For better performance you can store all references on all strings each node belongs to. so complexity wiil be O(n), where n - is lenght of input.
- glebstepanov1992 December 10, 2013