coderBon
BAN USER//'n' is the size of the array 'arr[]'
/*according to the question 'n' has to be even
if 'n' is odd then there is a confusion on what will
be the middle element - unique or non-unique*/
int element(int arr[],int n)
{
int tmp=0,ele;
for(int i=0;i<n/2;i++)
{
tmp^=arr[i]; //xor operation
}
if(tmp==0)
ele = arr[i-1];
else
ele = arr[i];
return ele;
}
Time complexity - O(n/2) = O(n)
void longestSubarray(int a[])
{
int n=sizeof(a)/sizeof(a[0]); //length of array
int max=0,*hash;
int subArray_start=0,subArray_end=0;
for(int i=0;i<n;i++) //get maximum and minimum in array
{
if(max<a[i])
max=a[i];
}
hash=new int[max+1](); //array values initialized to zero
for(i=0;i<n;i++)
{
if(hash[a[i]]==1)
{
delete hash;
hash=new int[max-min+1]();
subArray_start=i--; //initialize start of subarray
continue;
}
hash[a[i]]=1;
}
int tmp_strt=0,tmp_end=0;
for(i=0;i<=max;i++)
{
if(hash[i]==1 && (hash[i-1]==0|| i>=0))
tmp_start=i;
if(hash[i]==0)
tmp_end=i-1;
}
if(!tmp_end)
tmp_end=i-1;
while(n)
{
if(a[n]<=tmp_end || a[n]>=tmp_strt)
subArray_end=n; //initialize end of subarray
n--;
}
for(i=subArray_start;i<=subArray_end;i++) //print output
cout<<a[i]<<" ";
}
Time Complexity - O(4n)
This code will give a problem with negative numbers...Any ideas of improvement??
Your "printTree" function will return 0 to the main().
A little modification of your code is required:
void printTree(node *root,int i,int j,int a[])
{
static int len;
if(root)
{
if(!root->left && !root->right)
cout<<root->data<<" ";
else if(i>0 && j==0)
cout<<root->data<<" "; //printing left nodes
else if(i==0)
{
a[j]=root->data;
len=j;
}
fun(root->left,i+1,j,a);
fun(root->right,i,j+1,a);
}
return len;
}
void main()
{
node *root;
root=createTree(root); //this creates the tree
int a[50];
for(int len=printTree(root,0,0,a);len>=0;len--)
{
cout<<a[len]<<" ";
}
}
- coderBon August 22, 2012//return true if BT with root=node is a BST
int isBST(struct node* node, int min, int max,int *count)
{
/* an empty tree is BST */
if (node==NULL)
return 1;
/* false if this node violates the min/max constraint */
if (node->data < min || node->data > max)
return 0;
*count++;
/* otherwise check the subtrees recursively,
tightening the min or max constraint */
return
( isBST(node->left, min, node->data-1) && // Allow only distinct values
isBST(node->right, node->data+1, max)); // Allow only distinct values
}
struct node* largestSubTree(struct node *root)
{
int count=0;
static int tmp_count=0;
static struct node *node=NULL;
if(!root) return NULL;
if(isBST(root,INT_MIN,INT_MAX,&count))
if(count>tmp_count)
{
tmp_count=count;
node=root;
return node;
}
largestSubTree(R->left);
largestSubTree(R->right);
return node;
}
//prints tree in pre order traversal
void printTree(struct node *root)
{
if(!root)
return;
cout<<root->data<<" ";
printTree(root->left);
printTree(root->right);
}
void main()
{
struct node *root=NULL,temp;
root=createTree(root); //tree is created
if((temp=largestSubTree(root))!=NULL)
{
cout<<"The largest sub-tree which is a binary tree is:\n";
printTree(root);
}
else
{
cout<<"Such subtree does not exist";
}
}
This is in place array transpose.
#include <stdio.h>
int get_index(int idx, int N) {
return (idx % 2) * N + (idx / 2);
}
void swap(int *a,int *b)
{
int t=*a;
*a=*b;
*b=t;
}
void transform_array2(int *s, int len) {
int N = len / 2,i;
for(i = 0; i < len; i++) {
int new_idx = get_index(i, N);
while(new_idx < i) {
new_idx = get_index(new_idx, N);
}
printf("i: %d; new_idx: %d\n", i, new_idx);
swap(&s[i], &s[new_idx]);
}
for(i = 0; i < len; i++) {
printf("%d ", s[i]);
}
printf("\n");
}
int main()
{
int arr[]={1,2,3,4,5,6,7,8,9,10,11,12};
transform_array2(arr,12);
return 0;
}
Time complexity-O(n)
- coderBon August 19, 2012
Can be done in O(NlogK). Where N = total number of frequencies combined and K is the number of words.
For example:
W1: [4, 10, 15, 24, 26]
W2: [0, 3, 9, 12, 20]
W3: [5, 18, 22, 30]
The result is [3,5]
1. Use a minHeap and apply the similar logic of merging K sorted arrays. The structure of heap node is as follows.
2. Maintain a currMin and currMax to identify the current minimum and maximum values in the minHeap. Note that, as every node in the heap stores frequency of a unique word, which means all words will lie between [currMin,currMax]
3. currMin = heap[0].data and currMax = max(arr[wordArrayIndex][currentPosInArray],currMax)
4. In every loop check if(currMax-currMin) is minimum or not.
Dry Run:
The entire solution can be viewed here https://github.com/sohamchakravarty/InterviewPreparation/tree/master/rangeOfFrequencyOfAllWords
- coderBon May 12, 2016