Determining DNA Health HackerRank Solution in C, C++, Java, Python

DNA is a nucleic acid present in the bodies of living things. Each piece of DNA contains a number of genes, some of which are beneficial and increase the DNA’s total health. Each gene has a health value, and the total health of a DNA is the sum of the health values of all the beneficial genes that occur as a substring in the DNA. We represent genes and DNA as non-empty strings of lowercase English alphabetic letters, and the same gene may appear multiple times as a susbtring of a DNA.

Given the following:

  • An array of beneficial gene strings, genes = [g0,g1,g2…,gn-1]. Note that these gene sequences are not guaranteed to be distinct.
  • An array of gene health values,health=[h0,h1,h2…,hn-1] , where each  is the health value for gene .
  • A set of s DNA strands where the definition of each strand has three components,start ,end , and d, where string  is a DNA for which genes gstart,…,gend are healthy.

Find and print the respective total healths of the unhealthiest (minimum total health) and healthiest (maximum total health) strands of DNA as two space-separated values on a single line.

Constraints

  • 1<=n, s<=10^5
  • 0<=h<=10^7
  • 0<=first<=last<n
  • 1 <= the sum of the lengths of all genes and DNA strands <= 2*10^6
  • It is guaranteed that each  consists of lowercase English alphabetic letters only (i.e., a to z).

Output Format

Print two space-separated integers describing the respective total health of the unhealthiest and the healthiest strands of DNA.

Sample Input 0

6

a b c aa d b

1 2 3 4 5 6

3

1 5 caaab

0 4 xyz

2 4 bcdybc

 

Sample Output 0

0 19

Determining DNA Health HackerRank Solution in C++

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>
#include <cmath>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>

using namespace std;

#define INF 1e+9
#define mp make_pair
#define pb push_back
#define fi first
#define fs first
#define se second
#define i64 long long
#define li long long
#define lint long long
#define pii pair<int, int>
#define vi vector<int>

#define forn(i, n) for (int i = 0; i < (int)n; i++)
#define fore(i, b, e) for (int i = (int)b; i <= (int)e; i++)

struct vertex {
    int next[26];
    vi numbers;
    int p;
    char pch;
    int link;
    int go[26];
};

const int maxn = 2e6+5;
 
vertex t[maxn];
int sz;
int cost[maxn];
 
void init() {
    t[0].p = t[0].link = -1;
    memset (t[0].next, 255, sizeof t[0].next);
    memset (t[0].go, 255, sizeof t[0].go);
    sz = 1;
}
 
void add_string (const string & s, int num) {
    int v = 0;
    for (size_t i=0; i<s.length(); ++i) {
        int c = s[i]-'a';
        if (t[v].next[c] == -1) {
            memset (t[sz].next, 255, sizeof t[sz].next);
            memset (t[sz].go, 255, sizeof t[sz].go);
            t[sz].link = -1;
            t[sz].p = v;
            t[sz].pch = c;
            t[v].next[c] = sz++;
        }
        v = t[v].next[c];
    }
    t[v].numbers.pb(num);
}
 
int go (int v, int c);
 
int get_link (int v) {
    if (t[v].link == -1) {
        if (v == 0 || t[v].p == 0)
            t[v].link = 0;
        else
            t[v].link = go (get_link (t[v].p), t[v].pch);
    }
    return t[v].link;
}
 
int go (int v, int c) {
    if (t[v].go[c] == -1) {
        if (t[v].next[c] != -1)
            t[v].go[c] = t[v].next[c];
        else
            t[v].go[c] = v==0 ? 0 : go (get_link (v), c);
    }
    return t[v].go[c];
}

