vivek
BAN USER- 10of 10 votes
Answershow to merge two binary search tree into balanced binary search tree.. Let there be m elements in first tree and n elements in the other tree. Your merge function should take O(m+n) time with in constant space.
- vivek in United States
Examples:
A Balanced BST 1
90
/ \
70 110
A Balanced BST 2
60
/ \
5 800
output :-->
70
/ \
60 90
/ \
5 800| Report Duplicate | Flag | PURGE
Google Computer Scientist Algorithm - -3of 3 votes
Answersplease read full question before ans,
- vivek in United States
time complexity to merge k sorted arrays of size n each where space is not constraint and merge them with in m swap( m is total no of element i.e m=k*n )
Example:
Input:
k = 5, n = 4
arr[][] = { {3, 33, 55, 71},
{29, 63, 64, 88},
{100,999, 1100, 1800}
{18,99, 155, 180}
{360,480, 590, 620}} ;
Output: 3 18 29 33 55 63 64 71 88 99 100 155 180 360 480 590 620 999 1100 1800
==> ( " sort this array with in 15 swap or insertion ")| Report Duplicate | Flag | PURGE
Microsoft Computer Scientist Algorithm
import java.io.*;
public class RevSentence {
public static void main(String args[]) throws IOException
{
String s= new String();
BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
s=br.readLine();
char a[]=s.toCharArray();
int len=a.length;
// Reverse whole array
int j=len-1;
for(int i=0;i<=(len-1)/2;i++)
{
char temp=a[i];
a[i]=a[j];
a[j]=temp;
j--;
}
int start=0,end=0;
for(int i=0;i<a.length;i++)
{ // Reverse array word by word
if( a[i]==' ' || i==a.length-1)
{
end=i-1;
if( i==a.length-1) // to handle last word
{
end=a.length-1;
}
int k=end;
for(j=start;j<=(start+end)/2;j++)
{
char temp=a[j];
a[j]=a[k];
a[k]=temp;
k--;
}
start=end+2; // start of next word
}
}
String b=new String(a);
System.out.println(b);
}
}
/*
Output:
welcome to hell
hell to welcome
*/
Time complexity :- O(n)
- vivek December 27, 2015
Using sorting,
Time complexity : o(nlogn)
using hashing,
Time complexity : o(n)
- vivek December 27, 2015