## 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;}

}

}

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

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.