Amazon Interview Question for SDE-2s


Country: United States
Interview Type: Phone Interview




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

struct compare
{
	bool operator() (pair<int, int> operand1, pair<int, int> operand2)const
	{
		return operand1.second < operand2.second;
	}
};
int main()
{
	vector<int> input = { 6,7,1,3,2,4,5,2,3,1,2,5 };
	vector<int> keyNums = { 1,2,5 };
	set<int> keySet(keyNums.begin(), keyNums.end());
	map<int, int> keyCounts;
	for (int i = 0; i < keyNums.size(); i++)
		keyCounts[keyNums[i]] = 0;
	// skip non key elements
	int i = 0;
	while (i < input.size())
	{
		if (keySet.find(input[i]) != keySet.end())
			break;
		i++;
	}
	if (i == input.size())
		return 0;
	int ansStartIndex = i, ansMaxLength = INT_MAX, startIndex = i;
	keyCounts[input[i]]++;
	i++;
	while (i < input.size())
	{
		if (keySet.find(input[i]) != keySet.end())
		{
			keyCounts[input[i]]++;
			// check can we move start index towards right
			if (input[startIndex] == input[i])
			{
				keyCounts[input[i]]--;
				startIndex++;
				while ((keySet.find(input[startIndex]) == keySet.end()) || (keyCounts[input[startIndex]] > 1) )
				{
					if(keySet.find(input[startIndex]) != keySet.end())
						keyCounts[input[startIndex]]--;
					startIndex++;
				}
			}
			// Check is there a optimal solution
			if (((*min_element(keyCounts.begin(), keyCounts.end(), compare())).second > 0) && (i - startIndex + 1 < ansMaxLength))
			{
				ansStartIndex = startIndex;
				ansMaxLength = i - startIndex + 1;
			}
		}
		i++;
	}

	cout << "startIndex = " << ansStartIndex << " , length = " << ansMaxLength << endl;
	getchar();
}

- siva.sai.2020 November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Explain the logic please.

- Emon November 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

So, @ siva.sai.2020, did you get position at Amazon?

- zr.roman November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Identical to:
question?id=6326674964611072

- zr.roman November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create a window using hashing and keeping VisitCount. Slide windows with leftmost character match to obtain all possible positive windows. Capture minimum window at each stage.

- ankushbindlish November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Arrays.
// Mimimum window size in which all elements
// of second array are contained in first.

#include <iostream>
#include <climits>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <map>
#include <cmath>
using namespace std;

// Reset the target map for all '0's for all elements.
void resetTarget( map<int, int>& target, int arr2[], int m )
{
if ( target.size() == 0 )
{
for ( int i = 0; i < m; i++ )
target.insert(make_pair<int, int>(arr2[i], 0));
}
else
{
for ( int i = 0; i < m; i++ )
target[arr2[i]] = 0;
}
}

// Routine to set index map initially by searching
// for each element in target map.
bool searchValue( map<int, int>& target, int data )
{
map<int, int>::iterator iter;
for ( iter = target.begin(); iter != target.end(); ++iter )
if ( iter->first == data )
return true;

return false;
}

// Set the value in target map to '1' to help
// counter to fullfill it's task.
bool setValue( map<int, int>& target, int data )
{
if ( target[data] == 0 )
{
target[data] = 1;
return true;
}
return false;
}

// Routine to calculate the minimum size window in first
// array which contain all elements of second array.
void minimumWindow( int arr1[], int n, int arr2[], int m )
{
map<int, int> target;
map<int, int> index;
int counter = 0;
int min_diff = INT_MAX;
resetTarget( target, arr2, m );

// Insert indexes into the map.
for ( int i = 0; i < n; i++ )
{
if ( searchValue( target, arr1[i] ) )
index.insert(make_pair<int, int>( i, arr1[i] ));
}

while ( index.size() >= m )
{
map<int, int>::iterator iter;
map<int, int>::iterator start = index.begin();
for ( iter = index.begin(); iter != index.end(); ++iter )
{
if ( setValue( target, iter->second ) )
{
counter++;
}
if ( counter == m )
{
if ( min_diff > ((iter->first) - (start->first)) )
min_diff = (iter->first) - (start->first);
resetTarget( target, arr2, m );
index.erase(start);
counter = 0;
break;
}
}
}
cout << "Minimum window size is " << min_diff << endl;
}

// Test program.
int main()
{
int arr1[] = { 6, 7, 1, 3, 2, 4, 5, 2, 3, 1, 2, 5 };
int n = sizeof(arr1)/sizeof(arr1[0]);
int arr2[] = { 2, 5, 1 };
int m = sizeof(arr2)/sizeof(arr2[0]);

minimumWindow( arr1, n, arr2, m );

system("pause");
return 0;
}

