Clone a Binary Tree with Random Pointers Given a Binary Tree where every node has following structure.struct node {int key;struct node *left,*right,*random;}The random pointer points to any random node of the binary tree and can even point to NULL, clone the given binary tree.You can get code in c++ Here: https://gist.github.com/gk1721/36775e17719d460ac231
Saturday, September 6, 2014
Wednesday, August 27, 2014
Linkage in c
Translation unit:
A program in a single file - single translation unit.
sharing functions and variable btw translation units : possible if variables and function have external linkage
by default global variable and non static functions (non static variables also) has external linkage so can be shared
Ex
file1.c file2.c
int a=0; extern int a; // refering to file1.c's a
void abc() void ab()
{ {
abc(); //
notshared(); // error can't access notshared
} }
static void notshared()
{
}
variable and functions which has internal linkage like static functions and variables can't be accessed in other files(Translation units).
No linkage : variables within function
Linkage :
1. External
2. Internal
3. No linkage
A program in a single file - single translation unit.
sharing functions and variable btw translation units : possible if variables and function have external linkage
by default global variable and non static functions (non static variables also) has external linkage so can be shared
Ex
file1.c file2.c
int a=0; extern int a; // refering to file1.c's a
void abc() void ab()
{ {
abc(); //
notshared(); // error can't access notshared
} }
static void notshared()
{
}
variable and functions which has internal linkage like static functions and variables can't be accessed in other files(Translation units).
No linkage : variables within function
Linkage :
1. External
2. Internal
3. No linkage
Saturday, August 2, 2014
Sorting: bubble, selection,insertion, quick, merge, counting sort programs in c
Bubble sort:
#include<stdio.h>// compare adjacent elements and swap if needed until whole is not sorted
int arr[]={3,8,6,1,9,6,3,1,10,7,8,5,16};
int size;
void main()
{
size=sizeof(arr)/sizeof(int);
int out[size];
int i,j;
for(i=size-1;i>=0;i--)
{
for(j=0;j<i-1;j++)
{
if(arr[j]>arr[j+1])
{
int tmp;
tmp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp;
}
}
}
printf("size= %d\n",size);
for(i=0;i<size;i++)
printf("%d ",arr[i]);
}
Selection sort:
#include<stdio.h>
// find minimum and bring it to top
int arr[]={3,8,6,1,9,6,3,1,10,7,8,5,16};
int size;
void main()
{
size=sizeof(arr)/sizeof(int);
int out[size];
int i,j;
for(i=0;i<size-1;i++)
{
for(j=i+1;j<size;j++)
{
if(arr[i]>arr[j])
{
int tmp;
tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
}
}
printf("size= %d\n",size);
for(i=0;i<size;i++)
printf("%d ",arr[i]);
}
Insertion sort:
// insert element at right place in list
int arr[]={8,3,6,1,9,6,3,1,10,7,8,5,16};
int size;
void main()
{
size=sizeof(arr)/sizeof(int);
int out[size];
int i,j,v;
for(i=1;i<size;i++)
{
v=arr[i];
j=i;
while(arr[j-1]>v&&j>=1)
{
arr[j]=arr[j-1];
j--;
}
arr[j]=v;
}
printf("size= %d\n",size);
for(i=0;i<size;i++)
printf("%d ",arr[i]);
}
------------------------------------------------------------------
Quick sort:
-----------------------------------------------------------------
#include<stdio.h>int a[]={4,2,7,8,5,1,0,6};
int size;
void print()
{
int i;
for(i=0;i<size;i++)
printf("%d ",a[i]);
}
void swap(int left,int right)
{
int tmp=a[left];
a[left]=a[right];
a[right]=tmp;
}
int partition(int l,int r)
{
int x=a[l];
int left=l;
int right=r;
while(left<right)
{
while(a[left]<=x)
left++;
while(a[right]>x)
right--;
if(left<right)
swap(left,right);
}
a[l]=a[right];
a[right]=x;
//printf("\nPivot= %d ",a[right]);
//print();
//printf("\n");
return right;
}
void quicksort(int l,int r)
{
// printf("%d %d\n",l,r);
int i;
if(r>l)
{
int p=partition(l,r);
quicksort(l,p-1);
quicksort(p+1,r);
}
}
void main()
{
size=sizeof(a)/sizeof(a[0]);
//print();
int p=0;
int l=0,r=size;
quicksort(l,r);
print();
}
----------------------------------------------------------
Merge Sort:
----------------------------------------------------------
#include<stdio.h>
int a[]={3,3,6,1,9,6,3,1,10,7,8,5,16};
int size;
int tmp[13];
void merge(int l,int m,int r)
{
int tmp[r-l+1];
int p=0;
int i=0,j=0;
if(a[l]>a[r])
{
for(i=m;i<r+1;i++)
tmp[p++]=a[i];
for(i=l;i<m;i++)
tmp[p++]=a[i];
}
else if(a[m]>a[m-1])
{
for(i=l;i<m;i++)
tmp[p++]=a[i];
for(i=m;i<r+1;i++)
tmp[p++]=a[i];
}
else
{
i=l;
j=m;
while((i<m)&&(j<r+1))
{
if(a[i]<a[j])
{
tmp[p++]=a[i++];
}
else if(a[i]>a[j])
{
tmp[p++]=a[j++];
}
else
tmp[p++]=a[i++];
}
if(i<m)
{
//printf("\nIn case 1\n");
int q;
for(q=i;q<m;q++)
{
tmp[p++]=a[q];
}
}
else if(j<r+1)
{
// printf("\nIn case 2p=%d\n",p);
int q;
for(q=j;q<r+1;q++)
{
tmp[p++]=a[q];
}
}
}
for(i=l;i<r+1;i++)
{
a[i]=tmp[i-l];
}
}
void mergesort(int l,int r)
{
int m;
if(r>l)
{
m=(l+r)/2;
mergesort(l,m);
mergesort(m+1,r);
merge(l,m+1,r);
}
}
void main()
{
size=sizeof(a)/sizeof(a[0]);
int l=0,r=size-1;
mergesort(l,r);
int i;
for(i=0;i<size;i++)
printf("%d ",a[i]);
}
--------------------------------------------------
--------------------------------------------------
Counting sort:
-------------------------------------------------
#include<stdio.h>
int a[]={1,5,6,4,8,9,3,8,0,10,16,21,6};
int size,max;
void main()
{
size=sizeof(a)/sizeof(a[0]);
int i;
int out[size];
max=0;
for(i=0;i<size;i++)
{
if(a[i]>max)
max=a[i];
}
int c[max+1];
for(i=0;i<max+1;i++)
{
c[i]=0;
}
for(i=0;i<size;i++)
{
c[a[i]]=c[a[i]]+1;
}
for(i=1;i<max+1;i++)
{
c[i]=c[i]+c[i-1];
}
for(i=size;i>=0;i--)
{
out[c[a[i]]-1]=a[i];
c[a[i]]=c[a[i]]-1;
}
for(i=0;i<size;i++)
{
printf("%d ",out[i]);
}
}
Insert records from a table to other table
Note: While inserting records from a table to other table values clause must not be used
Example:
insert into highAchiever (name, age) (select name, age from salesperson where salary > 100000);
Friday, August 1, 2014
SQL JOINS
You have following tables
| Salesperson | Customer | ||||||||||||||||||||||||||||||||||||||||||||||||
|
|
| Orders | ||||||||||||||||||||||||||||||||||||||||
|
Given the tables above, find the following:
a. The names of all salespeople that have an order with Samsonic.
a. The names of all salespeople that have an order with Samsonic.
solution:
SELECT distinct name FROM `salesperson` WHERE id in(select salesperson_id from customer,orders where id=cust_id AND name='Samsonic');
if you write above query like:
SELECT distinct name FROM `salesperson` WHERE id=(select salesperson_id from customer,orders where id=cust_id AND name='Samsonic');
It is invalid query because subquery returning multiple records so it can't be compared.
SELECT distinct name FROM `salesperson` WHERE id=(select salesperson_id from customer,orders where id=cust_id AND name='Samsonic');
It is invalid query because subquery returning multiple records so it can't be compared.
Insert multiple rows in mysql
MySql :)
insert into customer values(4,'Samsonic','pleasant','J'),
(6,'Panasung','oaktown','J'),
(7,'Samony','jackson','B'),
(9,'Orange','Jackson','B');
insert into customer values(4,'Samsonic','pleasant','J'),
(6,'Panasung','oaktown','J'),
(7,'Samony','jackson','B'),
(9,'Orange','Jackson','B');
Insert into Multiple rows in single query: SQL
Method 1 - Traditional InsertINSERT INTO #SQLAuthority (ID, Value)VALUES (1, 'First');INSERT INTO #SQLAuthority (ID, Value)VALUES (2, 'Second');INSERT INTO #SQLAuthority (ID, Value)VALUES (3, 'Third');
TRUNCATE TABLE #SQLAuthority;
Method 2: INSERT…SELECT
INSERT INTO #SQLAuthority (ID, Value)
SELECT 1, 'First'UNION ALLSELECT 2, 'Second'UNION ALLSELECT 3, 'Third';
TRUNCATE TABLE #SQLAuthority;
Method 3: SQL Server 2008+ Row Construction
-- Method 3 - SQL Server 2008+ Row ConstructionINSERT INTO #SQLAuthority (ID, Value)VALUES (1, 'First'), (2, 'Second'), (3, 'Third');
Subscribe to:
Comments (Atom)