Microsoft Interview Question for Software Engineer in Tests

• 11

Country: United States
Interview Type: Phone Interview

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

The problem is same as finding the smallest window containing all the characters of a given string (here its 'ab'). If such a window is there return 'true'. Provide any alternate soln if there.

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

Yep. Create a set of letters from the smaller string (e.g. 'ab'). Advance character by character through the larger string, checking to see if current character is in the set. If it is, remove it from the set. If the set's empty, you're done. If not, keep advancing. If you find a character that's not in the set, advance to the next index, and repopulate the set from the smaller string.

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

showell30, I don't know if set would be the correct data structure. What if there were duplicate characters?

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

@Frank. If characters can repeat, you can maintain the difference in counts (between the window and the target string) and this idea would essentially work. Once a character count becomes zero, that means the window has the exact number required for that character (as we are maintaining difference). You can move it to a different set.

To check if a window matches, just check the length of the different set.

This is O(n) time (n is the length of the larger string).

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

@Loler: You mean to maintain the difference in count in a HashMap?

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

@Loler and @showell
will this solution work if we are looking to find 'abc' within 'abac'

With this solution, when I hit the 2nd 'a' within 'abac' I would re-populate my set and advance to 'c'; which essentially tells me that the permutation of 'abc' is not present. Am I missing something obvious??

Comment hidden because of low score. Click to expand.
11
of 19 vote

Given an input string A and the template string B, first use quicksort to sort B into B', and first |B| elements in A denoted as C; dynamically move C along A, each time the 1st element in C is removed and the next char is appended into C, just like insertion sort to sort C into C' and match C' == B'

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

A reasonable solution.

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

Most practical solution.

This will take nlog(n) time. Don't know if it's even possible to do it faster.

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

@Frank, it is possible. See my comment to the other upvoted answer.

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

Good solution @zhou0620. Thanks

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

Are we assuming that Input string A is always sorted? If not, this algorithm will not work.

Comment hidden because of low score. Click to expand.
2

It's Not O(n log n). It's O(n*m) because the window moves n steps, at EACH step we insert+compare (log m + m) >>> that is n*(log m+ m) = O(n*m)

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

lets say S1 is the main string and S2 is the substring why cant we do like this

S1= cdabfgd, S2=bac put s2 in character hash like hash[b]=1,hash[a]=1,hash[c]=1 and the length of s2 is 3 now iterate through s1 and check if the character exists in hash and decrement the corresponding hash value i.e when b is found in s1 make hash[b]-- lets maintain a global variable which increases it self when every time you decrease count in hash so when the global variable count becomes equal to length of s2 it means that the permutation of characters exist in s1.

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

I have an O(n) solution, please check the answer of mine below. I am using kmp search, more faster than you said.

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

Hi,
This will work only if the given long string is sorted. But for overall solution, we can generate a permutation of a smaller string. And then for each permutation, we can use KMP search or any search algo, to search this permuted string in the bigger string.

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

Here is my thought: For the permutation of string, its simplified represents is the number of each character existed in the string. If you want to check if A's permutation is sub string of the B string, you only need to be sure that the number of each kind of character in A is less the number of the same character in the string B. So you can build a histogram of characters in A by going through A, then going through B, decrease the count of character histogram of A when it find the one in B. Return true when all histogram reach zero during the going through B, otherwise return false.

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

here is the code

``````#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int compare(const void *a,const void * b)
{
return (*(char*)a-*(char*)b);
}
int main()
{
char str[]="aabcdefgh";
char b[]="ba";
char c[10];
qsort(b,strlen(b),sizeof(char),compare);
int p=strlen(str);
int l=strlen(b);
int k,m;
for(int i=0;i<=p-l;i++)
{
m=0;
for(int j=i;j<i+l;j++)
{c[m++]=str[j];

}
qsort(c,l,sizeof(char),compare);
cout<<endl;
for(k=0;k<l;k++)
{   if(c[k]!=b[k]) break;  }
if(k==l)
cout<<"string is found at location i=  "<<i;
}
return 0;
}``````

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

- take each character in smaller string and add its position in larger string into sorted array
- if all chars are there in larger string, check if all the position is in sequence

Eg
String a = abcdefghij
String = dcfe

Sorted positions will be 3 4 5 6 so will return true

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

