Interview Question
let N=A.size, M=Q.size
By using a hashmap, it can be solved in O(N).
We apply sliding window idea.
Assume there is a window of size M. Just move it from beginning of the array to the end, one by one element. At each step we just need to know about the number of elements in the window that match to Q's elements. Once it reaches to M, it means we found the answer.
The only thing is to update the information of inside the window when we are moving to next element. We can use a hashmap to keep track of frequency of Q's elements inside the window.
Simply, when we pass an element, we decrease its frequency and we insert new element into window, we increase its frequency. Also, by using another variable called "cur", we can keep track of number of distinct element inside the window at each step.
See the code for more clarifications.
pair<int,int> solve(vector<int> A,vector<int> Q)
{
int N=A.size(),M=Q.size();
if (N<M) return {-1,-1};
unordered_map<int,int> mp;
for (int i=0;i<M;i++)
mp[Q[i]]=0;
int cur=0;//number of common elements with Q in sliding window
for (int i=0;i<N;i++){
if (cur==M){
return {i-M,i-1};
}
//the window is becoming size M, so there is no removing
if (i<M){
if (mp.find(A[i])!=mp.end()){
mp[A[i]]++;
if (mp[A[i]]==1)
cur++;
}
}
//we should handle both removing and inserting
else{
//removing oldest element from the window
if (mp.find(A[i-M])!=mp.end()){
mp[A[i-M]]--;
if (mp[A[i-M]]==0)
cur--;
}
//adding new element to the window
if (mp.find(A[i])!=mp.end()){
mp[A[i]]++;
if (mp[A[i]]==1)
cur++;
}
}
}
if (cur==M)
return {N-M,N-1};
return {-1,-1};
}
Since the elements in Q are distinct, this can be done in Time Complexity: O(n) and space complexity: O(1).
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] A = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 11 };
int[] Q = { 9, 10, 12 };
int[] indices = getIndicesForSubset(A, Q);
System.out.println("beginIndex: " + indices[0] + " endIndex: " + indices[1]);
}
private static int[] getIndicesForSubset(int[] a, int[] q) {
int[] indices = { -1, -1 };
int limit = a.length;
int qCounter = 0;
for (int i = 0; i < limit; i++) {
if (a[i] == q[qCounter])
qCounter++;
else
qCounter = 0;
if (qCounter == q.length) {
indices[0] = i - qCounter + 1;
indices[1] = i;
break;
}
}
return indices;
}
Since the elements in Q are distinct, this can be done in Time Complexity: O(n) and space complexity: O(1).
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] A = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 11 };
int[] Q = { 9, 10, 12 };
int[] indices = getIndicesForSubset(A, Q);
System.out.println("beginIndex: " + indices[0] + " endIndex: " + indices[1]);
}
private static int[] getIndicesForSubset(int[] a, int[] q) {
int[] indices = { -1, -1 };
int limit = a.length;
int qCounter = 0;
for (int i = 0; i < limit; i++) {
if (a[i] == q[qCounter])
qCounter++;
else
qCounter = 0;
if (qCounter == q.length) {
indices[0] = i - qCounter + 1;
indices[1] = i;
break;
}
}
return indices;
}
My approach is a bit more exhaustic, but here it is.
I use a hashtable with key being the value in the array, and a list of indexes where the number appears. We go through the array A and populate the hashtable, then we go through the array B and get the indexes of each number.
Then we go through the list of indices to get different possible minimal paths for each occurence of the first element of arrayB. We return the indices of the path that is the shortest.
Please comment if you find some issues
public static int[] ArraySubset(int[] arrayA, int[] arrayQ)
{
// assume distinct array 1 and 2
HashTable<int, List<int>> ht = new HashTable<int, List<int>>(arrayA.Max());
for (int i=0;i<arrayA.Length;i++)
{
List<int> indexes = ht.Find(arrayA[i]);
if (indexes != null)
{
indexes.Add(i);
}
else
{
List<int> el = new List<int>();
el.Add(i);
ht.Add(arrayA[i], el);
}
}
List<List<int>> indices = new List<List<int>>();
for (int j = 0; j < arrayQ.Length; j++)
{
List<int> index = ht.Find(arrayQ[j]);
indices.Add(index);
}
// go through the list of lists and see if there is a shortest path from first element to last element
List<List<int>> paths = new List<List<int>>();
bool valid = true;
for (int i = 0; i < arrayQ.Length; i++)
{
if (indices[i] == null)
valid = false;
}
for (int i = 0;i<indices[0].Count() && valid;i++)
{
List<int> path = new List<int>();
int index = indices[0][i];
path.Add(index);
for (int j = 1; j < indices.Count() && valid; j++)
{// find smallest term in list which is larger than the previous index
int smallest = Int32.MaxValue;
bool found = false;
for (int k = 0; k < indices[j].Count(); k++)
{
if (indices[j][k] > index)
{
found = true;
if (indices[j][k] < smallest)
{
smallest = indices[j][k];
}
}
}
if (found == true)
{
index = smallest;
path.Add(index);
}
else
{// stop this path
valid = false;
}
}
if (valid)
paths.Add(path);
}
if (paths.Count() > 0)
{
// get lengths
int[] lengths = new int[paths.Count()];
int min = Int32.MaxValue;
int minIdx = Int32.MaxValue;
for (int i = 0; i < paths.Count(); i++)
{
lengths[i] = paths[i].Last() - paths[i].First() + 1;
if (min > lengths[i])
{
min = lengths[i];
minIdx = i;
}
}
int[] startstop = { paths[minIdx].First(), paths[minIdx].Last() };
return startstop;
}
else
{
return null;
}
}
One straight solution is solving LCS problem with modification everytime we find the common character from diagonal , we record the character and if there is some character missing from B in common subsequence immediately stop the search else carry on.
- coder September 14, 2015