- Anonymous November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ #include <iostream> #include <climits> #include <vector> #include <queue> #include <stack> #include <string> #include <map> #include <cmath> using namespace std; void resetTarget( map<int, int>& target, int arr2[], int m ) { if ( target.size() == 0 ) { for ( int i = 0; i < m; i++ ) target.insert(make_pair<int, int>(arr2[i], 0)); } else { for ( int i = 0; i < m; i++ ) target[arr2[i]] = 0; } } bool searchValue( map<int, int>& target, int data ) { map<int, int>::iterator iter; for ( iter = target.begin(); iter != target.end(); ++iter ) if ( iter->first == data ) return true; return false; } bool setValue( map<int, int>& target, int data ) { if ( target[data] == 0 ) { target[data] = 1; return true; } return false; } void minimumWindow( int arr1[], int n, int arr2[], int m ) { map<int, int> target; map<int, int> index; int counter = 0; int min_diff = INT_MAX; resetTarget( target, arr2, m ); // Insert indexes into the map. for ( int i = 0; i < n; i++ ) { if ( searchValue( target, arr1[i] ) ) index.insert(make_pair<int, int>( i, arr1[i] )); } while ( index.size() >= m ) { map<int, int>::iterator iter; map<int, int>::iterator start = index.begin(); for ( iter = index.begin(); iter != index.end(); ++iter ) { if ( setValue( target, iter->second ) ) { counter++; } if ( counter == m ) { if ( min_diff > ((iter->first) - (start->first)) ) min_diff = (iter->first) - (start->first); resetTarget( target, arr2, m ); index.erase(start); counter = 0; break; } } } cout << "Minimum window size is " << min_diff << endl; } int main() { int arr1[] = { 6, 7, 1, 3, 2, 4, 5, 2, 3, 1, 2, 5 }; int n = sizeof(arr1)/sizeof(arr1[0]); int arr2[] = { 2, 5, 1 }; int m = sizeof(arr2)/sizeof(arr2[0]); minimumWindow( arr1, n, arr2, m ); system("pause"); return 0; } - Anonymous November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

dude

- Eric December 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

dude. what?

- Eric December 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code is unreadable.

- Anonymous December 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <climits>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <map>
#include <cmath>
using namespace std;

void resetTarget( map<int, int>& target, int arr2[], int m )
{
	if ( target.size() == 0 )
	{
		for ( int i = 0; i < m; i++ )
			target.insert(make_pair<int, int>(arr2[i], 0));
	}
	else
	{
		for ( int i = 0; i < m; i++ )
			target[arr2[i]] = 0;
	}
}

bool searchValue( map<int, int>& target, int data )
{
	map<int, int>::iterator iter;
	for ( iter = target.begin(); iter != target.end(); ++iter )
		if ( iter->first == data )
			return true;

	return false;
}

bool setValue( map<int, int>& target, int data )
{
	if ( target[data] == 0 )
	{
		target[data] = 1;
		return true;
	}
	return false;
}

void minimumWindow( int arr1[], int n, int arr2[], int m )
{
	map<int, int> target;
	map<int, int> index;
	int counter = 0;
	int min_diff = INT_MAX;
	resetTarget( target, arr2, m );

	// Insert indexes into the map.
	for ( int i = 0; i < n; i++ )
	{
		if ( searchValue( target, arr1[i] ) )
			index.insert(make_pair<int, int>( i, arr1[i] ));
	}

	while ( index.size() >= m )
	{
		map<int, int>::iterator iter;
		map<int, int>::iterator start = index.begin();
		for ( iter = index.begin(); iter != index.end(); ++iter )
		{
			if ( setValue( target, iter->second ) )
			{
				counter++;
			}
			if ( counter == m )
			{
				if ( min_diff > ((iter->first) - (start->first)) )
					min_diff = (iter->first) - (start->first);
				resetTarget( target, arr2, m );
				index.erase(start);
				counter = 0;
				break;
			}
		}
	}
	cout << "Minimum window size is " << min_diff << endl;
}

int main()
{
	int arr1[] = { 6, 7, 1, 3, 2, 4, 5, 2, 3, 1, 2, 5 };
	int n = sizeof(arr1)/sizeof(arr1[0]);
	int arr2[] = { 2, 5, 1 };
	int m = sizeof(arr2)/sizeof(arr2[0]);

	minimumWindow( arr1, n, arr2, m );

	system("pause");
	return 0;
}

- Anonymous November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <climits>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <map>
#include <cmath>
using namespace std;

void resetTarget( map<int, int>& target, int arr2[], int m )
{
	if ( target.size() == 0 )
	{
		for ( int i = 0; i < m; i++ )
			target.insert(make_pair<int, int>(arr2[i], 0));
	}
	else
	{
		for ( int i = 0; i < m; i++ )
			target[arr2[i]] = 0;
	}
}

bool searchValue( map<int, int>& target, int data )
{
	map<int, int>::iterator iter;
	for ( iter = target.begin(); iter != target.end(); ++iter )
		if ( iter->first == data )
			return true;

	return false;
}

bool setValue( map<int, int>& target, int data )
{
	if ( target[data] == 0 )
	{
		target[data] = 1;
		return true;
	}
	return false;
}

void minimumWindow( int arr1[], int n, int arr2[], int m )
{
	map<int, int> target;
	map<int, int> index;
	int counter = 0;
	int min_diff = INT_MAX;
	resetTarget( target, arr2, m );

	// Insert indexes into the map.
	for ( int i = 0; i < n; i++ )
	{
		if ( searchValue( target, arr1[i] ) )
			index.insert(make_pair<int, int>( i, arr1[i] ));
	}

	while ( index.size() >= m )
	{
		map<int, int>::iterator iter;
		map<int, int>::iterator start = index.begin();
		for ( iter = index.begin(); iter != index.end(); ++iter )
		{
			if ( setValue( target, iter->second ) )
			{
				counter++;
			}
			if ( counter == m )
			{
				if ( min_diff > ((iter->first) - (start->first)) )
					min_diff = (iter->first) - (start->first);
				resetTarget( target, arr2, m );
				index.erase(start);
				counter = 0;
				break;
			}
		}
	}
	cout << "Minimum window size is " << min_diff << endl;
}

