пятница, 24 июля 2015 г.

Interview task

Problem: Count the most frequent k-mers in a text

Input: A string text and an integer k
Output: All most frequent k-mers in text

Term k-mer refers to a string of length k. A k-mer pattern is a most frequent k-mer in a text if no other k-mer is more frequent than pattern.

Example:
1. AATTT is a most frequent 5-mer in text: acaAATTTgcatAATTTcgggaAATTTcct

Note: Count(CGATATATCCATAG, ATA) is equal to 3 (not 2) since you should account for overlapping occurrences of Pattern in Text.

k = 4
Text:
atcaatgatcaacgtaagcttctaagcatgatcaaggtgctcacacagtttatccacaac
ctgagtggatgacatcaagataggtcgttgtatctccttcctctcgtactctcatgacca
cggaaagatgatcaagagaggatgatttcttggccatatcgcaatgaatacttgtgactt
gtgcttccaattgacatcttcagcgccatattgcgctggccaaggtgacggagcgggatt
acgaaagcatgatcatggctgttgttctgtttatcttgttttgactgagacttgttagga
tagacggtttttcatcactgactagccaaagccttactctgcctgacatcgaccgtaaat
tgataatgaatttacatgcttccgcgacgatttacctcttgatcatcgatccgattgaag
atcttcaattgttaattctcttgcctcgactcatagccatgatgagctcttgatcatgtt
tccttaaccctctattttttacggaagaatgatcaagctgctgctcttgatcatcgtttc