what if you have some chars occuring multiple times ?
example: string_1 = abcdeeffghijc
string_2 = dcfe

Also notice that by sorting the string, you disrupt the original order of chars in the string such that you have no way of telling for example if you are looking
for "cat" in "tsakc" or "cat" in "ckast"

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

Yes, this will work well only If string does not have repeating chars. Thanks for pointing it out

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

but "dcfe" is not in "abcdeeffghijc" right? "dcfee" is in. Isnt it?

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

I am assuming it should return false for above case since lookalike question is a specific permutation of smaller string must be sub string of larger string

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

true but you are missing my point.
i think your algorithm would return false for "abcabcabc" and "cab" when it should return true;

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

I agree orig algorithm need tweak but this example would work well..
Position of cab would be 3 1 2 and sorting it would put it in sequence so would return true..

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

yaker no that question is different

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

public static bool isubstring(string S1, string S2)
{
int sumS1 = 0;
int sumS2 = 0;

for (int i = 0; i < S2.Length; i++)
{
sumS2 += (int)S2[i];
}
for (int i = 0; i < S1.Length - S2.Length + 1; i++)
{
int index = i;
sumS1 = 0;
for (int j = 0; j < S2.Length; j++)
{
sumS1 += (int)S1[index];
index++;
}
if (sumS1 == sumS2)
return true;
}
return false;

}

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

what's poblem is this solution?

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

what's poblem in this solution?

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

Few things

1) It is not correct. For instance, if adef is the long string and bc is the string sought, then you will say true, while it is clearly false. (Basically a+d = b+c)

Basically, sum being same does not imply you have gotten your string.

2) For long strings there is a good chance of overflows, and messing up your results even more, 1) not withstanding.

3) The runtime of this is O(|A||B|) where the string lengths are |A| and |B|.

(I should have stated, 2 and 3 are no biggies, but being incorrect is).

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

1- if long string = "adef" and "bc" is the string sought code return false not true

2- overflow is difficult to occur beacuse if the length of long string is 1000000000 and the length of sougth string is 1000000 the sum of the string = 122*1000000 in worst case

3- this method when we need to use O(1) space

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

ok , i know my mistake thanks loler

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

for first case we need to check if sougth string contain one char of long string

if (sumS1 == sumS2 && S2.Contains(S1[index].ToString()))
return true;

Comment hidden because of low score. Click to expand.
-1
of 1 vote

but this poblem can solved if we use first 26 prime number as index for chars from a to z

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

get a element from string A, search for that in string B1(Copy of second string B),If we dont find it go to next element in A.
If we find element at position 'i' in B1, replace that element with 0 in B1(we did not modify anything in B).
search for the next element in A in B1 and replace that element with 0 in B1 till we could not find the a .elements of A in B1 or all elements in B1 are 0.
if all elements in B are 0.result is success.

if we could not find a element at position k of A in B1. get refresh B1 i.e copy from B.
now find for that element in B(the original string) if we could not find it in B, Continue to repeate the same steps from position k+1 .
if you find it in B,repeate steps from position i+1

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

To solve this problem.. First find the maximum window in which all the character of given pattern is present. If max window length is equal to pattern length than it is going to be the permutation of given string other wise not.Code is given below let me know if it fails in any scenario it is working for me for test cases i think of.

int FindpatLen(char *str,char *pat)
{
if(!*str)
return 0;
int len1=strlen(str),len2=strlen(pat),count=0;
int hasfound[26]={0},needtofound[26]={0};
int i=0,begin=0,max=999;
for(i=0;i<len2;i++)
needtofound[pat[i]-97]++;
i=0;
for(;i<len1;i++)
{
if(needtofound[str[i]-97]==0)
continue;
hasfound[str[i]-97]++;
if(hasfound[str[i]-97]<=needtofound[str[i]-97])
count++;
if(count==len2)
{
while((needtofound[str[begin]-97]==0) || (hasfound[str[begin]-97]>needtofound[str[begin]-97]))
{
if(hasfound[str[begin]-97]>needtofound[str[begin]-97])
hasfound[str[begin]-97]--;
begin++;
}
if(max>(i-begin))
max=i-begin+1;
}
}
return max;
}
bool Ispermutation(char *str,char *pat)
{
int len=strlen(pat);
if(len==FindpatLen(str,pat))
return true;
return false;
}
int main()
{
char str[]="abcabcabc";
char pat[]="cab";
bool res=Ispermutation(str,pat);
getchar();
return 0;
}

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