int main()
{
	int arr1[] = { 6, 7, 1, 3, 2, 4, 5, 2, 3, 1, 2, 5 };
	int n = sizeof(arr1)/sizeof(arr1[0]);
	int arr2[] = { 2, 5, 1 };
	int m = sizeof(arr2)/sizeof(arr2[0]);

	minimumWindow( arr1, n, arr2, m );

	system("pause");
	return 0;
}

- ravi November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <unordered_map>
#include <vector>
#include <iostream>
#include <climits>
using namespace std;

bool validate(unordered_map<int, int> & map){

	for(unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++){
		if(it->second < 1){
			return false;
		} 	
	}
	
	return true;
}

vector<int> smallestWindow(vector<int> input, vector<int> keys){

	unordered_map<int, int> map;
	vector<int> result;
	
	for(int i = 0; i < keys.size(); i++){
		map.insert({keys[i], 0});		
	}	
	
	int left, right;
	left = right = 0;
	
	int len = INT_MAX;
	int l=0, r=0;
	
	while(right < input.size()){
	
		// push a number to the window
		if(map.find(input[right]) != map.end()){
			map[input[right]]++;		
			
			// remove a number from the window until the window is invalid
			while(validate(map)){
				if(right - left < len){
					len = right - left;
					r = right;
					l = left;
				}
				
				if(map.find(input[left]) != map.end()){
					map[input[left]]--;
				}
				left++;
			}
		}
		
		right++;
	}
	
	for(int i = l; i <= r;i++){
	    result.push_back(input[i]);
    }
	
	return result;
}

int main(){
	
	vector<int> input = {2,5,7,9,8,5,1,3,6,5};
	vector<int> keys = {1, 3, 5};
	
	smallestWindow(input, keys);

	return 0;
}

- PoWerOnOff November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Above soln will only work if keys are unique though

- Anonymous January 20, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

c# implementation.
the key function.

static private int[] GetSmallestWindow( int[] arr, int[] keys ) {

            var occList = GetOccList( arr, keys ); // Get list of key occurences in initial array

            int[] target = new int[ occList.Count ];
            int minSum = int.MaxValue;
            bool next = false;

            foreach ( var i in occList ) {
                next = i.Value < i.Key.Length;
            }

            while ( next ) {

                int sum = GetSumOfSubtractions( occList );
                
                if ( sum < minSum ) {
                    minSum = sum;
                    target = GetArrayOfTargetIndexes( occList );
                }

                MoveIndexes( occList );
                next = GetIfNextIterationIsNeeded( occList );
            }

            var startPos = target.Min();
            var endPos = target.Max();

            int[] res = new int[ endPos - startPos + 1 ];

            int index = 0;
            for (int i = startPos; i <= endPos; i++) {
                res[index] = arr[i];
                index++;
            }
            return res;
        }

- zr.roman November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

16 /*
Logic :
17
18 find the index of all keys from the Input array and get the min_narrowet_window(
max_index - min_index).
19 while traversing the array , max_index/min_index is the current found key index.
keep on updating min_narrowest_index.
20 At the end the min(min_narrowest_index) would be the answer.
21
22
23 */
24
25
26 #include<stdio.h>
27 #include<unistd.h>
28 #define size 12
29 #define size1 3

30 bool isPresent(int i, int *arr,int *pos)
31 {
32 int j = 0;
33 int k = 0;
34 for(;k < size1; k++)
35 {
36 if(*arr++ == i)
37 {
38 *pos = j;
39 return true;
40 }
41 j++;
42 }
43
44 return false;
45
46 }
47 int find_min(int *arr,int *pos)
48 {
49 int l = 0,i;
50 for(i = 1; i < size1;i++)
51 {
52 if(arr[l] > arr[i])
53 {
54 l = i;
55 }
56 }
57 *pos = l;
58 return(arr[l]);
59 }
60 int find_narrowest_window(int arr[], int *arr1, int *pos, int *pos1)
61 {
62 int i=0;
63 int temp[3]={-1};
64 int narrowest_distance =999;
65 int max;
66 int min;
67 int pos3;
68 int count = 0;
69 int min_pos=0;
70 int l =0;
71 for(;i<size;i++)
72 {
73 //check if input array element is available in keys array.
74 if(isPresent(*arr,arr1,&pos3))
75 {
76 temp[pos3] = l;// hold the found input arrays indexes into an temp array.
77 if(count == 0){
78 max=min=l;
79 min_pos=pos3;// for the very first match of any of the keys element, the index in the input array would be the min_pos.
80 }
81 else
82 {
83 if(arr1[min_pos]==*arr)// really need to find the min of the found indexes, when we would replace the min index.
84 min = find_min(temp,&min_pos);
85 max = l;
86 }
87 count++;
88 }
89 if(count>=3)
90 {
91 if(narrowest_distance > (max-min))
92 {
93 *pos = min;
94 *pos1 = max;
95 narrowest_distance = max-min;
96 }
97 }
98 l++;
99 arr++;
100 }
101 if(count >=3)
102 return (1);
103 return 0;
104 }
105
106 main()
107 {
108
109 int arr[]={6,7,1,5,2,4,5,2,3,1,2,6,5};
110 int arr1[]={2,5,1};
111 int start = 0;// start position of the narrwest window
112 int last = 0;// last position of the narrowest window
113 if(find_narrowest_window(arr,arr1,&start,&last))
114 printf("The narrowest window is %d %d: ",start,last);
115 else
116 printf("No window available");
117 }

