CareerCup

Example

String str1= ABCDEFGHIJKLMNOPQR
String str2= DBCAXGFHTRQPONMKL

1. Find all the possible window from str1 and str2
Possible windows from Str1=[ABCD,FGH,KLMNOPQR]
Possible windows from Str2=[DBCA,GFH,RQPONMKL]

2. Sort each window in either asc/dsc order
Possible windows from Str1=[ABCD,FGH,KLMNOPQR]
Possible windows from Str2=[ABCD,FGH,KLMNOPQR]

3. Pick up all the windows from Str2 (Order by Descending Size Order) and one by one check, if it exist as a substring of any of the Str1 window.

In this case max window of str2 KLMNOPQR will match, hence no need to iterate further

Are they mutated patterns or permuted patterns? Please define what a mutated pattern is.

Adding to the above answer--3.Once the match is broken you can print out the consecutive match

Since you are looking for sequences, I do not think sorting will give you the right answer!

public class MaxWindowPattern {
	private static String pattenStr1 = "ABCDFGH";
	private static String pattenStr2 = "GHFDCBA";
	private static String reversePatternString = "";
	static {
		reversePatternString = reverseSubStr(pattenStr1);
		System.out.println(reversePatternString);
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		//System.out.println(reverseSubStr(pattenStr1));
		
		System.out.println(binarySearchWindowStr(reversePatternString));
	}

	private static String reverseSubStr(String str) {
		String resString = "";
		StringBuilder sBuilder = new StringBuilder(str);
		sBuilder.reverse();
		resString = sBuilder.toString();
		return resString;
	}

	private static String binarySearchWindowStr(String str) {
    if ("".equals(str)||str==null) {
	 System.out.println("empty string cannot find any window substring!");
	}else if (pattenStr2.contains(str)){
		System.out.println("max windows is "+str.length()+"window String from B is "+str);
	}
    int [][] strArray=new int[str.length()][pattenStr2.length()];
    int lenth=0;
    int end=0;
    char[] strArray1=str.toCharArray();
    char[] strArray2=pattenStr2.toCharArray();
    for (int i = 0; i < str.length(); i++) {
		for (int j = 0; j < pattenStr2.length(); j++) {
			int n =(i-1>0&&j-1>0)?strArray[i-1][j-1]:0;
			strArray[i][j]=(strArray1[i]==strArray2[j]?1+n:0);
			if(strArray[i][j]>lenth){
				lenth=strArray[i][j];
				end =i;
			}
		}
	}
    return str.substring(end-lenth+1,end+1);
	}
}

1. For both of the input strings S1 and S2, for all their N^2 substrings with beginIndex = i & endIndex = j, compute their integral values V1 and V2 just by summing up their charAt(k) values. [i<=k<=j]
2. Compare V1 and V2. If they are equal, sort the substrings S1.substring(i,j) and S2.substring(i,j) and compare if they are equal.
3. Save (i,j) that contains the maxlength substring and print it.

Full java implementation is given below. Provide in the console, the input strings one after the other.
Eg:
SKANDAPURANAGAJUTA
GARUDAAANURPJUJUGA

import java.util.Arrays;
import java.util.Scanner;
import java.util.regex.Pattern;

public class MaxMatchingPermutedStringWindow {
	static String input1, input2;
	static	int min= 1, max = 0;
	
	private static boolean cmpStrVal(int i, int j) {
		int sum=0;
		
		for (int k = i; k <=j ; k++) {
			sum += input1.charAt(k) - input2.charAt(k);			
		}		
		return 0 == sum;
	}
	
	private static boolean compareStr(int i, int j) {
		boolean equal = true;
		
		char[] arr1 = input1.substring(i, j + 1).toCharArray();
		char[] arr2 = input2.substring(i, j + 1).toCharArray();
		
		Arrays.sort(arr1);
		Arrays.sort(arr2);
		
		for (int k = 0; k < arr1.length; k++) 
			equal &= arr1[k] == arr2[k];
		
		return equal;
	}
	private static void findMaxMatSubString() {
		
		int len = input1.length();
		for (int k = 0; k < input1.length(); k++)
			for (int l = k; l < input1.length(); l++) 
				if (cmpStrVal(k,l) && compareStr(k,l) && (l-k+1) > (max - min + 1)) {					
					min = k; max = l;
				}
		
		System.out.println("Substring from 1st string:" + input1.subSequence(min,  max+1));
		System.out.println("Substring from 2nd string:" + input2.subSequence(min,  max+1));
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		Pattern pattern = Pattern.compile(System.getProperty("line.separator"));
		scanner.useDelimiter(pattern);

		if (scanner.hasNextLine()) {
			input1 = scanner.next();
		}
		
		if (scanner.hasNextLine()) {
			input2 = scanner.next();
		} else {
			System.out.println("Please provide both the strings");
		}
		
		if (input1.length() != input2.length()) 
			System.out.println("The strings are not of equal length!");
		else 
			findMaxMatSubString();				
	}
}

