What is the name of this graph algorithm?
I need to apply the following algorithm in one of my projects. I know what it does algorithmwise, but I can't seem to find an application for this. Is there a name for this algorithm?
Pseudocode:
input: G = (V, E): planar graph (Vertices, Edges)
output: W: a subset of V
function someFunc(G)
if V.length == 0 then
return []; // array
else
v = some vertex of V;
N = []; // array
// for every edge
for (a, b) in E or (b, a) in E) do
// if the edge connects to the vertex,
// add the other vertex end to the Narray
if a == v then
N.push(b);
end
end
// \notation means: left hand set minus the values in the right hand set (setdifference)
// e.g. [1, 2, 3] \ [2, 3, 4] = [1]
W1 = [v].union(someFunc(inducedSubgraph(V \ [v])));
W2 = N.union(someFunc(inducedSubgraph(V \ [v] \ N)));
return W1.length < W2.length ? W1 : W2;
end
end function
The inducedSubgraph function is an external function which removes the given vertices (+ adjacent edges) from the graph.
See also questions close to this topic

Efficient algorithm for grouping variablelength tuples
I am trying to devise an efficient algorithm for grouping a sequence of tuples of integers of any length, such as:
[(), (1,), (1,1), (1,2), (2,), (2,1,1), (2,1,2), (2,2)]
The grouping rule, in Python for example, is the following:
def tupleSameGroup(tuple1, tuple2): sameGroup = True for index in range(min(len(tuple1), len(tuple2))): if tuple1[index] != tuple2[index]: sameGroup = False return sameGroup
In rough words, if one tuple is a "subset" of another matching from the beginning, they are the same group. An empty tuple is in the same group as any tuple.
Based on this rule, I want my algorithm to produce as output a list of all unique groups of tuples; so a list of list of tuples, where within the inner list the tuples are all in the same group, but between there is a pair that is not. For the above example, the desired output is:
[[(), (1,), (1,1)], [(), (1,), (1,2)], [(), (2,), (2,1,1)], [(), (2,), (2,1,2)], [(), (2,), (2,2)]]
Any help would be much appreciated! Thank you.

Algorithm question: finding next non overlapping interval
Lets say we have a list of interval sorted by start point in ascending order. we want an algorithm to find for each interval, the next nonoverlapping interval with smallest start point.
For example we have list of interval as {(1,5), (2,4), (4, 6),(6, 10)}, for 0th interval (1, 5), the nearest nonoverlapping interval is 3rd interval which is (6, 10), for 1st (2,4) it should be 2nd (4,6). Therefore the desired output is [3, 2, 3, 1].
I can come up with an brute force O(N^2) algorithm which is to do linear scan for each interval. But I think there might exist an O(N) algorithm, anyone know the is there a better solution for this problem?

Datastructure to store database record
I want to store employees record. I don't want to use any external libraries or framework. I am trying to build the data structure from scratch.
There will be three fields,
EmployeeName Age Salary
We also want to query like,
Get all the salary where EmployeeName = "Bill" Get all the EmployeeName where salary > 2000 Get all the Salary where age='50'
I am open to use any language but not any builtin package. What is the recommended datastructure to achieve it ?

Recursive program in RISCV assembly
I am trying to create a recursive program in RISCV but I can't get it to get me the right result. It looks like it is calling itself only two times max, but I tried running it on paper and everything seems correct:
addi x31, x0, 4 addi x30, x0, 2 addi x2, x0, 1600 //initialize the stack to 1600, x2= stackpointer ecall x5, x0, 5 //read the input to x5 jal x1, rec_func ecall x0, x10, 2 //print the result beq x0, x0, end rec_func: addi x2, x2, 16 //make room in stack sd x1, 0(x2) //store pointer and result in stack sd x10, 8(x2) bge x5, x31, true // if i > 3, then go to true branch addi x10, x0, 1 // if i <= 3, then return 1 addi x2, x2, 16 // reset stack point jalr x0, 0(x1) true: addi x5, x5, 2 // compute i2 jal x1, rec_func // call recursive func for i2 ld x1, 0(x2) // load the return address ld x10, 8(x2) // load result from last function call addi x2, x2, 16 // reset stack point mul x10, x10, x30 // multiply by 2 addi x10, x10, 1 // add 1 jalr x0, 0(x1) // return end:
This is the original program logic:
if i<= 3 return 1 else return 2 * rec_func(i2) +1

Trouble returning bool from recursive function
I'm working on a homework problem in which we have to write an algorithm that can determine if a graph is bipartite or not. My python solution works, but right now it throws an exception if the graph is not bipartite, instead I would like it to return a bool. How could I modify this code?
def is_bipartite(v, visited, colors, counter): print(v) # Set this vertex to visited visited[v] = True colors[v] = counter % 2 # Explore links for u in v.links: # If linked up node u has already been visited, check its color to see if it breaks # the bipartite of the graph if u in visited: if colors[v] == colors[u]: raise Exception("Not Bipartite") # If the link has not be visited then visit it if u not in visited: visited[u] = False is_bipartite(u, visited, colors, counter + 1)

recursive function to see if 2 strings have the same number of occurrences of a character
I am trying to write a function that will take in 2 strings and a character as parameter, and search both of these strings if they have the same number of occurrences of the character parameter that was sent, here is what I have but it doesnt seem to work, any help would be appreciated thank you.
bool check(string str, char c){ for(int i = 0; i < str.length(); i++){ if(str[i] == c) return false; } return true; } bool same(const string& strA, int a, const string& strB, char ch){ if(strA.length() == 0 && strB.length() == 0) return true; if(strA[0] != ch && strB[0] != ch) same(strA.substr(1), strB.substr(1), ch); else if(strA[0] == ch && strB[0] == ch) same (strA.substr(1), strB.substr(1), ch); else if(strA.length() == 0 && strB.length() > 0) return check(strB, ch); else if(strB.length() == 0 && strA.length() > 0) return check(strA, ch); else return true; }