- Anand November 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public Tuple<int, int> GetMinInterval(int[] values, int[] keys)
{
    Tuple<int, int> result = Tuple.Create(-1, -1);

    int total = 0;
    var dic = new Dictionary<int, int>();

    foreach (var key in keys)
    {
        total += key;
        dic.Add(key, -1);
    }

    int min = int.MaxValue;
    bool completed = false;
    Tuple<int, int> = Tuple.Create(-1, -1);

    for (var i = 0; i < values.Lenght; i++)
    {
        int value = values[i];
        int lastIndex = -1;
        if (!dict.TryGetValue(value, out lastIndex))
            continue;

        if (lastIndex == -1)
        {
            total -= value;
            completed = total == 0;
            if (i < min)
                min = i;

            if (completed)
                result = Tuple.Create(min, i);
        }

        dict[value] = i;

        if (!completed)
            continue;

        int lastValue = values[min];
        // Trim the lower side 
        if (lastValue == value)
        {
            for (var j = min; j < i; j++)
            {
                if (!dict.TryGetValue(values[j], out lastIndex))
                    continue;
                if (j >= lastIndex)
                {
                    min = j;
                    break;
                }
            }

            if (i - min < result.Item2 - result.Item1)
                result = Tuple.Create(min, i);
        }
    }

    return result;
}

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

Is a C# implementation I did not have access to a compiler so not sure if runs but is the general idea.

- hnatsu December 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This worked for me :

#!/usr/bin/python
input_list = [6,7,1,3,2,4,5,2,3,1,2,5,9]
keys = [2,5,1]
maxLen= len(input_list)
keys_remaining = keys[:]
for i in range(0,len(input_list)) :
    if input_list[i] in keys :
        if input_list[i] in keys_remaining : keys_remaining.remove(input_list[i])
        if len(keys_remaining) == 0 :
             temp_list = list(reversed(input_list[0:i+1]))[0:maxLen]
             temp_keys = keys[:]
             for j in range(0,len(temp_list)) :
                 if temp_list[j] in temp_keys : temp_keys.remove(temp_list[j])
                 if len(temp_keys) == 0 :
                     maxLen = j + 1
                     index = i
                     break
if len(keys_remaining) == 0 :
    print input_list[index-maxLen+1 : index+1]

The logic is same as others have mentioned. It does a single iteration of the list. After all key elements are found, each time it finds an element from key it creates a reverse window from that element until the smallest window found. If it can find all keys in a much smaller window, it updates the index and smallest window length.

- gautam142857 December 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This worked for me :

#!/usr/bin/python
input_list = [6,7,1,3,2,4,5,2,3,1,2,5,9]
keys = [2,5,1]
maxLen= len(input_list)
keys_remaining = keys[:]
for i in range(0,len(input_list)) :
    if input_list[i] in keys :
        if input_list[i] in keys_remaining : keys_remaining.remove(input_list[i])
        if len(keys_remaining) == 0 :
             temp_list = list(reversed(input_list[0:i+1]))[0:maxLen]
             temp_keys = keys[:]
             for j in range(0,len(temp_list)) :
                 if temp_list[j] in temp_keys : temp_keys.remove(temp_list[j])
                 if len(temp_keys) == 0 :
                     maxLen = j + 1
                     index = i
                     break
if len(keys_remaining) == 0 :
    print input_list[index-maxLen+1 : index+1]

The logic is same as others have mentioned. It does a single iteration of the list. After all key elements are found, each time it finds an element from key it creates a reverse window from that element until the smallest window found. If it can find all keys in a much smaller window, it updates the index and smallest window length.

- gautam142857 December 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This worked for me :

#!/usr/bin/python
input_list = [6,7,1,3,2,4,5,2,3,1,2,5,9]
keys = [2,5,1]
maxLen= len(input_list)
keys_remaining = keys[:]
for i in range(0,len(input_list)) :
    if input_list[i] in keys :
        if input_list[i] in keys_remaining : keys_remaining.remove(input_list[i])
        if len(keys_remaining) == 0 :
             temp_list = list(reversed(input_list[0:i+1]))[0:maxLen]
             temp_keys = keys[:]
             for j in range(0,len(temp_list)) :
                 if temp_list[j] in temp_keys : temp_keys.remove(temp_list[j])
                 if len(temp_keys) == 0 :
                     maxLen = j + 1
                     index = i
                     break
if len(keys_remaining) == 0 :
    print input_list[index-maxLen+1 : index+1]

The logic is the same as others have used. It iterates through the list once. After all keys are found, it creates a reverse window and tries to find a smaller window within which all keys fit.

- gautam142857 December 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This worked for me :