1.Create a temporary bitMap of <character,Bit> initialize them with character and bit value 0
2. Scan through the big array when you find a character in the small array update the bit map with the char and set it to 1 if the character bit has 0.

public static boolean checkPresence(char[] arr, char[] temp) {

int track = 0;
Map<Character, Integer> tempMap = new HashMap<Character, Integer>();
for (char c : temp) {
tempMap.put(c, 0);
}
int prev = 0;
for (int i = 0; i < arr.length; i++) {
char c = arr[i];
if (tempMap.get(c) != null && tempMap.get(c) == 0
&& (prev == 0 || prev == i - 1)) {
tempMap.put(c, 1);
track++;
prev = i;
}
}
return track == temp.length ? true : false;
}

Let me know if i miss any case

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

If long string has length n and the short has length m
Best complexity I reached:
-Assuming no repeated characters in either string >> O(n)
-Allow repeated characters in the long string >> O(n) too
-Allow repeated characters in either string >> O(n*log m)

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

Firstly, Sort the string and substring separately。Time complexity is O(sqrt(n))
Secondly, use match algorithm on the ordered string。Time complexity is O(n)
so the total complexity is O(n).

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

``````package com.santosh.career;

import java.util.HashMap;
import java.util.Map;

public class Career15555796 {

/**
* @param args
*/
public static void main(String[] args) {
char[] small = { 'c', 'b' };
char[] big = { 'g', 'b', 'a', 'c', 'd', 'e' };
Map<Character, Integer> charMap = new HashMap<Character, Integer>(26);
Map<Character, Integer> fixedCharMap = new HashMap<Character, Integer>(
26);
resetCharMap(small, charMap);
resetCharMap(small, fixedCharMap);
int smallCount = small.length;
int flag = 0;
for (char c : big) {
if (charMap.get(c) != null) {
charMap.put(c, charMap.get(c) - 1);
flag = 1;
smallCount--;
}
if(smallCount==0){
System.out.println("Found a match");
break;
}
if (flag == 1 && charMap.get(c) == null) {
charMap = fixedCharMap;
flag = 0;
smallCount = small.length;
}
}
}

private static void resetCharMap(char[] small,
Map<Character, Integer> charMap) {
for (char c : small) {
if (charMap.get(c) == null) {
charMap.put(c, 1);
} else {
charMap.put(c, charMap.get(c));
}
}
}
}``````

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

The algorithm above should work but when you are copying fixedCharMap to charMap you are doing M copy operation. That makes the worst time complexity O(N*M). It is possible to do in O(N) if you use sliding window instead.

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

The Algorithm i posted above its O(n) and i am using two constant size arrays.
I handled all cases i suppose let me know if it fails in any case

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

``````package questions;

import java.util.Arrays;

public class HasPerm {
public static void main(String[] args) {
System.out.println(hasPerm("abcdefg", "ba"));
System.out.println(hasPerm("abcdefg", "gf"));
System.out.println(hasPerm("abcdefg", "dc"));
}

public static boolean hasPerm(String source, String find) {
String k = key(find);
for (int i = 0; (i + find.length()) <= source.length(); ++i) {
String sub = source.substring(i, i + find.length());
if (key(sub).equals(k))
return true;
}

return false;
}

private static String key(String s) {
char[] ary = s.toCharArray();
Arrays.sort(ary);
return new String(ary);
}
}``````

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

How about this, you just sort both the strings and then compare the index of the smaller string in the larger string. If it is -1, then the smaller string is not a part of the larger string.

``````import java.util.*;
public class sort {
public static void main(String args[])
{
String str1 = "abcdefgh";
String str2 = "fed";
char a[] = str1.toCharArray();
Arrays.sort(a);
String new_str_1 = new String(a);
System.out.println(new_str_1);
char b[] = str2.toCharArray();
Arrays.sort(b);
String new_str_2 = new String(b);
System.out.println(new_str_2);
if(new_str_1.indexOf(new_str_2) != -1)
{
System.out.println("True");
}
else
{
System.out.println("False");
}
}

}``````

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

