Morgan Stanley Interview Question for Java Developers


Country: India
Interview Type: Written Test




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

1. Split the str1 with each character of the str3.
2. Now iterate all the words and check the constraint that word contain all the characters of str2, Checking can be skipped by comparing string lengths.
3. Return the minimum length string which satisfies point 2.

- Kishore April 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Tried to implement the solution provided by Kishore.

public static void findShortestSubString() {

String s1 = "spqrstrupvqw";
String s2 = "sprt";
String s3 = "q";
Set<String> results = new HashSet<String>();

// 1. split the s1 with s3
// 2. sp rstrupv wrpts
// 3. find the shortest word that has s2 in it.
// -- if word's length >= s2.length --> find the shortest word sequence containing s2

String[] stringsToFind = s1.split(s3);

for(String stringToFind : stringsToFind)
{
// ignore shorter strings
if( stringToFind.length() < s2.length() )
{
continue;
}

// ignore the words that dont have every characters present in s2
if( !stringHasAllLetters(stringToFind, s2))
{
continue;
}

boolean subStringFound = false;
int offset = 0;
int i = 0;
// start with the exact length
while( !subStringFound )
{
// start to find all characters of s2 within equal length of words in stringToFind,
// if not found, increase length each time
for(i=0; i <= (stringToFind.length() - s2.length() - offset); i++ )
{
String currentSegment = stringToFind.substring(i, i + s2.length() + offset);

if( stringHasAllLetters(currentSegment, s2) )
{
results.add(currentSegment);
subStringFound = true;
break;
}
}

if( !subStringFound )
{
i = 0;
offset++;
}
}
}

System.out.println(results);

}

private static boolean stringHasAllLetters(String stringToFind, String letters)
{
boolean allLettersPresent = true;
for(char c : letters.toCharArray())
{
if(stringToFind.indexOf(c) == -1){
allLettersPresent = false;
break;
}
}
return allLettersPresent;
}

- Miral Patel May 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

I’m going to propose a linear time solution here.
Concept is to
1. Eliminate all characters of s3 from s1
2. Find the first subsequence of s1 that contains all chars of s2

- puneet.sohi April 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 votes

Create a bool array of 256 chars a[256]
Walk S3, char by char, for each char c set a[c] = TRUE
Walk S1, and if for any char c of S1, a[c] == TRUE, means this char is also present in S3, so delete it

Now , create another bool array of 256 chars b[256]
Walk S2, char by char, for each char c set b[c] = TRUE
Walk S1, and if for any char c , b[c] == TRUE, means this char is present both in S1 & S2 and not S3.
So, put this aside into a string (S)

At the end, S will give us the answer

- puneet.sohi April 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Nice one!

- iroodaz April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks!

- puneet.sohi April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Puneet, I was answering in an online interview to this question and followed your algorithm but then realised that its wrong. Please don't post wrong answers. Thankfully program from Kishor Kumar saved my day

- Girish April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Girish, I didn't post this algorithm knowing that it is wrong. When I post answer, I know they're correct as far as I know.
Can you tell me whats wrong with it?

- puneet.sohi April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

hey puneet.. nothing offensive here.. I just tried following your algorithm blindly as I had only 15 min to solve but couldn't get the desired answer.. better I post my code here.. may be I am wrong here.. you can help me out where I went wrong.. thanks :-)

boolean[] barray = new boolean[256];
for(int i=0;i<str3.length();i++)
{
char c= str3.charAt(i);
barray[c] = true;
}


for(int i=0;i<str1.length();i++)
{
if (barray[str1.charAt(i)]== true)
str1=str1.replaceAll(Character.toString(str1.charAt(i)), "");

}

System.out.println(str1);
boolean[] bary = new boolean[256];
for(int i=0;i<str2.length();i++)
{
char c= str2.charAt(i);
bary[c] = true;
}

StringBuilder sb=new StringBuilder();

for(int i=0;i<str1.length();i++)
{
if (bary[str1.charAt(i)]== true)
sb.append(str1.charAt(i));

}
System.out.println(sb.toString());

- Girish April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

As I said, I blindly followed your steps without thinking much on logic because of time constraint. May be you could've explained more in your steps.

- Girish April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Girish, no offense taken.
I'm not Java coder, so I don't know exactly what your code does.
I'm posting a working C++ code here(with examples)
I don't post code with my answers, because I prefer to leave something to the other person.

- puneet.sohi April 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

#include <iostream>
#include <tr1/unordered_map>
#include <vector>
#include <tr1/memory>
#include <memory>

using namespace std;
using namespace tr1;

int main(){
	int i = 0; 
	string str3 = "gh";
	string str1 = "asdfgjkl";
	string str2 = "zzyadl";
	string s; string s_final; //s_final stores final result
	char c;
	
	/*
	 =========== Remove S3 from S1 ============
	 */	
	
	bool a1[256];
	i = 0;
	for(i=0;i<256;i++)
	{
		a1[i] = false;
	}	
	
	i = 0;
	for(i=0;i<str3.length();i++)
	{
		c= str3[i];
		a1[c] = true;
	}
	

	i = 0;
	for(i=0;i<str1.length();i++)
	{
		c = str1[i];
		if (a1[c] != true)
			s.append(1, c);
	}
	
	cout << s << endl;
	
	/*
	 ============ FIND common in S and S2 ============
	 */	
	
	
	bool a2[256];
	i = 0;
	for(i=0;i<256;i++)
	{
		a2[i] = false;
	}	
	
	i = 0;
	for(i=0;i<str2.length();i++)
	{
		c = str2[i];
		a2[c] = true;
	}
	
	i = 0;
	for(i=0;i<s.length();i++)
	{
		c = s[i];
		if (a2[c] == true)
			s_final.append(1, c);
	}
	
	cout << s_final << endl;
	
	return 0;	
}

- puneet.sohi April 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This problem is ambiguous. I think you meant "substring" instead of "subsequence".

And this problem can be solved in linear time using window sliding technique. First remove characters from s1 those also appear on s3. So s1 is exploded into smaller strings. Now for any of these smaller strings, let's call it s4, keep track of the characters seen so far. For an example, if we need to find the shortest substring from string "abbbcba" that also contains "abc", when we find the second a, we don't need the first a any longer. So using a double ended queue we can solve it in O(N) time and O(N + 26) => O(N) space in worst case.

- Fallen April 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

My thoughts exactly.

- puneet.sohi April 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what will happen in case of
a="xayyz"
b="xyz"
will you skill when you encounter the y after y?
I think skipping is possible only on start boundary,

What if a="xayyzxybcd as here answer is zyx
means we also need to check from each start found

- pc October 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**This class find smallest subword in a string which contains a specified
* set of characters in any sequence. Also it checks for filter characters.
* @author Kishor Kumar Padhan
*
*/
public class StringSeqFinder {

public static void main(String[] s)
{
String str1 = "spqrstrupvqw";
String str2 = "sprt";
String str3 = "q";
System.out.println(findSmallestString(str1, str2, str3));

}

private static String findSmallestString(String str1, String str2, String str3) {
List<String> list = new ArrayList<String>();
for(int k=0;k<str1.length();k++) {
StringBuffer sb = new StringBuffer();
StringBuffer sb1 = new StringBuffer();
int noOfCharsFound = 0;
String str4=str1.substring(k,str1.length());
for(int i=0;i<str4.length();i++) {
sb.append(str4.charAt(i));
for(int j=0; j< str2.length(); j++) {
if(str2.charAt(j) == str4.charAt(i)) {
if(sb1.indexOf(String.valueOf(str2.charAt(j)))==-1) {
sb1.append(str2.charAt(j));
noOfCharsFound++;
}
}
}
if(noOfCharsFound == str2.length()) {
list.add(sb.toString());
sb = new StringBuffer();
sb1 = new StringBuffer();
noOfCharsFound = 0;
}
}
}

filterList(list, str3);
String small="Not found";
if(list.size()>0) {
small=list.get(0);
for (String string : list) {
if(small.length()>string.length()) {
small=string;
}
}
}
return small;
}

private static void filterList(List<String> list, String str3) {
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String string = (String) iterator.next();
if(doesStringContainInvalidCharacter(string,str3)) {
iterator.remove();
}
}
}

private static boolean doesStringContainInvalidCharacter(String string, String str3) {
for (int i = 0; i < str3.length(); i++) {
if(string.contains(String.valueOf(str3.charAt(i)))) {
return true;
}
}
return false;
}
}

- Kishor Kumar Padhan April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Awesome dude! you saved my day :)

- Girish April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here is my 2 cents to this problem. I guess, i have reduced the iterations significantly. I have not fully tested it. But, hopes this works fine.

package in.co.collection;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;

public class MyDemoQuestion {

String str1, str2, str3;
ArrayList<Integer> firstIndexOf = new ArrayList<Integer>();
ArrayList<String> foundList = new ArrayList<String>();
char[] str_2;
char[] str_3;

public MyDemoQuestion(String s1, String s2, String s3) {
str1 = s1;
str2 = s2;
str3 = s3;
str_2 = str2.toCharArray();
str_3 = str3.toCharArray();
}

@SuppressWarnings("unchecked")
boolean find() {
firstIndexOf.clear();
for (int i = 0; i < str_2.length; i++) {
int index = str1.indexOf(str_2[i]);
if (index != -1) {
firstIndexOf.add(index);
}
}
if (firstIndexOf.size() != str2.length()) {
return false;
} else {
Collections.sort(firstIndexOf);
String temp = str1;
System.out.println("Str1 --->"+temp + "--->Indexes of chars in str2---->" + firstIndexOf);
System.out.println("First sequence ---->"+temp.substring(firstIndexOf.get(0), firstIndexOf
.get(firstIndexOf.size() - 1)
- firstIndexOf.get(0) + 1));
foundList.add(temp.substring(firstIndexOf.get(0), firstIndexOf
.get(firstIndexOf.size() - 1)
- firstIndexOf.get(0) + 1));
str1 = str1.substring(firstIndexOf.get(1));
return true;
}
}

void filterList() {
Iterator itr = foundList.iterator();
while(itr.hasNext()){
for (int j = 0; j < str_3.length; j++) {
String x = (String) itr.next();
if (x.contains(String.valueOf(str_3[j]))) {
System.out.println("removed----->"+x);
itr.remove();
break;
}
}
}
}

public static void main(String args[]) {
String str1 = "spqrstrupvqw";
String str2 = "sprt";
String str3 = "q";
MyDemoQuestion obj = new MyDemoQuestion(str1, str2, str3);
while (obj.find()) {

}
obj.filterList();
System.out.println("------" + obj.foundList);

String shortest = obj.foundList.get(0);
for (String a : obj.foundList) {
if (a.length() < shortest.length()) {
shortest = a;
}
}
System.out.println(shortest);
}

}

- Vatsal Garg May 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public class ThreeStringProblem {
	public static void main(String[] args) {

		String one = "spqrstrupvqw";
		String two = "sprt";
		String three = "q";

		int minLength = Integer.MAX_VALUE;
		String minLengthString = "";

		// Sliding window; Start from index 0 with a window of size equivalent
		// to String two and increment by one character every iteration
		for (int i = 0; i < one.length(); i++) {
			for (int j = i + two.length(); j <= one.length(); j++) {

				// Get the subString
				String subString = one.substring(i, j);

				// Check if all the characters match
				if (checkIfAllCharactersArePresent(subString, two, three)) {
					if (subString.length() < minLength) {
						minLength = subString.length();
						minLengthString = subString;
					}
				}
			}
		}

		System.out.println(minLengthString);

	}

	/**
	 * The method is used to check if all the characters of String two are
	 * present in String one but not that of String three
	 * 
	 * @param first
	 * @param two
	 * @param three
	 * @return
	 */
	private static boolean checkIfAllCharactersArePresent(String first,
			String two, String three) {

		boolean result = true;
		BitSet bitSet = new BitSet();

		// Set first String
		for (int i = 0; i < first.length(); i++) {
			bitSet.set(first.charAt(i));
		}

		// Third
		for (int i = 0; i < three.length(); i++) {
			if (bitSet.get(three.charAt(i))) {
				result = false;
				return result;
			}
		}

		// Two
		for (int i = 0; i < two.length(); i++) {
			if (!bitSet.get(two.charAt(i))) {
				result = false;
				return result;
			}
		}

		return result;

	}
}

- SumitGaur April 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I liked SumitGaur code. Simple and works well. Here is a verified version of the above code which stops search the substring in str1 if it contains a letter of str3.

package morganstanleyquestions;

import java.util.HashSet;
import java.util.Set;

public class ThreeStringProblem {

public static void main(String args[]){
String str1 = "spqrstrupvqw";
String str2 = "sprt";
String str3 = "q";
int str2Len = str2.length();
String reqSubString = "";
String minSubSeq = "";
int minSubSeqLength = str1.length();
for(int i=0;i<str1.length();i++){

char startWndChar = str1.charAt(i);
if(str2.indexOf(startWndChar) == -1){
continue;
}
else{
//got the first char in str1 from where to start the window
for(int j = i + str2.length(); j<str1.length(); j++){
reqSubString = str1.substring(i,j);
System.out.println("req sub string to test :" + reqSubString);
int matchCondition = isQualifiedMatch(reqSubString, str2, str3);
if(matchCondition == 1){
if(reqSubString.length()<minSubSeqLength){
minSubSeq = reqSubString;
minSubSeqLength = minSubSeq.length();
}
}
else if(matchCondition == 0){
continue;
}
else{
//match is -1. No need to continue with the window.
break;
}
}
}
}

System.out.println("min sub sequence string :" + minSubSeq);
}

private static int isQualifiedMatch(String subSeq, String str2, String str3){

Set<Character> seqSet = new HashSet<>();
for(int i=0;i<subSeq.length();i++){
seqSet.add(subSeq.charAt(i));
}

for(int i = 0; i<str3.length(); i++){
if(seqSet.contains(str3.charAt(i))) return -1;
}

for(int i = 0; i<str2.length(); i++){
if(!seqSet.contains(str2.charAt(i))) return 0;
}

return 1;
}
}

- Srikanth Patruni April 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a brute force method...

/*
 * SortString.cc
 *
 *  Created on: Apr 21, 2014
 *      Author: Tom Tong
 */

#include <iostream>
#include <algorithm>
#include <string>
#include <cstddef>

using namespace std;

int main(int, char**)
{
	string s("spqrstrupvqw");
	string testFor("sprt");
	string avoid("q");


	int start = 0;
	unsigned int valid = 0;
	for(int i = 0; i < s.length(); i++)
	{
		// lets see how far we can get before hitting the first char of avoid
		if (avoid.find_first_of(s[i]) != string::npos) // then char is in the avoid list
		{
			start = i+1;
			valid = 0;
		}
		else
		{
			valid++;
		}

		if (valid >= testFor.length()) // we have valid length
		{
			string sub = s.substr(start, valid);
			//cout << "got substr:" << sub << endl;
			unsigned int j;
			for(j = 0; j < testFor.length(); j++)
				if (sub.find_first_of(testFor[j]) == string::npos) // then sub didn't have one of char's to test for
					break;

			if (j == testFor.length()) // then we have all the chars
			{
				// now trim it from front, since the last one added did the trick
				std::size_t matches;
				do {
					if ( (matches = testFor.find_first_of(sub[0])) != string::npos)
						sub = sub.substr(1, sub.length() - 1);
				} while (matches == string::npos);
				cout << "Found string:" << sub << endl;
				return true;
			}
		}
	}
	cout << "didn't find the substring" << endl;
	return false;
}

- TomT April 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I liked SumitGaur code. Simple and works well. Here is a verified version of the above code which stops search the substring in str1 if it contains a letter of str3.

package morganstanleyquestions;

import java.util.HashSet;
import java.util.Set;

public class ThreeStringProblem {

public static void main(String args[]){
String str1 = "spqrstrupvqw";
String str2 = "sprt";
String str3 = "q";
int str2Len = str2.length();
String reqSubString = "";
String minSubSeq = "";
int minSubSeqLength = str1.length();
for(int i=0;i<str1.length();i++){

char startWndChar = str1.charAt(i);
if(str2.indexOf(startWndChar) == -1){
continue;
}
else{
//got the first char in str1 from where to start the window
for(int j = i + str2.length(); j<str1.length(); j++){
reqSubString = str1.substring(i,j);
System.out.println("req sub string to test :" + reqSubString);
int matchCondition = isQualifiedMatch(reqSubString, str2, str3);
if(matchCondition == 1){
if(reqSubString.length()<minSubSeqLength){
minSubSeq = reqSubString;
minSubSeqLength = minSubSeq.length();
}
}
else if(matchCondition == 0){
continue;
}
else{
//match is -1. No need to continue with the window.
break;
}
}
}
}

System.out.println("min sub sequence string :" + minSubSeq);
}

private static int isQualifiedMatch(String subSeq, String str2, String str3){

Set<Character> seqSet = new HashSet<>();
for(int i=0;i<subSeq.length();i++){
seqSet.add(subSeq.charAt(i));
}

for(int i = 0; i<str3.length(); i++){
if(seqSet.contains(str3.charAt(i))) return -1;
}

for(int i = 0; i<str2.length(); i++){
if(!seqSet.contains(str2.charAt(i))) return 0;
}

return 1;
}
}

- Srikanth Patruni April 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I liked Sumit Gaur's code.
It is simple and elegant.
I tried my hand on this problem.
Following is the code

package com.javafries.string;

import java.util.ArrayList;
import java.util.List;

/**
 * @author vishal.naik
 * java-fries.com
 */
public class SmallestStrFinderProblem {

    public static void main(String[] args) {
	long start = System.currentTimeMillis();
	String str1 = "spqrstrupvqw";
	String str2 = "sprt";
	String str3 = "q";

	findSmallestSubString(str1, str2, str3);
	System.out.println("Time taken: "
		+ (System.currentTimeMillis() - start));
    }

    /**
     * Finds the smallest substring in str1 which contains all the characters in
     * str2 (in any order) and not those in str3.
     * 
     * @param str1 , not null
     * @param str2 , not null
     * @param str3 , not null
     */
    private static void findSmallestSubString(String str1, String str2,
	    String str3) {
	char[] str3Chars = str3.toCharArray();

	List<String> possibleSearchStrs = findPossibleSearchStrings(str1, str2,
		str3Chars);

	int minLength = Integer.MAX_VALUE;
	String minStr = "";

	for (String word : possibleSearchStrs) {
	    char[] wordChars = word.toCharArray();

	    // Iterate over characters of word.
	    for (int i = 0; i < wordChars.length; i++) {
		
		// Create substring of word starting at current character to str2.length,
		// Increment substring's length by one, on every iteration.
		for (int j = i + str2.length(); j < wordChars.length; j++) {
		    String subStr = word.substring(i, j);
		    
		    if (containsString2(subStr, str2)) {
			if (j - i < minLength) {
			    minLength = j - i;
			    minStr = subStr;
			}
		    }
		}
	    }
	}
	if (minStr.isEmpty()) {
	    System.out.println("No Solution found.");
	} else {
	    System.out.println(minStr);
	}
    }

    /**
     * Finds all possible search strings
     * 
     * @param str1 , not null
     * @param str2 , not null
     * @param str3Chars , not null
     * @return
     */
    private static List<String> findPossibleSearchStrings(String str1,
	    String str2, char[] str3Chars) {
	List<String> possibleSearchStrs = new ArrayList<String>();
	possibleSearchStrs.add(str1);

	for (int i = 0; i < str3Chars.length; i++) {
	    List<String> tempStore = new ArrayList<String>();
	    for (String word : possibleSearchStrs) {
		String[] wordSplit = word.split(String.valueOf(str3Chars[i]));
		for (int j = 0; j < wordSplit.length; j++) {
		    if (wordSplit[j].length() >= str2.length()) {
			tempStore.add(wordSplit[j]);
		    }
		}
	    }
	    possibleSearchStrs.clear();
	    possibleSearchStrs.addAll(tempStore);
	}
	return possibleSearchStrs;
    }

    /**
     * Checks if str2 is contained in subStr.
     * 
     * @param subStr , not null
     * @param str2 , not null
     * @return
     */
    private static boolean containsString2(String subStr, String str2) {
	char[] str2Chars = str2.toCharArray();
	for (int i = 0; i < str2Chars.length; i++) {
	    if (!subStr.contains(String.valueOf(str2Chars[i]))) {
		return false;
	    }
	}
	return true;
    }
}

- vishal naik April 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I guess most of you guys are splitting and solving this puzzle which is completely trash way to solve it..
rather just create an array of characters b[26] = count for string s2, c[26] = count for string s3;
now iterate over s1 and whenever you encounter a character of string s3 flush out a[26]; or else keep incrementing the character index in a[26], if a[26] >= b[26] element wise add up all the count in a[26] and thats one possible solution then delete the earliest char in a[26] till it keep satisying a[26]>=b[26] and updating the minimum solution, no other substring memories no splitting nothin, its a basic one pass linear algorithm

- kkr.ashish May 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class testing 
{

	// a="spqrstrupvqw"
	// b="sprt"
	// c="q"
	
	public static String findSubSequence(String a,String b,String c,ArrayList<String> strSubseq)
	{
		String result = "";
		
		char[] a1 = new char[a.length()];
		char[] b1 = new char[b.length()];
		char[] c1 = new char[c.length()];
				
		//ArrayList<String> strSubseq = new ArrayList<String>();
		//int[] arrIdx = new int[b.length()];
		ArrayList<Integer> arrIdx = new ArrayList<Integer>();
		
		a1 = a.toCharArray();
		b1 = b.toCharArray();
		c1 = c.toCharArray();
		
		int index,idxExist;
		int counter=0;
		int minIdx, maxIdx;
		String strSub, strSub2;
		
			arrIdx = findSubseqIdx(a1,b1); // find min and max index from a1 for match
			
			if (arrIdx.size()<b.length())
			{
				if (strSubseq.size() > 0)
				{
					result = showSubString(strSubseq);							
				}
				else
				{
					result = "";					
				}				
			}
			else
			{
				minIdx = findMin(arrIdx);
				maxIdx = findMax(arrIdx);
				idxExist = checkIfCharExists(a1,c1[0],minIdx,maxIdx); // check if "q" exists between min and  max index
				
				if (idxExist != -1)
				{
					strSub = a.substring(idxExist+1,a.length()); 
					findSubSequence(strSub,b,c,strSubseq);					
				}		
				else
				{
					strSubseq.add(a.substring(minIdx,maxIdx+1));
					
					for (int k = minIdx+1; k<a.length();k++)
					{
						findSubSequence(a.substring(k,a.length()),b,c,strSubseq);
					}
					
				}
				result = showSubString(strSubseq);
			}
			
			return result;
	}
	
	public static int findChar(char[] seq,char a)
	{
		int idx = 100;
		
		for (int j=0; j<seq.length; j++)
		{
			if (a == seq[j])
			{
				idx=j;
				break;
			}			
		}		
		return idx;
	}
	
	public static int findMin(ArrayList<Integer>a)
	{
		int temp = a.get(0);
		
		for (int i=0; i<a.size(); i++)
		{
			if (a.get(i)<temp)
			{
				temp = a.get(i);
			}
		}
		return temp;		
	}
	
	public static int findMax(ArrayList<Integer>a)
	{
		int temp = a.get(0);
		
		for (int i=0; i<a.size(); i++)
		{
			if (a.get(i)>temp)
			{
				temp = a.get(i);
			}
		}
		return temp;
	}
	
	public static int checkIfCharExists(char[] strArray, char c,int minIdx, int maxIdx)
	{
		int idx = -1;
		//char[] strArray = new char[str.length()];		
		for (int i=minIdx; i<maxIdx; i++)
		{
			if (strArray[i] == c)
			{
				idx = i;
				break;
			}
		}		
		return idx;
	}
	
	public static ArrayList<Integer> findSubseqIdx(char[] a1, char[] b1)
	{
		int index;
		ArrayList<Integer> arrIdx = new ArrayList<Integer>();
		
		for(int i=0; i<b1.length; i++)
		{
			index = findChar(a1,b1[i]);
			
			if (index!=100)
			{
				arrIdx.add(index);
			}			
		}	
		return arrIdx;		
	}
	
	public static String showSubString(ArrayList<String> a)
	{
		String out = a.get(0);
		
		for (int i=0; i<a.size(); i++)
		{
			if(a.get(i).length() < out.length())
			{
				out = a.get(i);
			}			
		}		
		return out;		
	}	
	
	public static void main (String[] args)
	{
		//System.out.println("hello world");
		
		String a,b,c,result;
		ArrayList<String> strArr = new ArrayList<String>();
		
		/*a = "spqrstrupvqw";
		b = "sprt";
		c = "q";*/
		
		a = "abdecfgdacdc";
		b = "dc";
		c = "e";
		
		result = findSubSequence(a,b,c,strArr);
		System.out.println(result);
	}

	
}

- humus June 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. For every character in str1, check if its there in str2
2. Add the character to linkedlist. Before adding check if this character is already there in linkedlist. If its there, then remove that character and add it to the end. In Parallel , update other linked list with its position
3. When size of str1 and linked list are same, find difference between first and last position and compare with old min value

int diff,min=100,first,last,min_first=0,min_last=0;
String str1="spqrstrupvqw ",str2="sprt";
LinkedList<Character> str=new LinkedList<Character>();
LinkedList<Integer> num=new LinkedList<Integer>();

for (int i = 0; i < str1.length(); i++) {
char ch = str1.charAt(i);

if (str2.indexOf(ch) >= 0) {
if (str.contains(ch)) {
int pos = str.indexOf(ch);
str.remove(pos);
num.remove(pos);
}
str.add(ch);
num.add(i);

if (str.size() == str2.length()) {
first = num.getFirst();
last = num.getLast();
diff = last - first;
if (diff <= min) {
min = diff;
min_first = first;
min_last = last;
}
}
}
}

System.out.println(str1.substring(min_first, min_last + 1));

- Anonymous June 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Inorder to check if its there in str3:
if(str3.indexOf(ch)>=0) {
str.clear();
num.clear();
}

- Meenakshi June 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class FindSubStringinAnotherStringNotInThirdString {
	String str1 = null;
	String str2 = null;
	String str3 = null;

	public FindSubStringinAnotherStringNotInThirdString() {
		str1 = "spqrstruvpqw";
		str2 = "sprt";
		str3 = "q";
	}

	String findSubString() {
		String newString = "";

		String strArray[] = str1.split(str3);
		for (String str : strArray) {
			if (str.length() >= str2.length())
				newString = str;
			// System.out.println(str);
		}

		return findpositions(newString);
	}

	public String findpositions(String newString) {
		int pos1 = 0, pos2 = 0;

		char ch[] = str2.toCharArray();

		int a1 = 0, b = 0, c = 1;

		for (char a2 : ch) {

			a1 = newString.indexOf(a2);

			if (a1 > b)
				b = a1;

			if (a1 < c)
				c = a1;

		}

		// System.out.println(c + " "+b+""+newString.substring(c+1,b+1));
		return newString.substring(c + 1, b + 1);

	}

	public static void main(String[] args) {

		FindSubStringinAnotherStringNotInThirdString fs = new FindSubStringinAnotherStringNotInThirdString();

		System.out.println("subString is=" + fs.findSubString());

	}

}

- Ravi Kumar June 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void findSubstring(){
		
	    String str1 = "spqrstrupvqw";
	    String str2 = "sprt";
	    String str3 = "q";
	    
	    int startIndex = 0;
	    int currIndex = 0;
	    
	    Set set = new HashSet();
	    
	    while(set.size()<str2.length()){
	    	char c = str1.charAt(currIndex);
		    if((c+"").equalsIgnoreCase(str3)){	    	
		    	startIndex=++currIndex;
		    	set.clear();
		    }else if(str2.contains(c+"")){	 
		    	if((startIndex!=currIndex) && c==str1.charAt(startIndex)){
		    		startIndex++;
		    		currIndex++;
		    	}else{
			    	set.add(c+"");
			    	currIndex++;
		    	}
		    }else{
		    	currIndex++;
		    }
	    }
	    System.out.println(str1.substring(startIndex, currIndex));
	}
}

- Deepali October 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Requires one pass through str1, so linear time.

1. Find first example from str2 in str1. (Any chars before this must make the string longer and can be ignored.)
2. Iterate through str1, adding characters to candidate_string. If character is in str2 and was not previously in candidate_string, increment match_counter. (This assumes there are no duplicate characters in str2.)
3. If we encounter a character in str3, truncate candidate_string, set match_counter to zero, move iterator to next occurrence of str2 character in str1, then start reading characters into candidate_string again.
4. If length of candidate_string is now >= any previously stored result_string, find the second occurrence of a str2 char in candidate_string (as that's the next possible shortest candidate_string start). Take the substring from that position to the end of candidate_string, decrement match_counter. Continue to iterate through str1 from current position, adding characters to candidate_string.
5. If match_counter == str2.length() then we have matched all candidate chars in a shorter length than the previous result_string. Copy candidate_string to result_string. Take the substring from second occurrence of str2 character in candidate_string to be the new candidate_string, as above.
6. If result_string.length() == str2.length() then this is the shortest possible sequence, so we can break. Otherwise, move the str1 iterator to the next occurrence of str2 in str1, decrement match_counter.
7. Finish when we break on shortest possible sequence or end of str1. Return result_string. Could be empty if there was no substring contained all chars from str2.

- merlinme December 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming there are only lowercase letters and string 2 has distinct characters.

Time Complexity ~= O (s1.len + s2.len + s3.len)

public String smallest(String s1, String s2, String s3) {
// target string.
char[] c1 = s1.toCharArray();

// allowed characters.
char[] c2 = s2.toCharArray();

//disallowed characters.
char[] c3 = s3.toCharArray();

int[] i2 = new int[26];
int[] i3 = new int[26];

// capturing characters present in string 2.
for (int i = 0; i < c2.length; i++) {
i2[ c2[i] - ‘a’ ] = 1;
}

// same as above for string 3.
for (int i = 0; i < c3.length; i++) {
i3[ c3[i] - ‘a’ ] = 1;
}

// starting & finish of the smallest subsequence.
int s, e;
s = 0;
e = c1.length + 1;

int start, end, count;
start = end = count = 0;

for (int i = 0; i < c1.length; i++) {

// check whether disallowed.
if (i3[ c1[i] - ‘a’ ] == 1) {
// reset all the flags.
start = end = count = 0;
}
// check whether allowed.
else if (i2[ c1[i] - ‘a’ ] == 1) {
start = count > 0 ? start : i;
count++;

// assuming c2 has distinct characters.
if (count == c2.length) {
// found a possible result.
end = i;

// lets see whether this is the smallest.
if ((e-s) > (end - start)) {
e = end;
s = start;
}

// lets starting from next character.
i = start;
start = end = count = 0;
}
}
else {
count = count > 0 ? count+1 : count;
}

}

// check whether we found any subsequence or not.
if (e == (c1.length+1))
return null;

int offset = e - s + 1;
return new String(c1, s, offset);
}

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

Assuming there are only lowercase letters and string 2 has distinct characters.

Time Complexity ~= O (s1.len + s2.len + s3.len)

public String smallest(String s1, String s2, String s3) {
  // target string.
  char[] c1 = s1.toCharArray();

  // allowed characters.
  char[] c2 = s2.toCharArray();

  //disallowed characters.
  char[] c3 = s3.toCharArray();

  int[] i2 = new int[26];
  int[] i3 = new int[26];

  // capturing characters present in string 2.
  for (int i = 0; i < c2.length; i++) {
    i2[ c2[i] - ‘a’ ] = 1;
  }

  // same as above for string 3.
  for (int i = 0; i < c3.length; i++) {
    i3[ c3[i] - ‘a’ ] = 1;
  }

  // starting & finish of the smallest subsequence.
  int s, e;
  s = 0;
  e = c1.length + 1;

  int start, end, count;
  start = end = count = 0;

  for (int i = 0; i < c1.length; i++) {

    // check whether disallowed.
    if (i3[ c1[i] - ‘a’ ] == 1) {
      // reset all the flags.
      start = end = count = 0;
    } 
    // check whether allowed. 
    else if (i2[ c1[i] - ‘a’ ] == 1) {
      start = count > 0 ? start : i;
      count++;

      // assuming c2 has distinct characters.
      if (count == c2.length) {
        // found a possible result.
        end = i;

        // lets see whether this is the smallest.
        if ((e-s) > (end - start)) {
          e = end;
          s = start;
        }

        // lets starting from next character.
        i = start;
        start = end = count = 0;
     }
    }
    else {
      count = count > 0 ? count+1 : count;
    }

  }

  // check whether we found any subsequence or not.
  if (e == (c1.length+1))
    return null;

  int offset = e - s + 1;
  return new String(c1, s, offset);
}

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

WAP which takes two string as input from the user (a & b).This prog should print two strings as output (a1 & b1).
(a1) should contain all the characters which are present in (a).but not present in (b).
(b1)should contains all the characters which are present in (b).but not present in(a).

- mmr February 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

WAP which takes two string as input from the user (a & b).This prog should print two strings as output (a1 & b1).
(a1) should contain all the characters which are present in (a).but not present in (b).
(b1)should contains all the characters which are present in (b).but not present in(a).

- malli April 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Below code will solve the problem and this in liner order

package randomProblem;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class PatternSearching {
	
	public static Map<String,Integer> mapData = new HashMap<String, Integer>();
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input=br.readLine();
		char[] patternToMatch=br.readLine().toCharArray();
		String ignore=br.readLine();
		List<String> containsPattern=new ArrayList<String>();
		
		String[] convertedString = input.split(ignore);
		
	for(String pattern:convertedString){
		 if(pattern.length()< patternToMatch.length){
			 continue;
		 }
		 
			for (int jj = 0; jj < pattern.length() - patternToMatch.length; jj++) {

				int offset = 0;
				boolean notFound = true;
				while (notFound) {
					String subString = pattern.substring(jj,
							patternToMatch.length + offset);
					if (checkIfPatterExist(subString, patternToMatch)) {
						containsPattern.add(subString);
						notFound = false;

					} else {
						offset++;
						if (!(pattern.length() > patternToMatch.length + offset)) {
							break;
						}

					}
				}
			}
	 

 
	}
	int minLength=containsPattern.get(0).length();
	String str=containsPattern.get(0);
	for(String value:containsPattern){
		 if(value.length() < minLength){
			 minLength=value.length();
			 str=value;
		 }
	 }
	 System.out.println(str);
	}
	
	private static boolean checkIfPatterExist(String pattern, char[] patternToMatch) {
		

	  for(int i=0;i<patternToMatch.length;i++){
		  if(pattern.indexOf(patternToMatch[i])==-1){
			  return false;
		  }
	  }
	return true;	
	}

}

- Anand Soni April 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What will be the running time to find the minimum substring in S1 after removing s3?
Can you elaborate that?

- Peter April 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void Main(string[] args)
        {
            var str1 = "spqrstrupvqw";
            var str2 = "sprt";
            var str3 = "q";

            var testDictionary = new List<KeyValuePair<string, bool>>();

            var str1Split = str1.Split(str3.ToCharArray());
            var str2Split = str2.ToCharArray();

            foreach (var item in str1Split)
            {
                var counter = 0;
                foreach (var item2 in str2Split)
                {
                    if (item.Contains(item2))
                    {
                        counter++;
                    }
                }

                if (counter >= str2Split.Length)
                {
                    testDictionary.Add(new KeyValuePair<string, bool>(item, true));
                }
            }

            var fnalResult = testDictionary.Select(x =>
            {
                var myDict = new Dictionary<char, int>();
                var result = "";
                foreach (var item in testDictionary)
                {
                    if (item.Key.Length <= x.Key.Length)
                    {
                        result = x.Key;
                    }
                }

                if (!string.IsNullOrWhiteSpace(result))
                {
                    var index = 0;
                    foreach (var item in result.ToCharArray())
                    {
                        if (str2.Contains(item))
                        {
                            if (myDict.ContainsKey(item))
                            {
                                myDict[item] = index;
                            }
                            else
                            {
                                myDict.Add(item, index);
                            }
                        }

                        index++;
                    }
                }

                var min = myDict.OrderBy(p => p.Value).FirstOrDefault().Value;
                var max = myDict.OrderBy(p => p.Value).LastOrDefault().Value;
                return result.Substring(min, max);

            }).Where(x => x != null).FirstOrDefault();

            Console.WriteLine(fnalResult);
        }

- Sanjiv Mehra March 30, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
String s1 = "spqrstrupvqw";
String s2 = "sprt";
String s3 = "q";
for (String s4 : s1.split(s3)) {
if (s4.length() >= s2.length()) {
getComb(s4, s2);
}
}
}

public static boolean checkString(String sData, String sCheck) {
for (char c : sCheck.toCharArray()) {
if (!sData.contains(Character.toString(c))) {
return false;
}
}
return true;
}

public static void getComb(String sData, String sCheck) {
String sComb;
aa: for (int j = sCheck.length() - 1; j < sData.length(); j++) {
for (int i = 0; i < sData.length() - j; i++) {
sComb = sData.substring(i, i + j + 1);
if (checkString(sComb, sCheck)) {
System.out.println(sComb);
break aa;
}
}
}

}

- Abhilash April 13, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class interview {

public static void main(String[] args) {
String s1 = "spqrstrupvqw";
String s2 = "sprt";
String s3 = "q";
for (String s4 : s1.split(s3)) {
if (s4.length() >= s2.length()) {
getComb(s4, s2);
}
}
}

public static boolean checkString(String sData, String sCheck) {
for (char c : sCheck.toCharArray()) {
if (!sData.contains(Character.toString(c))) {
return false;
}
}
return true;
}

public static void getComb(String sData, String sCheck) {
String sComb;
aa: for (int j = sCheck.length() - 1; j < sData.length(); j++) {
for (int i = 0; i < sData.length() - j; i++) {
sComb = sData.substring(i, i + j + 1);
if (checkString(sComb, sCheck)) {
System.out.println(sComb);
break aa;
}
}
}

}

}

- Abhilash April 13, 2018 | 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