Flipkart Interview Question for SDE-2s


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.
S = "ADOBECODEBANC"
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.
	}
	
    add new count node in to 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;
		LinkedList<WindowNode> orderedList =  new LinkedList<WindowNode>();
    	int count = text.length();
		int[] window = new int[2];
		window[0] = 0;
		window[1] = 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[1] - window[0]) > (orderedList.getLast().index - orderedList.getFirst().index)){
						window[0] = orderedList.getFirst().index;
						window[1] = orderedList.getLast().index;
					}
					orderedList.remove(map.get(source.charAt(i)));					
				}
				WindowNode node = new WindowNode(source.charAt(i), i);
				orderedList.addLast(node);
				map.put(source.charAt(i), node);								
			}
		}		
		System.out.println("Here is the smallest window: from " + window[0] + " to " + window[1]);
	}

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

- Ajeet November 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ajeet November 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- *regex* November 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ajeet November 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- joe kidd November 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ok yes double LL helping
Thannk

- *regex* November 09, 2013 | Flag
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[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.

- Rakesh Roy November 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yup... thanks

- Ajeet November 12, 2013 | Flag
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.

- Stupid Developer November 09, 2013 | Flag Reply
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|).

- Epic_coder November 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 !");
	}
}

- knoesis December 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi,
Please review your code. Suppose if str1=cPagQRjhfPQaRhgPanRbRc and str2=PQR. It returns PagQR instead of PQaR.

- Jawahar Ganesh December 15, 2013 | Flag
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;
}

- wer December 03, 2013 | Flag Reply
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

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

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.

- Manku July 16, 2015 | 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