Bliss8's blog

By Bliss8, 6 years ago, In English

Recently there was a problem DIV2 A to count subsequences 'QAQ' in given string

There is O(N) solution for that problem: count how many 'Q' we have on a prefix[i], and then for each 'A' res+=prefix[i]*(qTotal - prefix[i]). (multiply number of 'Q's to the left and right from 'A')

But what if we had to count 'QAQAQ' or any other sequence? I would like to get some insights on general solution of the problem.

Full text and comments »

  • Vote: I like it
  • +7
  • Vote: I do not like it

By Bliss8, 6 years ago, In English

Given small string s and bigger string b
Need to find all permutations of string s in b. How to do it in O(|b|)?

example:
s = "ab" b = "babba"

output: "ba", "ab", "ba"

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it

By Bliss8, 6 years ago, In English

Given a problem:
find diameter of binary tree (diameter is longest possible path between any two nodes in a tree)
Node format:

public class TreeNode {
    TreeNode left;
    TreeNode right;
}

External variable approach:

int maxDiameter = 0; //we will update this external variable from recursion calls
public int diameterOfBinaryTree(TreeNode root) {
    explore(root);
    return maxDiameter;
}

public int explore(TreeNode node) {
    if (node == null) {
        return 0;
    }
    int left = explore(node.left);
    int right = explore(node.right);
    maxDiameter = Math.max(maxDiameter, left + right);
    return Math.max(left, right) +  1;
}

Composite return approach:
To solve this task in clear functional way, without external variables, need to return information about max diameter found instead of updating a variable. As now it's needed to return 2 values (max diameter found and depth), will simply return int[].

public int diameterOfBinaryTree(TreeNode root) {
    return explore(root)[1];
}

public int[] explore(TreeNode node) {
    if (node == null) {
        return new int[]{0, 0};
    }
    int[] left = explore(node.left);
    int[] right = explore(node.right);
    int maxDepth = Math.max(left[0], right[0]);
    int maxDiameter = Math.max(Math.max(left[1], right[1]), left[0] + right[0]);
    return new int[]{maxDepth + 1, maxDiameter};
}

Which approach do you prefer?
From my point of view, if mutability is acceptable, external variable is the way to go.

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it

By Bliss8, history, 7 years ago, In English

question example:
given a string "aaaabbbasd" and dictionary, for example {a, aa, aaa, b, bb, s, d}
1) find one possible way to split the string into words from dictionary
2) find all possible ways to split the string into words from dictionary

Searching for the best approach on web I found different ones: dp, backtracking + memorization, dfs + memorization.
I lost in all of this huge variety.
Does somebody know what approach is the best here?

Full text and comments »

  • Vote: I like it
  • -5
  • Vote: I do not like it

By Bliss8, history, 8 years ago, In English

Is there a way to find some post if the only thing i remember is approximate date when it was visible in "Recent actions"? Seems like CF is lacking of such functionality.

Full text and comments »

  • Vote: I like it
  • +12
  • Vote: I do not like it