Implementarea unui Rate Limiter

public class RateLimiter {
    private static final int ONE_SECOND = 1000;
    private final Map<String, List<Long>> requests;
    private boolean enabled = false;
    private int requestsPerSecond;

    public RateLimiter(Environment environment) {
        requests = new HashMap<>();
        if (environment.getProperty("enable.rate.limiter") != null) {
            this.enabled = Boolean.parseBoolean(environment.getProperty("enable.rate.limiter"));
        }
        if (this.enabled) {
            String property = environment.getProperty("max.requests.per.user.per.second");
            Assert.notNull(property, "Max requests per second not defined!");
            this.requestsPerSecond = Integer.parseInt(property);
        }
    }

    public boolean allows(String ipAddress) {
        if (!enabled) {
            return true;
        }

        if (!requests.containsKey(ipAddress)) {
            requests.put(ipAddress, new ArrayList<>());
        }

        Long now = System.currentTimeMillis();
        cleanup(ipAddress, now);
        requests.get(ipAddress).add(now);

        return requests.get(ipAddress).size() <= requestsPerSecond;
    }

    private void cleanup(String ipAddress, Long now) {
        List<Long> markedForDeletion = new ArrayList<>();
        for (Long timestamp : requests.get(ipAddress)) {
            if (now - timestamp > ONE_SECOND) {
                markedForDeletion.add(timestamp);
            }
        }
        requests.get(ipAddress).removeAll(markedForDeletion);
    }
}

Test de integrare pt Kafka Consumer

@EmbeddedKafka
@SpringBootTest(properties = "spring.kafka.consumer.bootstrap-servers=${spring.embedded.kafka.brokers}")
public class ProductCreatedEventHandlerTest {
    @MockBean
    ProcessedEventRepository processedEventRepository;

    @Autowired
    KafkaTemplate<String, Object> kafkaTemplate;

    @SpyBean // true object, its methods can be intercepted
    ProductCreatedEventHandler productCreatedEventHandler;

    @Test
    public void testHandle() throws Exception {
        // Arrange
        ProductCreatedEvent event = new ProductCreatedEvent(UUID.randomUUID().toString(), "iPhone SE", BigDecimal.valueOf(24.5), 12);
        ProducerRecord<String, Object> record = new ProducerRecord<>(PRODUCT_CREATED_EVT_TOPIC, event.getProductId(), event);
        String messageId = UUID.randomUUID().toString();
        record.headers().add("messageId", messageId.getBytes());
        record.headers().add(KafkaHeaders.RECEIVED_KEY, event.getProductId().getBytes());

        ProcessedEventEntity processedEventEntity = new ProcessedEventEntity();
        when(processedEventRepository.findByMessageId(any())).thenReturn(processedEventEntity);

        // Act
        kafkaTemplate.send(record).get();

        // Assert
        ArgumentCaptor<String> messageIdCaptor = ArgumentCaptor.forClass(String.class);
        ArgumentCaptor<String> messageKeyCaptor = ArgumentCaptor.forClass(String.class);
        ArgumentCaptor<ProductCreatedEvent> eventCaptor = ArgumentCaptor.forClass(ProductCreatedEvent.class);
        verify(productCreatedEventHandler, timeout(5000).times(1))
                .handle(eventCaptor.capture(), messageIdCaptor.capture(), messageKeyCaptor.capture());
        Assertions.assertEquals(messageId, messageIdCaptor.getValue());
        Assertions.assertEquals(event.getProductId(), messageKeyCaptor.getValue());
        Assertions.assertEquals(event.getProductId(), eventCaptor.getValue().getProductId());
    }
}

Test de integrare pt Kafka Producer

1. Testarea serviciului care trimite mesaje Kafka

package com.hanul.pis.ProductsMicroservice;