#!/usr/bin/python
input_list = [6,7,1,3,2,4,5,2,3,1,2,5,9]
keys = [2,5,1]
maxLen= len(input_list)
keys_remaining = keys[:]
for i in range(0,len(input_list)) :
    if input_list[i] in keys :
        if input_list[i] in keys_remaining : keys_remaining.remove(input_list[i])
        if len(keys_remaining) == 0 :
             temp_list = list(reversed(input_list[0:i+1]))[0:maxLen]
             temp_keys = keys[:]
             for j in range(0,len(temp_list)) :
                 if temp_list[j] in temp_keys : temp_keys.remove(temp_list[j])
                 if len(temp_keys) == 0 :
                     maxLen = j + 1
                     index = i
                     break
if len(keys_remaining) == 0 :
    print input_list[index-maxLen+1 : index+1]

The logic is the same as others have used. It iterates through the list once. After all keys are found, it creates a reverse window and tries to find a smaller window within which all keys fit.

- gautam142857 December 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This worked for me :

#!/usr/bin/python
input_list = [6,7,1,3,2,4,5,2,3,1,2,5,9]
keys = [2,5,1]
maxLen= len(input_list)
keys_remaining = keys[:]
for i in range(0,len(input_list)) :
    if input_list[i] in keys :
        if input_list[i] in keys_remaining : keys_remaining.remove(input_list[i])
        if len(keys_remaining) == 0 :
             temp_list = list(reversed(input_list[0:i+1]))[0:maxLen]
             temp_keys = keys[:]
             for j in range(0,len(temp_list)) :
                 if temp_list[j] in temp_keys : temp_keys.remove(temp_list[j])
                 if len(temp_keys) == 0 :
                     maxLen = j + 1
                     index = i
                     break
if len(keys_remaining) == 0 :
    print input_list[index-maxLen+1 : index+1]

The logic is the same as others have used. It iterates through the list once. After all keys are found, it creates a reverse window and tries to find a smaller window within which all keys fit.

- gautam December 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This worked for me :

#!/usr/bin/python
input_list = [6,7,1,3,2,4,5,2,3,1,2,5,9]
keys = [2,5,1]
maxLen= len(input_list)
keys_remaining = keys[:]
for i in range(0,len(input_list)) :
    if input_list[i] in keys :
        if input_list[i] in keys_remaining : keys_remaining.remove(input_list[i])
        if len(keys_remaining) == 0 :
             temp_list = list(reversed(input_list[0:i+1]))[0:maxLen]
             temp_keys = keys[:]
             for j in range(0,len(temp_list)) :
                 if temp_list[j] in temp_keys : temp_keys.remove(temp_list[j])
                 if len(temp_keys) == 0 :
                     maxLen = j + 1
                     index = i
                     break
if len(keys_remaining) == 0 :
    print input_list[index-maxLen+1 : index+1]

The logic is the same as others have used. It iterates through the list once. After all keys are found, it creates a reverse window and tries to find a smaller window within which all keys fit.

- gautam December 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

abcd

- gautam December 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

abcd

- gautam December 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This worked for me

#!/usr/bin/python
input_list = [6,7,1,3,2,4,5,2,3,1,2,5,9]
keys = [2,5,1]
maxLen= len(input_list)
keys_remaining = keys[:]
for i in range(0,len(input_list)) :
    if input_list[i] in keys :
        if input_list[i] in keys_remaining : keys_remaining.remove(input_list[i])
        if len(keys_remaining) == 0 :
             temp_list = list(reversed(input_list[0:i+1]))[0:maxLen]
             temp_keys = keys[:]
             for j in range(0,len(temp_list)) :
                 if temp_list[j] in temp_keys : temp_keys.remove(temp_list[j])
                 if len(temp_keys) == 0 :
                     maxLen = j + 1
                     index = i
                     break
if len(keys_remaining) == 0 :
    print input_list[index-maxLen+1 : index+1]

The method is same as others have described. It iterates once through the list. After it has found all the keys, every time it finds an element thats in the keys, it tries to find a smaller window that would accommodate all the keys.

- gautam December 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This worked for me

#!/usr/bin/python
input_list = [6,7,1,3,2,4,5,2,3,1,2,5,9]
keys = [2,5,1]
maxLen= len(input_list)
keys_remaining = keys[:]
for i in range(0,len(input_list)) :
    if input_list[i] in keys :
        if input_list[i] in keys_remaining : keys_remaining.remove(input_list[i])
        if len(keys_remaining) == 0 :
             temp_list = list(reversed(input_list[0:i+1]))[0:maxLen]
             temp_keys = keys[:]
             for j in range(0,len(temp_list)) :
                 if temp_list[j] in temp_keys : temp_keys.remove(temp_list[j])
                 if len(temp_keys) == 0 :
                     maxLen = j + 1
                     index = i
                     break
if len(keys_remaining) == 0 :
    print input_list[index-maxLen+1 : index+1]

The method is same as others have described. It iterates once through the list. After it has found all the keys, everytime it finds an element thats in the keys, it tries to find a smaller window that would accommodate all the keys.

- gautam December 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

c# code:

