Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
2.1 kB
5
Indexable
Never
1. Greedy Algorithm :

public class GreedyAlgorithm {
int currentLevel = 0;
final int maxLevel = 3;
SocialConnector sc;
public GreedyAlgorithm(SocialConnector sc) {
this.sc = sc;
}
}
public long findMostFollowersPath(String account) {
long max = 0;
SocialUser toFollow = null;

List followers = sc.getFollowers(account);
for (SocialUser el : followers) {
long followersCount = el.getFollowersCount();
if (followersCount > max) {
toFollow = el;
max = followersCount;
}
}
if (currentLevel < maxLevel - 1) {
currentLevel++;
max += findMostFollowersPath(toFollow.getUsername());
}
return max;
}

2. Recursive Algorithm :

static class Node
{
Node left;
Node right;
int data;
};
static Node newNode(int data)
{
Node temp = new Node();

temp.data = data;
temp.left = null;
temp.right = null;

return temp;
}
static void printPath(int Data,
HashMap<Integer,
Integer> parent)
{
if (parent.get(Data) == Data)
return;
printPath(parent.get(Data), parent);
System.out.print(parent.get(Data) + " ");
}
static void leftMostShortest(Node root)
{
Queue<Node> q = new LinkedList<>();
q.add(root);
int LeafData = -1;
Node temp = null;
HashMap<Integer,
Integer> parent = new HashMap<>();
parent.put(root.data, root.data);=
while (!q.isEmpty())
{
temp = q.poll();
if (temp.left == null &&
temp.right == null)
{
LeafData = temp.data;
break;
}
else
{
if (temp.left != null)
{
q.add(temp.left);

// Set temp's left node's parent
// as temp
parent.put(temp.left.data,
temp.data);
}
if (temp.right != null)
{
q.add(temp.right);
parent.put(temp.right.data,temp.data);
}
}
}
printPath(LeafData, parent);
System.out.println(LeafData + " ");
}

3. Dynamic Programming :

class GFG
{
static int[] dp = new int[100];
static void dfs(int[] a, Vector<Integer>[] v,
int u, int parent)
{
int maximum = 0;
for (int child : v[u])
{
if (child == parent)
continue;
dfs(a, v, child, u);]
maximum = Math.max(maximum, dp[child]);
}
dp[u] += maximum;
}
Vector<Integer>[] v)
{
dfs(a, v, 1, 0);
return dp[1];
}
}

Was this answer helpful?
Post a question

Answers from our experts for your tough homework questions
20 questions left - Renews Jan. 15, 2023
Post a question text