Google Interview Question Software Engineer / Developers
hash small array and look for big array elements in hash table one by one.
n -big array
m - small array
time - O(n+m)
space - O(m)
dono if its a a good idea why do we hash when we have to pattern match... i mean extra space and still u need to know if the hash keys are in an order...u might think of using linkedhashmap
A1 [1...n1]
A2 [1...n2]
int OneContainInOther(A1,l1, r1, A2,l2, r2) {
int index ;
if (r1 > l1 || r2 > l2)
return 0 ;
if (BinSearch(A2[r2], &index))
return (A1, l1, index - 1, A2, l2, r2 -1) ;
return 0;
}
Sort both A1 and A2
if (n1 > n2) // Check for A1 contains A2
OneContainInOther(A1, 1, n1, A2, 1, n2) ;
else // Check for A2 contains A1
OneContainInOther(A2, 1, n2, A1, 1, n1) ;
bool IsArrayConatain(int [] a, int [] b)
{
for(int i = 0; i< n; i++)
{
for(int j=0; j<m; j++)
{
if(a[i] == b[j])
{
for(int k = j + 1 ; k < m ; j++)
{
if(a[k] != b[k])
{
return false;
}
}
return true;
}
}
}
return false;
}
public class array_match {
/**
* @param args
*/
public static int check(int[] a,int[] b)
{
int j=0;
for (int i = 0; (i < a.length) && (j < b.length);i++)
{
if(a[i] == b[j])
{
j++;
}
else
{
j=0;
}
}
if (j == (b.length))
return 1;
else return 0;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a={1,2,3,4,5};
int[] b={2,3};
int[] c={2,5};
if (check(a,b)==1)
{
System.out.println("a and b Match");
}
else
System.out.println("a and b No Match");
if (check(a,c)==1)
{
System.out.println("a and c Match");
}
else
System.out.println("a and c No Match");
}
}
/**
* function for a method that takes two arrays and returns true if one array is contained in the other.
* @param container int[]
* @param contained int[]
* @return boolean
*/
public static boolean containsArray(int []container, int[] contained) {
int containerLenth = container.length;
int containedLength = contained.length;
if(containerLenth< containedLength){
return false;
}
int index = Arrays.binarySearch(container, contained[0]);
if(index != -1){
if(containerLenth - index < containedLength){
return false;
} else {
for (int i=0;i<containedLength;i++) {
if( container[index+i]!= contained[i]){
return false;
}
}
return true;
}
}
return false;
}
An O9n) algorithm :
public static bool isSubset(int[] a, int[] b)
{
int chk =0;
int v=-1;
int ct = 0;
for ( int i=0;i< b.Length; i++)
{
chk |= (1<< b[i]);
}
for( int i=0;i< a.Length;i++)
{
if ((chk & (1 << a[i])) > 0)
{
//kick off...///
if (v == -1)
{
v = i; ct++;
}
else if ((v > 0) && (i == v + 1))
{
v = i; ct++;
}
}
else if (ct == b.Length)
{
break;
}
else
{
v = -1; ct = 0;
}
}
if (v > 0) { return true; }
else { return false; }
}
please let me know if there are any errors....
thankyou!!
Assuming the n is much bigger than n
1. Scan m to find 1 element that is not repetitive O(m).
2. If found them binary search that search element in array n, O(long n)
3. If found match the remaining patter from m around that elment O(m)
so for this case where there is at least 1 non repetitive in m complexity = O(2m) + O(log n)
If there is no non-repetitve element the it will be O(m.log n)
Assuming the n is much bigger than m
1. Scan m to find 1 element that is not repetitive O(m).
2. If found them binary search that search element in array n, O(long n)
3. If found match the remaining patter from m around that elment O(m)
so for this case where there is at least 1 non repetitive in m complexity = O(2m) + O(log n)
If there is no non-repetitve element the it will be O(m.log n)
just use dp.......KMP will do fine in o(n) time complexity
- Anonymous February 16, 2011