void Main()
{
	int[] input = new int[] {6,7,1,3,2,4,5,2,3,1,2,5};
	int[] keys = new int[] {2,5,1};
	
	keys = insertionSort(keys);
	
	for(int i = 2; i < input.Length; i++)
	{
		//Console.WriteLine("i = " + i);
	    
		bool temp = false;
		int[] tempArr = new int[] {input[i], input[i-1], input[i-2]};
		tempArr = insertionSort(tempArr);
		if (tempArr[0] == keys[0] &&
		tempArr[1] == keys[1] &&
		tempArr[2] == keys[2])
			temp = true;
		if (temp)
		{
			Console.WriteLine(string.Format("from {0} to {1}", i-2, i));
		}
	}	
}
int[] insertionSort(int[] arr)
{
	for (int i = 1;i < arr.Length - 1; i++)
	{
		var temp = arr[i];
		int j = i;
		while (j > 0 && arr[j-1] > temp)
		{
			arr[j] = arr[j-1];
			j = j-1;
		}
		arr[j] = temp;
	}
	return arr;
}

- jooyoung_sung December 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

c# code:

void Main()
{
	int[] input = new int[] {6,7,1,3,2,4,5,2,3,1,2,5};
	int[] keys = new int[] {2,5,1};
	
	keys = insertionSort(keys);
	
	for(int i = 2; i < input.Length; i++)
	{
		//Console.WriteLine("i = " + i);
	    
		bool temp = false;
		int[] tempArr = new int[] {input[i], input[i-1], input[i-2]};
		tempArr = insertionSort(tempArr);
		if (tempArr[0] == keys[0] &&
		tempArr[1] == keys[1] &&
		tempArr[2] == keys[2])
			temp = true;
		if (temp)
		{
			Console.WriteLine(string.Format("from {0} to {1}", i-2, i));
		}
	}	
}
int[] insertionSort(int[] arr)
{
	for (int i = 1;i < arr.Length - 1; i++)
	{
		var temp = arr[i];
		int j = i;
		while (j > 0 && arr[j-1] > temp)
		{
			arr[j] = arr[j-1];
			j = j-1;
		}
		arr[j] = temp;
	}
	return arr;
}

- jooyoung_sung December 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Definitely not the most efficient code in the world, but it's a start.

private int[] getMinimumWindow(int[] input, int[] keys) {
		final int inputLength = input.length;
	
		for (int windowLength = keys.length; windowLength < inputLength; windowLength++) {
			for (int i = 0; i < (inputLength - (windowLength - 1)); i++) {
				if (containsAny(input, keys, i, windowLength) && containsAll(input, keys, i, windowLength)) {
					return new int[] { i, i + (windowLength - 1) };
				}
			}
		}

		return new int[] { -1, -1 };
	}

	private boolean containsAny(int[] input, int[] keys, int startOfWindow, int windowLength) {
		for (int i = 0; i < keys.length; i++) {
			for (int j = startOfWindow; j < (startOfWindow + windowLength); j++) {
				if (input[j] == keys[i]) {
					return true;
				}
			}
		}

		return false;
	}

	private boolean containsAll(int[] input, int[] keys, int startOfWindow, int windowLength) {
		for (int i = 0; i < keys.length; i++) {
			boolean foundMatch = false;
			for (int j = startOfWindow; j < (startOfWindow + windowLength); j++) {
				if (input[j] == keys[i]) {
					foundMatch = true;
					break;
				}
			}
			if (!foundMatch) {
				return false;
			}
		}		

		return true;
	}

- Chris December 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class PrintMinWindow {

	public static Map<Integer, LinkedList<Integer>> invertedIndex = new HashMap<Integer, LinkedList<Integer>>();

	public static void printMinWindowIndex(int[] in, int[] keys) {

		if (in == null || in.length == 0)
			return;

		for (int i = 0; i < keys.length; i++) {
			invertedIndex.put(keys[i], new LinkedList<Integer>());
		}
		
		for(int i = 0; i < in.length; i++ ) {
			LinkedList<Integer> v = invertedIndex.get(in[i]);
			if(v != null) v.push(i);
		}

		int minIndex = Integer.MIN_VALUE;
		int minDist = Integer.MAX_VALUE;
		
		for (int i = 0; i < in.length; i++) {
			LinkedList<Integer> vs = invertedIndex.remove(in[i]);

			if (vs != null) {
				int startIndex = vs.peekLast();
				int temp = Integer.MIN_VALUE;
				
				for (Map.Entry<Integer, LinkedList<Integer>> e : invertedIndex.entrySet()) {
					if(e.getValue() != null && !e.getValue().isEmpty()) {
						temp = Math.max(temp, Math.abs(e.getValue().peekLast()-startIndex));
					} else {
						temp = Integer.MAX_VALUE;
						break;
					}
				}

				if (temp < minDist) {
					minDist = temp;
					minIndex = startIndex;
				}
				
				vs.pollLast();
				invertedIndex.put(in[i], vs);
			}
		}

		System.out.println(" " + minIndex);
	}
	
	public static void main(String[] args) {
		printMinWindowIndex(new int[]{6,7,1,3,2,4,5,2,3,1,2,5}, new int[]{2,5,1});
	}
}

- Guru December 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Found some interesting approach, combined use of TreeMap and TreeSet

import java.util.Arrays;
import java.util.HashSet;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 */
public class SlidingWindow2 {

