jackass
BAN USERThere can be two cases.
(1) One in which the subtree should completely be a BST.
(2) Other in which a part of subtree can be a BST.
So which one is being referred ?
(1)
bool findLargestBST(tree *root, int *c)
{
if(root == NULL)
{
return true;
}
int x = 0;
int y = 0;
bool p = findLargestBST(root->left, &x);
bool q = findLargestBST(root->right, &y);
if(root->left)
root->min = root->left->min;
else
root->min = root->data;
if(root->right)
root->max = root->right->max;
else
root->max = root->data;
if(p && q && (root->left == NULL || root->data > root->left->max) && (root->right == NULL || root->right->min > root->data))
{
*c = (x + y + 1);
return true;
}
*c = max(x, y);
return false;
}
Xi = sum(xi - xj) for all j in occupied.
Yi = sum(yi - yj) for all j in occupied.
Zi = sum(zi - zj) for all j in occupied.
We need to find all Xi, Yi, Zi and find the point with minimum (Xi + Yi + Zi). All this can be done in O(nlogn) by doing as follows:
(a) Sort x coordinates and keep these in A. Similarly Y, Z in B and C.
(b) X[A[0].id] can be calculated in O(n)
Note: A[x].id gives the actual index of coordinate x before getting sorted.
(c) X[A[1].id] = X[A[0].id] - (n-2) *(A[1].x - A[0].x);
Hence Xi's can be calculated in O(n), similarly Yi's , Zi's.
answer = (xi, yi) such that (Xi + Yi + Zi) is maximum.
int reachLastFromSomeIndex(int a[], int n, int start)
{
int dp[n-start];
dp[0] = 0;
for(int i = 1; i < n - start; i++)
{
dp[i] = 10000000;
for(int j = 0; j < i; j++)
{
if(a[j + start] >= (i-j))
{
dp[i] = min(dp[i], dp[j] + 1);
}
}
}
print(dp, n - start);
return dp[n-start-1];
}
The below solution works. I answered this in my Google Interview :
void findSubstring(char s1[], char s2[])
{
// s2 is Ssmall
// s1 is Sbig
int hash[26] = {0};
int hash1[26] = {0};
for(int i = 0; i < len(s2); i++)
hash[s2[i] - 'a'] += 1;
int left = 0;
int minL = 0;
int minR = len(s1) - 1;
for(int i = 0; i < len(s1); i++)
{
if(flag == 0)
left = i;
if(hash[s1[i] - 'a'] != 0)
{
hash1[s1[i] - 'a'] += 1;
if(hash1[s1[i] - 'a'] > hash[s1[i] - 'a'])
{
while(hash1[s1[i] - 'a'] > hash[s1[i] - 'a'])
{
hash1[s1[left] - 'a']--;
left++;
}
}
int u;
for(u = 0; u < 26; u++) // checking if hash1 has same entries as hash.
{
if(hash[u] != hash1[u])
break;
}
if(u == 26) // If hash1 has same entries as hash then we have one more substring containing all entries of Ssmall
{
if(minR - minL > i - left)
{
minL = left;
minR = i;
}
}
flag = 1;
}
else if(flag == 1)
{
reset(hash1); // make all hash1 entries to zeros.
flag = 0;
}
}
for(int i = minL; i <= maxL; i++)
cout << s[i] <<;
cout << endl;
return;
}
there is an alternate solution .
(1) Select pairs of elements i.e 1, 2; 3, 4; 5, 6; ....
(2) compare if elements of pair are equal. If equal keep one element. Else remove that pair. Do this recursively until there is one element left.
ex:
Given array ->
10, 20 , 10, 10, 20, 20, 10, 10
Step 1 : (10, 20) , (10, 10), (20, 20), (10, 10)
Step 2 : (), (10), (20), (10) => 10, 20, 10
Step 3 : (10, 20), 10
Step 4 : (), 10 => 10
Hence 10 is the number.
Why don't we use the basic mathematical way to find if a number is a perfect square or not.
The code below illustrates that:
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
void findNearest(char s[], char q[])
{
char s1[20];
int t = atoi(s);
cout << t << endl;
int val;
int x, y, xVal;
int temp;
for(int i = 0; i < 10; i++)
{
if(q[0] != '\0')
{
sprintf(s1, "%s%d", q, i);
x = atoi(s1) ;
}
else
{
x = i;
}
y = x * i;
if(y <= t)
{
val = y;
temp = i;
xVal = x;
}
}
sprintf(q, "%d", xVal + temp);
y = t - val;
sprintf(s,"%d",y);
}
bool PerfectSquare(char s[])
{
int l = strlen(s);
char s1[20];
char q[10];
q[0] = '\0';
if(l == 0) return false;
for(int i = 0; i < l;)
{
if( l % 2 != 0 && i == 0)
{
sprintf(s1, "%c", s[i]);
i++;
}
else
{
if(i == 0)
sprintf(s1, "%c%c", s[i], s[i+1]);
else
sprintf(s1, "%s%c%c", s1, s[i], s[i+1]);
i+=2;
}
findNearest(s1, q);
}
int x = atoi(s1);
if(x != 0)
return false;
return true;
}
int main(void)
{
char s[20];
cin >> s;
if(PerfectSquare(s))
cout << "True" << endl;
else
cout << "False" << endl;
return 0;
}
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
void swap(int *a, int *b)
{
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;
}
void concatinate(int a[], int n)
{
char s[100];
int t1, t2;
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
sprintf(s, "%d%d",a[i],a[j]);
t1 = atoi(s);
sprintf(s, "%d%d",a[j],a[i]);
t2 = atoi(s);
if(t1 < t2)
swap(&a[i], &a[j]);
}
}
}
int main(void)
{
int a[] = {4, 94, 9, 14, 1};
concatinate(a, 5);
for(int i = 0; i < 5; i++)
{
cout << a[i];
}
cout << endl;
}
Partition(int a[], int l, int n1, int n2, int k1, int k2)
{
int S1 = sum(a[0 ... l/2 - 1]) + k1;
int S2 = sum(a[l/2 .... l - 1]) + k2;
n1 = l/2 ;
n2 = l/2 ;
if(k1 != 0 && k2 == 0)
n1 += k1;
else if(k2 != 0 && k1 == 0)
n2 += k2;
if(S1 * n1 > S2 * n2)
{
Partition(a, l / 2, 0, n2, 0, S2);
}
else if( S1 * n1 > S2 * n2)
{
Partition(a, l / 2, n1, 0, S1, 0);
}
else
return l/2;
}
// call in main
Partition(a, l, 0, 0, 0, 0);
Divide the array into two equal halves array1, array2. Say each one has sum S1, S2.
if(S1 > S2)
Then recurse on left array.
(i.e
divide array1 in two equal halves S11, S12.
if(S11 < S22 + S2)
Then recurse on array[n/4... n/2]....
else if (S11 > S22 + S2)
Then recurse on array[0... n/4]
and so on....
)
else if( S1 < S2)
Recurse on right half....
While implementing BFS, we enque the neighbours of the present node into the queue. Then we deque each of them and again run a BFS on them sequentially. Because we have a parallel processing available, we can execute them in parallel instead of sequential. But we need to keep the common information like visited nodes etc with each of the process.
- jackass October 17, 20111) Detect Loop using Floyd’s Cycle detection algo and get the pointer to a loop node.
2) Count the number of nodes in loop. Let the count be k.
3) Fix one pointer to the head and another to kth node from head.
4) Move both pointers at the same pace, they will meet at loop starting node.
(1) Find the distinct elements and put them in b1, b2, b3;
(2) Keep 3 pointers a1 = 0, a2 = 0, a3 = length - 1;
for(int i = 0 ; i < length ; i++)
{
if( arr[a2] == b1 )
{
swap(arr[a2], arr[a1])
a1++;
}
else if( arr[a2] == b3 )
{
swap(arr[a2], arr[a3])
a3--;
}
a2++;
}
(1) Put the elements in an array.
(2) Divide array into two parts. Let it be A and B.
(3) Let ASum be max sum in A and BSum be max sum in B.
(4) Let AlSum be array sum left to ASum array and ArSum be array sum right to th
e ASum array. Similarly are BlSum and BrSum.
(5)
maxSum = ASum;
if( BSum > maxSum )
maxSum = BSum;
if(ASum + AlSum + BrSum + BSum > maxSum)
maxSum = AlSum + ASum + BrSum + BSum;
if(ASum + ArSum + BlSum + BSum > maxSum)
maxSum = ASum + ArSum + BlSum + BSum > maxSum;
print maxSum
dude ... it is mentioned that you should not be using any linear selection algorithm...
- jackass December 04, 2011