codeAddict
BAN USER
This question is not clear to me. If possible can you please explain the question in brief manner. Seems like it is a system design question
- codeAddict August 19, 2016package FindingSumOfSmallerElementsOnLeft;
public class FindingSumOfSmallerElementsOnLeft {
public static void main(String[] args) {
int[] Arr = { 2, 3, 8, 6, 1 ,10};
//Sum of prev small numbers in arr
BST ob = new BST();
for (int i = 0; i < Arr.length; i++)
{
System.out.println(ob.AddNodeAndReturnSumOfPrevSmallNumInArr(Arr[i]));
}
ob.inOrder();
}
}
class BST
{
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public int Sum; //for SumOfPrevSmallNumInArr
public TreeNode(int val)
{
this.data = val;
this.left = null;
this.right = null;
this.Sum = 0;
}
public TreeNode(int val, int index)
{
this.data = val;
this.left = null;
this.right = null;
this.Sum = 0;
}
public TreeNode()
{
this.data = 0;
this.left = null;
this.right = null;
this.Sum = 0;
}
}
TreeNode Root;
public BST()
{
Root = null;
}
public int AddNodeAndReturnSumOfPrevSmallNumInArr(int val)
{
TreeNode Node = new TreeNode(val);
if (Root == null)
{
Root = Node;
return 0;
}
TreeNode cur = Root;
TreeNode Prev = null;
int Sum = 0;
while (cur != null)
{
Prev = cur;
//If moving towards right add the current node's value and its
//sum value to the sum being calculated to return.
if (val >= cur.data)
{
Sum += cur.data + cur.Sum;
cur = cur.right;
}
//If moving towards left add the value to current node's sum.
else
{
cur.Sum += val;
cur = cur.left;
}
}
if (val >= Prev.data)
Prev.right = Node;
else
Prev.left = Node;
return Sum;
}
public void inOrder(){
inOrder(Root);
}
public void inOrder(TreeNode t){
if(t==null) return;
inOrder(t.left);
System.out.print(t.data + " ");
inOrder(t.right);
}
}
Fully working Code in java :::
Time Complexity :: O(n) Bottom Up Approach
Space Complexity :: O(1) not considering recursion stack space
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author nikhil.agrawal
*/
public class UnivaluedSubTree {
public static void main(String[] args) {
TreeNode root = new TreeNode(2);
TreeNode r2 = new TreeNode(2);
TreeNode r3 = new TreeNode(2);
TreeNode r4 = new TreeNode(3);
TreeNode r5 = new TreeNode(3);
TreeNode r6 = new TreeNode(3);
TreeNode r7 = new TreeNode(3);
root.left=r2;
root.right=r3;
r2.left=r4;
r2.right=r5;
r3.left=r6;
r3.right=r7;
countingUnivaluedTree(root);
}
static int count =0;
static void countingUnivaluedTree(TreeNode root)
{
countingUnivaluedTreeUtil(root);
System.out.println("Number of univalued trees :: " + count);
}
static boolean countingUnivaluedTreeUtil(TreeNode r )
{
if(r==null) return true;
boolean lB = countingUnivaluedTreeUtil(r.left);
boolean rB = countingUnivaluedTreeUtil(r.right);
if(lB && rB && (r.left==null || r.val==r.left.val) && (r.right==null || r.val==r.right.val))
{
count++;
return true;
}
return false;
}
}
class TreeNode
{
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
Question is not clear . Please explain.
- codeAddict March 17, 2016Complete Running code in java ::
1. Time Complexity :: O(n)
2. Space Complexity :: O(n)
class InternalNode {
int low;
int high;
int max;
InternalNode left;
InternalNode right;
@Override
public String toString() {
return "InternalNode{" +
"max=" + max +
", low=" + low +
", high=" + high +
'}';
}
}
public class IntervalTree {
public InternalNode insert(InternalNode root, int low, int high) {
if(root == null) {
InternalNode node = new InternalNode();
node.low = low;
node.high = high;
node.max = high;
return node;
}
if(low < root.low) {
root.left = insert(root.left, low, high);
} else {
root.right = insert(root.right, low, high);
}
root.max = Math.max(root.high, high);
return root;
}
public InternalNode isOverlap(InternalNode root, int low, int high) {
if(root == null) {
return null;
}
if(root.high >= low && root.low <= high) {
return root;
// return root;
}
if(root.left != null && root.left.max > low) {
return isOverlap(root.left, low, high);
} else {
return isOverlap(root.right, low, high);
}
}
public int isOverlapWithCount(InternalNode root, int low, int high , int count) {
if(root == null) {
return 0;
}
if(root.high >= low && root.low <= high) {
return 1+ (isOverlapWithCount(root.left, low, high , count) +
isOverlapWithCount(root.right, low, high, count)
);
}
if(root.left != null && root.left.max > low) {
return isOverlapWithCount(root.left, low, high , count);
} else {
return isOverlapWithCount(root.right, low, high, count);
}
}
public static void main(String args[]) {
IntervalTree it = new IntervalTree();
InternalNode root = null;
root = it.insert(root, 10, 15);
root = it.insert(root, 11, 13);
root = it.insert(root, 18, 21);
root = it.insert(root, 20, 25);
root = it.insert(root, 0, 7);
System.out.println(it.isOverlap(root, 8, 9));
System.out.println(it.isOverlap(root, 17, 17));
System.out.println(it.isOverlap(root, 21, 22));
// System.out.println(it.isOverlap(root, 21, 22));
System.out.println(it.isOverlap(root, 12, 18));
System.out.println(it.isOverlap(root, 24, 26));
System.out.println("total count = " + it.isOverlapWithCount(root, 10, 12,0));
}
}
Complete running Code in java ::
1. Time Complexity - O(nLogn)
2. Space Complexity - O(1) (Not considering recursion stack in space complexity)
public Node sortedListToBst()
{
Node temp=h;
int n=countNodes();
return formBalancedBST_inPlace_nlogn(temp,n);
// return formBalancedBST_outPlace_n(temp, n);//formBalancedBST_inPlace_nlogn(temp,n);
}
// In place conversion of DLL to Balanced BST
// Space Complexity : O(1)
// Time complexity: O(n)
//In-place conversion of Sorted DLL to Balanced BST
// The tree must be constructed in-place (No new DoublyLinkedNode should be
//allocated for tree conversion)
public Node formBalancedBST_inPlace_nlogn(Node head,int n)
{
// Base case
if(n<=0)
return null;
else if(n==1)
{
head.next = null;
head.prev = null;
return head;
}
int i=1;
Node current = head;
while(i <= n/2)
{
current = current.next;
i++;
}
current.prev= formBalancedBST_inPlace_nlogn(head, i-1);
current.next = formBalancedBST_inPlace_nlogn(current.next, n-i);
return current;
}
Complete running code in java ::
public class TernaryTree2DLL{
// Demonstrate tree->list with the list 1..5
public static void main(String[] args) {
//-------------------------------------------
BTOperation ob=new BTOperation();
TernaryTreeNode r5 = new TernaryTreeNode(5);
TernaryTreeNode r6 = new TernaryTreeNode(6);
TernaryTreeNode r7 = new TernaryTreeNode(7);
TernaryTreeNode r8 = new TernaryTreeNode(8);
TernaryTreeNode r9 = new TernaryTreeNode(9);
TernaryTreeNode r10 = new TernaryTreeNode(10);
TernaryTreeNode r11 = new TernaryTreeNode(11);
TernaryTreeNode r12 = new TernaryTreeNode(12);
TernaryTreeNode r13 = new TernaryTreeNode(13);
TernaryTreeNode r2 = new TernaryTreeNode(2,r5,r6,r7);
TernaryTreeNode r3 = new TernaryTreeNode(3,r8,r9,r10);
TernaryTreeNode r4 = new TernaryTreeNode(4,r11,r12,r13);
TernaryTreeNode root = new TernaryTreeNode(1, r2, r3, r4);
// ob.treeInsert(root,16);
// ob.treeInsert(root,18);
// ob.treeInsert(root,17);
// ob.treeInsert(root,20);
// ob.treeInsert(root,6);
// ob.treeInsert(root,7);
// ob.treeInsert(root,3);
// ob.treeInsert(root,13);
// ob.treeInsert(root,9);
// ob.treeInsert(root,2);
// ob.treeInsert(root,4);
//-------------------------------------------
System.out.println("tree:");
// ob.printTree(root); // 1 2 3 4 5
// System.out.println();
System.out.println("Inorder traversal of tree:");
ob.inOrderTree(root);
TernaryTreeNode head = ob.treeToList(root); // treeToDLL(root);
// TernaryTreeNode head = ob.toList(root);
System.out.println("DLL traversal: ");
ob.printList(head); // 1 2 3 4 5 yay!
}
}
class TernaryTreeNode
{
int data;
TernaryTreeNode left;
TernaryTreeNode middle;
TernaryTreeNode right;
public TernaryTreeNode(int v)
{
this.data=v;
}
public TernaryTreeNode(int v , TernaryTreeNode small, TernaryTreeNode middle , TernaryTreeNode large) {
this.data=v;
this.left = small;
this.middle = middle;
this.right=large;
}
}
class BTOperation {
public TernaryTreeNode treeToList(TernaryTreeNode root)
{
// base case: empty tree -> empty list
if (root==null)
return(null);
// Recursively do the subtrees (leap of faith!)
TernaryTreeNode aList = treeToList(root.left);
TernaryTreeNode bList = treeToList(root.middle);
TernaryTreeNode cList = treeToList(root.right);
// Make the single root node into a list length-1
// in preparation for the appending
root.left = root;
root.right = root;
// At this point we have three lists, and it's
// just a matter of appending them together
// in the right order (aList, root, bList)
aList=append(aList, bList);
aList=append(aList, cList);
aList = append(aList,root );
// root = append(root, bList);
return(aList);
}
public TernaryTreeNode append(TernaryTreeNode a, TernaryTreeNode b)
{
// if either is null, return the other
if (a==null) return(b);
if (b==null) return(a);
// find the last node in each using the .previous pointer
TernaryTreeNode aLast = a.left; // small;
TernaryTreeNode bLast = b.left; // small;
// join the two together to make it connected and circular
join(aLast, b);
join(bLast, a);
return(a);
}
public void join(TernaryTreeNode a, TernaryTreeNode b) {
a.right = b;
b.left = a;
}
/*
Given a non-empty tree, insert a new node in the proper
place. The tree must be non-empty because Java's lack
of reference variables makes that case and this
method messier than they should be.
*/
public void treeInsert(TernaryTreeNode root, int newData) {
if (newData<=root.data)
{
if (root.left!=null)
treeInsert(root.left, newData);
else
root.left = new TernaryTreeNode(newData);
}
else
{
if (root.right!=null)
treeInsert(root.right, newData);
else
root.right = new TernaryTreeNode(newData);
}
}
// Do an inorder traversal to print a tree
// Does not print the ending "\n"
public void printTree(TernaryTreeNode root) {
if (root==null) return;
printTree(root.left);
System.out.print(root.data+ " ");
printTree(root.right);
}
// postorder travseral of tree
public void inOrderTree(TernaryTreeNode root)
{
if(root==null) return;
inOrderTree(root.left);
inOrderTree(root.middle);
inOrderTree(root.right);
System.out.print(root.data+" ");
}
// Do a traversal of the list and print it out
public void printList(TernaryTreeNode head) {
// System.out.println(" head :: " + head.right.right.data);
TernaryTreeNode current = head;
while (true)
{
System.out.print(current.data + " ");
current = current.right;
if(current==head)
{
break;
}
}
System.out.println();
}
}
Can you please explain your code. I am unable to understand it.
- codeAddict March 12, 2015The upper bound (for worst case) on number of comparison is log(n) , and lower bound(for best case i.e, when all elements are same) is O(1) , so overall complexity will be O(logn) , NOT theta(n) because its not a tight bound.
Correct me if I am wrong
Note: Java Code & running for all cases:
Case 1: Negative number
Case 2: 0<=n<=1
Case 3: n>1
public static double sqrtMethod3(double a)
{
//firstly check if a is non-negative value
if(a<0)
return -1;
//also check if a==0 or a==1 because in these two cases sqrt(a) = a
if(a==0 || a==1) return a;
//now start the core part of the code
double precision = 0.0000000000001;//define the precision, so we stop when precision is achieved
double start = 0;
double end = a;
//we define these two start/end values because usually 0<sqrt(a)<a
//however, if a<1; then 0<a<sqrt(a)
if(a<1)
end = 1;
//define a loop to continue if the precision is not yet achieved
while(end-start>precision)
{
// System.out.println("end-start = "+(end-start));
// System.out.println("precision = "+precision);
double mid = (start+end)/2;
double midSqr = mid*mid;
if(midSqr==a)
return mid;//we find the exact sqrt value!
else if(midSqr<a)
start = mid;//we shift our focus to bigger half
else
end = mid;//shift focus to smaller half
}
//if we did not find exact sqrt value, we return the approxiated value with the defined precision
return (start+end)/2;
}
1. Threads are easier to create than processes since they
don't require a separate address space.
2. Multithreading requires careful programming since threads
share data strucures that should only be modified by one thread
at a time. Unlike threads, processes don't share the same
address space.
3. Threads are considered lightweight because they use far
less resources than processes.
4. Processes are independent of each other. Threads, since they
share the same address space are interdependent, so caution
must be taken so that different threads don't step on each other.
This is really another way of stating #2 above.
5. A process can consist of multiple threads.
Java version: Working for all kinds of test cases:
public static void printMatrix_Spiral_form(int a[][])
{
if(a==null)
return ;
// int column=a.length;
int row=a.length-1; // correct answer
int column=a[0].length-1; // correct answer
// first printing row then printing column
int i=0,j=0,k=0,p=0;
while(j<=column && i<=row)
{
k=j;
while(j<=column)
{
System.out.print(a[i][j]+" ");
j++;
}
i++;
j--;
p=i;
while(i<=row)
{
System.out.print(a[i][j]+" ");
i++;
}
i--;
j--;
while(j>=k)
{
System.out.print(a[i][j]+" ");
j--;
}
i--;
j++;
while(i>=p)
{
System.out.print(a[i][j]+" ");
i--;
}
i++;
j++;
column--;
row--;
}
}
The only solution possible for LC substring between two strings is : Manacher’s Algorithm
// Transform S into T.
// For example, S = "abba", T = "^#a#b#b#a#$".
// ^ and $ signs are sentinels appended to each end to avoid bounds checking
string preProcess(string s) {
int n = s.length();
if (n == 0) return "^$";
string ret = "^";
for (int i = 0; i < n; i++)
ret += "#" + s.substr(i, 1);
ret += "#$";
return ret;
}
string longestPalindrome(string s) {
string T = preProcess(s);
int n = T.length();
int *P = new int[n];
int C = 0, R = 0;
for (int i = 1; i < n-1; i++) {
int i_mirror = 2*C-i; // equals to i' = C - (i-C)
P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
// Attempt to expand palindrome centered at i
while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
P[i]++;
// If palindrome centered at i expand past R,
// adjust center based on expanded palindrome.
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
// Find the maximum element in P.
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < n-1; i++) {
if (P[i] > maxLen) {
maxLen = P[i];
centerIndex = i;
}
}
delete[] P;
return s.substr((centerIndex - 1 - maxLen)/2, maxLen);
}
Source: Refer to leetcode.com
- codeAddict January 10, 2014I also thought of same procedure of maintaining an auxiliary space of 10 digits and then taking each digit of each element in BST.
Time Complexity: O(Summation of digits of all elements in BST)
Space Complexity: O(10) // Since there are 10 digits
Edit:
(1). Whether the input numbers are given in form BST, unsorted array or anything else complexity can't be reduced further.
(2). Please some one explain essence of BST in this question.
Method 1: Using HashTable. (Not so efficient because of limited memory constrains)
Method 2: Using Trie and Heaps. (Memory Efficient)
Source : geeksforgeeks
This question is already asked in CareerCup. For more details refer to question with id= 183797
- codeAddict July 16, 2013i think ur distribution is correct but there would be some minor changes:
public int my_rand(int n)
{
int i;
int a=randomNumber(n)+1;
int b=randomNumber(n)+1;
System.out.println("a="+a);
System.out.println("b="+b);
i=a +b; // 2 to 10
i=i-1;
if(i==8 || i== 9)
return my_rand(n);
return i;
// return my_rand(n);
}
Two solution possible depending on situation:
Solution 1: More time complexity and less space complexity
Use Max-Heap of size k.
Time complexity: O(n*logk)
Space complexity: O(k)
Solution 2: Same time complexity and more space complexity
Use Map<Cordinate,distance> of size n.
Time complexity: O(n)+O(nlogk)
Space complexity: O(n)
@Praveen-
Complexity for your solution- O(log n)
Complexity of sharath hari solution- O(1)
U can compare
@learner- Does that mean that paging is always required irrespective of size of memory available so as to maintain protection among the processes?
- codeAddict January 03, 2013@hardy. I am sorry to say but question is contradictory in itself. Please check or remove the question.
thanks
Let total possibility be p:
Case 1: 1c,1a p1= N;
Case 2: 1c,2a p2= N*(N-1)/2
Case 3: 1c,1b p3= N
Case 4: 1a,1b,1c p4= N*(N-1)
Case 5: 2a,1b,1c p5= N*(N-1)*(N-2)/2
Total possibility p=p1+p2+p3+p4+p5
- codeAddict August 19, 2016