Nagarro Interview Question for Java Developers


Country: India
Interview Type: Phone Interview




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

west12as, assuming you know the query in advance that would probably be the best solution.

Assuming 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.

- srterpe January 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Build a series of tries: one for every string, one for every string with the first character removed, one with the first two characters removed, and so on.

Then simply search all the tries for the input string, in order.

- tjcbs2 January 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- jarek January 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- jarek January 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

- jarek January 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- jarek January 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- jarek January 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- dogfish January 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Anonymous January 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous January 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

	}

- this should do the work.. February 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

	}

- Anonymous February 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

	}

- Maximus February 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous March 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- pawan September 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- pawan September 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

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

- Archer January 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Archer January 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Why I can't add my code?

- Archer January 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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 January 12, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More