Ali_BABA
BAN USERFind the preorder traversal of both lists , this gives the list in ascending order.
Copy it in an array and then call BST with the array
Running time
O(n) + O(m) + c(m+n) + O(m+n)
where n- no of elements in tree 1
m= no of elements in tree2
c- constant time to copy each element to an array
O(m+n) - time for BST algo to construct a BST
we can use NTP algorithm to deal with this situation.it uses a hierarchical, semi-layered system of levels of clock sources.
This algorithm is a class of mutual network synchronization algorithm which allows for use-selectable policy control in the design of the time synchronization and evidence model. NTP supports single inline and meshed operating models in which a clearly defined master source of time is used ones in which no penultimate master or reference clocks are needed.
In NTP service topologies based on peering all clocks equally participate in the synchronization of the network by exchanging their timestamps using regular beacon packets. In addition NTP supports a UNICAST type time transfer which provides a higher level of security. NTP performance is tunable based on its application and environmental loading as well.
1. C by Kernighan and Ritchie
2. Algorithms by Thomas H Cormen (a great book for algos)
3. C++ reference by Herbert Schildt
4. Thinking in Java
5. UNIX - Sumitabha Das
6. The C Odessey
7. Exploring C by Yashwant Kanetkar (Covers most of Ritchie concepts)
8. Test your C skills, Test Your C++ Skills
9. Operating Systems ( "Silberschatz" is enough)
For interview questions refer:
1. Crack The Interview
2. Orkut Community Forum - Target Placements
3.careercup (a great site for MS and Amazon interview questions)
For smoothing your algorithm skills:
1.Algorithm Design(John Klenberg & Eva Tordas)
if random generator generates number from a to b
then the first number it has to select from a to b-9( because it has to select next 9 more consecutive number)
so the probability of selecting first number will be->((b-9)-a)/b-a
=>(b-a-9)/(b-a)
for second no.->1/b-a
for third no.->1/b-a
..
..
..
for tenth no.->1/b-a
so the total prob-
(b-a-9)/b-a * 1/(b-a)^9
=>(b-a-9)/(b-a)^10
struct node *reverse (struct node *head, int k)
{
struct node* current = head;
struct node* next;
struct node* prev = NULL;
int count = 0;
while (current != NULL && count < k)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}
if(next != NULL)
{ head->next = reverse(next, k); }
return prev;
}
Let’s assume a given string S represented by the letters A1, A2, A3, ... , An
To permute set S, we can select the first character, A1, permute the remainder of the string to get a new list. Then, with that new list, we can “push” A1 into each possible position.
For example, if our string is “abc”, we would do the following:
1. Let first = “a” and let remainder = “bc”
2. Let list = permute(bc) = {“bc”, “cd”}
3. Push “a” into each location of “bc” (--> “abc”, “bac”, “bca”) and “cb” (--> “acb”, “cab”, “cba”)
4. Return our new list
Now, the code to do this:
public static ArrayList<String> getPerms(String s) {
ArrayList<String> permutations = new ArrayList<String>();
if (s == null) { // error case
return null;
} else if (s.length() == 0) { // base case
permutations.add(“”);
return permutations;
}
char first = s.charAt(0); // get the first character
String remainder = s.substring(1); // remove the first character
ArrayList<String> words = getPerms(remainder);
for (String word : words) {
for (int j = 0; j <= word.length(); j++) {
permutations.add(insertCharAt(word, first, j));
}
}
return permutations;
}
public static String insertCharAt(String word, char c, int i) {
String start = word.substring(0, i);
String end = word.substring(i);
return start + c + end;
}
This solution takes O(n!) time, since there are n! permutations.
int column(char *str)
{
int *p1,*p2;
p1=p2=str;
while(p2)p2++;
p2--//p2 ponting to last char of string and p1 to first char
int i=0,sum=0;
while(p2!=p1)
{
int k=(66-(int)(*p2));//converting char to corresponding integer eg. A=1,B=2,Z=26...
sum+=k*pow(26,i++);
}
return sum;
}
if Rows are sorted left to right in ascending order. Columns are sorted top to bottom in ascending order....
This algorithm works by elimination. Every move to the left (--col) eliminates all the elements below the current cell in that column. Likewise, every move down eliminates all the elements to the left of the cell in that row.
boolean FindElem(int[][] mat, int elem, int M, int N) {
int row = 0;
int col = N-1;
while (row < M && col >= 0) {
if (mat[row][col] == elem) {
return true;
} else if (mat[row][col] > elem) {
col--;
} else {
row++;
}
}
return false;
}
void delete(node *head,int n)
{
node *current=head->next;
node *prev=head;
node *temp;
while(prev)
{
if(head->value==n)
{
temp=head;
head=head->next;
prev=current;
current=current->next;
}
elseif(current->value==n)
{
temp=current;
prev->next=current->next
current=current->next;
}
else
{prev=current; current=current->next;}
free(temp)
}
One solution is to use two priority heaps: a max heap for the values below the median, and a min heap for the values above the median. The median will be largest value of the max heap. When a new value arrives it is placed in the below heap if the value is less than or equal to the median, otherwise it is placed into the above heap. The heap sizes can be equal or the below heap has one extra. This constraint can easily be restored by shifting an element from one heap to the other. The median is available in constant time, so updates are O(lg n).
private Comparator<Integer> maxHeapComparator, minHeapComparator;
private PriorityQueue<Integer> maxHeap, minHeap;
public void addNewNumber(int randomNumber) {
if (maxHeap.size() == minHeap.size()) {
if ((minHeap.peek() != null) &&
randomNumber > minHeap.peek()) {
maxHeap.offer(minHeap.poll());
minHeap.offer(randomNumber);
} else {
maxHeap.offer(randomNumber);
}
}
else {
if(randomNumber < maxHeap.peek()){
minHeap.offer(maxHeap.poll());
maxHeap.offer(randomNumber);
}
else {
minHeap.offer(randomNumber);
}
}
}
public static double getMedian() {
if (maxHeap.isEmpty()) return minHeap.peek();
else if (minHeap.isEmpty()) return maxHeap.peek();
if (maxHeap.size() == minHeap.size()) {
return (minHeap.peek() + maxHeap.peek()) / 2;
} else if (maxHeap.size() > minHeap.size()) {
return maxHeap.peek();
} else {
return minHeap.peek();
}
}
int max(int *a,int start,int end))
{
int mid=(start+end)/2;
if(a[mid-1]<a[mid] && a[mid]<a[mid+1])//mid falls in increasing series
return(max(a,mid+1,end));//search in next half
elseif((a[mid-1]>a[mid] && a[mid]>a[mid+1])//mid falls in decreasing series
return(max(a,start,mid-1));//search in previoushalf
else return a[mid];
}
int maxDepth(node* root)
{
if(NULL == root)
return 0;
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return 1 + (leftDepth > rightDepth ? leftDepth:rightDepth);
}
int minDepth(node* root)
{
if(NULL == root)
return 0;
int leftDepth = minDepth(root->left);
int rightDepth = minDepth(root->right);
return 1 + (leftDepth < rightDepth ? leftDepth:rightDepth);
}
int isBalanced(node* root)
{
if(maxDepth(root) - minDepth(root) > 1)
return 0;
else
return 1;
}
The number of nodes per level contributes to the density of the tree. Intuitively, density is a measure of the size of a tree (number of nodes) relative to the height of the tree.
so density can be calculated as- d=(size)/(height)
float density(struct node*root)
{
return(size(root)/height(root));
}
//calculating size
int size(struct node*root)
{
if(root==NULL) return 0;
else
return(size(root->left)+size(root->right)+1);
}
//calculating height
int height(struct node* root)
{
int l,r;
if(root==NULL) return 0;
else
{
l=height(root->left);
r=height(root->right);
if(l>r)return ++l;
else return ++r;
}
}
void fibonacci(int n, int len);
{
if(len<=0 ||n<0)cout<<"wrong Input";
else
{
for(int i=1; i<=len;i++)
cout<<fibo(n-1,i);
}
}
int fibo(int n, int len)
{
if(len==1)return n;
if(len==2)return (n+1);
return fibo(n-2) +fibo(n-1);
}
//test case:
1.(0,0)
2.(0,1)
3.(0,2)
4.(5,0)
5.(5,5)
6.(-1,-1)
void balancepoint(int *a ,int n)
{
int i,sum1=0,sum2=0,avg1,avg2;
//find sum of the array
for(i=0;i<n;i++)
sum2+=a[i];
//find left hand side and right hand side avg.
for(i=0;i<n;i++)
{
sum1+=a[i]; avg1=sum1/(i+1);
sum2-=a[i]; avg2=sum2/(n-i-1);
if(avg1==avg2)
{cout<<i ;return;}
}
}
car A in 10 simulation will move 1 time ==> 5feet
- Ali_BABA November 06, 2012car B in 10 simulation will move 6 time ==>1X6 ==> 6feet
so in 100 simulation :
Car A : 50 feet ;Car B :60 feet
so,mathematically car B have more chance to win the race. we know that when no. of experiment increases then outcome automatically get more aligned toward the mathematical output(drawn from probability).
here 100 is a large no. so we can say Car B will win and result will me according to mathematical analysis.