We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Strings
  4. Determining DNA Health
  5. Discussions

Determining DNA Health

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 236 Discussions, By:

recency

Please Login in order to post a comment

  • leoalexander_777
    6 days ago+ 0 comments

    can some suggesset how this can be optimized?

    int TotalHealthOfUnhealthiest (int first, int last, string d, 
                                                                    vector<string> genes, vector<int> health)
    {
            int result = 0, hvalue, start, end, sub;
    
            for(int i = first; i <= last; i++)
            {
                    string str = genes[i];
    
                    start = 0;
                    end = str.size();
    
                    while(d.size() >= end)
                    {
                            string dsub = "";
                            sub = start;
    
                            while(sub < end)
                            {
                                    dsub += d[sub];
                                    sub++;
                            }
    
                            if(str == dsub)
                            {
                                    result += health[i];
                            }
    
                            start++;
                            end++;
                    } 
            }
    
            return result;
    }
    
    0|
    Permalink
  • helenalovato
    2 weeks ago+ 0 comments

    thanks

    0|
    Permalink
  • davidjohan405
    1 month ago+ 0 comments

    History, Suryakant Tripathi Nirala was a renowned Hindi poet, novelist, essayist, and story writer. He was born on February 21, 1896, in a small village in Uttar Pradesh, India, and died on March 15, 1961, in Allahabad, India.

    0|
    Permalink
  • davidjohan405
    2 months ago+ 0 comments

    NFTs have gained popularity in recent years as a new way for artists, musicians, and other content creators to monetize their work. With NFTs, creators can sell their digital works as unique, one-of-a-kind assets, which can be owned and traded by buyers. WE LIST NFT PROJECTS TO FACILITATE THE USER TO SEARCH FOR NEW PROJECTS

    -1|
    Permalink
  • mark_webster
    2 months ago+ 0 comments

    Fast C++ version.

    O(n) complexity where n=length of DNA string. ie, performs only 1 lookup / comparison per character in DNA string. When a valid gene sequence is found, a further O(log m) where m=number of duplicate gene entries, to locate the first gene that falls within the [start, end] range. Finally, O(p) to enumerate each gene that falls within the [start, end] range.

    int main() {
        int ngenes, ndna;
        string tmp;
    
        cin >> ngenes;
        struct sHealth {
            int    index;
            int    val;
        };
        struct sGene {
            string            seq;
            vector<sHealth>    health;
            sGene() = default;
            sGene(const string &s) : seq{s} {}
        };
        struct sLut { int gi; int v[26]; };
        vector<sGene> genes {{""}};
        vector<sLut> lut(26);
    
        {
            vector<int> ndx(ngenes);
            unordered_map<string,int> map;
    
            for (int i=0; i<ngenes; i++) {
                cin >> tmp;
                auto t = map.emplace(tmp, genes.size());
                if (t.second) genes.emplace_back(tmp);
                ndx[i] = t.first->second;
    
                sLut *L = &lut[tmp[0]-97];
                for (int j=1, l=tmp.length(); ; j++) {
                    if (j == l) { L->gi = ndx[i]; break; }
                    int ch = tmp[j]-97;
                    if (L->v[ch]) L = &lut[L->v[ch]]; else {
                        L->v[ch] = lut.size();
                        lut.emplace_back();
                        L = &lut.back();
                    }
                }
            }
    
            for (int i=0, h; i<ngenes; i++) {
                cin >> h;
                genes[ndx[i]].health.push_back({i, h});
            }
        }
    
        cin >> ndna;
        int64_t hsum=0, htop=0, hlow=INT64_MAX;
    
        for (int i=0, first, last; i<ndna; i++) {
            string dna;
            cin >> first >> last >> dna;
    
            for (int p=hsum=0, e=dna.length(), j, n; p<e; p++) {
                sLut *L = &lut[dna[p]-97];
                for (j=p;;) {
                    if (L->gi) {
                        const auto &G = genes[L->gi];
                        int l=0, s=G.health.size(), r=s, m;
                        do {
                            m = l + ((r-l) >> 1);
                            const auto &H = G.health[m];
                            if (first > H.index) { l=m+1; continue; }
                            if (first < H.index && m && first <= G.health[m-1].index) { r=m; continue; }
                            while (m < s && G.health[m].index <= last) hsum += G.health[m++].val;
                            break;
                        } while (r!=l);
                    }
    
                    if (++j >= e) break;
                    n = L->v[dna[j]-97];
                    if (n) L = &lut[n]; else break;
                }
            }
            htop = max(htop, hsum);
            hlow = min(hlow, hsum);
        }
        cout << hlow << " " << htop << "\n";
        
        return 0;
    }
    
    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy