nilesh.d.agrawal
BAN USERApproach : Using Inorder traversal...
1. Flatten the left subtree.
2. Flatten the right subtree.
3. Set the rightnode of root to flattened rightsubtree
4. Iterate through the flattened left subtree till the last element.
5. Set the right node of last element to root.
code
public BSTNode<T> flattenBinarySearchTree(BSTNode<T> root){
if(root == null){
return null;
}
if(root.getLeftNode() == null && root.getRightNode() == null){
return root;
}
BSTNode<T> leftResult = flattenBinarySearchTree(root.getLeftNode());
root.setRightNode(flattenBinarySearchTree(root.getRightNode()));
BSTNode<T> currentNode = leftResult;
while(currentNode!=null && currentNode.getRightNode()!=null){
currentNode = currentNode.getRightNode();
}
currentNode.setRightNode(root);
return leftResult;
}
Same as two sum interface :
package com.careercup.linkedin;
import java.util.HashSet;
import java.util.Set;
/**
* Created by nileshagrawal on 11/18/16.
*/
interface TwoSumInterface{
public void store(int value);
public boolean test(int value);
}
public class TwoSumInterfaceImpl implements TwoSumInterface {
private Set<Integer> localStore = new HashSet<Integer>();
@Override
public void store(int value) {
localStore.add(value);
}
@Override
public boolean test(int newValue) {
for(int currentNumber:localStore){
if(localStore.contains(newValue - currentNumber)) {
return true;
}
}
return false;
}
}
code
interface TwoSumInterface{
public void store(int value);
public boolean test(int value);
}
public class TwoSumInterfaceImpl implements TwoSumInterface {
private Set<Integer> localStore = new HashSet<Integer>();
@Override
public void store(int value) {
localStore.add(value);
}
@Override
public boolean test(int newValue) {
for(int currentNumber:localStore){
if(localStore.contains(newValue - currentNumber)) {
return true;
}
}
return false;
}
}
Store Time Complexity: O(1), Space Complexity : O(n)
Test Time Complexity O(n), Space Complexity : O(n).
1. There are two types of classes - Person class and Friend Class.
2. Person Class should be notified only when the nearness of friend is updated. Person class should notify of its location changes to friend. Person Class should implement LocationObservable Interface and NearnessObserver Interface
3. Friend Class should be notified only when the location of the person is updated. Friend class should notify of its nearness location based on the location changes he receives from the Person.
4. Following is a simple method stub , not complete solution just class diagram :
public interface LocationObservable {
addFriend(LocationObserver locationObserver);
removeFriend(LocationObserver locationObserver);
notifyLocationChangeToAll();
notifyLocationChangeToObserver(LocationObserver locationObserver);
}
public interface LocationObserver{
getLocationUpdates();
}
public interface NearnessObersvable{
addNearnessNotification(Nearness Observer nearnessObserver);
removeNearnessNotification(NearnessObserver nearnessObserver);
notifyNearnessChange(Nearness Observer);
notifyNearnessChangeToAll();
}
public interface NearnessOberserver{
getNearNessUpdates();
}
public class Friend implements LocationObserver,NearnessObservable{
private List<NearnessObserver> persons;
addNearnessNotification(Nearness Observer nearnessObserver){
}
removeNearnessNotification(NearnessObserver nearnessObserver){
}
notifyNearnessChange(Nearness Observer){
}
notifyNearnessChangeToAll(){
}
getLocationUpdates(){
}
}
public class Person implements NearnessOberserver, LocationObservable{
private List<LocationObserver> friends;
getNearNessUpdates(){
}
addFriend(LocationObserver locationObserver){
}
removeFriend(LocationObserver locationObserver){
}
notifyLocationChangeToAll(){
}
notifyLocationChangeToObserver(LocationObserver locationObserver){
}
}
Simple Observer pattern Design
1. There are two types of classes - Person class and Friend Class.
2. Person Class should be notified only when the nearness of friend is updated. Person class should notify of its location changes to friend. Person Class should implement LocationObservable Interface and NearnessObserver Interface
3. Friend Class should be notified only when the location of the person is updated. Friend class should notify of its nearness location based on the location changes he receives from the Person.
4. Following is a simple method stub , not complete solution just class diagram :
public interface LocationObservable {
addFriend(LocationObserver locationObserver);
removeFriend(LocationObserver locationObserver);
notifyLocationChangeToAll();
notifyLocationChangeToObserver(LocationObserver locationObserver);
}
public interface LocationObserver{
getLocationUpdates();
}
public interface NearnessObersvable{
addNearnessNotification(Nearness Observer nearnessObserver);
removeNearnessNotification(NearnessObserver nearnessObserver);
notifyNearnessChange(Nearness Observer);
notifyNearnessChangeToAll();
}
public interface NearnessOberserver{
getNearNessUpdates();
}
public class Friend implements LocationObserver,NearnessObservable{
private List<NearnessObserver> persons;
addNearnessNotification(Nearness Observer nearnessObserver){
}
removeNearnessNotification(NearnessObserver nearnessObserver){
}
notifyNearnessChange(Nearness Observer){
}
notifyNearnessChangeToAll(){
}
getLocationUpdates(){
}
}
public class Person implements NearnessOberserver, LocationObservable{
private List<LocationObserver> friends;
getNearNessUpdates(){
}
addFriend(LocationObserver locationObserver){
}
removeFriend(LocationObserver locationObserver){
}
notifyLocationChangeToAll(){
}
notifyLocationChangeToObserver(LocationObserver locationObserver){
}
}
Idea is to use the array as queues.
import java.io.InputStream;
import java.util.Scanner;
/**
* Created by Nilesh Agrawal on 5/25/16.
*/
public class MovingAverage {
public void movingAvergage(int K){
double[] a = new double[K];
double sum = 0.0;
Scanner scanner = new Scanner(System.in);
for(int i =1;scanner!=null;i++){
sum -= a[i%K];
a[i%K] = scanner.nextDouble();
sum += a[i%K];
if(i>=K){
System.out.print(sum/K +" ");
}else{
System.out.print(sum/i+" ");
}
}
}
public static void main(String args[]){
MovingAverage movingAverage = new MovingAverage();
movingAverage.movingAvergage(6);
}
}
/**
* Created by nileshagrawal on 5/22/16.
* BFS on the queue elements
*/
class TreeNode{
private int x;
private int y;
private List<TreeNode> childNodeList;
public TreeNode(int x, int y, List<TreeNode> childNodeList) {
this.x = x;
this.y = y;
this.childNodeList = childNodeList;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public List<TreeNode> getChildNodeList() {
return childNodeList;
}
public void setChildNodeList(List<TreeNode> childNodeList) {
this.childNodeList = childNodeList;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
TreeNode treeNode = (TreeNode) o;
if (x != treeNode.x) return false;
if (y != treeNode.y) return false;
return childNodeList != null ? childNodeList.equals(treeNode.childNodeList) : treeNode.childNodeList == null;
}
@Override
public int hashCode() {
int result = x;
result = 31 * result + y;
result = 31 * result + (childNodeList != null ? childNodeList.hashCode() : 0);
return result;
}
}
public class FindingElementWithTwoValues {
public boolean findTheValue(TreeNode root,TreeNode givenNode){
if(root == null){
return false;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
queue.add(null);
boolean leftFound = false;
boolean rightFound = false;
while (!queue.isEmpty()){
TreeNode tempNode = queue.poll();
if(tempNode == null){
System.out.print("end of level.");
if(leftFound && rightFound){
return true;
}else{
leftFound = false;
rightFound = false;
queue.add(null);
}
}else{
for(TreeNode childNode:tempNode.getChildNodeList()){
if(childNode!=null){
queue.add(childNode);
if(childNode.getX() == givenNode.getX()){
leftFound = true;
}
if(childNode.getY() == givenNode.getY()){
rightFound = true;
}
}
}
}
}
return false;
}
}
public class MinimumSpanningTreeWithRedBlackEdges<T> {
public class EdgeComparator implements Comparator<Edge<T>>{
@Override
public int compare(Edge<T> edge1, Edge<T> edge2) {
if(edge1.getWeight()>edge2.getWeight()){
return 1;
}else{
return -1;
}
}
}
public List<Edge<T>> getMinimumSpanningTreeWithRedBlackEdges(Graph<T> graph){
if(graph == null){
return null;
}
List<Edge<T>> resultset = new ArrayList<Edge<T>>();
List<Edge<T>> allEdges = graph.getAllEdges();
List<Edge<T>> allRedEdges = new ArrayList<Edge<T>>();
List<Edge<T>> allBlackEdges = new ArrayList<Edge<T>>();
for(Edge<T> edge : allEdges){
if(edge.getColor() == "red"){
allRedEdges.add(edge);
}else if(edge.getColor() == "black"){
allBlackEdges.add(edge);
}
}
EdgeComparator edgeComparator = new EdgeComparator();
Collections.sort(allRedEdges,edgeComparator);
Collections.sort(allBlackEdges,edgeComparator);
DisjointSet disjointSet = new DisjointSet();
disjointSet.makeSet(allRedEdges.get(0).getVertex1().getId());
ListIterator<Edge<T>> redEdgeIterator = allRedEdges.listIterator();
ListIterator<Edge<T>> blackEdgeIterator = allBlackEdges.listIterator();
for(int i = 0;i<allRedEdges.size()+allBlackEdges.size();i++){
Edge<T> currentEdge;
if(i%2 == 0 && redEdgeIterator.hasNext()){
currentEdge = redEdgeIterator.next();
}else{
currentEdge = blackEdgeIterator.next();
}
long root1 = disjointSet.findset(currentEdge.getVertex1().getId());
long root2 = disjointSet.findset(currentEdge.getVertex2().getId());
if(root1 == root2){
continue;
}else{
resultset.add(currentEdge);
disjointSet.union(currentEdge.getVertex1().getId(),currentEdge.getVertex2().getId());
}
}
return resultset;
}
}
Repannasteven1246, Analyst at Accenture
Creative, highly visual fashion professional who can brilliantly mix and match the technical expertise and intuition like fabric and color ...
Result :
- nilesh.d.agrawal April 11, 2017B A D E C
B A E C D
B C A E D
B C D E A
B C E A D
B D A E C
B D E A C
B D E C A
B E D C A
B E D A C
B E A C D
C A B E D
C A D E B
C A E B D
C D A E B
C D B E A
C D E B A
C D E A B
C E A B D
C E D A B
C E D B A
C E B A D
D C B E A
D C A E B
D C E A B
D C E B A
D A B E C
D A E B C
D A E C B
D E A C B
D E A B C
D E B A C
D E B C A
E C B A D
E C D B A
E C D A B
E C A B D
E D B C A
E D B A C
E D A B C
E D A C B
E A D C B
E A D B C
E A B C D