int main() {
#ifdef LOCAL
    freopen("inp", "r", stdin);
    //freopen("outp", "w", stdout);
#else
    // freopen(TASKNAME ".in", "r", stdin);
    // freopen(TASKNAME ".out", "w", stdout);
#endif
    init();
    int n;
    scanf("%d", &n);
    forn(j, n) {
        string s;
        cin >> s;
//        cout << "s = " << s << endl;
        add_string(s, j);
    }
    forn(j, n)
        scanf("%d", &cost[j]);
    int q;
    scanf("%d", &q);
    i64 minn = 0;
    i64 maxx = 0;
    forn(query, q) {
        int L, R;
        scanf("%d%d", &L, &R);
        string s;
        cin >> s;
        int cur = 0;
        i64 sum = 0;
        for (char c : s) {
            cur = go(cur, (int)(c - 'a'));
            //printf("cur = %d\n", cur);
            int tmp = cur;
            while(tmp != 0) {
                for (int x : t[tmp].numbers) {
                    if (x >= L && x <= R)
                        sum += cost[x];
                    //printf("%c x = %d sum = %lld\n", c, x, sum);
                }
                tmp = get_link(tmp);
            }
        }
        if (query == 0 || sum > maxx)
            maxx = sum;
        if (query == 0 || sum < minn)
            minn = sum;
    }
    cout << minn << " " << maxx;
}

 

Determining DNA Health HackerRank Solution in Java

import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class QuickScanner {
    static final int BUFFER_NOT_READ = -1;
    static final int BUFFER_SIZE = 64*1024;
    final InputStream is;
    int curr = BUFFER_NOT_READ;
    int length;
    byte[] buffer = new byte[BUFFER_SIZE];
    QuickScanner(InputStream is) {
        this.is = is;
    }

    void readBuffer() throws IOException {
        int readBytes = is.read(buffer);
        if (readBytes == -1) {
            throw new IllegalStateException(
                    "End of stream reached.");
        }
        curr = 0;
        length = readBytes;
    }

    void initialRead() throws IOException {
        if (curr == BUFFER_NOT_READ || curr >= BUFFER_SIZE) {
            readBuffer();
        }
    }

    char nextChar() throws IOException {
        initialRead();
        if (curr >= length) {
            return ' ';
        }
        return (char) buffer[curr++];
    }

    // Currently only positive numbers are supported.
    long nextLong() throws IOException {
        StringBuilder sb = new StringBuilder();
        while (true) {
            char ch = nextChar();
            if (ch >= '0' && ch <= '9') {
                sb.append(ch);
            } else {
                break;
            }
        }
        return Long.parseLong(sb.toString());
    }

    // Currently only positive numbers are supported.
    int nextInt() throws IOException {
        long l = nextLong();
        assert(l < (long) Integer.MAX_VALUE);
        return (int) l;
    }

    String nextAlphanumericString() throws IOException {
        StringBuilder sb = new StringBuilder(256);
        while (true) {
            char ch = nextChar();
            if ((ch >= 'a' && ch <= 'z') ||
                    (ch >= '0' && ch <= '9')) {
                sb.append(ch);
            } else {
                break;
            }
        }
        return sb.toString();
    }

    void close() throws IOException {
        length = 0;
        curr = 0;
        is.close();
    }
}

class DNATask implements Comparable<DNATask> {
    final int gene;
    final int dna;
    final boolean isStart;

    DNATask(int gene, int dna, boolean isStart) {
        this.gene = gene;
        this.dna = dna;
        this.isStart = isStart;
    }

    @Override
    public int compareTo(DNATask o) {
        int comp;
        comp = Integer.compare(gene, o.gene);
        if (comp != 0) return comp;
        comp = Integer.compare(dna, o.dna);
        if (comp != 0) return comp;
        return - Boolean.compare(isStart, o.isStart);
    }

    @Override
    public String toString() {
        return "DNATask{" +
                "gene=" + gene +
                ", dna=" + dna +
                ", isStart=" + isStart +
                '}';
    }
}

class Node {
    final Node parent;
    final int ch;  // 0-25 : 'a' - 'z'
    String nodeName;  // used only for printing the tree

    Node[] children;
    long score;

    Node postfix;
    Set<Node> reversePostfixes;

    Node(Node parent, int ch) {
        this.parent = parent;
        this.ch = ch;
    }