Based on two Strings (InputA and InputB) - create two Sets or ordered sequences.

Once I have two Sets of ordered sequences find the intersection. I'm using BST to build by ordered sequence since I still need to find the possible sequences. As I build the sequence I also expand the BST and essentially reset it once I'm working on the next set of sequences.

package amazon;

import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Set;

public class MatchingMutatedSequence {
	public static void main(String[] args) {
		new MatchingMutatedSequence().run();
	}

	private final String _inputA = "ABCDEFG";
	private final String _inputB = "DBCAPFG";

	/**
	 * Create two Sets containing all ordered sequences. From there just find
	 * the largest intersection.
	 * 
	 * @author MReyes
	 */
	public void run() {
		Set<String> _setA = createSet(_inputA);
		Set<String> _setB = createSet(_inputB);

		_setB.retainAll(_setA);

		String maxValue = "";
		Iterator<String> iter = _setB.iterator();
		while (iter.hasNext()) {
			String s = iter.next();
			if (s.length() > maxValue.length()) {
				maxValue = s;
			}
		}

		System.out.println(maxValue);
	}

	/**
	 * Create a Set of ordered sequences.
	 * 
	 * @param input
	 * @return
	 * @author MReyes
	 */
	public Set<String> createSet(String input) {
		Set<String> s = new HashSet<String>();
		for (int x = 0; x < input.length(); x++) {
			SortedChar sc = new SortedChar();
			for (int y = x; y < input.length(); y++) {
				sc.insert(input.charAt(y));
				s.add(sc.toString());
			}
		}
		return s;
	}

	/**
	 * Character based BST. Also supports duplicates.
	 * 
	 * @author MReyes
	 * 
	 */
	public static class SortedChar {
		private static class Node {
			private char _data;
			private Node _left;
			private Node _right;

			public Node(char data) {
				_data = data;
			}

			public Node getLeft() {
				return _left;
			}

			public void setLeft(Node left) {
				_left = left;
			}

			public Node getRight() {
				return _right;
			}

			public void setRight(Node right) {
				_right = right;
			}

			public char getData() {
				return _data;
			}
		}

		private Node _root;

		public String toString() {
			StringBuilder sb = new StringBuilder();
			_traverse(sb, _root);
			return sb.toString();
		}

		private void _traverse(StringBuilder sb, Node node) {
			if (node == null)
				return;

			_traverse(sb, node.getLeft());
			sb.append(node.getData());
			_traverse(sb, node.getRight());
		}

		public SortedChar insert(char data) {
			_root = _insert(_root, data);
			return this;
		}

		public Node _insert(Node node, char data) {
			if (node == null)
				return new Node(data);

			if (data < node.getData())
				node.setLeft(_insert(node.getLeft(), data));
			else
				node.setRight(_insert(node.getRight(), data));

			return node;
		}
	}

}

public static void sequenceMatching(StringBuffer seq1, StringBuffer seq2){
		
		int size = seq1.length();
		while(size != 0){
			char[] seq1array = seq1.toString().toCharArray();
			char[] seq2array = seq2.toString().toCharArray();
			Arrays.sort(seq1array);
			Arrays.sort(seq2array);
			
			if(Arrays.equals(seq1array, seq2array)){
				System.out.print(seq1+","+seq2);
				return;
			}
			
			size--;
			seq1 = new StringBuffer(seq1.substring(0,size));
			seq2 = new StringBuffer(seq2.substring(0,size));
		}
		
	}

If I get the question right, the following would work.
1. Sort the characters in both the string O(n log n).
2. Use two pointers(strPtr1 and strPtr2) pointing to start of the string, in a loop of 1..N. Store the windows in an array. And later find the greatest from windows array. O(n)
If string1 char is > string2 char
if(window>0){windows[arr++] = window; window = 0 }; str2ptr++; continue;
If string1 char == string2 char window++
strPtr1++;str2ptr++; continue;
if string1 char < string2 char
if(window>0){windows[arr++] = window; window = 0 }; strPtr1++; continue;

n log n + n

Can someone please explain what does this means
"Patterns can be mutated"

Whatever "mutated" means, this approach should solve it:
1. Create a hashtable H1 out of the first string: key = char (i.e. "a", "b", etc); value = position in the string (1, 2, etc.)
2. Create another hashset S2 out of the second string by iterating over it and taking values matching from H1 (i.e. for the given example it would be: 4,2,3,1,6,7).
3. Go over S2 and find the longest consecutive sequence of numbers by removing each next number and its neighbors left and right . For the given example that would be 4,2,3,1 or 6,7 => 4,2,3,1

I think that following approach should work.

1. call a function int cmp(str a,str b) to compare strings a,b which return max common len.
2. inside function:
a. set all flags of string a' characters to 1. alen=strlen(a);
b. iterate on b till it is not null.
I check b' ith charactor's flag. if its set increment count if count == alen return count
continue. (maintain a start variable for b string).
II if some flag is not set -> make that chat NULL and recursive call to our function with
strings role reversed and b being only this portion from last cmp(&b[start],a)
III store this returned value and maintain a max_len variable to be returned.

above example a=ABCDEFG, b=DBCAPFG
first char in b not to match P so call (DBCA,ABCDEFG) - returns 4 as all initial 4 match full string
calls again (FG,ABCDEFG) A is not set , shall not call with null. puts null at BCDE and calls (FG,FG) return 2.
return 4 to main func.

1 more example dbpcalm, bdacemp
e is not set in str b-> calls (bdac,dbpcalm)
p is not set in str b-> calls (db,bdac) returns 2
l is not set -> (ca,bdac) -> will finally return 2
next calls (mp,dbpcalm) which finally will return 1
answer max(2,1) 2

char* GetMaxWindow(char* seq1, int seq1Len, char* seq2, int seq2Len)
{
    if(!seq1 || !seq2)
    {
        return 0;
    }
    
    int maxSeqLen = seq1Len;
    if(seq2Len < maxSeqLen)
    {
        maxSeqLen = seq2Len;
    }
    
    // search all window lengths
    for(int i = maxSeqLen; i > 0; i--)
    {
        hash_multimap h;
    
        // search all window locations in seq1
        for(int j = 0; (j + i) <= seq1Len; j++)
        {
            // add all letters to this set
            for(int k = j; (k + i) <= seq1Len; k++)
            {
                // fill a hash table with i letters
                h.insert(*(seq1+k));
            }
            
            // search all window locations in seq2
            for(int m = 0; (m + i) <= seq2Len; m++)
            {
                hash_multimap hCopy = h;
                
                // add all letters to this set
                for(int k = m; (k + i) <= seq2Len; k++)
                {
                    // fill a hash table with i letters
                    if(hCopy.find(*(seq1+k)))
                    {
                        hCopy.remove(*(seq1+k));
                    }
                    else
                    {
                        break;
                    }
                }
                
                if(hCopy.size() == 0)
                {
                    return i;
                }
            }
        }
    }
    
    return 0;
}

1) Convert substrings to sums
2) Compare sums
3) Sort subString
4) Compare subStrings

import java.util.Arrays;

class Solution {
	
	public void solution(String A, String B) {
		int sumA,sumB;
		String subA,subB;
		int largestSub = 0;
		int largestI = 0,largestJ = 0,largestI2 = 0;
		for(int i = 0; i < A.length(); i++){
			for(int j = i+1; j < A.length(); j++){
				subA = A.substring(i,j);
				sumA = sumSubString(subA);
				for(int i2 = 0; i2+(j-i) < B.length(); i2++){
					subB = B.substring(i2,i2+(j-i));
					sumB = sumSubString(subB);
					if (sumA == sumB) {

						char[] charsA = subA.toCharArray();
						Arrays.sort(charsA);
						String sortedA = new String(charsA);

						char[] charsB = subB.toCharArray();
						Arrays.sort(charsB);
						String sortedB = new String(charsB);

						if (sortedA.equals(sortedB)) {
							if(largestSub<subB.length()) {
								largestSub = subB.length();
								largestI = i;
								largestJ = j;
								largestI2 = i2;
							}
							System.out.print("subA=" + subA + " subB=" + subB);
							System.out.print(" sumA=" + sumA + " sumB=" + sumB);
							System.out.println(" sortedA=" + sortedA
									+ " sortedB=" + sortedB);
						}
					}
				}
			}
		}
		System.out.println("\n Result: A="+A+" B="+B);
		System.out.println(" Result: subA="+A.substring(largestI,largestJ)+" subB="+B.substring(largestI2,largestI2+(largestJ-largestI)));
	}
	
	private int sumSubString(String str){
		int result = 0;
		for(int i = 0; i < str.length(); i++){
			result+=(int)str.charAt(i);
		}
		return result;
	}

	public static void main(String[] args) {
		String A = "ABCDEFG";
		String B = "DBCAPFG";
		solution(A,B);
	}
}

#!/usr/bin/python

count_cache = {}

def has_match(s1, s1o, s2, s2o, length):
  if not s1[s1o:s1o+length] in count_cache:
    counts = [0] * 256
    for i in range(s1o, s1o+length):
      counts[ord(s1[i])] += 1
      count_cache[s1[s1o:s1o+length]] = counts

  counts = count_cache[s1[s1o:s1o+length]][:]

  for i in range(s2o, s2o+length):
    counts[ord(s2[i])] -= 1
    if counts[ord(s2[i])] < 0:
      return False
  return True

def longest_match(s1, s2):
  if len(s1) > len(s2):
    tmp = s1
    s1 = s2
    s2 = tmp
  for length in range(len(s1), 0, -1):
    for s1o in range(0, len(s1)-length+1):
      for s2o in range(0, len(s2)-length+1):
        if has_match(s1, s1o, s2, s2o, length):
          return length
  return 0

private static int maxWindow(String source, String target) {
		if(source==null || target==null) return -1;
		HashMap<Character, Integer> smap = new HashMap<Character, Integer>();
		for(int i=0; i<source.length(); i++){
			smap.put(source.charAt(i), i+1);
		}
		
		int[] t = new int[target.length()+2];
		ArrayList<Integer> notPresentCount = new ArrayList<Integer>();
		t[0]=-1; 
		notPresentCount.add(0);
		for(int i=1 ;i<target.length()+1; i++){
			if(smap.containsKey(target.charAt(i-1))){
				t[i] = smap.get(target.charAt(i-1));
			}
			else {
				t[i]=-1;
				notPresentCount.add(i);
			}
		}
		t[target.length()+1]=-1;
		notPresentCount.add(target.length()+1);
		
		int maxWindow = 0;
		for(int j=0; j<notPresentCount.size()-1; j++){
			int temp = getMaxWindow(t,notPresentCount.get(j), notPresentCount.get(j+1));
			if(temp > maxWindow){
				maxWindow = temp; 
			}
		}
		
		return maxWindow;
	}

	private static int getMaxWindow(int[] t, int start, int end) {
		//start with index start. end with index end-1
		Arrays.sort(t, start, end);
		int max=1, localmax=1;
		for(int i=start+1; i<end; i++){
			if(t[i] == t[i-1]+1) localmax++;
			else localmax=1;
			if(localmax > max) max=localmax;
		}
		
		return max;
	}

A solution in Python. It's not the fastest solution, but it's pretty straighforward to code

def maxmatching(seq1, seq2):
    window = ""
    maxwindowsize = 0
    for i in range(len(seq1)):
        # keep increasing window
        for j in range(i, len(seq2)):
            windowsize = j - i
             # move window through seq2 to see if there is match
            for k in range(len(seq2)-windowsize):
                if sorted(seq1[i:j]) == sorted(seq2[k:k+windowsize]):
                    if windowsize > maxwindowsize:
                        maxwindowsize = windowsize
                        window = seq1[i:j]
    return window

One Idea can be to find the character in seq2 which is not present in seq1. It means this is the place before which we have finished one range and after which we’ll start another range. Let’s rephrase the logic.
Find the first character in seq2 which is not present in seq1.
Now get seq2 string before this non-matching character (and previous non-matching, if present).
The number of characters in this cut string are the matching window. Do this till the end and return the maximum matching window value.

Complexity: For each character in seq2, we are matching if it is present in seq1 or not. So n characters of seq2 will be machted with m characters of seq1 making complexity as O(n*m).

Issues: How to deal duplicate characters in seq2? Depends over the interviewer's view otherwise a simple check for duplicate will do the job.

package MaxWindow;

public class MaxWindow {
	int maxWindow(String seq1, String seq2) {

		int count = 0;
		if (seq1 == null || seq1.isEmpty() || seq2 == null || seq2.isEmpty())
			return count;
		else {
			for (int i = 1; i <= seq1.length(); i++) {
				for (int j = 0; j < seq1.length() && j + i <= seq1.length(); j++) {
					String temp1 = seq1.substring(j, j + i);
					
					for (int k = 1; k <= seq2.length() && k <= i; k++) {
						for (int l = 0; l < seq2.length()
								&& k + l <= seq2.length(); l++) {
							String temp2 = seq2.substring(l, l + k);
							boolean flag = permute(temp1, temp2);
							if (flag) {
								count = k - l;
							}
						}
					}
				}
			}
		}

		return count;
	}

	boolean permute(String seq1, String seq2) {
		if (seq1.length() != seq2.length())
			return false;
		int[] count = new int[256];
		char[] seqChar = seq1.toCharArray();
		for (char s : seqChar) {
			count[s]++;
		}
		for (int i = 0; i < seq2.length(); i++) {
			int c = (int) seq2.charAt(i);
			if (--count[c] < 0)
				return false;
		}
		return true;
	}

	public static void main(String[] args) {
		String seq1 = "abcdefgh";
		String seq2 = "hfg";
		MaxWindow maxWindow = new MaxWindow();
		System.out.println(maxWindow.maxWindow(seq1, seq2));
	}
}

My solution. We first need to generate all the possible windows of each string, and after SORTING, we will store it in a hashMap for each string.
Once we have all the possible windows, we need to check if any window from string1 is present on the hash of the second, and we return the biggest.

string getMaxWindow(string s1, string s2){
    HashMap <string, bool> firstHash = new HashMap <string, bool>;
    HashMap <string, bool> secondHash = new HashMap <string, bool>;
    
    string firstWord, secondWord;
    
    for(int i = 0; i < string.size(); i++) {
        for(int j = 0; j < string.size(); j++) {
            firstWord = s1.substring(i,j+1).sort();
            secondWord = s1.substring(i,j+1).sort();
            
            firstHash.insert(firstWord, true);
            secondHash.insert(secondWord, true);
        }
    }
    
    List<string> firstHashKeys = firstHash.keys(); // keys returns all the keys in unsorted order, we dont care
    int maxSize = 0;
    string result = "";
    for(int i = 0; i < firstHashKeys.size(); i++){
        if(secondHash.containsKey(firstHash[firstHashKeys[i]])){
            if(maxSize < firstHash[firstHashKeys[i]].size()){
                result = firstHash[firstHashKeys[i]];
            }
        }
    }
}

1.Sort strings in alphabetical order first.
2.Use two pointers and compare each alphabet one by one and if match is found place it in a array.

Here is a simple code with Recursion

#include<stdio.h>
#include<conio.h>
#include<string.h>
void generate_alphabets(char *num,char *str,int start,int depth)
{
   if(start>=strlen(num))
   {
       printf("\n %s",str);
       return;
   }


       str[depth]=(num[start]-'0'-1+97);
       generate_alphabets(num,str,start+1,depth+1);
       if(num[start+1])
       {
         int result=(num[start]-'0')*10+(num[start+1]-'0')-1;
         if(result<=25)
         str[depth]=result+97;
         str[depth+1]='\0';

         generate_alphabets(num,str,start+2,depth+1);

       }

}
int main()
{
    char str[50]={'\0'};
    char num[10]="1123";
    generate_alphabets(num,str,0,0);
}

String str1= ABCDEFGHIJKLMNOPQR
String str2= DBCAXGFHTRQPONMKL

All the position which are not matching character of str2

X=4
T=8

max index of String =17

17-8=9(RQPONMKL)-1 = 8 (Window Size)
8-4=4 (GFH) -1 =3(Window Size)
4-0=4 (DBCA)=4(Window Size)

max(8,3,4) = 8 Answer

Please validate above solution.

Thanks

I thinkk the best solution is ordered windows. Here is the python code

def findMaxWindow(s1, s2):
	s1 = sorted(s1)
	s2 = sorted(s2)
	count = 0
	for i, s in enumerate(s1):
		if s == s2[i]:
			count += 1
	return count

seq1 = ABCDEFGH
seq2 = DACBPHQRFGH

sort seq2, and maintain pointers to original positions
A->2 B->4 C->3 D->1 F->9 G->10 H->6,11 P->5 Q->7 R->8

scan seq1, and for each match, store the index values at appropriate positions

index- > 4 1 3 2 0 8 0 0 6 7 8

sort subarrays between 0's

1 2 3 4 0 8 0 0 6 7 8

longest sequence willl give the answer ...

Since both the sequences are of equal length,

a. Start with the complete sequence, sort and check for equlity
b. if not equal, sort and check the sub-sequence of 0 to n-1 and check for equality

As soon as two patterns match, then that is the longest sequence matching.

String str1= ABCDDFGHHJKLMNOPQR

Above solution also work if we have repetative character in the string.
str1.contans("KLMNOPQR")--> true