sort is not required, i think

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

reverse the second string and use kmp search will be better. and also we can use suffix tree or suffix array, but they are too complicated. here is my program, and it will take O(n) time complexity(n: the length of first string) and O(m) space complexity(m: the length of second string):

``````#include<iostream>
#include<string>
using namespace std;

void swap(char *a, char *b) {
char temp;
temp = *a;
*a = *b;
*b = temp;
}

void reverse(char *p_start, char *p_end) {
while(p_start < p_end) {
swap(p_start, p_end);
p_start++;
p_end--;
}
}

void get_next(char *p, int len, int *next) {
int j = -1;
int i = 0;
next[i] = -1;
while(i < len - 1) {
if(j == -1 || p[i] == p[j]) {
++i;
++j;
if(p[i] != p[j])
next[i] = j;
else
next[i] = next[j];
} else {
j = next[j];
}
}
}

char *kmp_search(char *s, int s_len, char *p, int p_len) {
if(NULL == s || NULL == p || 0 == s_len || 0 == p_len)
return NULL;
int *next = (int*)malloc(sizeof(int) * p_len);
memset(next, 0, sizeof(int) * p_len);
get_next(p, p_len, next);
int i = 0;
int j = 0;
while(i < s_len && j < p_len) {
if(j == -1 || s[i] == p[j]) {
++i;
++j;
} else {
j = next[j];
}
}
if(next)
free(next);
if(j >= p_len)
return s + i - p_len;
else
return NULL;
}

int is_contain_permutation(char *s, char *d) {
if(NULL == s || NULL == d)
return 0;
int s_len = strlen(s);
int d_len = strlen(d);
char *temp = (char*)malloc(d_len + 1);
strcpy(temp, d);
reverse(temp, temp + d_len - 1);
char *ret = kmp_search(s, s_len, temp, d_len);
if(temp)
free(temp);
if(ret)
return 1;
else
return 0;
}

int main(int argc, char *argv[]) {
char s[] = "abcdefg";
char d[] = "ba";
is_contain_permutation(s, d);
cin.get();
return 0;
}``````

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

int[] count = new int[256];
for(char c: str1.toCharArray())
++count[c];
for(char c: str2.toCharArray())
{
if(count[c]==0)
return false;
}
return true;

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

I think of hashing all the characters into the hashtable and maintain the count. Then, for every character in S2, check if it exists in the hashtable. if so, then result is true. it takes o(n) where n is the size of the longest string.

This idea is not based on the order and it depends whether there exists every character of a string exists in the original string. When it exists, the permutation is possible (obviously)

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

will this idea work pls correct me if I am wrong:)
1.create two hash tables one for string 1 and another for string 2
2.if the hash values of string 2 if it is contained within string 1 then string is accepted....

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

p1 = &Array1;
strcpy(Array3, Array2);
while (*p1 != '\0')
{
for (i = (p1 - Array1); i < ((p1-Array1) + strlen(Array2)); i++)
{
for (j = 0; j < strlen(Array2); j++)
{
if (Array1[i] == Array2[j])
{
Array2[j] = 'x';
count++;
break;
}
}
}
if(count == strlen(Array2))
{
success = 1;
break;
}
else
{
p1++;
strcpy(Array2, Array3);
count = 0;
}
}

if (success == 1)
{
printf("Success");
}
else
{
printf("Failure");
}

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

``````Check if a substring permutation exists in a string

Check if a substring permutation exists in a string. Ex. A = “most random” B = “mod”

So the function should return true since “mod” a permutation of “dom” exists in string A

—————————————————————————————————————–

// Have this as class field to expose to multiple methods
private Hashtable mTable;public bool SubStringExistsAsPermutation(string A, string B)