    void add(String str, int strIdx, int sc) {
        if (strIdx >= str.length()) {
            score += sc;
            // clearTotalScore();
        } else {
            int c = str.charAt(strIdx) - 'a';
            if (children == null) {
                children = new Node[26];
            }
            Node child = children[c];
            if (child == null) {
                children[c] = child = new Node(this, c);
                child.calculatePostfix();
                child.updateReversePostfixes(this);
            }
            child.add(str, strIdx + 1, sc);
        }
    }

    void setPostfix(Node newPostfixNode) {
        if (postfix != null) {
            postfix.reversePostfixes.remove(this);
        }
        postfix = newPostfixNode;
        if (newPostfixNode != null) {
            Set<Node> h = newPostfixNode.reversePostfixes;
            if (h == null) {
                newPostfixNode.reversePostfixes =
                        h = new HashSet<>(4);
            }
            h.add(this);
        }
    }

    void calculatePostfix() {
        if (parent == null) {
            return;
        }
        Node p = parent.postfix;
        if (p == null) {
            setPostfix(parent);
            return;
        }
        while (true) {
            if (p.children != null) {
                Node child = p.children[ch];
                if (child != null) {
                    setPostfix(child);
                    break;
                }
            }
            if (p.postfix == null) {
                setPostfix(p);
                break;
            }
            p = p.postfix;
        }
    }

    void updateReversePostfixes(Node parentNode) {
        if (parentNode == null || parentNode == this ||
                parentNode.reversePostfixes == null) return;
        for (Node n:parentNode.reversePostfixes.toArray(
                new Node[0])) {
            if (n.children != null) {
                Node sameChild = n.children[ch];
                if (sameChild != null) {
                    sameChild.setPostfix(this);
                    continue;
                }
            }
            updateReversePostfixes(n);
        }
    }

    String getNodeName() {
        if (nodeName == null) {
            nodeName = parent == null
                ? "l_" : parent.getNodeName() + (char)(ch + 'a');
        }
        return nodeName;
    }

    @Override
    public String toString() {
        return "Node{" +
                "ch=" + (char)(ch + 'a') +
                ", nodeName='" + getNodeName() + '\'' +
                ", score=" + score +
                ", postfix=" + (postfix == null ?
                '-' : postfix.getNodeName()) +
                '}';
    }

    void printTree() {
        System.err.println(getNodeName() +
                " [ label=\"" + (char)(ch + 'a') +
                ": " + score + " (" + getTotalScore() + ")\" ]");
        if (parent != null) {
            System.err.println(
                    parent.getNodeName() + " -> " + getNodeName());
        }
        if (postfix != null) {
            System.err.println(
                    getNodeName() + " -> " +
                            postfix.getNodeName() + " [color=blue]");
        }
        if (children != null) {
            for (int i = 0; i < 26; i++) {
                Node child = children[i];
                if (child != null) child.printTree();
            }
        }
    }

    public long getTotalScore() {
        long sc = score;
        if (postfix != null) {
            sc += postfix.getTotalScore();
        }
        return sc;
    }
}

class DNAHealth {
    private static final int SPACE = ' ' - 'a';

    int n;  // number of genes
    String[] genes;
    int[] scores;

    int s;  // number of DNA strands
    String[] dnaStrands;
    DNATask[] dnaTasks;
    long[] dnaScores;

    long startTime;
    long lastTime;

    void startTimer() {
        startTime = System.nanoTime();
        lastTime = startTime;
        System.err.println("--- Timer started.");
    }

    synchronized void logTime(String txt) {
        long now = System.nanoTime();
        System.err.format("--- %8.3fms (%8.3fms) %s\n",
                (now - startTime)/1000000.0, (now - lastTime)/1000000.0, txt);
        lastTime = now;
    }

    long addTime = 0;
    long addCount = 0;
    long walkTime = 0;
    long walkCount = 0;

