DS PROBLEM :Find a pair with given sum in a BST(Binary Search Tree)

Problem : Given a Balanced Binary Search Tree and a target sum, write a function that returns true if there is a pair with sum equals to target sum, otherwise return false. Expected time complexity is O(n) and only O(Logn) extra space can be used. Any modification to Binary Search Tree is not allowed. Note that height of a Balanced BST is always O(Logn).

Solution: There are two approaches to solve the problem

The Brute Force Solution is to consider each pair in BST and check whether the sum equals to X. The time complexity of this solution will be O(n^2).

A Better Solution is to create an auxiliary array and store Inorder traversal of BST in the array. The array will be sorted as Inorder traversal of BST always produces sorted data. Once we have the Inorder traversal, we can pair in O(n) time (See this for details). This solution works in O(n) time, but requires O(n) auxiliary space.

Comments

LOVE THE WAY SINGLETON PATTERN CAN BE DESIGNED ! WOWW...

To implement Singleton pattern, we have different approaches : 1.Eager initialization: In this method the instance of clss is created at loading time .As whenever in java there is a requirement of species at loading time we first remember of Static keyword. package com.questprogram.singleton; public class EagerInitializedSingleton { private static final EagerInitializedSingleton instance = new EagerInitializedSingleton(); //private constructor to avoid client applications to use constructor private EagerInitializedSingleton(){} public static EagerInitializedSingleton getInstance(){ return instance; } } 2. Static block initialization Static Block initialization implementation is similar to eager initialization, except that instance of class is created in the static block that provides option for exception handling. package com.questprogram.singleton; public class StaticBlockSingleton { private static StaticBlockSingleton in

Before Starting MicroServices just walk through Orchestration !! Matters a lot

What is this Orchestration : Orchestration is the traditional way of handling interactions between different services in Service-Oriented Architecture (SOA). With orchestration process, there is typically one controller that acts as the “orchestrator” of the overall service interactions. This typically follows a request/response type pattern. For example, if three services needed to be called in a particular order, the orchestrator makes a call to each one, waiting for a response before calling the next.

10 points to know about volatile variable in JAVA?

Volatile variable have some specific uses.It's better to know all the major reason why java adopt such variables .Please found the below 10 points which need to be noticed: 1.Volatile variable always get allocated in the main memory.To allocate any variable in main memory volatile keyword is used. 2.Precisely volatile variable are always read and write directly from main memory.It doesn't perform any operation from CPU 's cache. 3.Volatile variable after JAVA 5 guranatees the visibilty of changes to variable across multiple threads. 4.Volatile also provide atomicity in some cases e.g .while reading double and long data types. 5.In case of volatile long and volatile double data types which are of 64 bytes the read operation is atomic. 6. If you know that a long field is accessed by more than one thread e.g. a counter or anything, you better make it volatile. Why? because reading to a long variable is not atomic in Java and done in two steps, If one thread is w

TechBlog

Search This Blog