import com.hanul.pis.ProductsMicroservice.rest.NewProductDto;
import com.hanul.pis.ProductsMicroservice.service.ProductService;
import com.hanul.pis.core.event.ProductCreatedEvent;
import org.apache.kafka.clients.consumer.ConsumerConfig;
import org.apache.kafka.clients.consumer.ConsumerRecord;
import org.apache.kafka.common.serialization.StringDeserializer;
import org.junit.jupiter.api.*;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;
import org.springframework.core.env.Environment;
import org.springframework.kafka.core.DefaultKafkaConsumerFactory;
import org.springframework.kafka.listener.ContainerProperties;
import org.springframework.kafka.listener.KafkaMessageListenerContainer;
import org.springframework.kafka.listener.MessageListener;
import org.springframework.kafka.support.serializer.ErrorHandlingDeserializer;
import org.springframework.kafka.support.serializer.JsonDeserializer;
import org.springframework.kafka.test.EmbeddedKafkaBroker;
import org.springframework.kafka.test.context.EmbeddedKafka;
import org.springframework.kafka.test.utils.ContainerTestUtils;
import org.springframework.test.annotation.DirtiesContext;
import org.springframework.test.context.ActiveProfiles;

import java.math.BigDecimal;
import java.util.Map;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.TimeUnit;

@DirtiesContext                                 // it will corrupt the application context -> each test will start with a clean state
@TestInstance(TestInstance.Lifecycle.PER_CLASS) // one instance for all test methods, for expensive setup code
@ActiveProfiles("test")                         // look for application-test.properties
// use embedded Kafka server
@EmbeddedKafka (partitions = 3, count = 3, controlledShutdown = true)
@SpringBootTest(properties = "spring.kafka.producer.bootstrap-servers=${spring.embedded.kafka.brokers}")
public class ProductServiceImplTest {
    @Autowired
    private ProductService productService;

    @Autowired
    private EmbeddedKafkaBroker embeddedKafkaBroker;

    @Autowired
    private Environment environment;

    private KafkaMessageListenerContainer<String, ProductCreatedEvent> container;
    private BlockingQueue<ConsumerRecord<String, ProductCreatedEvent>> records = new LinkedBlockingQueue<>();

    @BeforeAll
    void setUp() {
        Map<String, Object> consumerProperties = getConsumerProperties();
        DefaultKafkaConsumerFactory<String, Object> consumerFactory = new DefaultKafkaConsumerFactory<>(consumerProperties);
        ContainerProperties containerProperties = new ContainerProperties(environment.getProperty("product-created-evt-topic-name"));
        container = new KafkaMessageListenerContainer<>(consumerFactory, containerProperties);
        container.setupMessageListener((MessageListener<String, ProductCreatedEvent>) records::add);
        container.start();
        ContainerTestUtils.waitForAssignment(container, embeddedKafkaBroker.getPartitionsPerTopic());
    }

    @AfterAll
    void tearDown() {
        container.stop();
    }

    @Test
    void testCreateProduct_validProduct_success() throws Exception {
        // Arrange
        NewProductDto newProductDto = new NewProductDto();
        newProductDto.setPrice(new BigDecimal(1200));
        newProductDto.setQuantity(10);
        newProductDto.setTitle("Philips monitor 40\"");

        // Act
        String productId = productService.createProduct(newProductDto);

        // Assert
        Assertions.assertNotNull(productId);
        ConsumerRecord<String, ProductCreatedEvent> message = records.poll(3, TimeUnit.SECONDS);
        Assertions.assertNotNull(message);
        Assertions.assertNotNull(message.key());
        ProductCreatedEvent event = message.value();
        Assertions.assertNotNull(event);
        Assertions.assertEquals(newProductDto.getTitle(), event.getTitle());
        Assertions.assertEquals(newProductDto.getPrice(), event.getPrice());
        Assertions.assertEquals(newProductDto.getQuantity(), event.getQuantity());
    }

