Path sum in a Directed Acyclic Graph
Given a directed acyclic graph, determine if any branch returns a path sum that equals 22. In the example below, such a path can be found at (7 + 8 + 3 + 4). What is the run time complexity of such an algorithm?
7
/ \
8 6
/ \ / \
2 3 8
/ / \
5 4 1
This is what I came up with.
public boolean hasPathToSum(Node root, int sum)
{
if (root == null) return false;
if (root.value == sum && (root.left == null && root.right == null))
return true;
return hasPathToSum(root.left, sum  root.value)  hasPathToSum(root.right, sum  root.value);
}
Any better suggestions on improving the complexity?
1 answer

If all values in the graph are nonnegative you can solve this problem in O((n + m) * sum) using memoization. In your case sum is fixed and equal to 22, so the solution is effectively linear.
Memoization is a technique not to compute the same value twice. Note that
hasPathToSum(root, sum)
is a pure function: its result depends only on arguments, it has no side effects. It means that we can save the result of this function into some map(root, sum) > bool
(probably a HashMap or a TreeMap in Java, I cannot say precisely as I'm not familiar with the language).Now, when calling the function, we check if its arguments are presented in the map. If yes, just return saved value. Otherwise calculate it, save into the map and return. This way the function will be really computed only once for any set of arguments.
The last optimization works only with nonnegative values. Note that the result of
hasPathToSum(v, x)
is false if x < 0. So you can make a cutoff: just return false immediately if this is the case. This optimization ensures that, for each node,hasPathToSum
will be called with at most 23 different sum values, yielding the aforementioned running time.
See also questions close to this topic

Updating Kafka Offset Immediately
I am developing a Spring Boot app that reacts to messages pushed onto a Kafka queue.
The version is Spring Boot 2.0.5, Finchley.SR1.
The Kafka version is kafka_2.121.1.0
The issue I am facing is that sometimes when I restart the application it replays old messages. This doesn't always happen  the only pattern I have spotted is that it seems to be after a few days of inactivity (say on Monday morning, just after the weekend).
I stop and start the app multiple times during the day as part of the development and don't see the same issue, only sporadically. It isn't linked to errors in the application either, as all the processing is clean.
I have configured my Kafka listener to use MANUAL_IMMEDIATE acknowledgement, and call ack.acknowledge() at the end of the listener method.
My Spring property file looks as follows:
spring: kafka: bootstrapservers: kafka:9092 listener: ackmode: MANUAL_IMMEDIATE consumer: enableautocommit: false autooffsetreset: earliest groupid: usermgmtapp
My Listener class is defined as follows:
@org.springframework.kafka.annotation.KafkaListener(topics = "aggregateeventtopic") public void receive(ConsumerRecord<?, ?> cr, Acknowledgment ack) { ... ack.acknowledge(); }
I have one instance of the app running, so it's the leader in the consumer group each time.
I have used the Kafka tools to look at the offset for the consumer group, and one thing I've noticed is that when I breakpoint the app at the acknowledge step it's not updating the CURRENTOFFSET, it only seems to update it once all messages have been processed.
./kafkaconsumergroups.sh bootstrapserver kafka:9092 group usermgmtapp describe
My understanding from other posts was that MANUAL_IMMEDIATE would update the Kafka server straight away after calling acknowedge(), rather than at the end of the batch.
Is my understanding incorrect? If so is there anyway to get the functionality I want (such as setting the batch size to 1 on each read from the partition, which I'm guessing may have performance implications). If so, how do I do this (any help gratefully accepted!)
TIA

Java Spring with mustache keeps looking for files on server
I've been trying to develop a quick website using Java Spring with Mustache for templating but I have an issue when it comes to getting local files (css stylesheets or images). I'm running the website on intelliJ on http://localhost:8000 and for some reason it looks for every files on http://localhost:8000/Path/to/the/file and returns a 404 error on the inspector (no error in the console log)
Here are my filetree and the code I'm using. The templates .mustache are in the templates directory.
<nav class="level"> <div class="levelleft"> <div class="levelitem"> <img src="/img/flags/gb.svg"/> </div> <div class="levelitem"> <img src="/img/flags/fr.svg"/> </div> <div class="levelitem"> <img src="/img/flags/es.jpg"/> </div> <div class="levelitem"> <img src="/img/flags/ch.svg"/> </div> <div class="levelitem"> <img src="/img/flags/de.svg"/> </div> </div> </nav>
I saw some posts telling to add a resource handler like this :
registry.addResourceHandler("/css/**").addResourceLocations("/resources/static/css"); registry.addResourceHandler("/img/**").addResourceLocations("/resources/static/img"); registry.addResourceHandler("/resources/**").addResourceLocations("/resources/static/");
But no luck so far. Any help would be appreciated.

How can I expose my Rest services in multiple swagger pages.
I am using Spring boot to create some Rest services. How can I expose my Rest services in multiple swagger pages. For example All delete methods be in a separated page!

How can i Encrypt Serialized string using "RijndaelManaged" algorithm ,Crypto mode = "CBC" Crypto padding = "PKCS7"
How can I Encrypt Serialised string using "RijndaelManaged" algorithm?
Crypto mode = "CBC" Crypto padding = "PKCS7" Encryption key = date

Is there an efficient way of calculating the density of 1s in bitstream?
I am attempting to come up with a good method of comparing binary arrays (from length 1 to length 1000) to determine a relative 'density' of 1's.
01010101 would be less dense than 00011011, as the 1's are more spread out.
Likewise, the total number is important. Thus, 11111111 is worse (higher value) than 11, despite both being 100% 1's. (Padding the second to 00000011 would solve this issue, but cause later problems).
The algorithm will be used in nested loops (scoring method in genetic program), so my current solution of O(n^2) time and O(n) space will not cut it!
The two dirty methods I have so far will be explained using the following data (from a terrible algorithm that would be culled in gen 1):
Stream Result A Result B (8+7+6+5+4+3+2) A: 001000 1.17 7 1+1+1+1+1+1+1 B: 000 0.00 0 0+0+0+0+0+0+0 C: 1011011 5.57 25 5+5+4+4+3+2+2 D: 1011 4.25 19 3+3+3+3+3+2+2 E: 1 2.00 7 1+1+1+1+1+1+1 F: 1001010 2.29 16 3+3+3+2+2+2+1 G: 11111111 16.00 35 8+7+6+5+4+3+2 H: 1001001 2.29 14 3+3+2+2+2+1+1 I: 10101 2.80 17 3+3+3+3+2+2+1
Result A: The calculation is the number of 1's squared, divided by the total number of digits, plus the max size of contiguous 1's. So for C, 5 out of 7 are 1's, with the max grouping of 2, so 2+(5*5/7). The problem with this method is that F and H are matching, despite F being more 'bunched up'. The benefit is that it runs in O(n), and has space of O(1) [4 variables: num1s, totalnum, maxBunch, bunchSoFar] by keeping a running total.
Result B: The calculation is to start with n = maximum size (in this case 8, but in my program 900), and count the maximum number of 1's that can be captured by grouping n consecutive digits together. Then adding that to the max captured by grouping n1 consecutive digits together. I stop at groupings of 2, because a grouping of 1 will always return 1 for any nonzero array. This has the benefit of correctly setting H as a lower score than F, but would require time O(n^2) and space O(n) as the entire array needs to be stored as more digits are being added. (Compression could help the space, but would be outweighed by the time cost).
Conclusion I am looking for a more efficient method than Result B, yet can provide more detailed ordering than Result A. I attempted to google, but 'bit density' refers to something completely different! I will keep working on this, but thought that, in parallel, I would ask to see if anyone happens to know of an algorithm already that I don't know the name of.

how do I find the largest element in an array of length n with the first k elements increasing and next nk elements decreasing
I am looking for a divide and conquer algorithm to find the largest element of an array where:
 the first k elements of the array increase
 the next (nk) elements decrease
Example:
[1 2 3 4 5 6 88 99 100 99 98 79 49 23 2 1 0]

Command terminated by signal 11
#include<stdio.h> #include<stdlib.h> #include<malloc.h> struct node{ char data; int p; struct node *ptr; }; struct node *start=NULL; struct node *insert() { struct node *new_node,*z; int num; char s; printf("\nEnter 1 to stop."); printf("\nEnter the characters and their priorities: "); scanf("\n%c %d",&s,&num); while(num!=1) { new_node=(struct node *)malloc(sizeof(struct node)); new_node>data=s; new_node>p=num; if(start==NULL) { start=new_node; z=start; new_node>ptr=NULL; } else { z>ptr=new_node; new_node>ptr=NULL; z=z>ptr; } scanf("%c %d",&s,&num); } return start; } struct node *display() { struct node *z; z=start; printf("\nDisplaying elements:\n"); while(z!=NULL) { printf("\t%c [Priority=%d]\n",z>data,z>p); z=z>ptr; } return start; } struct node *sortit() { struct node *z,*q; int t; char x; z=start; while(z>ptr!=NULL) { q=z>ptr; while(q!=NULL) { if(z>p>q>p) { t=z>p; x=z>data; z>p=q>p; z>data=q>data; q>p=t; q>data=x; } q=q>ptr; } z=z>ptr; } return start; } struct node *new_insert() { struct node *y,*z; int n; char s; y=(struct node *)malloc(sizeof(struct node)); printf("\nEnter character and priority for new node:"); scanf("%c %d",&s,&n); printf("%c",s); y>data=s; y>p=n; printf("%c",y>data); printf("%d",y>p); if(n<start>p) { y>ptr=start; start=y; printf("%d",y>p); } else {printf("\nff"); z=start; while(z>ptr>p<=n&&z>ptr!=NULL) z=z>ptr; y>ptr=z>ptr; z>ptr=y; } return start; } int main() { insert(); display(); sortit(); display(); new_insert(); display(); return 0; }
In this C code, I have tried to implement priority queues.
Everything works perfectly fine except the
new_insert()
function. The print statements aftery>p=n;
innew_insert()
function print0
.Hence, the function doesn't work properly. Also, in
display()
function the print statement prints the[Priority]
twice.Hence, I am not able to add an external node in my priority queue.

Matching between two series after manipulation
Suppose, we're given two series of integer numbers as X[..] And Y[..], which has the same length. We can choose any position i of the series X[] and doing the operation like ,
X[i]=X[i] + 3
,X[i + 2] = X[i + 2] + 2
,X[i + 4] = X[i + 4] + 1
. After manipulating the series with any number of time, is it possible to find the same series like Y[..]?I am thinking to implement it by brute force and normal combinational matching after manipulation. Is there any other process which can make it faster?
Given two series, X [ 1, 2, 3 ,4, 5 ,6,8 ] Y [ 1, 5, 6 ,6, 7 ,7,9 ] if i=2 then X [ 1, 5, 3 ,6, 5 ,7,8 ] Y [ 1, 5, 6 ,6, 7 ,7,9 ] and if i=3 then X [ 1, 5, 6 ,6, 7 ,7,9 ] Y [ 1, 5, 6 ,6, 7 ,7,9 ] Matches the series.

Convert an Array to Tree in Typescript
I have structure database in array of objects stored like this:
arry = [{"name": "a", "id": "2", "data":"foo", "parent": "1"}, {"name": "b", "id": "3", "data":"foo", "parent": "2"}, {"name": "c", "id": "4", "data":"foo", "parent": "3"}, {"name": "d", "id": "5", "data":"foo", "parent": "3"}, {"name": "e", "id": "6", "data":"foo", "parent": "4"}, {"name": "f", "id": "7", "data":"foo", "parent": "5"}]
I want nested structure like this
{ "2":{ "name": "a", "data": "foo", "3":{ "name": "b", "data":"foo", "4":{ "name": "c", "data":"foo", "6":{ "name": "e", "data": "foo", }; }, "5":{ "name": "d", "data": "foo", "7":{ "name": "f", "data": "foo" } } } } };
so I can use it Angular Material tree.

Finding Components in Complement Graph
Consider a graph G having N vertices. For each vertex, I am given adjacency vector, denoting the elements adjacent to vertex in G.
For example say :
N = 4, and adjacency matrix is like :
[1] = {3,4}
[2] = {3}
[3] = {1,2,4}
[4] = {1, 3}What I am required to find is the number of connected components in the complement of G
in say O(N) or O(Nlog(N)). I tried but my approach is O(N^2). I am applying dfs and iterating i from 1 to N and checking if i is not present in the adjaceny matrix of source vertex (in dfs) and then continuing DFS. 
Creating an array for each neighbor of a node in graph using matlab
i want to create an array or a table for each neighbor of a node. In the sample of code give, the neighbors of a certain random node is what is in the variable 'acnode , so i want to create an array for each variable in 'acnode'. So i want new arrays in the form 'node' plus the name of the neighbor, example: node1322 = [], node1416 = [], node1845 = [].
nodepos = randi(length(1:nodesize)); rnode = (nodepos) node_ngb = neighbors(G, rnode) acnode = []; for i = 1:length(node_ngb) acnode = node_ngb(1:i); end acnode acnode = 1322 1416 1845

How to draw Log graph
I want to set data of duty On/Off and rest time in Log graph like:
as well user can edit the data like this:

I need to make a tree containg all possible moves in tic tac toe in java
As the title says i need to make a tree with the root containg all 9 possibles moves for x with each of those containg "O"s 8 possible remaning moves etc untill all 362,000 possibilities are filled i need to store them in a 2d char array for future reference can anyone please help

Calculate characteristic polynomial of a tree efficiently?
How to calculate characteristic polynomial of adjacency matrix of a tree efficiently? n<=2000 where n are number of nodes. where characteristic polynomial is det((lambda)IA), where I is identity matrix and A is adjacency matrix of tree, in terms of lambda.

Search for function in Object and list its path
I have an object with different attributes and functions.
My object looks like the following: data.user.identification
Now this object has a function somewhere in his tree called "GetName"This function can be always in various attributes, for example:
data.user.identification.ys.z.GetName
OR
data.user.identification.dkz.ys.GetName
OR
data.user.identification.list.blub.GetName
Now I have to know in which path this function is.
For example: data.user.identification.ys.z.GetName
I hope somebody can help me further with this?I'm using Javascript.
Thanks a lot!