    static class SlidedWindow implements Comparable<SlidedWindow> {
        public final static int UNDEFINED = -1;

        int[] window;
        int lowMark = -1, highMark = -1;

        public SlidedWindow() {
        }

        public SlidedWindow(int[] window, int lowMark, int upperIndex) {
            this.window = window;
            this.lowMark = lowMark;
            this.highMark = upperIndex;
        }

        public int[] getWindow() {
            return window;
        }

        public void setWindow(int[] window) {
            this.window = window;
        }

        public int getLowMark() {
            return lowMark;
        }

        public void setLowMark(int lowMark) {
            this.lowMark = lowMark;
        }

        public int getHighMark() {
            return highMark;
        }

        public void setHighMark(int highMark) {
            this.highMark = highMark;
        }


        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            SlidedWindow that = (SlidedWindow) o;
            return this.window.length == that.window.length;
        }

        public int compareTo(SlidedWindow w) {
            if (window.length < w.window.length)
                return -1;
            if (window.length > w.window.length)
                return 1;
            return 0;
        }


        @Override
        public String toString() {
            return "SlidedWindow{" +
                    "window=" + Arrays.toString(window) +
                    ", lowMark=" + lowMark +
                    ", highMark=" + highMark +
                    '}';
        }

        @Override
        public int hashCode() {
            return window.hashCode();
        }
    }

    public static void main(String[] args) {
        int[] input = {6, 7, 1, 3, 2, 4, 5, 2, 3, 1, 2, 5};
        int[] keys = {2, 5, 1};

        SlidedWindow w =  new SlidingWindow2().getMinWindow(input, keys);
        System.out.println("for input: "+ Arrays.toString(input)  +" has a minimum window: " + w);
    }

    private SlidedWindow getMinWindow(int[] input, int[] keys) {
        //easy retrieval of key characters
        HashSet<Integer> keySet = new HashSet<Integer>();
        for (int ic=0;ic<keys.length;ic++) keySet.add(keys[ic]);

        //origin
        TreeMap<Integer, Integer> indexInTree = new TreeMap<Integer, Integer>();
        //sorted
        TreeSet<Integer> indexInWindow = new TreeSet<Integer>();

        SlidedWindow minWin = null;

        for (int i=0;i<input.length;i++)  {
            int inputValue = input[i];
            if (keySet.contains(inputValue)) {

                //remove when already seen
                if (indexInTree.containsKey(inputValue)) {
                    indexInWindow.remove(indexInTree.get(inputValue));
                }

                //interesting value, what did I find indexInTree
                indexInTree.put(inputValue, i);
                indexInWindow.add(i);

                //find possible window when all chars found
                if (keySet.size()==indexInWindow.size()) {
                    Integer first = indexInWindow.first();
                    Integer last = indexInWindow.last();
                    SlidedWindow sw = new SlidedWindow(Arrays.copyOfRange(input, first, last+1), first, last);
                    //first windows
                    if (minWin == null) {
                        minWin = sw;
                    } else {
                        if (minWin.compareTo(sw)>0) {
                            minWin = sw;
                        }
                    }
                }

            }
        }

        return minWin;
    }


}

- keerekeerweere December 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I might have misunderstood the problem but...my code below seemed to do the trick...

def minWindow(array, keySet):                                                                                                                                                                                                                 
    minSize = len(keySet)                                                                                                                                                                                                                     
    while minSize < len(array):                                                                                                                                                                                                               
        lowIndex = 0                                                                                                                                                                                                                          
        highIndex = lowIndex + minSize                                                                                                                                                                                                        
        while (lowIndex + minSize) <= len(array):                                                                                                                                                                                             
            if set(array[lowIndex:highIndex]).intersection(keySet) == keySet:                                                                                                                                                                 
                return (lowIndex, highIndex - 1)                                                                                                                                                                                              
            lowIndex += 1                                                                                                                                                                                                                     
            highIndex += 1                                                                                                                                                                                                                    
        minSize += 1                                                                                                                                                                                                                          
    return (0, len(array) - 1)                                                                                                                                                                                                                
                                                                                                                                                                                                                                              
                                                                                                                                                                                                                                              
                                                                                                                                                                                                                                              
if __name__ == '__main__':                                                                                                                                                                                                                    
    vals = [6,7,1,3,2,4,5,2,3,1,2,5]                                                                                                                                                                                                          
    keys = set([1, 2, 5])                                                                                                                                                                                                                     
    print minWindow(vals, keys)

- NK January 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Not sure if I misunderstood the problem but this worked for me:

def minWindow(array, keySet):
    minSize = len(keySet)
    while minSize < len(array):
        lowIndex = 0
        highIndex = lowIndex + minSize
        while (lowIndex + minSize) <= len(array):
            if set(array[lowIndex:highIndex]).intersection(keySet) == keySet:
                return (lowIndex, highIndex - 1)
            lowIndex += 1
            highIndex += 1
        minSize += 1
    return (0, len(array) - 1)

if __name__ == '__main__':
    vals = [6,7,1,3,2,4,5,2,3,1,2,5]
    keys = set([1, 2, 5])
    print minWindow(vals, keys)

- NK January 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

#define INPUT_LEN 12
#define KEY_LEN 3