    private Map<String, Object> getConsumerProperties() {
        // Brokers' port numbers will dynamically change during executions of this test
        // Therefore, they should be dynamically retrieved in configuration
        return Map.of(
                ConsumerConfig.BOOTSTRAP_SERVERS_CONFIG, embeddedKafkaBroker.getBrokersAsString(),
                ConsumerConfig.KEY_DESERIALIZER_CLASS_CONFIG, StringDeserializer.class,
                ConsumerConfig.VALUE_DESERIALIZER_CLASS_CONFIG, ErrorHandlingDeserializer.class,
                ErrorHandlingDeserializer.VALUE_DESERIALIZER_CLASS, JsonDeserializer.class,
                ConsumerConfig.GROUP_ID_CONFIG, environment.getProperty("spring.kafka.consumer.group-id"),
                JsonDeserializer.TRUSTED_PACKAGES, environment.getProperty("spring.kafka.consumer.properties.spring.json.trusted.packages"),
                ConsumerConfig.AUTO_OFFSET_RESET_CONFIG, environment.getProperty("spring.kafka.consumer.auto-offset-reset")
                );
    }
}

2. Testarea configurarilor - ex. ca producatorul este idempotent

package com.hanul.pis.ProductsMicroservice;

import com.hanul.pis.core.event.ProductCreatedEvent;
import org.apache.kafka.clients.producer.ProducerConfig;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;
import org.springframework.kafka.core.KafkaTemplate;
import org.springframework.kafka.core.ProducerFactory;

import java.util.Map;

@SpringBootTest
public class IdempotentProducerItTest { // it will test based on real configuration
    @Autowired
    KafkaTemplate<String, ProductCreatedEvent> kafkaTemplate;

    @Test
    void test_enabledIdempotence() {
        // Arrange
        ProducerFactory<String, ProductCreatedEvent> producerFactory = kafkaTemplate.getProducerFactory();

        // Act
        Map<String, Object> config = producerFactory.getConfigurationProperties();

        // Assert
        Assertions.assertEquals("true", config.get(ProducerConfig.ENABLE_IDEMPOTENCE_CONFIG));
        Assertions.assertTrue("all".equalsIgnoreCase((String) config.get(ProducerConfig.ACKS_CONFIG)));
        if (config.containsKey(ProducerConfig.RETRIES_CONFIG)) {
            Assertions.assertTrue(Integer.parseInt(config.get(ProducerConfig.RETRIES_CONFIG).toString()) > 0);
        }
    }
}

Grind75

#57. Insert Interval (link)

class Solution {

public int[][] insert(int[][] intervals, int[] newInterval) {

int start = newInterval[0], stop = newInterval[1];

// case: newInterval contains all intervals

if (intervals.length == 0 || start <= intervals[0][0] && stop >= intervals[intervals.length-1][1]) {

int[][] result = new int[1][2];

result[0] = newInterval;

return result;

}

int[] insertion = new int[2];

// What should insertion[0] be?

insertion[0] = start;

if (start > intervals[0][0]) {

for (int i=0; i<intervals.length; i++) {

if (start >= intervals[i][0] && start <= intervals[i][1]) {

insertion[0] = intervals[i][0];

break;

}

}

}

// What should insertion[1] be?

insertion[1] = stop;

if (stop < intervals[intervals.length-1][1]) {

for (int i=0; i<intervals.length; i++) {

if (stop >= intervals[i][0] && stop <= intervals[i][1]) {

insertion[1] = intervals[i][1];

break;

}

}

}

// Place insertion

boolean added = false;

List<Integer[]> result = new ArrayList<>();

for (int i=0; i<intervals.length; i++) {

if (insertion[0] <= intervals[i][0]) {

addToList(insertion, result);

added = true;

while (i<intervals.length && intervals[i][1] <= insertion[1]) {

i++;

}

copyRest(i, intervals, result);

break;

} else {

addToList(intervals[i], result);

}

}

if (!added) {

// add at the end

addToList(insertion, result);

}

// List to arrays

int[][] array = new int[result.size()][2];

for (int i=0; i<result.size(); i++) {

array[i][0] = result.get(i)[0];

array[i][1] = result.get(i)[1];

}

return array;

}

private void copyRest(int from, int[][] intervals, List<Integer[]> list) {

for (int i=from; i<intervals.length; i++) {

addToList(intervals[i], list);

}

}

private void addToList(int[] interval, List<Integer[]> list) {

Integer[] pair = new Integer[2];

pair[0] = interval[0];

pair[1] = interval[1];

list.add(pair);

}

}

