Flipkart Interview Question
SDE-2sCountry: India
Interview Type: In-Person
Here is small visualisation of above problem: For "coobdafceeaxab" and "abc"
step-0:
Initial doubly linked-list = NULL
Initial hash-table = NULL
step-1:
Head<->[c,0]<->tail
hashTable[c] = [0, 'pointer to c node in LL']
step-2:
Head<->[c,0]<->[b,3]<->tail
hashTable[c] = [0, 'pointer to c node in LL'], h[b] = [3, 'pointer to b node in LL'],
Step-3:
Head<->[c,0]<->[b,3]<->[a,5]<->tail
hashTable[c] = [0, 'pointer to c node in LL'], h[b] = [3, 'pointer to b node in LL'], h[a] = [5, 'pointer to a node in LL']
Minimum Window => difference from tail and head => (5-0)+1 => Length: 6
Step-4:
Update entry of C to index 7 here. (Remove 'c' node from linked-list and append at the tail)
Head<->[b,3]<->[a,5]<->[c,7]<->tail
hashTable[c] = [7, 'new pointer to c node in LL'], h[b] = [3, 'pointer to b node in LL'], h[a] = [5, 'pointer to a node in LL'],
Minimum Window => difference from tail and head => (7-3)+1 => Length: 5
Amazing ... how did you calculate it .. ? ...this algo required two for loops.. one to pre process hashMap and it will be done in O(str2.length)
In second we required only O(str1.length)..
How is it ..(n2)(logn) or n2 .. ?
The remove operation from LinkedList is O(n). As it's in the loop then the complexity is O(|string1| * |string2|). But as he suggests to use the doubly linked list we can keep in the hash table directly the nodes of it. So then the remove would be O(1) what gives linear complexity.
Hi Ajeet,
I am not sure if I have missed some concept in your algo. But I think the piece of code :
if((window[1] - window[0]) > (orderedList.getLast().index - orderedList.getFirst().index)){
window[0] = orderedList.getFirst().index;
window[1] = orderedList.getLast().index;
}
should also be placed outside the second for loop, just to ensure that we are not missing the case where map and LL is updated during the last iteration. For an example:
S = "ADOBECODEBANC"
T = "ABC"
The minimum window if I have understood correctly should be "BANC" (last four character in S), which will be obtained if we check ((window[1] - window[0]) > (orderedList.getLast().index - orderedList.getFirst().index)) one last time after the foor loop. Correct me if I am wrong. Thanks.
Do a breadth wise traversal. Break stri1 into 2 parts removing the first and last character. Check for all the char of str2 in both the parts if all the chars present in both the parts. Then continue to divide them into respective parts. Else ignore the part which does not have all the characters. The part u obtain at the depest level will have the minimum window.
For example: str1 : KAMALESH str2: ASH
Break str1 into : KAMALES & AMALESH
Now if use the first part doesn not have H char so ignore that part and break the second part further. into AMALES & MALESH. Continue this to the depeest level where all the char of str2 are present.
This is hard to explain in words. Let me explain with an example:
str1= cPagQRjhfPQaRhgPanRbRc
str2= PQR
1. Create a frequency map of str2 i.e.
P => 1, Q=> 1, R=>1
2. Find the first window from the left in str1 that has all the chars from str2. This could be done in a single scan of str1. Found window is enclosed between square brackets below.
[cPagQR]jhfPQaRhgPanRbRc (window_size =6)
3. Now compress this window from left if possible by advancing the left pointer one step ahead when the character on the left isn't found in str2. So I get:
c[PagQR]jhfPQaRhgPanRbRc (window_size =5)
4. Now advance the right pointer of the window to the right until I find the left char (which is P). so I get
c[PagQRjhf]PQaRhgPanRbRc (window_size =8) (some steps skipped)
5. Advance the left pointer of the window when right character is same as left pointer character.
cP[agQRjhfP]QaRhgPanRbRc (window_size =8)
6. Using rule from step 3, I get
cPag[QRjhfP]QaRhgPanRbRc (window_size =6)
cPagQ[RjhfPQ]aRhgPanRbRc (window_size =6) (rule 5)
cPagQ[RjhfPQa]RhgPanRbRc (window_size =7) (rule 4)
cPagQR[jhfPQaR]hgPanRbRc (window_size =7) (rule 5)
cPagQRjhf[PQaR]hgPanRbRc (window_size =4) (rule 3)
cPagQRjhf[PQaRhg]PanRbRc (window_size =6) (rule 4)
cPagQRjhfP[QaRhgP]anRbRc (window_size =6) (rule 5)
(some steps skipped)
7. Return the minimum window size(which is 4 here) and its starting and ending pointer.
cPagQRjhf[PQaR]hgPanRbRc (window_size =4) (rule 3)
Worst case time complexity is O(|str1|+|str2|).
public class exp1 {
public static void main(String[] args) {
String str1 = "adfdfdbcdeffg";
String str2 = "fdbdeffg";
char[] c2 = str2.toCharArray();
int lastIndex = -1;
int minIndex = -1;
boolean found = true;
for(int i=0;i<c2.length;i++) {
if(str1.indexOf(c2[i], lastIndex+1) >= lastIndex) {
if(minIndex == -1)
minIndex = str1.indexOf(c2[i], lastIndex+1);
lastIndex = str1.indexOf(c2[i], lastIndex+1);
} else {
found = false;
}
}
if(found)
System.out.println(str1.substring(minIndex, lastIndex+1));
else
System.out.println("Not found !");
}
}
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<vector>
#include<string>
#include<list>
using namespace std;
int main()
{
string S, T;
cin >> S >> T;
unordered_map<char, int> map;
for (size_t i = 0; i < T.length(); i++)
map.insert(make_pair(T[i], -1));
//list<pair<char, int*>> List;
int count = 0;
int min=std::numeric_limits<int>::max();
int low, high;
for (size_t i = 0; i < S.length(); i++)
{
if (map.find(S[i])!=map.end() && map[S[i]]==-1)
{
if (count==1)
{
low = i;
}
map[S[i]] = i;
count++;
if (count==T.length())
{
high = i;
min = high - low + 1;
continue;
}
}
if (count == T.length() && map.find(S[i])!=map.end())
{
high = i;
map[S[i]] = i;
low = numeric_limits<int>::max();
for (auto i = map.begin(); i != map.end(); i++)
{
if (i->second<low)
{
low = i->second;
}
}
int temp = high - low + 1;
if (min > temp)
min = temp;
}
}
return 0;
}
How about this.
Take an int array of size 26: where arr[0]=> 'a' and arr[25]=>'z'. initialize it with -INT_MAX.
1. p= &str2[0];
2. repeat step 3 till *p= '\0';
3. if(arr[*p]= -INT_MAX)
arr[*p]= 0;
else
arr[*p]++;
After above, we wud have array initialized with occurrence of each characters in str2. We would use this arry for matching with str1.
Now traverse str1 from left to right with two pointers p1 and p2.
1. P1= str1[0], P2=str1[0].
2. while(1)
if (arr[*P1] != -INT_MAX), arr[*P1]--; break; //We reached first matching char
else P1++;
3. P2= p1+1; // Make P2 points to next char in str1;
4. Repeat steps 5-7 till p1 and p2 both reach end of str1.
5. If All element in arr are '0' or '-INT_MAX', we found a window.
store index of p1 and p2 for MIN(earlier window, found window).
goto step 6.
else
arr[*P2]--;
P2++;
go to step 5;
6. while(1)
if (arr[*P1] != -INT_MAX),
arr[*P1]--;
break; //We reached a matching char
else
arr[P1*]++;
P1++;
7. Goto step 5.
8. Return minimum window.
- Ajeet November 09, 2013