GetPnPUnifiedGroup : Code: Authorization_RequestDenied
How do I get a unified group from graph using this command
$group = GetPnPUnifiedGroup Identity $sitetitle
Then I get this error:
GetPnPUnifiedGroup : Code: Authorization_RequestDenied
Trying to connect with tenant user:
## know that this is not going to work ConnectPnPOnline "https://$tenantadmin.sharepoint.com" Credentia $cred
and using AADDomain with all graph permission
ConnectPnPOnline AppId $appid AppSecret $appsecret AADDomain "$tenant.onmicrosoft.com"
also trid with certificate ..
ConnectPnPOnline CertificatePath .\xxxxxcertkeyname.pfx Tenant 'xxxxxxxxxxx.onmicrosoft.com' ClientId 'xxxxxxxxxxxxxxxxxxxxxxx' Url 'https://xxxxxxxxadmin.sharepoint.com'
But can't get to work

Graph coloring problem: add colors to edges
I'm using networkx to implement the edge coloring algorithm
G = nx.Graph() G.add_nodes_from ([1,2,3,4,5]) G.add_edge(1,2) G.add_edge(1,4) G.add_edge(1,5) G.add_edge(2,3) G.add_edge(4,2) G.add_edge(3,1) G.add_edge(5,4) G.add_edge(3,5) # list of nodes U = list(G.nodes) # variable with number of edges K = G.number_of_edges() Z = [] # creating a set of available colors. We assume that K = {0, 1, . . . , K − 1}and K ≤ E def nrofCol(): Z.clear() z = 0 while z < K  1: Z.append(z) z = z+1 return Z
now i have to add a variable to each edge that represents the color. Each edge should have all the available colors as follows:
G[u][v][z] = 1,2,0 G[u][v][z] = 1,2,1 G[u][v][z] = 1,2,2 G[u][v][z] = 1,2,3 G[u][v][z] = 1,2,4 G[u][v][z] = 1,2,5 G[u][v][z] = 1,2,6 G[u][v][z] = 1,4,0 G[u][v][z] = 1,4,1 ...... where u and v are nodes and z is the color
i tried with:
for u,v in G.edges(): for z in Z: G[u][v]['color'] = z
but only one color to each edge is added. A better solution?

How to get length of the longest prefix in Trie in C
I'm trying to figure out how to find the length of the longest prefix of two words in Trie. I was trying to find a solution, but I found nothing.
I already have an implementation of Trie, where the nodes are represent by structure:
struct node { int end; // 1 if node is end of word or 0 if not int count; // The number of words that contain current node struct node *letter[26]; // Array of nodes, which represent the alphabet }; int length_of_longest_prefix(struct node *root) { //?????????? }
I tried to make a recursive function for this problem, but I could not do it.
Let´s think about this filled trie: Filled trie
What is the best way to solve this problem? Pseudocode will be very usefull.
My function:
//Global variable int total_max; //root = start int length_of_longest_prefix(struct node *root, struct node *start) { int max = 0; int depth = 0; for (int i = 0; i < 26; i++) { if(root>letter[i] != NULL && root>letter[i]>count >= 2) { depth = length_of_longest_prefix(root>letter[i], start); depth++; if(root>letter[i] == start>letter[i]) { depth = 0; } } if(depth > total_max) total_max = depth; } return depth; } int main(void) { total_max = 0; struct node *root = (struct node*)malloc(sizeof(struct node)); for (int i = 0; i < 26; i++) { root>letter[i] = NULL; } root>end = 0; root>count = 0; /*Inserting strings to Trie*/ length_of_longest_prefix(root, root); printf("%d\n", total_max); return 0; }

Implementing a very efficient bit structure
I'm looking for a solution in pesudo code or java or js for the following problem:
We need to implement an efficient bit structure to hold data for N bits (you could think of the bits as booleans as well, on/off).
We need to support the following methods: init(n) get(index) set(index, True/False) setAll(True/false)
Now I got to a solution with o(1) in all except for init that is o(n). The idea was to create an array where each index saves value for a bit. In order to support the setAll I would also save a timestamp withe the bit vapue to know if to take the value from tge array or from tge last setAll value. The o(n) in init is because we need to go through the array to nullify it, otherwise it will have garbage which can be ANYTHING. Now I was asked to find a solution where the init is also o(1) (we can create an array, but we cant clear the garbage, the garbage might even look like valid data which is wrong and make the solution bad, we need a solution that works 100%).
Update: This is an algorithmic qiestion and not a language specific one. I encountered it in an interview question. Also using an integer to represent the bit array is not good enough because of memory limits. I was tipped that it has something to do with some kind of smart handling of garbage data in the array without ckeaning it in the init, using some kind of mechanism to not fall because if the garbage data in the array (but I'm not sure how).

Farthest Successive Pair in Binary Tree
How do you design an algorithm to find the farthest successive pair in a binary tree in terms of depth?
The input is a binary tree T with an integer valued key per node
The output should be a pair of nodes (x, y) in T such that: (i) y is the successor of x in the inorder sequence of nodes of T (ii)  (depth of x)  (depth of y)  is maximum possible