{
if (String.IsNullOrEmpty(A))
{
throw new ArgumentException(“A cannot be null”);
}
if (String.IsNullOrEmpty(B))
{
throw new ArgumentException(“B cannot be null”);
}

mTable = new Hashtable();

// Fill hashtable with B string
foreach (char ch in B)
{
mTable[ch] = Convert.ToInt32(mTable[ch]) + 1;
}

// Read each character from String A. Keep comparing it with hashtable characters
// If character in A is not found in hashtable, keep moving A pointer
// If character in A is found in hashtable, Set a flag LookForConsecutiveCharacter = true
// If you find LookForConsecutiveCharacter = true, and next character is not found Then –
// Set LookForConsecutiveCharacter = false and reset hashmap to its initial state to look for next pattern ahead

bool LookForConsecutiveCharacter = false;
int count = 0;

foreach(char ch in A)
{

if (count == B.Length)

{
break;
}

if (Convert.ToInt32(mTable[ch]) >= 1)
{
mTable[ch] = Convert.ToInt32(mTable[ch]) – 1;
LookForConsecutiveCharacter = true;
count++;
}
else
{
// If we expected consecutive characters for permutation and its not found, reset hashtable
if (LookForConsecutiveCharacter)
{
ResetHashTableToDefault(B);
LookForConsecutiveCharacter = false;
count = 0;
}
}
}

// Verify if we found permutation
bool permutationFound = true;
foreach (char key in mTable.Keys)
{
if (Convert.ToInt32(mTable[key]) != 0)
{
permutationFound = true;
break;
}
}
return permutationFound;
}

private void ResetHashTableToDefault(string B)
{
mTable.Clear();
foreach (char key in B)
{
mTable[key] = Convert.ToInt32(mTable[key]) + 1;
}
}``````

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

``````bool find_permutation(const string& str, const string& other)
{
string sorted;
sort(other, sorted); //O(nlogn)

for(int i = 0; i < str.length(); ++i)
{
if(i + sorted.length() < str.length())
{
string subs = str.substr(i, sorted.length());
string sortedSub;
sort(subs, sortedSub); //O(klogk)
if(sortedSub == sorted) return true;
}
}

return false;
}``````

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

We can do this in O(n). The algorithm is simple, we move a window of |p| from left to right, and keep a counter of characters passed. We also update a counter d whenever a match
between the moving counter and histogram of p happens or otherwise.

``````def persub(s, p):
pc = Counter(p)
cc = Counter()
d = 0
for i, c in enumerate(s):
_cc = cc.get(c, 0)
if c in pc and _cc == pc[c]:
d -= 1
cc[c] = _cc + 1
if cc[c] == pc[c]:
d += 1

if i >= len(p):
_c = s[i - len(p)]
_cc = cc.get(_c, 0)
if _c in pc and _cc == pc[_c]:
d -= 1
cc[_c] = _cc - 1
if cc[_c] == pc[_c]:
d += 1

if d == len(pc):
yield i - len(p) + 1``````

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

Guys we need to find a substring of string 1 which consists of only characters of string2 and has same length as string 2, once while iterating you find such a substring then compare the count of each character in the substring and string 2 , if string 2 has all unique characters this
problem becomes simply finding the longest substring in string 1 that consists of all unique characters , characters here being those of string 2 , then if the length of this longest substring equals length of string 2 , then this is the code

i m posting the c code

``````#include<stdio.h>
#include<iostream>
using namespace std;

void printallpermutations(char* a , char* b)
{
int i;

bool aux[26]={0};
int visited[26]={-1};
int current_substring_begin=0;
int max_substring_len=0;
int max_substring_begin=0;
for(int i=0;b[i]!='\0';++i)aux[b[i]]=1;

while(a[current_substring_begin]!='\0')
{

while(b[a[i]]==0)i++;

count=0;
//first char encountered

current_substring_begin=i;
while(b[a[i]])
{
if(visited[a[i]]==-1){
visited[a[i]]=i;
count++;
}

else{
//it occurs but has previous occurence , if previous occurence is after current begin, then its a duplicate within current substring
//and the current unique substring ends one char before this char and the new begins after the previous visited val

if(visited[a[i]]>=current_substring_begin)
{
//substring ends
if(count>max_substring_len){
max_substring_len=count;
max_substring_begin=current_substring_begin;
current_substring_begin=visited[a[i]]+1;//start from next char since last visit
}

}
}
}

}

if(max_substring_len==strlen(b)){
cout<<"contains";
for(int p=max_substring_begin;p<max_substring_begin+max_substring_len;++p)cout<<a[p];

}

else cout<<"doesnot contains";
return;
}

int  main()
{
char a[] = "abcdnmpbacdmnpccc";
char b[] = "pmn";

printallpermutations(a,b);

return 0;
}``````

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

