Google Interview Question Software Engineer in Tests
<pre lang="c++" line="1" title="CodeMonkey92642" class="run-this">#include <iostream>
using namespace std;
bool minWindow(int N[], int n, int K[], int k, int Boundaries[]) {
int minWin=-1;
int* P = new int[k]; // All elements init to 0
P[0] = -1;
while(true)
{
for(int i=0;i<k;i++) {
if(i>0 && P[i] < P[i-1])
P[i] = P[i-1];
if(i==0 || P[i]==P[i-1]) {
do {
P[i]++;
if(P[i]>=n) {
delete[] P;
return minWin>0 ? true : false;
}
} while(N[P[i]]!=K[i]);
}
}
int win = P[k-1] - P[0] + 1;
if(minWin==-1 || win<minWin) {
Boundaries[0] = P[0];
Boundaries[1] = P[k-1];
minWin = win;
}
}
}
int main() {
int N[] = {23, 46, 24, 16, 16, 29, 35, 2,77,29, 35, 77, 29, 2 };
int K[] = {16,2,77,29};
int Boundaries[2];
bool success = minWindow(N, sizeof(N)/sizeof(int), K, sizeof(K)/sizeof(int), Boundaries);
if(success)
cout << "start: " << Boundaries[0] << ", end: " << Boundaries[1] << endl;
else
cout << "No such window" << endl;
return 0;
}</pre><pre title="CodeMonkey92642" input="yes">
</pre>
A little addition, in last code by Anonymous, there may be large number of useless iterations searching for a particular query term if the size of input array is too large and the only window is present at the end of the input array. In such a case, preparing a term-position matrix would be a better idea to avoid useless iterations. The term-position matrix will store for each query term, occurences of the term in the input array in increasing order. Thus, the search space will become shorter (only the positions where the query terms are present).
Input [1 9 3 4 12 13 9 12 21 ]
query Array [9 12 21]
1. Find the index of each element in the query Array
9 -- 2,7
12 -- 5,8
21 -- 9
2. Calculate the distance, such that all elements are included. The following distances are possible
2->5->9 = 3+4 = 7
2->8->9 = 6+1 = 7
7->8->9 = 1+1 = 2
(Note :7 > 5, so the path 7->5->9 is not acceptable. because order has to be maintained)
3. Output the window between (7,9)
May be someone can comment on the complexity.
Nice idea man, lot space for improvements thou. What we have is sorted arrays of positions we have to search. Now we have to find smallest range of integers in these arrays, so we do it in this manner: Iterate first array from last element to first, and for every index encountered, search element more than this one in next array using binary search. continue this process for all remaining arrays.
Using this search pattern we guarantee that first found solution is the smallest one, i.e. the one we're seeking.
at last one thing i want to add store occurrence of each of the digit of sub array and store it in 2-d matrix and check along the each column....like
9 -- 2,7
12 -- 5,8
21 -- 9,9 << repeat the value >>
first column = 9-2 = 7;
second column = 9-7 = 2;
so second column is minimum...
How about using linked list?
1.Create a linked list out of array 1
2.search for the first element of array 2 in linked list
3.Compare remaining elements from array 2
4.At any point if there is mismatch and there more elements in array 2 stop comparing
5.Find the next match of first element from array 2 in linked list (remember the location of first match and look for the next match after than).
6.If number of elements in linked list from the match is not equal to or greater than the number of elements of array two break.
Create linked list O(n), find first element O(n), compare elements in array 2 O(m)
2O(n)+O(m)
bool FindPattern( int input[], int inSize, int query[], int qSize)
{
int k = 0;
int j=0;
bool matchfound = false;
while ( k+qSize <= insize)
{
while ( input[k] != query[j])
k++;
for( int i = k, j=0; j< qSize ;i++,j++)
{
if( input[i] != query[j])
break;
}
if(j== qSize)
{
matchfound = true;
break;
}
j=0;
k = i;
}
return matchfound;
}
#include<stdio.h>
#include<conio.h>
int a[]={1,9,3,4,12,13,9,2,12,21,7};
int alen=11;
int b[]={9,12,21};
int blen=3;
int found[11];
int length[11];
void commonwindow()
{
int i,m,n,tt;
int count=0,k=0;
for(i=0;i<alen;i++)
{
if(a[i]==b[0])
{
count++;
found[k++]=i;
}
}
k=0;
while(k<count)
{
m=found[k];
n=0;
tt=0;
while(m<alen )
{
if(a[m]==b[n])
{
n++;
}
if(n==blen)
break;
m++;
tt++;
}
if(n==blen)
{
length[k]=tt;
}
else
length[k]=0;
k++;
}
for(i=0;i<count;i++)
{
printf("\nPosition and length:");
printf("%d,",found[i]);
printf("%d",length[i]);
}
}
void main()
{
clrscr();
commonwindow();
getch();
}
The final Found array contains the position of posibble common windows in A array and the corresponding Length array contains its length.Length zero denotes that it is not a common window.We can get the minimum window using these arrays.....
Space complexity:2O(n)
Time Complexity:O(n^2) in worst case
Can this be done better????Try for many test cases
public class main {
public static void main(String args[])
{
int z=0;
int flag=0;
int[] oaray=new int[15];
int[] qaray={4,8,10};
int[] subindex = new int[5];
for(int i=0;i<12;i++)
oaray[i]=i+1;
for(int i=0;i<12;i++)
{
if(oaray[i]==qaray[0])
{
flag=1;
subindex[z++]=i;
for(int j=1;j<3;)
{
if(oaray[++i]==qaray[j])
{
subindex[z++]=i;
j++;
}
}
}
if(flag==1)
break;
}
for(int a=0;a<3;a++)
System.out.println(subindex[a]);
}
}
Let the data array be { 1, 2, 5, 4, 1,5, 2, 3, 5 }
Query array = { 1, 2, 5}
Create a array pos = { -1 , -1, -1 }
min_window_start=0,min_window_end=n-1, min_len=n;
Search the data array from n-1 to 0 and see whether you find any matching
in query array, if there is matching update the index in pos array,
if, it maintains the increasing sequence of positions. If all positions are filled
find the distances between 1st and last element, and check whether it is better than
earlier min_len, if it is update the new value for all the min_* variable.
When you reach zero, you got the minimum window, in the min array.
public static void containsAllInSeq(char a[] , char b[]){
int n = a.length;
int m = b.length;
int j, k;
for(int i = 0; i <= n-m; i++){
if(a[i] == b[0]){
j = i+1;
k = 1;
while((j < i+m) && (a[j] == b[k])){
j++; k++;
}
if(k==m){
System.out.println("SubString found at index "+i);
return;
}
}
}
System.out.println("Not Found");
}
nlog(n) solution
use string as example
arr1: a a * b * * c * * * a * * b * c
location: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
arr2:abc
hash arr1, Hash<list<int>> hash
hash[arr[i]]->push_back(i);
so the hash become:
a: 1,2,11
b: 4,14
c: 7,16
begin=0
end=0;
while(true){
//expand the window by move end to right
then for j=1:sizeof(arr2)
nextbegin=find the first element in hash[arr2[j]] which is >=begin
if can not find ,then break;
begin=nextbegin+1;
}
end=begin-1;//find one match ,but the left may move right to reduce the window
//reduce the window by move begin to right
tmp=end
for j=sizeof(arr2)-1:1
tmp=find the first element in hash[arr2[j]] which is <tmp
}
begin=tmp;
update minLength use [begin,end];
begin++;
}
every match use m*log(n)*2 time, if arr2 is not like aaaaabbbbb(continues element,which need to optimazed by match several repeated elements), there are at most n/m matches, so n/m * mlog(n)=nlog(n)
update:
for j=sizeof(arr2)-1:1
tmp=find the first element in hash[arr2[j]] which is > tmp
}
nlog(n) solution
use string as example
arr1: a a * b * * c * * * a * * b * c
location: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
arr2:abc
hash arr1, Hash<list<int>> hash
hash[arr[i]]->push_back(i);
so the hash become:
a: 1,2,11
b: 4,14
c: 7,16
begin=0
end=0;
while(true){
//expand the window by move end to right
then for j=1:sizeof(arr2)
nextbegin=find the first element in hash[arr2[j]] which is >=begin
if can not find ,then break;
begin=nextbegin+1;
}
end=begin-1;//find one match ,but the left may move right to reduce the window
//reduce the window by move begin to right
tmp=end
for j=sizeof(arr2)-1:1
tmp=find the first element in hash[arr2[j]] which is <tmp
}
begin=tmp;
update minLength use [begin,end];
begin++;
}
every match use m*log(n)*2 time, if arr2 is not like aaaaabbbbb(continues element,which need to optimazed by match several repeated elements), there are at most n/m matches, so n/m * mlog(n)=nlog(n)
public int findWindow (m) {
public static int start = end = 0;
public static int bIndex = 1;
// small problem
if(m < k) {
return 0;
}
// sub-problem
smallestWindow = findWindow (m-1);
// find out next steps from the sub-problem
if(a[m] == b[bIndex]) {
if(bIndex == 1) {
start = m;
}
else if(bIndex == k) {
end = m;
bIndex = 0;
}
bIndex++;
}
if(start < end) {
if(end - start + 1 < smallestWindow) {
smallestWindow = end - start + 1;
}
}
return smallestWindow;
}
ideone.com/5gElF
- abc January 17, 2011Found this.This should work if the query array doesnt have elements that repeat