    void readInitialData(String inputFile) throws IOException {
        final QuickScanner scanner = new QuickScanner(inputFile == null ? System.in : new FileInputStream(inputFile));
        n = scanner.nextInt();

        genes = new String[n];

        for (int i = 0; i < n; i++) {
            genes[i] = scanner.nextAlphanumericString();
        }

        scores = new int[n];

        for (int i = 0; i < n; i++) {
            scores[i] = scanner.nextInt();
        }

        logTime("Genes read: " + n);

        s = scanner.nextInt();

        dnaTasks = new DNATask[2*s];
        dnaStrands = new String[s];
        for (int i = 0; i < s; i++) {
            int first = scanner.nextInt();
            int last = scanner.nextInt();
            dnaStrands[i] = scanner.nextAlphanumericString();
            int idx = 2*i;
            dnaTasks[idx] = new DNATask(first, i, true);
            dnaTasks[idx + 1] = new DNATask(last + 1, i, false);
        }
        scanner.close();
        dnaScores = new long[s];
        logTime("DNA Strands read: " + s);
    }

    class ProcessingThread extends Thread {
        final int partition;
        final int geneStart;
        int geneEnd;
        final int dnaTaskStartIdx;
        int dnaTaskEndIdx;
        Integer[] finishProc;
        long t0;

        void resetT0() {
            t0 = System.nanoTime();
        }

        void endWalkTime() {
            synchronized (DNAHealth.this) {
                walkTime += System.nanoTime() - t0;
                walkCount++;
            }
        }

        void endAddTime() {
            synchronized (DNAHealth.this) {
                addTime += System.nanoTime() - t0;
                addCount++;
            }
        }

        ProcessingThread(int partition, int geneStart, int dnaTaskStartIdx) {
            super("Partition " + partition);
            this.partition = partition;
            this.geneStart = geneStart;
            this.dnaTaskStartIdx = dnaTaskStartIdx;
        }

        @Override
        public void run() {
            logTime("Thread for partition " +
                    partition + " started. geneStart: " + geneStart);
            final Node tree = new Node(null, SPACE);
            int treeBuiltIdx = geneStart - 1;
            for (int i = dnaTaskStartIdx; i < dnaTaskEndIdx; i++) {
                DNATask task = dnaTasks[i];
                while (treeBuiltIdx < task.gene - 1) {
                    treeBuiltIdx++;
                    resetT0();
                    tree.add(genes[treeBuiltIdx], 0, scores[treeBuiltIdx]);
                    endAddTime();
                }
                long score = (task.isStart ? -1L : 1L)
                        * calcScoreForStrand(tree, dnaStrands[task.dna]);
                synchronized (DNAHealth.this) {
                    dnaScores[task.dna] += score;
                }
            }
            while (treeBuiltIdx < geneEnd - 1) {
                treeBuiltIdx++;
                resetT0();
                tree.add(genes[treeBuiltIdx], 0, scores[treeBuiltIdx]);
                endAddTime();
            }
            for (int finishProcDna : finishProc) {
                long sc = calcScoreForStrand(tree, dnaStrands[finishProcDna]);
                synchronized (DNAHealth.this) {
                    dnaScores[finishProcDna] += sc;
                }
            }
            logTime("Thread for partition " + partition + " completed.");
        }

        long calcScoreForStrand(Node tree, String d) {
            resetT0();
            Node p = tree;
            long score = 0;
            for (int i = 0; i < d.length(); i++) {
                int c = d.charAt(i) - 'a';
                while (true) {
                    if (p.children != null) {
                        Node child = p.children[c];
                        if (child != null) {
                            p = child;
                            score += p.getTotalScore();
                            break;
                        }
                    }
                    if (p.postfix == null) {
                        // we are at root.
                        break;
                    }
                    p = p.postfix;
                }
            }
            endWalkTime();
            return score;
        }
    }

