## Interview Question

• 0
of 0 votes

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

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.

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

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

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

Consider the two arrays:
A[n], Q[m]

Create a matrix M [n X m]

Solve using dynamic programming with the following conditions
if A[i] != Q[j] then M[i,j] =0
if A[i] == ![j] then M[i,j] = M[i-1,j-1] + 1

O(M*N)

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

Consider the two arrays:
A[n], Q[m]

Create a matrix M [n X m]

Solve using dynamic programming with the following conditions
if A[i] != Q[j] then M[i,j] =0
if A[i] == ![j] then M[i,j] = M[i-1,j-1] + 1

O(M*N)

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

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

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

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

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

for example
A={1,2,3,4,5,6,7,8,9,10}
Q = {1,10}

length A = 10
length Q = 2
length A[i,j] = 10

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

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

}``````

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

Wouldn't the length of an array sequentially covering Q be the length of Q?

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

for example
A={1,2,3,4,5,6,7,8,9,10}
Q = {1,10}

length A = 10
length Q = 2
length A[i,j] = 10

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