Pt. restul LINK

Exemple Deadlock & Livelock

Deadlock

Cand doua sau mai multe fire de executie sunt blocate in asteptarea eliberarii unor resurse de care au nevoie. Solutie: how to prevent deadlock in Java.

private static void deadlock() {
    final String res1 = "Resource_1";
    final String res2 = "Resource_2";

    Thread t1 = new Thread(() -> {
        synchronized (res1) {
            System.out.println("[t1] acquired access to res1");
            try {
                Thread.sleep(5000);
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
            synchronized (res2) {
                System.out.println("[t1] Yay! escaped deadlock."); // not happening
            }
        }
    });
    Thread t2 = new Thread(() -> {
        synchronized (res2) {
            System.out.println("[t2] acquired access to res2");
            try {
                Thread.sleep(5000);
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
            synchronized (res1) {
                System.out.println("[t2] Yay! escaped deadlock.");
            }
        }
    });

    t1.start();
    t2.start();
}

Livelock

Doua sau mai multe fire de executie isi cedeaza dreptul de a rula in favoarea celorlalte astfel ajungand sa nu ruleze niciodata, iar aplicatia nu progreseaza. Solutie: schimbarea logicii.

static class Spoon {
    Diner owner;

    public Spoon (Diner firstOwner) {
        this.owner = firstOwner;
    }

    synchronized void setOwner(Diner owner) {
        this.owner = owner;
    }

    synchronized void use() {
        System.out.println(owner.name + " just ate!");
    }
}

static class Diner {
    String name;
    boolean isHungry;

    public Diner (String name) {
        this.name = name;
        this.isHungry = true;
    }

    public void eatWith (Spoon spoon, Diner spouse) {
        while (isHungry) {
            if (spoon.owner != this) {
                // wait for a while for the spoon to be released
                try {
                    Thread.sleep(3000);
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
            }

            // after wait, try to give the spoon to the spouse if she's hungry
            if (spouse.isHungry) {
                System.out.println("[" + name + "] Eat, baby, eat!");
                spoon.owner = spouse;
            } else {
                // finally
                spoon.use();
                isHungry = false;
                System.out.println("[" + name + "] Finally ate!!!"); // never
                spoon.owner = spouse;
            }
        }
    }
}

private static void livelock() {
    final Diner husband = new Diner("Adnan");
    final Diner wife = new Diner("Hannan");
    Spoon spoon = new Spoon(wife);
    
    try {
        new Thread(() -> husband.eatWith(spoon, wife)).start();
        Thread.sleep(1500);
        new Thread(() -> wife.eatWith(spoon, husband)).start();
    } catch (InterruptedException e) {
        throw new RuntimeException(e);
    }
}

Script bash pt build proiecte

 ./script.sh <nume branch>

branch="master"

if [ -n "$1" ]; then

branch=$1

fi

printf "\ngit pull from "$branch"\n\n"

currentDate=`date +"%Y-%m-%d-%H%M"`

filename="$currentDate.log"

touch $filename

for dir in `ls .`;

do

if [[ -d $dir ]]; then

echo $'\n'$dir

cd $dir

mvn clean &>> ../$filename

git checkout master

git pull

cd ..

echo $'\n' &>> $filename

fi

done

# legacy first

echo $'\n' >> $filename

for dir in `ls .`;

do

if [[ -d $dir && "$dir" == *"legacy"* ]]; then

echo $'\n'$dir

cd $dir

mvn install -DskipTests &>> ../$filename

cd ..

echo $'\n' &>> $filename

fi

done

printf "\n"

for dir in `ls .`;

do

if [[ -d $dir && "$dir" != *"legacy"* ]]; then

echo $'\n'$dir

cd $dir

mvn install -DskipTests &>> ../$filename

cd ..

echo $'\n' &>> $filename

fi

done

Probleme grafuri & arbori (2)

#5. Aranjarea unor cursuri cu relatie de dependenta intre ele

Se da un numCourses si o lista de dependinte prereq[i] = [a, b], cu semnificatia: pentru a putea participa la cursul a, un student trebuie sa participe intai la cursul b. Sa se gaseasca o aranjare posibila a cursurilor, cu satisfacerea tuturor relatiilor de dependenta. 

Nota: sortare topologica intr-un graf orientat. Se pun intr-o stiva si se elimina succesiv nodurile care nu au arce de iesire, impreuna cu arcele lor de intrare. Se repeta pana cand nu mai ramane niciun nod, apoi se scot nodurile din stiva; ele vor fi sortate topologic. Daca exista un ciclu in graf, nu exista sortare topologica - se va observa ca de la o iteratie la alta nu se mai sterg noduri.

class Solution {

public int[] findOrder(int numCourses, int[][] prereq) {

Map<Integer, Set<Integer>> outgoingEdges = new HashMap<>();

for (int i=0; i<numCourses; i++) {

outgoingEdges.put(i, new HashSet<>());

}

for (int[] edges : prereq) {

int to = edges[0], from = edges[1];

outgoingEdges.get(from).add(to);

}

int result[] = new int[numCourses];

try {

Stack<Integer> stack = topologicalSort(numCourses, outgoingEdges);

int i = 0;

while (!stack.isEmpty()) {

result[i++] = stack.pop();

}

} catch (CircularException e) {

return new int[0];

}

return result;

}

private Stack<Integer> topologicalSort(int numCourses, Map<Integer, Set<Integer>> outgoingEdges) {

Stack<Integer> nodeStack = new Stack<>();

int remainingNodes = outgoingEdges.size();

while (!outgoingEdges.isEmpty()) {

List<Integer> connectionsToDelete = new LinkedList<>();

for (int i=0; i<numCourses; i++) {

if (outgoingEdges.containsKey(i) && outgoingEdges.get(i).isEmpty()) {

nodeStack.push(i);

outgoingEdges.remove(i);

connectionsToDelete.add(i);

}

}

outgoingEdges.forEach((k,v) -> v.removeAll(connectionsToDelete));

connectionsToDelete.clear();

// este un ciclu atunci cand dupa o parcurgere completa nu se mai scot noduri

if (remainingNodes == outgoingEdges.size()) {

throw new CircularException();

}

remainingNodes = outgoingEdges.size();

}

return nodeStack;

}

private class CircularException extends RuntimeException {

public CircularException() {

super();

}

}

}

Varianta mai eficienta: sortare topologica folosind DSF. Dupa obtinerea unei ordini topologice, trebuie sa se verifice ca graful nu contine cicluri.

class Solution {

public int[] findOrder(int numCourses, int[][] prereq) {

List<List<Integer>> adjList = getAdjList(numCourses, prereq);

boolean visited[] = new boolean[numCourses]; // all false

Stack<Integer> stack = new Stack<>();

int result[] = new int[numCourses];

for (int i=0; i<numCourses; i++) {

if (!visited[i]) {

dfs(i, adjList, stack, visited);

}

}

int i = 0;

while (!stack.isEmpty()) {

result[i++] = stack.pop();

}

// check for any cycle

for (int node = 0; node < numCourses; node++) {

for (int conn : adjList.get(node)) {

// we have a vertex from node -> conn

// if conn appears before node in the ordering => cycle

if (indexOf(conn, result) < indexOf(node, result)) {

return new int[0]; // cycle

}

}

}

return result;

}

private void dfs(int node, List<List<Integer>> adjList, Stack<Integer> stack, boolean visited[]) {

visited[node] = true;

for (int neighbor : adjList.get(node)) {

if (!visited[neighbor]) {

dfs(neighbor, adjList, stack, visited);

}

}

stack.push(node);

}

private List<List<Integer>> getAdjList(int numCourses, int[][] prereq) {

List<List<Integer>> adjList = new ArrayList<>();

for (int i=0; i<numCourses; i++) {

adjList.add(new ArrayList<>());

}

for (int[] edges : prereq) {

int to = edges[0], from = edges[1];

adjList.get(from).add(to);

}

return adjList;

}

private int indexOf(int node, int[] order) {

for (int i=0; i<order.length; i++) {

if (order[i] == node) {

return i;

}

}

return -1;

}

}

#6. Primul stramos comun a doua noduri dintr-un arbore binar

Cand avem acces la parintii unui nod:

class Solution {

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if (p == root || q == root) {

return root;

}

int diffDepth = depth(root, p) - depth(root, q);

while (diffDepth > 0) {

p = p.parent; // bring p on the same level with q

diffDepth--;

}

while (diffDepth < 0) {

q = q.parent; // bring q on the same level with p

diffDepth++;

}

while (p != q && p != null && q != null) {

// go up together

p = q.parent;

p = q.parent;

}

return (p != null && q != null) ? p : null;

}

private int depth(TreeNode root, TreeNode node) {

int depth = 0;

while (node != root) {

depth++;

node = node.parent;

}

return depth;

}

}

Cand nu avem acces la parintii unui nod:

class Solution {

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if (p == root || q == root || root == null) {

return root;

}

return search(root, p, q);

}

private TreeNode search(TreeNode node, TreeNode p, TreeNode q) {

if (node == p || node == q) {

return node;

}

boolean isPinLeft = isNodeInSubtree(node.left, p);

boolean isQinLeft = isNodeInSubtree(node.left, q);

if (isPinLeft != isQinLeft) { // if p and q are in different branches of node

return node; // common ancestor

} else {

TreeNode nodeNext = isPinLeft ? node.left : node.right;

return search(nodeNext, p, q);

}

}

private boolean isNodeInSubtree(TreeNode subtree, TreeNode node) {

if (subtree == null) {

return false;

}

if (subtree.val == node.val) {

return true;

}

return isNodeInSubtree(subtree.left, node) || isNodeInSubtree(subtree.right, node);

}

// issue: repetitive calls to isNodeInSubtree when it already found the node

}

Alternativa - fara acces la parinti, tinem minte calea pana la nod in format L/R

class Solution {

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if (p == root || q == root || root == null) {

return root;

}

search(root, p, "", q, "");

TreeNode ancestor = root;

int i = 0;

while (finalPathP.length() > i && finalPathQ.length() > i && finalPathP.charAt(i) == finalPathQ.charAt(i)) {

char c = finalPathP.charAt(i);

ancestor = c == 'L' ? ancestor.left : ancestor.right;

i++;

}

return ancestor;

}

String finalPathP = null;

String finalPathQ = null;

private void search(TreeNode node, TreeNode p, String pathP, TreeNode q, String pathQ) {

if (node == null) {

return;

}

if (node.val == p.val) {

finalPathP = pathP;

}

if (node.val == q.val) {

finalPathQ = pathQ;

}

if (finalPathP == null || finalPathQ == null) {

search(node.left, p, pathP + "L", q, pathQ + "L");

search(node.right, p, pathP + "R", q, pathQ + "R");

}

}

}

