## Flipkart Interview Question for SDE-2s

• 6

Country: India
Interview Type: In-Person

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

``````Found window for T in S.
T = "ABC"
Algorithm:
--------------
1. Create a hash table of size "text.length" for all the characters from string T. (I assume all characters are different in Y).  Set value for each character "-1".
2. count = T.length;
window  = Integer.MAX_VALUE;//A larger value
for( 0 to "S.length")
if(S[i] match with T[i]) {
//if hash table is not populated with all values.	or first window is not completed.
if(count > 0)
count--;
update its position(from S) in Hash table.

//If all values of hash table has been populated, or we should say first window was completed.
else
Find min and max values from the hash table: we can use a linked list to find min and max in O(1) time.
current_window  = max - min;
if(window > current_window)
window = current_window;
if current window is smaller than previous one, than replace it.
remove old node for this character from the linked list.
}

update new count node in Hash table.
3. return window;

Note:
We are moving from left to right (0 to N), and removing old values from the list
So it will be sorted. And we its first node will be smallest and last node will be largest.

Here is implementation in java:
public static void find(String source, String text){
int min = -1;
int max = -1;
int count = text.length();
int[] window = new int;
window = 0;
window = Integer.MAX_VALUE;

HashMap<Character, WindowNode> map = new HashMap<Character, WindowNode>();
//Preprocess
for(int i=0; i<text.length(); i++){
map.put(text.charAt(i), new WindowNode(text.charAt(i), -1));
}

for(int i=0; i< source.length(); i++){
if(map.containsKey(source.charAt(i))){
//If first window is not filled
if(count > 0){
count--;
} else {
//If last window is bigger than current window than replace it with current window
if((window - window) > (orderedList.getLast().index - orderedList.getFirst().index)){
window = orderedList.getFirst().index;
window = orderedList.getLast().index;
}
orderedList.remove(map.get(source.charAt(i)));
}
WindowNode node = new WindowNode(source.charAt(i), i);
map.put(source.charAt(i), node);
}
}
System.out.println("Here is the smallest window: from " + window + " to " + window);
}

Time = O(N), where N = size of S
Space  = O(2M), where M = size of T``````

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

``````Here is small visualisation of above problem: For "coobdafceeaxab" and "abc"

step-0:
Initial hash-table = NULL

step-1:
hashTable[c] = [0, 'pointer to c node in LL']

step-2:
hashTable[c] = [0, 'pointer to c node in LL'], h[b] = [3, 'pointer to b node in LL'],

Step-3:
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)
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``````

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

It is (n2)(logn)
We can get n2

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

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

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

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.

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

Ok yes double LL helping
Thannk

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

Hi Ajeet,
I am not sure if I have missed some concept in your algo. But I think the piece of code :

``````if((window - window) > (orderedList.getLast().index - orderedList.getFirst().index)){
window = orderedList.getFirst().index;
window = 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:
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 - window) > (orderedList.getLast().index - orderedList.getFirst().index)) one last time after the foor loop. Correct me if I am wrong. Thanks.

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

Yup... thanks

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

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.

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

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

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

``````public class exp1 {
public static void main(String[] args) {
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
}
}``````

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

Hi,

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

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

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

tech-queries.blogspot.in/2010/12/finding-minimum-window-in-array-which.html

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

Take an int array of size 26: where arr=> 'a' and arr=>'z'. initialize it with -INT_MAX.

``````1. p= &str2;
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, P2=str1.
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.``````

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.