    void calcStrands() throws Exception {
        Arrays.sort(dnaTasks);
        logTime("DNATasks sorted.");
        int partitions =
            n > 50 * s ? 8 :
                    n > 5 * s ? 4 : 1;
        logTime("Partitions: " + partitions);
        if (partitions > n) partitions = n;
        ProcessingThread[] threads =
                new ProcessingThread[partitions];
        Set<Integer> dnasInProgress = new HashSet<>();
        int lastPartition = -1;
        for (int i = 0; i < dnaTasks.length; i++) {
            DNATask task = dnaTasks[i];
            int partition = (int) (
                    (task.gene - 1.0) * partitions / (n + 0.0) );
            if (partition != lastPartition) {
                if (lastPartition >= 0) {
                    ProcessingThread lastThread =
                            threads[lastPartition];
                    lastThread.finishProc =
                            dnasInProgress.toArray(new Integer[0]);
                    lastThread.dnaTaskEndIdx = i;
                    lastThread.geneEnd = task.gene;
                    lastThread.start();
                }
                lastPartition = partition;
            }

            ProcessingThread thread = threads[partition];
            if (thread == null) {
                threads[partition] = thread =
                        new ProcessingThread(partition, task.gene, i);
            }

            if (task.isStart) {
                dnasInProgress.add(task.dna);
            } else {
                dnasInProgress.remove(task.dna);
            }
        }
        if (lastPartition >= 0 && threads[lastPartition] != null) {
            ProcessingThread lastThread = threads[lastPartition];
            lastThread.finishProc = new Integer[0];
            lastThread.dnaTaskEndIdx = dnaTasks.length;
            lastThread.geneEnd = n;
            lastThread.start();
        }
        for (ProcessingThread thread : threads) {
            if (thread != null) thread.join();
        }
    }

    void printTree(int builtUpTo) {
        System.err.println("*** Tree built up to " + (builtUpTo - 1));
        System.err.println("digraph x {");
        // tree.printTree();
        System.err.println("}");
    }

    void run(String[] args) throws Exception {
        startTimer();
        readInitialData(args.length > 0 ? args[0] : null);
        logTime("Data read.");
        calcStrands();
        logTime("Calculated.");
        long minScore = Long.MAX_VALUE;
        long maxScore = Long.MIN_VALUE;
        for (int i = 0; i < s; i++) {
            long score = dnaScores[i];
            if (score > maxScore) {
                maxScore = score;
            }
            if (score < minScore) {
                minScore = score;
            }
        }
        logTime(String.format(
                "End. Add time (%d): %8.3fms, Walk time (%d): %8.3fms",
                addCount, addTime / 1000000.0,
                walkCount, walkTime / 1000000.0));
        System.out.println(minScore + " " + maxScore);
    }
}

public class Solution {
    public static void main(String[] args) throws Exception {
        new DNAHealth().run(args);
    }
}

 

Determining DNA Health HackerRank Solution in Python

from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

# ------------------------------------------------------------------------------
def getHealth(seq, first, last, largest):
  h, ls = 0, len(seq)
  for f in range(ls):
    for j in range(1, largest+1):
      if f+j > ls: break
      sub = seq[f:f+j]
      if sub not in subs: break
      if sub not in gMap: continue
      ids, hs = gMap[sub]
      h += hs[bRight(ids, last)]-hs[bLeft(ids, first)]
  return h

# ------------------------------------------------------------------------------
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda: [[], [0]])
subs = set()
for id, gene in enumerate(genes):
  gMap[gene][0].append(id)
  for j in range(1, min(len(gene), 500)+1): subs.add(gene[:j])
for v in gMap.values():
  for i, ix in enumerate(v[0]): v[1].append(v[1][i]+healths[ix])

# ------------------------------------------------------------------------------
largest = max(list(map(len, genes)))
hMin, hMax = inf, 0
for _ in range(howStrands):
  firstLastd = input().split()
  first = int(firstLastd[0])
  last = int(firstLastd[1])
  strand = firstLastd[2]
  h = getHealth(strand, first, last, largest)
  hMin, hMax = min(hMin, h), max(hMax, h)
print(hMin, hMax)

 