Please check out this generic solution, that will work on all cases, even if the text is not sorted.
we create all possible permutations of a pattern and then simply compare.

``````class P13
{
static String text;
static boolean result = false;
public static void main(String[] args)
{
String patt = "fcd";
permutations(patt);
System.out.println(result);
}

public static void permutations(String patt)
{
permutations("",patt);
}

public static void permutations(String prefix, String patt)
{
int l = patt.length();
if(l == 0)
{
//System.out.println(prefix);
if(search(text, prefix))
result = true;
}
for(int i=0;i<l;i++)
permutations(prefix+patt.charAt(i), patt.substring(0, i)+patt.substring(i+1, l));
}

public static boolean search(String text, String pattern)
{

for(int i=0;i<text.length()-pattern.length();i++)
{
int x = i;
int count = 0;
for(int j=0;j<pattern.length();j++,x++)
{
if(text.charAt(x) == pattern.charAt(j))
count++;
}
if(count == pattern.length())
return true;
}
return false;
}
}``````

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

``````class P13
{
static String text;
static boolean result = false;
public static void main(String[] args)
{
String patt = "fcd";
permutations(patt);
System.out.println(result);
}

public static void permutations(String patt)
{
permutations("",patt);
}

public static void permutations(String prefix, String patt)
{
int l = patt.length();
if(l == 0)
{
//System.out.println(prefix);
if(search(text, prefix))
result = true;
}
for(int i=0;i<l;i++)
permutations(prefix+patt.charAt(i), patt.substring(0, i)+patt.substring(i+1, l));
}

public static boolean search(String text, String pattern)
{

for(int i=0;i<text.length()-pattern.length();i++)
{
int x = i;
int count = 0;
for(int j=0;j<pattern.length();j++,x++)
{
if(text.charAt(x) == pattern.charAt(j))
count++;
}
if(count == pattern.length())
return true;
}
return false;
}``````

}

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

An easy solution assuming alphabets from 'a' to 'z' allowed.
Time O(N)
Space O(1)

``````bool isSubstr(string s, string sub)
{
int l1 = s.length();
int l2 = sub.length();
if(l2 > l1)
return false;
string alpha2 = "00000000000000000000000000";
string alpha1 = "00000000000000000000000000";
for(int i = 0;i < l2;i++)
{
alpha1[sub[i] - 'a']++;
alpha2[s[i]-'a']++;
}
if(alpha2 == alpha1)
return true;
for(int i = 1;i +l2  < l1;i++)
{
printf("here\n");
alpha2[s[i-1]-'a']--;
alpha2[s[i+l2-1]-'a']++;
if(alpha2 == alpha1)
return true;
}
return false;
}``````

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

sorry a minute correction its i + l2 -1 < l1

``````bool isSubstr(string s, string sub)
{
int l1 = s.length();
int l2 = sub.length();
if(l2 > l1)
return false;
string alpha2 = "00000000000000000000000000";
string alpha1 = "00000000000000000000000000";
for(int i = 0;i < l2;i++)
{
alpha1[sub[i] - 'a']++;
alpha2[s[i]-'a']++;
}

if(alpha2 == alpha1)
return true;
for(int i = 1;i +l2 -1 < l1;i++)
{
alpha2[s[i-1]-'a']--;
alpha2[s[i+l2-1]-'a']++;
if(alpha2 == alpha1)
return true;
}
return false;
}``````

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

in python:

``````#!/usr/bin/python
import itertools

s="abcdefg"
s2="ed"
l=list(itertools.permutations(s2))

for i in l :
s3="".join(i)

if s.find(s3)!=-1 :
print("%s occurs in %s" % (s3,s))``````

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

C++ solution is below. Only one inefficiency: you need to repopulate the hash every time you don't have match.

``````int StrLen(char *s)
{
int length = 0;

if (s)
{
while (*s)
{
length++;
s++;
}
}

return length;
}

void InitHash(int *hash, int hashSize, char *s)
{
if (hash && s)
{
for (int i = 0; i < hashSize; hash[i++] = 0);

while (*s)
{
hash[*s] += 1;
s++;
}
}
}