Probleme grafuri & arbori (1)

#1. Aflare daca exista o cale intre doua noduri dintr-un graf

Graf neorientat cu n noduri pentru care se da o lista de muchii edges[i] = [n1, n2] care inseamna ca exista o legatura directa intre n1 si n2. Sa se afle daca din n1 se poate ajunge in n2.

Nota: BFS. Nu este necesar sa folosim Map, un simplu ArrayList e suficient.

class Solution {

public boolean validPath(int n, int[][] edges, int source, int destination) {

if (source == destination) {

return true;

}

Map<Integer, Node> nodes = new HashMap<>();

for (int i=0; i<n; i++) {

nodes.put(i, new Node(i));

}

for (int i=0; i<edges.length; i++) {

int from = edges[i][0], to = edges[i][1];

nodes.get(from).addNeighbor(nodes.get(to));

nodes.get(to).addNeighbor(nodes.get(from));

}

Node startNode = nodes.get(source);

if (startNode.isLinkedTo(nodes.get(destination))) {

return true;

}

startNode.setVisited();

Queue<Node> queue = new LinkedList<>();

queue.addAll(startNode.neighbors);

while(!queue.isEmpty()) {

Node next = queue.remove();

if (!next.visited) {

next.setVisited();

if (next.isLinkedTo(nodes.get(destination))) {

return true;

}

queue.addAll(next.neighbors);

}

}

return false;

}

private class Node {

int value;

List<Node> neighbors;

boolean visited = false;

public Node (int value) {

this.value = value;

this.neighbors = new ArrayList<>();

}

public void addNeighbor(Node node) {

this.neighbors.add(node);

}

public boolean isLinkedTo(Node node) {

return this.neighbors.contains(node);

}

public void setVisited() {

this.visited = true;

}

}

}