Determining DNA Health HackerRank Solution in C#

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
    static void Main(String[] args)
    {
            Console.ReadLine();
            string[] patterns = Console.ReadLine().Split(' ');
            int[] values = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
            var trie = MakeTrie(patterns, values);
            int s = Convert.ToInt32(Console.ReadLine());
            ulong max = ulong.MinValue;
            ulong min = ulong.MaxValue;
            for (int a = 0; a < s; a++)
            {
                string str = Console.ReadLine();
                if (str == null)
                    continue;
                string[] tokens = str.Split(' ');
                int first = Convert.ToInt32(tokens[0]);
                int last = Convert.ToInt32(tokens[1]);
                string d = tokens[2];
                ulong val = GetValue(trie, d, first, last);
                if (val > max) max = val;
                if (val < min) min = val;
            }

            Console.WriteLine("{0} {1}", min, max); 
    }

    private static Trie MakeTrie(string[] patterns, int[] values)
    {
        var trie = new Trie();
        int index = 0;
        foreach (var item in patterns)
        {
            trie.AddWord(item, index, values[index++]);
        }

        return trie;
    }

    private static ulong GetValue(Trie t, string d, int first, int last)
    {
        Node runner;
        ulong total = 0;
        var index = new List<int>();
        var value = new List<int>();
        bool isEndOfWord = false;
        for (int i = 0; i < d.Length; ++i)
        {
            runner = t.GetHeadNode();
            isEndOfWord = false;
            for (int j = 0; j + i < d.Length; ++j)
            {
                runner = t.FindNextLetter(d[i + j], ref isEndOfWord, ref index, ref value, runner);
                if (runner == null) break;
                if (isEndOfWord)
                {
                    isEndOfWord = false;
                    for (int k = 0; k < index.Count; k++)
                    {
                        if (index[k] >= first && index[k] <= last)
                            total += (ulong)value[k]; 
                    }
                }

            }
        }

        return total;
    }

    
}

public class Trie
{
    Node head;
    public Trie()
    {
        this.head = new Node();
    }

    public Node GetHeadNode()
    {
        return head;
    }

    public void AddWord(string word, int index, int value)
    {
        Node runner = head;
        for(int i = 0; i < word.Length; ++i)
        {
            runner = runner.AddLetter(word[i]);
        }

        runner.SetIsEndOfWord();
        runner.SetIndex(index);
        runner.SetValue(value);
    }

    public Node FindNextLetter(char letter, ref bool IsEndOfWord, ref List<int> Index, ref List<int> Value, Node node)
    {
        if (node == null) return null;
        Node curr = node.GetLetter(letter);
        if (curr == null) return null;
        if (curr.IsEndOfWord)
        {
            Index = curr.Index;
            Value = curr.Value;
            IsEndOfWord = true;
        }

        return curr;
    }
}

public class Node
{
    Node[] letters;

    public Node(char c)
    {
        CurrentChar = c;
        if(letters == null)
            letters = new Node[26];
    }

    public Node()
    {
        CurrentChar = null;
        if (letters == null) 
            letters = new Node[26];
    }

    public List<int> Index { get; private set; }
    public bool IsEndOfWord { get; private set; }
    public char? CurrentChar { get; private set; }
    public List<int> Value { get; private set; }

    public Node AddLetter(char c)
    {
        if (letters[c - 'a'] == null)
        {
            letters[c - 'a'] = new Node(c);
        }

        return letters[c - 'a'];
    }

    public Node GetLetter(char c)
    {
        return letters[c - 'a'];
    }

    public void SetIndex(int i)
    {
        if (Index == null) Index = new List<int>();
        Index.Add(i);
    }

    public void SetValue(int i)
    {
        if (Value == null) Value = new List<int>();
        Value.Add(i);
    }

    public void SetIsEndOfWord()
    {
        IsEndOfWord = true;
    }
}

 

Attempt Determining DNA Health Hackerrank Challenge

Link – https://www.hackerrank.com/challenges/determining-dna-health

Leave a Comment