Interview Question






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.

- coder September 14, 2015 | Flag Reply
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};
}

- MehrdadAP September 15, 2015 | Flag Reply
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)

- PyrocasterX90 September 16, 2015 | Flag Reply
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)

- PyrocasterX90 September 16, 2015 | Flag Reply
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;
	}

- Saran Prasad Ambikapathy September 17, 2015 | Flag Reply
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;
	}

- asaranprasad September 17, 2015 | Flag Reply
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

- djtrance January 10, 2016 | Flag Reply
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;
            }

        }

- djtrance January 11, 2016 | Flag Reply
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?

- Anonymous September 12, 2015 | Flag Reply
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

- djtrance January 10, 2016 | Flag


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