bool FindPermutation(char *str1, char *str2)
{
bool found = false;
int length2 = -1;
int i = -1;
int hash[256];

if (str1 && str2)
{
length2 = StrLen(str2);
InitHash(hash, 256, str2);

while (*str1)
{
for (i = 0; i < length2 && str1[i] != '\0'; i++)
{
if (hash[str1[i]] != 0)
{
hash[str1[i]]--;
}
else
{
break;
}
}

if (i == length2 || str1[i] == '\0')
{
// permutation is found
found = (i == length2);
break;
}
else
{
str1 += (i + 1);
InitHash(hash, 256, str2);
}
}

}

return found;
}``````

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

``````#include <iostream>
#include<algorithm>
#include<string>
using namespace std;

int main()
{
int n;
cin>>n;
cin.ignore();
for(int i=0;i<n;i++)
{
string p,t;
getline(cin,p);
getline(cin,t);
int lp=p.length();
int lt=t.length();
int fp[26]={0},ft[26]={0};
for(int i=0;i<lp;i++)
fp[p[i]-'a']++;
for(int i=0;i<lp;i++)
ft[t[i]-'a']++;
bool m;
for(int i=lp;i<=lt;i++)
{
m=true;
for(int j=0;j<26;j++)
if(fp[j]!=ft[j])
{
m=false;
break;
}
if(m)
break;
ft[t[i-lp]-'a']--;
ft[t[i]-'a']++;
}
if(m)
cout<<"YES\n";
else
cout<<"NO\n";
}
return 0;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

cracking the coding interview has the same question in chapter 1

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

it's not exactly the same. The q in cc is to assume they should be permutation of each other - both sides.

Comment hidden because of low score. Click to expand.
-1
of 3 vote

convert two arrays to numbers

S1 : abcdefg -------> 01234567
S2 : ba -------> 10
int sumS1 = 0;
int sumS2 = 0;

for(int i = 0;i<S.length;i++)
{
sumS2+=S2[i];
}
for(int i = 0;i<S1.length - S2.length + 1; i++)
{
if(S1[i] + S1[i+1] == sumS2)
return true;
}

Comment hidden because of low score. Click to expand.
-1
of 3 vote

Compute all the permutations of the smaller string(easily done recursively). For each permutation, check if it is a substring of bigger string.

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

This is highly inefficient if the smaller string is say, more than 15 characters.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public static void main(String[] args) throws Exception
{
String one = "abcdefg";

String two = "ba";

System.out.println(findifsubperumuation(one, two));

}

//Assumes one is longer than 2
public static boolean findifsubperumuation(String one, String two)
{

int k = two.length();

ArrayList<String> all;
for(int i=0; i<one.length() && i+k<one.length()+1; i++)
{
String current = one.substring(i, i+k);
all=permutation(current);
for(String perm : all)
{
if(perm.equals(two))
{
return true;
}
}

}

return false;
}

public static ArrayList<String> permutation(String s)
{

if(s.length()==1)
{

ArrayList<String> perms = new ArrayList<String>();
return perms;
}

ArrayList<String> permsother = permutation(s.substring(1));

ArrayList<String> perms = new ArrayList<String>();

String firstletter = s.substring(0,1);

for(String current : permsother)
{
for(int i=0; i<=current.length(); i++)
{

String Firstpart = current.substring(0,i);
String Secondpart = current.substring(i);
String together = Firstpart.concat(firstletter);
together=together.concat(Secondpart);

}

}

return perms;

}``````

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

I don't claim it's optimized but it will work,
1) I find all substring's in the first word that are the length of the second word.
2) I generate all the permutations for a substring of the first word
3) check every permutation i generate and compare it to the second word

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

O((n/k)(k)!), it's a horrible solution, but I already had the code for permutation. A better solution would be to look for every substring of size k in the longer string, and check that the number of occurrences of every letter is in this substring is same as the number of every occurrences of every letter in the smaller string.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

HI i think this can be easily solved by Hash maps.
Create a hash map for the second string and keep incrementing for a new instance found for a letter. ex: abdds: a(1),b(1),d(2),s(1).
Then for the second string, keep decrementing if the same letter is found.
if the first string ends and all the letters have the values associtaed to them as zeroes: return TRUE.
The complexity is m+n, 1.e. of O(m)

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
3

If you sort both strings, you will get a false positive for acb and ab.

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.

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.