#2. Transformarea unui array sortat intr-un BST (binary search tree)

Sirul este sortat crescator. In arborele creat, toti descendentii din stanga ai unui nod <= valoarea nodului, iar descendentii din dreapta > valoarea nodului. In plus, arborele trebuie sa fie aiba inaltimea minima posibila.

class Solution {

public TreeNode sortedArrayToBST(int[] nums) {

return transform(nums, 0, nums.length - 1);

}

TreeNode transform(int[] nums, int indexFrom, int indexTo) {

if (indexFrom == indexTo) {

return new TreeNode(nums[indexFrom]);

}

if (indexFrom == indexTo - 1) {

TreeNode root = new TreeNode(nums[indexTo]);

root.left = new TreeNode(nums[indexFrom]);

return root;

}

int size = indexTo - indexFrom + 1;

TreeNode root = new TreeNode(nums[indexFrom + size/2]);

root.left = transform(nums, indexFrom, indexFrom + size/2 - 1);

root.right = transform(nums, indexFrom + size/2 + 1, indexTo);

return root;

}

}

#3. Arbore binar echilibrat

Dandu-se un arbore binar, sa se afle daca este echilibrat, adica pt fiecare nod diferenta intre inaltimile in jos ale fiecarui subarbore sa nu fie mai mare decat 1.