int input[INPUT_LEN] = { 6, 7, 1, 3, 2, 4, 5, 2, 3, 1, 2, 5 };
int key[KEY_LEN] = { 2, 5, 1 };
int order[KEY_LEN][INPUT_LEN] = { 0, };

int key_num[KEY_LEN] = { 0, };
int dep_key[KEY_LEN] = { 0, };
int min[KEY_LEN] = { 0, };
int max[KEY_LEN] = { 0, };



int main(){
	int i, j, k;
	int start, flag=0, lFlag=0;
	int fmin, fmax;

	for (i = 0; i < KEY_LEN; i++){
		k = 0;
		for (j = 0; j < INPUT_LEN; j++){
			if (key[i] == input[j]){
				order[i][k] = j;
				k++;
			}

		}
		key_num[i] = k;
		min[i] = INPUT_LEN;
		max[i] = 0;
	}

	i = 0;
	fmin = 0;
	fmax = INPUT_LEN;
	j = 0;
	k = 0;
	do{
		if (lFlag==0){
			if (min[i] > order[i][j])min[i] = order[i][j];
			if (max[i] < order[i][j])max[i] = order[i][j];
			dep_key[i] = j;
			i++;
			j = 0;
			if (i != KEY_LEN){
				max[i] = max[i - 1];
				min[i] = min[i - 1];
			}
			else {
				lFlag = 1;
				i--;
			}
		}
		else {
			lFlag = 0;
			if ((max[i] - min[i]) < (fmax - fmin)){
				fmin = min[i];
				fmax = max[i];
			}
			
			j = dep_key[i];
			k = 0;
			
			if (j != (key_num[i] - 1)){
				j++;
				max[i] = max[i-1];
				min[i] = min[i-1];
			}
			else {
				while (j == (key_num[i]-1)){
					max[i] = 0;
					min[i] = INPUT_LEN;
					i--;
					if (i < 0){
						flag = 1;
						break;
					}
					j = dep_key[i];
				}
				if (flag != 1){
					j++;
					if (i == 0){
						max[i] = 0;
						min[i] = INPUT_LEN;
					}
					else{
						max[i] = max[i - 1];
						min[i] = min[i - 1];
					}
				}
			}
			
		}
		
	} while (flag==0);
	
	printf("%d %d\n", fmin, fmax);
	
	return 1;
}

- prelude618 January 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

public class FindWindow {

public void findMinWindow(int bigArr[], int smallArr[]){

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int max = 0;
int min = 0;
int diff = 0;

for(int i= 0; i<bigArr.length; i++){
for(int j =0; j< smallArr.length; j++){
if(bigArr[i]== smallArr[j]){
map.put(smallArr[j], i);
}
}
if(map.size() == smallArr.length){
max = Collections.max(map.values());
min = Collections.min(map.values());
int minMaxDiff = max - min;
if(diff> minMaxDiff){
diff = minMaxDiff;
max = max;
min = min;
}
}
}
System.out.println("indexes are : "+min+" and "+max);
}

public static void main(String[] args) {
FindWindow fm = new FindWindow();
int arr1[] = new int[]{3,1,4,3,5,6,7,8,5,4,3,2,4,5,6,7,2,3,4,1,5,6};
int arr2[] = new int[]{1,2,5};
fm.findMinWindow(arr1, arr2);
}
}

- Rahul Singh January 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

// This code will work as expected
public class FindWindow {

public void findMinWindow(int bigArr[], int smallArr[]){

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int max = 0;
int min = 0;
int diff = 0;

for(int i= 0; i<bigArr.length; i++){
for(int j =0; j< smallArr.length; j++){
if(bigArr[i]== smallArr[j]){
map.put(smallArr[j], i);
}
}
if(map.size() == smallArr.length){
max = Collections.max(map.values());
min = Collections.min(map.values());
int minMaxDiff = max - min;
if(diff> minMaxDiff){
diff = minMaxDiff;
max = max;
min = min;
}
}
}
System.out.println("indexes are : "+min+" and "+max);
}

public static void main(String[] args) {
FindWindow fm = new FindWindow();
int arr1[] = new int[]{3,1,4,3,5,6,7,8,5,4,3,2,4,5,6,7,2,3,4,1,5,6};
int arr2[] = new int[]{1,2,5};
fm.findMinWindow(arr1, arr2);
}
}

- Rahul Singh January 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

public class FindWindow {

public void findMinWindow(int bigArr[], int smallArr[]){

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int max = 0;
int min = 0;
int diff = 0;

for(int i= 0; i<bigArr.length; i++){
for(int j =0; j< smallArr.length; j++){
if(bigArr[i]== smallArr[j]){
map.put(smallArr[j], i);
}
}
if(map.size() == smallArr.length){
max = Collections.max(map.values());
min = Collections.min(map.values());
int minMaxDiff = max - min;
if(diff> minMaxDiff){
diff = minMaxDiff;
max = max;
min = min;
}
}
}
System.out.println("indexes are : "+min+" and "+max);
}

public static void main(String[] args) {
FindWindow fm = new FindWindow();
int arr1[] = new int[]{3,1,4,3,5,6,7,8,5,4,3,2,4,5,6,7,2,3,4,1,5,6};
int arr2[] = new int[]{1,2,5};
fm.findMinWindow(arr1, arr2);
}
}

- Rahul January 19, 2016 | 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