Nagarro Interview Question Java Developers
Country: India
Interview Type: Phone Interview
vector< string > data{"fabcsdf", "asdfabc", "dfadsfsdfabc", "abckdf",
"ddfabc"};
string pattern{"abc"};
multimap< int, string > m;
for (const auto& s : data)
{
auto pos = search(cbegin(s), cend(s), cbegin(pattern), cend(pattern));
if (pos != cend(s))
{
m.insert(make_pair(pos - cbegin(s), s));
}
}
for (const auto& i : m)
{
cout << i.second << endl;
}
vector< string > data{"fabcsdf", "asdfabc", "dfadsfsdfabc", "abckdf",
"ddfabc"};
string pattern{"abc"};
multimap< int, string > m;
for (const auto& s : data)
{
auto pos = search(cbegin(s), cend(s), cbegin(pattern), cend(pattern));
if (pos != cend(s))
{
m.insert(make_pair(pos - cbegin(s), s));
}
}
for (const auto& i : m)
{
cout << i.second << endl;
}
vector< string > data{"fabcsdf", "asdfabc", "dfadsfsdfabc", "abckdf",
"ddfabc"};
string pattern{"abc"};
multimap< int, string > m;
for (const auto& s : data)
{
auto pos = search(cbegin(s), cend(s), cbegin(pattern), cend(pattern));
if (pos != cend(s))
{
m.insert(make_pair(pos - cbegin(s), s));
}
}
for (const auto& i : m)
{
cout << i.second << endl;
}
vector< string > data{"fabcsdf", "asdfabc", "dfadsfsdfabc", "abckdf",
"ddfabc"};
string pattern{"abc"};
multimap< int, string > m;
for (const auto& s : data)
{
auto pos = search(cbegin(s), cend(s), cbegin(pattern), cend(pattern));
if (pos != cend(s))
{
m.insert(make_pair(pos - cbegin(s), s));
}
}
for (const auto& i : m)
{
cout << i.second << endl;
}
vector< string > data{"fabcsdf", "asdfabc", "dfadsfsdfabc", "abckdf",
"ddfabc"};
string pattern{"abc"};
multimap< int, string > m;
for (const auto& s : data)
{
auto pos = search(cbegin(s), cend(s), cbegin(pattern), cend(pattern));
if (pos != cend(s))
{
m.insert(make_pair(pos - cbegin(s), s));
}
}
for (const auto& i : m)
{
cout << i.second << endl;
}
Good question, I used a trie and a tree set to solve this. I recursively search every node in the Trie searching for the pattern, and then add words found with the pattern to the TreeSet, which will order the words by the position of the pattern in the word. This needs to be optimized to avoid blowing the stack..
public class TestCareerCup {
public static void main(String [] args){
MyTrie trie = new MyTrie();
trie.add("fabcsdf");
trie.add("asdfabc");
trie.add("dfadsfsdfabc");
trie.add("abckdf");
trie.add("ddfabc");
Set<MyString> set = trie.searchForPattern("abc");
Iterator<MyString> it = set.iterator();
while(it.hasNext()){
MyString ms = it.next();
System.out.println(ms.getString());
}
System.out.println("Finished testing: set has " + set.size() + " elements.");
}
}
public class MyTrie{
private TrieNode root;
private class TrieNode{
Map<Character, TrieNode> children = new HashMap<Character, TrieNode>();
boolean isWord = false;
}
public MyTrie(){
root = new TrieNode();
}
public void add(String word){
TrieNode temp = root;
if(word == null){
throw new IllegalArgumentException();
}
for(int i = 0; i < word.length(); ++i){
char c = word.charAt(i);
TrieNode node = temp.children.get(c);
if(node == null){
node = new TrieNode();
temp.children.put(c, node);
}
temp = node;
}
temp.isWord = true;
}
public boolean search(String word){
if(word == null){return false;}
TrieNode temp = root;
char c = '\0';
for(int i = 0; i < word.length(); ++i){
c = word.charAt(i);
temp = temp.children.get(c);
if(temp == null){
return false;
}
}
return temp.isWord;
}
public Set<MyString> searchForPattern(String pattern){
Set<MyString> set = new TreeSet<MyString>(); //use TreeSet to order strings lexographically or however we want
searchForPattern(root, "", set, pattern, 0);
return set;
}
private void searchForPattern(TrieNode node, String soFar, Set<MyString> set, String pattern, int index){
Map<Character, TrieNode> map = node.children;
for(Entry entry: map.entrySet()){
int startIndex = index;
TrieNode nextNode = (TrieNode)entry.getValue();
Character key = (Character)entry.getKey();
if(startIndex == pattern.length()){
//found the pattern continue until finished
}else if(key == pattern.charAt(0) && key != pattern.charAt(startIndex)){
startIndex = 1; //found the first char in pattern
}else if( startIndex > 0 && key != pattern.charAt(startIndex)){
startIndex = 0; //reset index
}else if(key == pattern.charAt(startIndex)){
++startIndex; //found a piece of the pattern
}
String string = soFar;
string += entry.getKey();
if(nextNode.isWord && startIndex == (pattern.length())){
MyString myString = new MyString(string, pattern);
set.add(myString);
}
searchForPattern(nextNode, string, set, pattern, startIndex);
}
}
class MyString implements Comparable<MyString>{
private String string;
private String pattern;
public MyString(String string, String pattern){
this.string = string;
this.pattern = pattern;
}
public String getString(){ return string;}
@Override
public int compareTo(MyString o) {
int cmp = string.compareTo(o.string);
int indexOfThis = string.indexOf(pattern);
int indexOfOther = o.string.indexOf(pattern);
if(indexOfThis > indexOfOther){
return 1;
}else if(indexOfThis < indexOfOther){
return -1;
}else{
return cmp;
}
}
}
}
import java.util.ArrayList;
import java.util.List;
public class StringSearch {
public static void main(String[] args) {
List<String> lisStr = new ArrayList<String>();
List<String> lisStrModify = new ArrayList<String>();
lisStr.add("1234abcdef");
lisStr.add("abcdef");
lisStr.add("12abcdef");
lisStr.add("1abcdef");
lisStr.add("123abcdef");
for (int i = 0; i < lisStr.size(); i++) {
for (int j = 0; j < lisStr.size(); j++) {
if (lisStr.get(j).startsWith("abc", i)) {
lisStrModify.add(lisStr.get(j));
}
}
}
System.out.println(lisStrModify);
}
}
package com.newgen.practice;
import java.util.ArrayList;
import java.util.List;
public class StringSearch {
public static void main(String[] args) {
List<String> lisStr = new ArrayList<String>();
List<String> lisStrModify = new ArrayList<String>();
lisStr.add("1234abcdef");
lisStr.add("abcdef");
lisStr.add("12abcdef");
lisStr.add("1abcdef");
lisStr.add("123abcdef");
for (int i = 0; i < lisStr.size(); i++) {
for (int j = 0; j < lisStr.size(); j++) {
if (lisStr.get(j).startsWith("abc", i)) {
lisStrModify.add(lisStr.get(j));
}
}
}
System.out.println(lisStrModify);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String test="avscfaabc";
String test1="abcdrst";
String test2="aasabcdfs";
String test3="vbabcsdr";
Map<String,Integer> map=new HashMap<String,Integer>();
map.put(test, test.indexOf("abc"));
map.put(test1, test1.indexOf("abc"));
map.put(test2, test2.indexOf("abc"));
map.put(test3, test3.indexOf("abc"));
Map<String,Integer> sortedNewMap = map.entrySet().stream().sorted((e1,e2)-> e1.getValue().compareTo(e2.getValue()))
.collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue,(e1, e2) -> e1, LinkedHashMap::new));
sortedNewMap.forEach((key,val)->{
System.out.println(key+ " = "+ val.toString());
});
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String test="avscfaabc";
String test1="abcdrst";
String test2="aasabcdfs";
String test3="vbabcsdr";
Map<String,Integer> map=new HashMap<String,Integer>();
map.put(test, test.indexOf("abc"));
map.put(test1, test1.indexOf("abc"));
map.put(test2, test2.indexOf("abc"));
map.put(test3, test3.indexOf("abc"));
Map<String,Integer> sortedNewMap = map.entrySet().stream().sorted((e1,e2)-> e1.getValue().compareTo(e2.getValue()))
.collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue,(e1, e2) -> e1, LinkedHashMap::new));
sortedNewMap.forEach((key,val)->{
System.out.println(key+ " = "+ val.toString());
});
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String test="avscfaabc";
String test1="abcdrst";
String test2="aasabcdfs";
String test3="vbabcsdr";
Map<String,Integer> map=new HashMap<String,Integer>();
map.put(test, test.indexOf("abc"));
map.put(test1, test1.indexOf("abc"));
map.put(test2, test2.indexOf("abc"));
map.put(test3, test3.indexOf("abc"));
Map<String,Integer> sortedNewMap = map.entrySet().stream().sorted((e1,e2)-> e1.getValue().compareTo(e2.getValue()))
.collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue,(e1, e2) -> e1, LinkedHashMap::new));
sortedNewMap.forEach((key,val)->{
System.out.println(key+ " = "+ val.toString());
});
}
At first I use simpl list array to hold string data. During the search I make 1 loop for all strings to select items with searchedString. Than I create comparable IndexedString object to sort selected string. Than I select 1 match for each string index.
public class SearchString {
List<String> baseList = new ArrayList<>();
public void addString(String s) {
baseList.add(s);
}
public List<String> getSortedSearchList(String searchString) {
TreeSet<IndexedString> sortedSet = new TreeSet<>();
int maxIndex = Integer.MIN_VALUE;
for (String s : baseList) {
if (s.contains(searchString)) {
int testIndex = s.indexOf(searchString);
maxIndex = Math.max(testIndex, maxIndex);
sortedSet.add(new IndexedString(testIndex, s));
}
}
int resultIndex = -1;
Iterator<IndexedString> iter = sortedSet.iterator();
List<String> result = new ArrayList<>();
for (Iterator<IndexedString> it = iter; it.hasNext(); ) {
IndexedString indexedString = it.next();
if (resultIndex != indexedString.index) {
resultIndex = indexedString.index;
result.add(indexedString.string);
}
}
return result;
}
private class IndexedString implements Comparable<IndexedString> {
String string;
int index;
public IndexedString(int i, String s) {
index = i;
string = s;
}
@Override
public int compareTo(IndexedString o) {
if (index == o.index) {
return string.compareTo(o.string);
}
return index < o.index ? -1 : 1;
}
}
}
List<String> lisStr = new ArrayList<String>();
List<String> lisStrModify = new ArrayList<String>();
Map<Integer,String> treemap = new TreeMap<Integer,String>();
lisStr.add("1234abcdef");
lisStr.add("abcdef");
lisStr.add("12abcdef");
lisStr.add("1abcdef");
lisStr.add("123abcdef");
lisStr.add("12334afabcdef");
lisStr.add("123sweede1abcdef");
for(int i = 0 ; i < lisStr.size(); i++){
int loc = lisStr.get(i).indexOf("abc");
if(loc != -1){
treemap.put(loc,lisStr.get(i));
}
}
System.out.println(treemap.toString());
List<String> lisStr = new ArrayList<String>();
Map<Integer,String> treemap = new TreeMap<Integer,String>();
lisStr.add("1234abcdef");
lisStr.add("abcdef");
lisStr.add("12abcdef");
lisStr.add("1abcdef");
lisStr.add("123abcdef");
lisStr.add("12334afabcdef");
lisStr.add("123sweede1abcdef");
for(int i = 0 ; i < lisStr.size(); i++){
int loc = lisStr.get(i).indexOf("abc");
if(loc != -1){
treemap.put(loc,lisStr.get(i));
}
}
System.out.println(treemap.toString());
Javascript Program
function getABCString(str,subStr) {
const strArr = str.split(',');
const indexArr=[];
for(let i=0;i<strArr.length;i++){
const pos = strArr[i].indexOf(subStr);
indexArr.push({index:pos,str:strArr[i]});
}
indexArr.sort((a,b)=>a.index-b.index);
for(let obj of indexArr) {
console.log(obj.str);
}
}
getABCString('fabcsdf,asdfabc,dfadsfsdfabc,abckdf,ddfabc', 'abc');
Hi, I like C#, it has syntax like C#.
code:
static void Main(){
Dictionary<int, string> dictionary = new Dictionary<int, string>();
string[] array = { "fabcsdf", "asdfabc", "dfadsfsdfabc", "abckdf", "ddfabc" };
foreach (var item in array)
{
dictionary.Add(item.IndexOf("abc"), item);
}
var select = from d in dictionary
orderby d.Key ascending
select d;
foreach (var item in select)
{
Console.WriteLine(item.Value);
}
}
C# code:
Dictionary<int, string> dictionary = new Dictionary<int, string>();
string[] array = { "fabcsdf", "asdfabc", "dfadsfsdfabc", "abckdf", "ddfabc" };
foreach (var item in array)
{
dictionary.Add(item.IndexOf("abc"), item);
}
var select = from d in dictionary
orderby d.Key ascending
select d;
foreach (var item in select)
{
Console.WriteLine(item.Value);
}
Hi, I use C#, it has similar Java syntax.
Dictionary<int, string> dictionary = new Dictionary<int, string>();
string[] array = { "fabcsdf", "asdfabc", "dfadsfsdfabc", "abckdf", "ddfabc" };
foreach (var item in array)
{
dictionary.Add(item.IndexOf("abc"), item);
}
var select = from d in dictionary
orderby d.Key ascending
select d;
foreach (var item in select)
{
Console.WriteLine(item.Value);
}
west12as, assuming you know the query in advance that would probably be the best solution.
- srterpe January 12, 2017Assuming you don't:
I would think your "dictionary" should be an array of objects that map the word to a corresponding suffix-trie of the word. This will allow you to quickly determine if the query is a substring of a particular word, and the suffix-trie can also provide the index of the substring within in the word.
This doesn't solve the problem of searching millions of dictionary entries though.
Depending on the distribution of characters in the dictionary entries (is it common to have "a", "b", "c" but not "abc", etc) you might be able to create a hashmap where the values are indexes into the dictionary array and the keys are hashed by taking only the unique letters in each string and alphabetizing them "abcabcf" -> "abcf". Then you could create another suffix-trie for each of these keys and quickly determine that a given key's indexes _might_ contain the searched for query:
"abcf" contains substring "abc" -> points to indexes D[0, 1]
D[0] = { word: "fabc", "trie": X}
D[1] = {word: "facb", "trie": Y
...
D[1M] = {word: "qpert", "trie": Z }
Only need to search the suffix-tries of D[0], D[1] for "abc"
Of course this offers little benefit if it's quite common to have the chars "a", "b", "c" somewhere but not necessarily as a sequence.