class Solution {

public boolean isBalanced(TreeNode root) {

if (root == null) {

return true;

}

try {

findHeightUnderNode(root);

} catch (UnbalancedTreeException e) {

return false;

}

return true;

}

private int findHeightUnderNode(TreeNode node) throws UnbalancedTreeException {

if (node.left == null && node.right == null) {

return 1;

}

int heightUnderLeft = node.left == null ? 0 : findHeightUnderNode(node.left);

int heightUnderRight = node.right == null ? 0 : findHeightUnderNode(node.right);

if (Math.abs(heightUnderLeft - heightUnderRight) > 1) {

throw new UnbalancedTreeException();

}

return 1 + Math.max(heightUnderLeft, heightUnderRight);

}

private class UnbalancedTreeException extends RuntimeException {

public UnbalancedTreeException() {

super();

}

}

}

#4. Validarea unui BST

Se da un arbore binar. Sa se verifice daca este un arbore binar de cautare (BST).

class Solution {

public boolean isValidBST(TreeNode root) {

try {

checkValid(root, null, null);

} catch(InvalidBSTException e) {

return false;

}

return true;

}

private void checkValid(TreeNode node, Integer lessThan, Integer moreThan) {

// lessThan, moreThan - constrangeri propagate de sus in jos

if (node == null || (node.left == null && node.right == null)) {

return;

}

if (node.left != null) {

if (node.left.val >= node.val || (lessThan != null && node.left.val >= lessThan) ||

(moreThan != null && node.left.val <= moreThan)) {

throw new InvalidBSTException();

}

}

if (node.right != null) {

if (node.right.val <= node.val || (lessThan != null && node.right.val >= lessThan) ||

(moreThan != null && node.right.val <= moreThan)) {

throw new InvalidBSTException();

}

}

checkValid(node.left, min(node.val, lessThan), moreThan);

checkValid(node.right, lessThan, max(node.val, moreThan));

}

private int min(Integer x, Integer y) {

if (x != null && y != null) {

return Math.min(x,y);

}

return x != null ? x : y;

}

private int max(Integer x, Integer y) {

if (x != null && y != null) {

return Math.max(x,y);

}

return x != null ? x : y;

}

private class InvalidBSTException extends RuntimeException {

public InvalidBSTException() {

super();

}

}

}