Amazon Interview Question
SDE-2sCountry: United States
Interview Type: Phone Interview
// 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;
}
#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;
}
#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;
}
#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;
}
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;
}
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 }
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;
}
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.
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.
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.
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.
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.
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.
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.
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.
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;
}
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;
}
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;
}
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});
}
}
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;
}
}
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)
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)
#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;
}
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);
}
}
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);
}
}
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);
}
}
- siva.sai.2020 November 29, 2015