Booking.com Interview Question Software Developers
Country: United States
Here is a simple java solution -
package com.cubestacklabs.problems.careercup;
import java.util.*;
import java.util.stream.Collectors;
/**
* Given a stream of characters (e.g. acacabcatghhellomvnsdb) and
* a list of words (e.g. ["aca","cat","hello","world"] )
* find and display count of each and every word once the stream ends.
* (Like : "aca" : 2 , "cat" : 1 , "hello" : 1 , "world" : 0 )
*/
public class StreamOfCharacters {
public static void main(String[] args) {
System.out.println(wordCount("acacabcatghhellomvnsdb", new String[] { "aca","cat","hello","world" }));
}
public static Map<String, Integer> wordCount(String stream, String[] words) {
Map<String, Integer> counts = new HashMap<>();
for(String w: words) counts.put(w, 0);
List<Integer> wordLengths = counts.keySet().stream().map(key -> key.length()).distinct().sorted().collect(Collectors.toList());
char[] chars = stream.toCharArray();
for(int i=0; i<chars.length; i++) {
if(!checkChars(chars, counts, wordLengths, i)) break;
}
return counts;
}
private static boolean checkChars(char[] stream, Map<String, Integer> counts, List<Integer> wordLengths, int begin) {
for(int length: wordLengths) {
int end = length + begin;
if(end > stream.length) {
return false;
} else {
char[] temp = Arrays.copyOfRange(stream, begin, end);
String part = String.valueOf(temp);
if(counts.containsKey(part)) {
counts.put(part, counts.get(part) + 1);
}
}
}
return true;
}
}
First thought:
dictionary made by Trie, in example, only 4 words. For each position in the input stream, along with the next k characters (k is the length of the longest word in the dictionary), we search in the dictionary and see which words appears, and increase its counter.
The complexity is than O(kn), k is the length of the longest word in the dictionary, and n is the length of the input stream.
Trie is hard to implement during an Interview though.
Below is the code that I have written in C++,
Comment if you think code can be made more efficient
#include <iostream>
#include <list>
#include <map>
#include<string>
#include <utility>
using namespace std;
void findsubstring(string,list<string>,map<string,int>&);
int main()
{
list <string> l;
l.push_back("aca");
l.push_back("cat");
l.push_back("hello");
l.push_back("world");
string input = "acacabcatghhellomvnsdb";
map<string,int> _map;
list<string>::iterator li = l.begin();
while(li != l.end())
{
// _map.insert(*li,0);
_map[*li] = 0;
li++;
}
map<string,int>::iterator mitr = _map.begin();
while(mitr != _map.end())
{
cout<<mitr->first<<" "<<mitr->second<<endl;
mitr++;
}
findsubstring(input,l,_map);
mitr = _map.begin();
while(mitr != _map.end())
{
cout<<mitr->first<<" "<<mitr->second<<endl;
mitr++;
}
return 0;
}
void findsubstring(string inputS,list<string> l,map<string,int>& m)
{
//int len = input.length();
list<string>::iterator ltr = l.begin();
while(ltr != l.end())
{
string input = inputS;
int step;
for(int i=0; i<input.length()-1; i++)
{ step = input.find(*ltr);
if(step!= string::npos)
{
step++;
m.find(*ltr)->second++;
// string st = *ltr;
// step = step+st.length();
}
else{
step =i+1;
}
input = input.substr(step,input.length());
}
ltr++;
}
}
#!/usr/bin/env python
def main():
str_stream = "acacabcatghhellomvnsdb"
words = { "aca" : 0, "cat" : 0, "hello" : 0, "world" : 0 }
for key in words:
i = 0
while True:
i = str_stream.find(key, i)
if i >= 0:
words[key] += 1
i += 1
else:
break
for key in sorted(words):
print("{}: {}".format(key, words[key]))
main()
Trie is a good solution. Another solution is postfix array.
1. Generate a postfix array based on input string. Time complexity O(n). Space complexity O(n). n is the length of the stream.
2. Sort the postfix array. Time complexity O(n*lgn*t). t is the average character comparison number in sort. Space complexity O(lgn), the maximize stack number in quick sort.
3. Iterate the list of words. Do binary search in postfix array. Time complexity O(lgn*k). k is the maximize length of word.
Overall time complexity: O(n*lgn*t). space complexity O(lgn).
bool lessStr(const char * s1, const char * s2) {
return strcmp(s1, s2) <= 0;
}
bool equalStr(const char * s1, const char * s2) {
int sz1 = strlen(s1);
int sz2 = strlen(s2);
if(sz1 < sz2) return false;
int i = 0;
while(i < sz2) {
if(s1[i] != s2[i]) return false;
i ++;
}
return true;
}
int binarySearchLeftIndex(const char * postfix[], int lo, int hi, const char * s) {
int start = lo;
int end = hi;
while(start < end) {
int mid = start + (end - start) / 2;
if(equalStr(postfix[mid], s)) {
end = mid;
}
else if(lessStr(postfix[mid], s)) {
start = mid + 1;
}
else {
end = mid - 1;
}
}
return equalStr(postfix[start], s) ? start : -1;
}
int binarySearchRightIndex(const char * postfix[], int lo, int hi, const char * s) {
int start = lo;
int end = hi;
while(start < end - 1) {
int mid = start + (end - start) / 2;
if(equalStr(postfix[mid], s)) {
start = mid;
}
else if(lessStr(postfix[mid], s)) {
start = mid + 1;
}
else {
end = mid - 1;
}
}
return equalStr(postfix[end], s) ? end :
equalStr(postfix[start], s) ? start : -1;
}
void f(string & s, vector<string> & v) {
int sz = s.size();
if(0 == sz) return ;
const char * postfix[sz];
for(int i = 0; i < sz; i ++) {
postfix[i] = s.c_str() + i;
}
sort(postfix, postfix + sz, lessStr);
for(int i = 0; i < v.size(); i ++) {
int leftIndex = binarySearchLeftIndex(postfix, 0, sz - 1, v[i].c_str());
if(-1 == leftIndex) {
printf("count of %s is: %d\n", v[i].c_str(), 0);
continue;
}
int rightIndex = binarySearchRightIndex(postfix, 0, sz - 1, v[i].c_str());
printf("count of %s is: %d\n", v[i].c_str(), rightIndex - leftIndex + 1);
}
}
Objective-C solution
O(n*t) complexity where t= number of strings to search and n = length of stream
#define VALUE_KEY 1
#define COUNT_KEY 2
NSMutableArray *stringsToSearchFor = [@[[@{@VALUE_KEY: @"cat", @COUNT_KEY: @0} mutableCopy],[@{@VALUE_KEY: @"aca", @COUNT_KEY: @0} mutableCopy], [@{@VALUE_KEY: @"hello", @COUNT_KEY: @0} mutableCopy],[@{@VALUE_KEY: @"world", @COUNT_KEY: @0} mutableCopy]] mutableCopy];
NSString *stringStream = @"acacabcatghhellomvnsdb" ;
for(NSMutableDictionary *nextDict in stringsToSearchFor)
{
NSUInteger currRangeStart = 0 ;
NSUInteger currRangeLength = [nextDict[@VALUE_KEY] length] ;
NSUInteger currentStringNumFound = 0 ;
while(currRangeStart <= [stringStream length]-currRangeLength)
{
NSRange foundRange = [stringStream rangeOfString:nextDict[@VALUE_KEY]
options:0
range:NSMakeRange(currRangeStart, [stringStream length]-currRangeStart)] ;
if(foundRange.location != NSNotFound)
{
currRangeStart = foundRange.location+1 ;
currentStringNumFound++;
}
else
{
break ;
}
}
if(currentStringNumFound)
{
nextDict[@COUNT_KEY] = @(currentStringNumFound) ;
}
}
NSLog(@"Num occurrences dict is %@",stringsToSearchFor) ;
An object oriented approach: using an object to keep track of every possible instance of the word as a state machine or graph, and an object to store the word with the count of times it has been found.
It would need to iterate through all the words first for initialization of word objects O(n), then iterate through all the stream characters, and for each character analyze each word object and it's instances O(n*w*logn(n)) where n = number of characters in stream, w = number of words, and logn(n) = number of running state machines in that iteration (0 to (n-iteration)). Finally, another O(n) to print the results.
Word.h:
#ifndef WORD_H
#define WORD_H
#include <iostream>
#include <string>
#include <vector>
using namespace std;
enum AnalysisResult { SUCCESS = 0, FAILURE, CONTINUE };
class WordInstance
{
private:
string m_word;
int m_totalstates;
int m_currentstate;
AnalysisResult m_lastResult;
public:
WordInstance(string);
~WordInstance();
AnalysisResult Analyze(char);
};
class Word
{
private:
string m_word;
vector<WordInstance*> m_instances;
int m_count;
public:
Word(string);
~Word();
void Analyze(char);
void Print();
};
#endif // WORD_H
Word.cpp:
#include <iostream>
#include <fstream>
#include "Word.h"
WordInstance::WordInstance(string word)
{
m_word = word;
m_totalstates = word.length();
m_currentstate = 1;
m_lastResult = CONTINUE;
}
AnalysisResult WordInstance::Analyze(char c)
{
if(m_lastResult != CONTINUE) return m_lastResult;
if(m_word[m_currentstate] == c)
{
m_currentstate++;
m_lastResult = m_currentstate == m_totalstates ? SUCCESS : CONTINUE;
return m_lastResult;
}
m_lastResult = FAILURE;
return m_lastResult;
}
Word::Word(string word)
{
m_count = 0;
m_word = word;
m_instances.clear();
}
void Word::Analyze(char c)
{
for(int i = 0; i < m_instances.size(); i++)
{
AnalysisResult result = m_instances[i]->Analyze(c);
switch(result)
{
case SUCCESS:
m_count++;
case FAILURE:
m_instances.erase(m_instances.begin() + i);
i--;
break;
default:
break;
}
}
if(m_word.at(0) == c)
{
m_instances.push_back(new WordInstance(m_word));
}
}
void Word::Print()
{
cout << endl << m_word << ":" << endl;
cout << "\t" << m_count << " times" << endl;
}
int main()
{
vector<string> listOfWords = { "aca", "cat", "hello", "world" };
vector<Word*> words;
char c;
for(auto word = listOfWords.begin(); word != listOfWords.end(); word++)
{
words.push_back(new Word(*word));
}
ifstream inputfile;
inputfile.open("input.txt");
while(inputfile.get(c))
{
for(int i = 0; i < words.size(); i++)
{
words[i]->Analyze(c);
}
}
inputfile.close();
for(int i = 0; i < words.size(); i++)
{
words[i]->Print();
}
}
import java.util.*;
class StreamWordsApp
{
public static void main(String[] args)
{
StreamWords sw= new StreamWords();
sw.countAll();
sw.display();
}
}
class StreamWords
{
String input = "acacabcatghhellomvnsdb";
Hashtable<String,Integer> ht= new Hashtable<String,Integer>();
String[] arr={"aca","cat","hello","world"};
public StreamWords()
{
for(int i=0;i<arr.length;i++)
{
ht.put(arr[i],0);
}
}
public int countWords(int index)
{
int count=0;
String currentWord= arr[index];
int j=0;
for(int i=0;i<input.length();i++)
{
if(input.charAt(i)==currentWord.charAt(0))
{
if(input.charAt(i+currentWord.length()-1)==currentWord.charAt(0+currentWord.length()-1))
{
int k=i;
while(true)
{
if(j==currentWord.length()-1)
{
j=0;
count++;
}
else if(input.charAt(k)==currentWord.charAt(j))
{
k++;
j++;
}
else
break;
}
}
}
}
return count;
}
public void countAll()
{
for(int i=0;i<arr.length;i++)
{
int count= countWords(i);
ht.put(arr[i],ht.get(arr[i])+count);
}
}
public void display()
{
System.out.println(ht);
}
}
public findWords(){
String input = "acacabcatghhellomvnsdb";
HashMap<String,Integer> hm= new HashMap<String,Integer>();
String[] arr={"aca","cat","hello","world"};
for (String word: arr){
int i = input.indexOf(word);
if (i>=0)
hm.put(word, 1);
i = input.indexOf(word, i+1);
while(i>=0){
hm.put(word, hm.get(word)+1);
i=input.indexOf(word, i+1);
}
}
Here is my code ,which use Acho Corasic algorithm with time complexity O(n+m+k), where n is stream length, m - total length of dictionary world, k - number of appearance of dict keys in text.
Trie could be implemented with only HashMap, but I decided for the sake of clarity to implement class Trie with internal class TrieNode
class Trie {
TrieNode root = new TrieNode();
class TrieNode {
private List<Integer> output;
private TrieNode link;
private Map<Character,TrieNode> children;
private boolean end;
public TrieNode() {
output = new ArrayList<>();
children = new HashMap<Character,TrieNode>();
link = root;
}
public Map<Character,TrieNode> getChildren() {
return children;
}
public TrieNode getLink() {
return link;
}
public void setLink(TrieNode lnk) {
link = lnk;
}
public boolean hasChild(char ch) {
return children.get(ch)!=null;
}
public TrieNode getChild(char ch) {
return children.get(ch);
}
public List<Integer> getOutput() {
return output;
}
public void addOutput(List<Integer> ls) {
output.addAll(ls);
}
public void addOutput(int index) {
output.add(index);
}
TrieNode add(char ch) {
TrieNode node = children.get(ch);
if (node == null) {
node = new TrieNode();
children.put(ch, node);
}
return node;
}
void setEnd(boolean isEnd) {
end = isEnd;
}
}
public void add(String key, int index) {
TrieNode current = root;
for (char ch : key.toCharArray()) {
current = current.add(ch);
}
current.setEnd(true);
current.addOutput(index);
}
public TrieNode getRoot() {
return root;
}
}
//------------------------------------------------------------------------------------------------------------
Map<String,Integer> getWordCount(String input, String[] dict) {
Trie trie = new Trie();
Map<String,Integer> res = new HashMap<>();
for (int index =0; index < dict.length; index++) {
String key = dict[index];
trie.add(key, index);
}
Queue<TrieNode> q = new java.util.LinkedList<>();
trie.getRoot().setLink(trie.getRoot());
q.add(trie.getRoot());
TrieNode root = trie.getRoot();
while (!q.isEmpty()) {
TrieNode parent = q.remove();
for(Entry<Character,TrieNode> childEntry : parent.getChildren().entrySet()) {
TrieNode child = childEntry.getValue();
char ch = childEntry.getKey();
if (parent != root) {
TrieNode link = parent.getLink();
while (!link.hasChild(ch)) {
link = link.getLink();
if (link == root)
break;
}
if (link.hasChild(ch)) {
TrieNode childLink = link.getChild(ch);
child.setLink(childLink);
child.addOutput(childLink.getOutput());
}
}
q.add(child);
}
}
TrieNode current = root;
for (char ch : input.toCharArray()) {
while (!current.hasChild(ch)) {
current = current.getLink();
if (current == root)
break;
}
if (current.hasChild(ch)) {
current = current.getChild(ch);
countWords(current.getOutput(), res, dict);
}
}
return res;
}
public static Dictionary<string, int> findWords(string stream, List<string> words)
{
Dictionary<string, int> toBeReturned = new Dictionary<string, int>();
for (int i = 0; i < words.Count; i++)
{
int foundChar = 0;
int startindex = 0;
toBeReturned.Add(words[i], 0);
for (int j = 0; j < stream.Length; j++)
{
if (j + words[i].Length <= stream.Length)
{
if (stream.Substring(j, words[i].Length) == words[i])
{
toBeReturned[words[i]]++;
}
}
}
}
return toBeReturned;
}
public static Dictionary<string, int> findWords(string stream, List<string> words)
{
Dictionary<string, int> toBeReturned = new Dictionary<string, int>();
for (int i = 0; i < words.Count; i++)
{
int foundChar = 0;
int startindex = 0;
toBeReturned.Add(words[i], 0);
for (int j = 0; j < stream.Length; j++)
{
if (j + words[i].Length <= stream.Length)
{
if (stream.Substring(j, words[i].Length) == words[i])
{
toBeReturned[words[i]]++;
}
}
}
}
return toBeReturned;
}
public static Dictionary<string, int> findWords(string stream, List<string> words)
{
Dictionary<string, int> toBeReturned = new Dictionary<string, int>();
for (int i = 0; i < words.Count; i++)
{
int foundChar = 0;
int startindex = 0;
toBeReturned.Add(words[i], 0);
for (int j = 0; j < stream.Length; j++)
{
if (j + words[i].Length <= stream.Length)
{
if (stream.Substring(j, words[i].Length) == words[i])
{
toBeReturned[words[i]]++;
}
}
}
}
return toBeReturned;
}
Objective-C solution
- (NSDictionary *)countOfEachWord:(NSArray *)input inStream:(NSString *)stream
{
NSMutableDictionary *dict = [[NSMutableDictionary alloc] init];
NSString *tempString = [stream copy];
for (NSString *temp in input) {
NSInteger count = 0;
tempString = [stream substringFromIndex:count];
NSInteger startIndex = 0;
while ([tempString containsString:temp]) {
NSRange range = [tempString rangeOfString:temp];
if (range.location > 0)
{
startIndex += range.location + 1;
} else {
startIndex++;
}
count++;
tempString = [stream substringFromIndex:startIndex];
}
[dict setObject:[NSNumber numberWithLong:count] forKey:temp];
}
return [dict copy];
}
Objective-C solution
- (NSDictionary *)countOfEachWord:(NSArray *)input inStream:(NSString *)stream
{
NSMutableDictionary *dict = [[NSMutableDictionary alloc] init];
NSString *tempString = [stream copy];
for (NSString *temp in input) {
NSInteger count = 0;
tempString = [stream substringFromIndex:count];
NSInteger startIndex = 0;
while ([tempString containsString:temp]) {
NSRange range = [tempString rangeOfString:temp];
if (range.location > 0)
{
startIndex += range.location + 1;
} else {
startIndex++;
}
count++;
tempString = [stream substringFromIndex:startIndex];
}
[dict setObject:[NSNumber numberWithLong:count] forKey:temp];
}
return [dict copy];
}
x = "acacabcatghhellomvnsdb"
y = ["aca","cat","hello","world"]
def find_segment(x, y):
n = len(x)
z = {}
for j in y:
z[j] = 0
for i in xrange(0, n, 1):
count = 0
for k in xrange(0, n, 1):
for j in y:
if x[i:k] == j:
count += 1
if z.get(x[i:k]):
count += 1
z[x[i:k]] = count
return z
print find_segment(x, y)
void ProcessWordStream() {
std::vector<std::string> wordHolder = {"aca","cat","hello","world"};
std::string inputStream = "acacabcatghhellomvnsdb";
std::map<std::string, int> wordCounter;
int len = inputStream.length();
for(auto word : wordHolder) {
int count = 0;
std::string tempWord = inputStream;
wordCounter[word] = count;
while(tempWord.length() != 0) {
std::size_t pos = tempWord.find(word);
if (pos != std::string::npos) {
wordCounter[word] = ++count;
tempWord = tempWord.substr(pos+word.length()-2);
}
tempWord = tempWord.substr(1);
}
}
for(auto w : wordCounter) {
std::cout << " " << w.first << " : "<<w.second <<"\n";
}
}
How about having prefix match array for each of the string that need to be matched something similar to KMP.
When a charater is coming from the stream (say getNextChar()) then try to use prefix matching and update the match counte for each one of the string
function for prefix match
int prefix[100][100];
prefixMatch(char str[i], int correspondingPrefixArray[i]);
void prefixMatch(char *P, int *pi) {
int len = strlen(P);
int k = 0;
pi[0] = 0;
for (int i = 1; i < len; ++i) {
//pattern failure fix - aaababab
while(k > 0 && P[k] != P[i])
k = pi[k-1];
if(P[k] == P[i])
++k;
pi[i] = k;
}
}
And then using the prefix match array of each one for compare with next coming character from string
class WordCount # Using trie hash
attr_accessor :stream, :words_list, :word_trie, :word_count_hash
def initialize(stream, words_list)
self.stream = stream
self.words_list = words_list
initialize_word_count_hash
build_trie
end
def word_count
(0...stream.length).each do |index|
next if word_trie[stream[index]].nil?
check_word_in_trie(index)
end
word_count_hash
end
def check_word_in_trie(index)
current_node = word_trie
word = ""
while current_node.has_key?(stream[index]) do
word << stream[index]
current_node = current_node[stream[index]]
index += 1
end
if word_count_hash.has_key?(word)
word_count_hash[word] += 1
end
end
private
def initialize_word_count_hash
self.word_count_hash = {}
words_list.each do |word|
word_count_hash[word] = 0
end
end
def build_trie
self.word_trie = {}
current_node = word_trie
words_list.each do |word|
current_node = word_trie
word.each_char do |char|
current_node[char] ||= {}
current_node = current_node[char]
end
end
puts word_trie
end
end
wc = WordCount.new("acacabcatghhellomvnsdb", ["aca","cat","hello","world"])
wc.word_count
public static void main (String[] args) throws java.lang.Exception {
String arr [] = {"aca", "hello", "world", "cat", "sdb", "acacabcatghhellomvnsdb"};
String input = "acacabcatghhellomvnsdb";
HashMap<String, Integer> map = new HashMap<>();
// put all words into map - O(l)
for (int i = 0 ; i < arr.length; i ++) {
map.put(arr[i], 0);
int len = arr[i].length();
int j = input.indexOf(arr[i].charAt(0));
while (j < input.length()) {
try {
String str = input.substring(j, len+j);
if (str.equals(arr[i])) {
map.put(str, map.get(str) + 1);
}
} catch(StringIndexOutOfBoundsException e) {
}
j++;
}
}
for (int i = 0; i < arr.length; i ++) {
System.out.println(arr[i] + " : " + map.get(arr[i]));
}
}
this is my solution, i used two hashmaps to one for counting and the other for holding the matches, Time complexity is O(n*k) where n is the length of the stream and k is the number of the lookup words.
public void streamSearch(String in, ArrayList<String> dic){
StringReader reader = new StringReader(in);
try {
HashMap<String, Integer> counterDictionary = new HashMap<>();
HashMap<String, String> matchingDictionary = new HashMap<>();
dic.forEach((s) -> {
matchingDictionary.put(s,"");
counterDictionary.put(s,0);
});
int characterRep = reader.read();
while(characterRep >= 0){
//System.out.println((char)characterRep);
for(String key : matchingDictionary.keySet()){
if(key.startsWith(matchingDictionary.get(key) + String.valueOf((char)characterRep))){
matchingDictionary.put(key, matchingDictionary.get(key) + String.valueOf((char)characterRep));
if(matchingDictionary.get(key).equals(key)){
counterDictionary.put(key, counterDictionary.get(key) + 1);
matchingDictionary.put(key, "");
}
}
}
characterRep = reader.read();
}
System.out.println(counterDictionary.toString());
} catch (IOException ex) {
Logger.getLogger(HackerRankTryouts.class.getName()).log(Level.SEVERE, null, ex);
}
}
int main()
{
cout << "find count of each and every word " << endl;
string s;
cin >> s;
cout << "The input string is - " << s << endl;
string words[] = {"aca","cat","hello","world"};
vector<string> ws(words,words + sizeof(words)/sizeof(words[0]));
vector<int> count(ws.size());
for(int i=0;i<ws.size();++i)
{
int j=0;
int cc = 0;
while(j<s.size())
{
if(ws[i][0] == s[j])
{
string s2 = ws[i];
string s1 = s.substr(j,s2.size());
if(s1 == s2)
{
cc++;
j++;
}
else
j++;
}
else
j++;
}
count[i] = cc;
}
for(int i=0;i<ws.size();++i)
cout << ws[i] << ":" << count[i] << endl;
return 0;
}
int main()
{
cout << "find count of each and every word " << endl;
string s;
cin >> s;
cout << "The input string is - " << s << endl;
string words[] = {"aca","cat","hello","world"};
vector<string> ws(words,words + sizeof(words)/sizeof(words[0]));
vector<int> count(ws.size());
for(int i=0;i<ws.size();++i)
{
int j=0;
int cc = 0;
while(j<s.size())
{
if(ws[i][0] == s[j])
{
string s2 = ws[i];
string s1 = s.substr(j,s2.size());
if(s1 == s2)
{
cc++;
j++;
}
else
j++;
}
else
j++;
}
count[i] = cc;
}
for(int i=0;i<ws.size();++i)
cout << ws[i] << ":" << count[i] << endl;
return 0;
}
int main()
{
cout << "find count of each and every word " << endl;
string s;
cin >> s;
cout << "The input string is - " << s << endl;
string words[] = {"aca","cat","hello","world"};
vector<string> ws(words,words + sizeof(words)/sizeof(words[0]));
vector<int> count(ws.size());
for(int i=0;i<ws.size();++i)
{
int j=0;
int cc = 0;
while(j<s.size())
{
if(ws[i][0] == s[j])
{
string s2 = ws[i];
string s1 = s.substr(j,s2.size());
if(s1 == s2)
{
cc++;
j++;
}
else
j++;
}
else
j++;
}
count[i] = cc;
}
for(int i=0;i<ws.size();++i)
cout << ws[i] << ":" << count[i] << endl;
return 0;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String line = scan.nextLine();
ArrayList<String> arr = new ArrayList<>();
int i = 0;
while (i < 4) {
arr.add(scan.next());
i++;
}
scan.close();
for (String string : arr) {
findWord(line, string);
}
}
private static void findWord(String line, String word) {
int l = word.length();
int count = 0;
for (int i = 0; i < line.length(); i ++) {
for (int j = 0; j < word.length() && i+j < line.length(); j ++) {
char c1 = word.charAt(j);
char c2 = line.charAt(i+j);
if (c1 == c2) {
l -- ;
} else {
break;
}
}
if (l == 0) count ++;
l = word.length();
}
System.out.println(word + " : " +count);
}
public static void main(String[] args) {
String stream = "acacabcatghhellomvnsdb";
String arr [] = {"aca", "cat", "hello", "world", "sdb", "db", "b"};
HashMap<String, Integer> map = new HashMap<>();
if (stream == null) return;
for (int i = 0; i < arr.length; i++ ) {
String word = arr[i];
if (word == null) continue;
map.put(word, 0);
if (word.length() > stream.length()) continue;
if (word.length() == stream.length() && word.equals(stream)) {
map.put(word, 1);
continue;
}
for (int j = 0; j <= stream.length() - word.length(); j++) {
if (stream.charAt(j) == word.charAt(0)) {
if (stream.substring(j, j+word.length()).equals(word)) map.put(word, map.get(word) + 1);
}
}
System.out.println(word + " :" + map.get(word));
}
}
private static void robinKarp() {
long time = System.currentTimeMillis();
String stream = "acacabcatghhellomvnsdb";
String arr [] = {"aca", "cat", "hello", "world", "sdb", "db", "b"};
HashMap<String, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
String word = arr[i];
int l = word.length();
long currentHash = hash(word, l);
map.put(word, 0);
long hash = 0L;
for (int j = 0; j <= stream.length() - l ; j ++) {
hash = hash(stream, j , hash, l);
if (hash == currentHash) {
map.put(word, map.get(word) + 1);
}
}
System.out.println("robinKarp : "+ word + " :" + map.get(word));
}
System.out.println("robinKarp Time : "+(System.currentTimeMillis() - time));
}
private static long hash(String str, int length) {
long values = 0L;
for (int i = 0; i < length ; i ++) {
values = values + str.charAt(i) * (long)Math.pow(101, (length - 1 - i));
}
return values;
}
private static long hash(String str, int position, long oldHash, int lenght) {
if (position == 0 || oldHash == 0) {
return hash(str, lenght);
} else {
return (oldHash - str.charAt(position - 1) * (long)Math.pow(101, lenght - 1)) * 101 + str.charAt(position + lenght - 1);
}
}
import java.util.Map;
import java.util.HashMap;
public class Streams {
static Map<String,Integer> wordsToSearch = new HashMap<String,Integer>();
private static void fillWordsToSearch( String[] words ){
for (int i = 0; i < words.length; i++) {
wordsToSearch.put( words[i], 0);
}
}
public static void findWords( String stream ) {
for( String word : wordsToSearch.keySet() ){
// Our limit would be the length of the stream minus the length of the needle
for( int i = 0; i<=(stream.length()-word.length()); i++ ){
String needle = stream.substring(i, (i+word.length()) );
// DEBUG only
//System.out.println("Searching for word->" + word + ",needle->" + needle);
if( needle.compareTo(word)==0 ){
int counter = 0;
// DEBUG only
// System.out.println("Found->"+ needle );
counter = wordsToSearch.get(word)+1;
wordsToSearch.put(word, counter);
}
}
}
for( String word : wordsToSearch.keySet() ){
System.out.println("Word->" + word + ", appeared->" + wordsToSearch.get(word) );
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String stream = "acacabcatghhellomvnsdb";
String[] words = { "aca", "cat", "hello", "world" };
//String[] words = { "aca", "cat" };
fillWordsToSearch(words);
findWords(stream);
}
}
public class Sol {
public static void main (String args[]) {
System.out.println(Arrays.toString(new Sol().find("williamwilliam", new String[] {"l", "iam"})));
}
public int[] find(String string, String[] words) {
int[] results = new int[words.length];
int i = 0;
for (String one: words) {
results[i] = find(string, 0, one, 0, false);
i++;
}
return results;
}
private int find(String string, int index, String word, int index2, boolean continu) {
if (continu) {
if (word.charAt(index2) == string.charAt(index)) {
if (index2 == word.length()-1) {
return 1;
}else{
return find(string, index+1, word, index2+1, true);
}
}else{
return 0;
}
}else{
char c = word.charAt(0);
int count = 0;
for (int i = index ;i< string.length();i++) {
if (string.charAt(i) == c) {
if (word.length() == 1)
count++;
else{
count+=find(string, i+1, word, 1, true);
}
}
}
return count;
}
}
}
import java.util.*;
public class Solution {
public static void main (String args[]) {
Solution solution = new Solution();
String string = "acacabcatghhellomvnsdb";
System.out.println(solution.find(string, "aca"));
System.out.println(solution.find(string, "cat"));
System.out.println(solution.find(string, "hello"));
System.out.println(solution.find(string, "world"));
System.out.println(solution.find(string, "a"));
}
public int find(String string, String word) {
if (string.length() == 0)
return 0;
if (word.length() == 0)
return 0;
if (word.length() > string.length())
return 0;
word = word.toLowerCase();
string = string.toLowerCase();
if (string.charAt(0) == word.charAt(0)) {
String potentialEqual = string.substring(0, word.length());
if (potentialEqual.equals(word)) {
return 1+find(string.substring(1), word);
}else{
return find(string.substring(1), word);
}
}else{
return find(string.substring(1), word);
}
}
}
public void findSubStringsCount()
{
String input = "acacatcghhellomvnsdb";
String[] words = {"aca", "cat","hello","world"};
Map<String, Integer> outputMap = new HashMap<String, Integer>();
for(int i=0;i<words.length;i++)
{
outputMap.put(words[i], 0);
}
System.out.println(outputMap);
for(String i : outputMap.keySet())
{
for(int input_j=0;input_j<input.length()-4;input_j++)
{
if(i.equals(input.substring(input_j, input_j+i.length())))
{
outputMap.put(i, outputMap.get(i)+1);
}
}
}
for(String k : outputMap.keySet())
{
System.out.println(k +":"+outputMap.get(k));
}
}
function analyzeStream(stream, words) {
var stream_array = stream.split('');
var dicto = {};
for(var x = 0; x < words.length; x++) {
dicto[words[x]] = 0;
}
for(var word in words) {
var token = words[word].split('');
var token_index = stream_array.indexOf(token[0]);
if(token_index > -1) {
for(var j = 1; j < token.length; j++) {
if(token[j] == stream_array[token_index + j]) {
dicto[words[word]] += 1;
}
}
}
}
return dicto;
}
package com.command.grep;
import java.util.*;
class StreamWordsApp
{
public static void main(String[] args)
{
StreamWords sw= new StreamWords();
sw.countAll();
sw.display();
}
}
class StreamWords
{
String input = "acacabcatghhellomvnsdb";
Hashtable<String,Integer> ht= new Hashtable<String,Integer>();
String[] arr={"aca","cat","hello","world"};
public StreamWords()
{
for(int i=0;i<arr.length;i++)
{
ht.put(arr[i],0);
}
}
public int countWords(int index)
{
int count=0;
String currentWord= arr[index];
String tempInput = input;
while(tempInput.contains(currentWord)){
int temp = tempInput.indexOf(currentWord);
if(temp >= 0){
tempInput = tempInput.substring(temp+1);
count++;
}
}
return count;
}
public void countAll()
{
for(int i=0;i<arr.length;i++)
{
int count= countWords(i);
ht.put(arr[i],ht.get(arr[i])+count);
}
}
public void display()
{
System.out.println(ht);
}
}
stream = 'acacacbcatghhellomvnsdbcatcat'
words = {"aca": 0,"cat": 0,"hello": 0,"world": 0, 'ac':0, 'hell': 0}
dict = {}
stream = list(stream)
st_dict = {}
for i in words.keys():
st_dict[len(i)] = []
def insert_in_stack(ch):
for i in st_dict:
if len(st_dict[i]) == i:
st_dict[i].pop(0)
st_dict[i].append(ch)
def check_in_words():
for i in st_dict:
word = "".join(st_dict[i])
if word in words:
words[word] += 1
break
for i in stream:
insert_in_stack(i)
check_in_words()
print(words)
package com.interviewbit;
import java.util.LinkedList;
import java.util.List;
public class SuffixTrieToSearchInStreams {
public static void main(String[] args) {
SuffixTrieToSearchInStreams suff = new SuffixTrieToSearchInStreams("bananaandotherthingsotherbro");
suff.search("other");
}
SuffixSearchTrie root = new SuffixSearchTrie();
public SuffixTrieToSearchInStreams(String word) {
for(int i=0;i<word.length();i++) {
root.insertSuffix(word.substring(i), i);
}
}
public void search(String word) {
List<Integer> ind = root.search(word);
if(null==ind) {
System.out.println("Pattern not found");
}
else {
for(int i : ind)
System.out.println("Found at "+i);
}
}
}
class SuffixSearchTrie {
SuffixSearchTrie[] children = new SuffixSearchTrie[256];
List<Integer> indexes;
public SuffixSearchTrie() {
indexes = new LinkedList<>();
}
public void insertSuffix(String S , int index) {
indexes.add(index);
if(S.length()>0) {
char first = S.charAt(0);
if(children[first]==null) {
children[first] = new SuffixSearchTrie();
}
children[first].insertSuffix(S.substring(1), index+1);
}
}
public List<Integer> search(String word) {
if(word.length()==0)
return indexes;
if(children[word.charAt(0)]!=null) {
return children[word.charAt(0)].search(word.substring(1));
}
else
return null;
}
}
package com.interviewbit;
import java.util.LinkedList;
import java.util.List;
public class SuffixTrieToSearchInStreams {
public static void main(String[] args) {
SuffixTrieToSearchInStreams suff = new SuffixTrieToSearchInStreams("bananaandotherthingsotherbro");
suff.search("other");
}
SuffixSearchTrie root = new SuffixSearchTrie();
public SuffixTrieToSearchInStreams(String word) {
for(int i=0;i<word.length();i++) {
root.insertSuffix(word.substring(i), i);
}
}
public void search(String word) {
List<Integer> ind = root.search(word);
if(null==ind) {
System.out.println("Pattern not found");
}
else {
for(int i : ind)
System.out.println("Found at "+i);
}
}
}
class SuffixSearchTrie {
SuffixSearchTrie[] children = new SuffixSearchTrie[256];
List<Integer> indexes;
public SuffixSearchTrie() {
indexes = new LinkedList<>();
}
public void insertSuffix(String S , int index) {
indexes.add(index);
if(S.length()>0) {
char first = S.charAt(0);
if(children[first]==null) {
children[first] = new SuffixSearchTrie();
}
children[first].insertSuffix(S.substring(1), index+1);
}
}
public List<Integer> search(String word) {
if(word.length()==0)
return indexes;
if(children[word.charAt(0)]!=null) {
return children[word.charAt(0)].search(word.substring(1));
}
else
return null;
}
}
package com.interviewbit;
import java.util.LinkedList;
import java.util.List;
public class SuffixTrieToSearchInStreams {
public static void main(String[] args) {
SuffixTrieToSearchInStreams suff = new SuffixTrieToSearchInStreams("bananaandotherthingsotherbro");
suff.search("other");
}
SuffixSearchTrie root = new SuffixSearchTrie();
public SuffixTrieToSearchInStreams(String word) {
for(int i=0;i<word.length();i++) {
root.insertSuffix(word.substring(i), i);
}
}
public void search(String word) {
List<Integer> ind = root.search(word);
if(null==ind) {
System.out.println("Pattern not found");
}
else {
for(int i : ind)
System.out.println("Found at "+i);
}
}
}
class SuffixSearchTrie {
SuffixSearchTrie[] children = new SuffixSearchTrie[256];
List<Integer> indexes;
public SuffixSearchTrie() {
indexes = new LinkedList<>();
}
public void insertSuffix(String S , int index) {
indexes.add(index);
if(S.length()>0) {
char first = S.charAt(0);
if(children[first]==null) {
children[first] = new SuffixSearchTrie();
}
children[first].insertSuffix(S.substring(1), index+1);
}
}
public List<Integer> search(String word) {
if(word.length()==0)
return indexes;
if(children[word.charAt(0)]!=null) {
return children[word.charAt(0)].search(word.substring(1));
}
else
return null;
}
}
class ReadStream:
def getWordsCount(self, stream, words):
map_char_positions = {}
for index,char in enumerate(stream):
if char in map_char_positions:
map_char_positions[char].append(index)
else:
map_char_positions[char] = []
map_char_positions[char].append(index)
map_word_count = {}
stream_length = len(stream)-1
for word in words:
first_char = word[0]
if first_char in map_char_positions:
positions = map_char_positions[first_char]
length_word = len(word)
count=0
for position in positions:
if stream[position:position+length_word] == word and position+length_word-1<=stream_length:
count+=1
map_word_count[word]=count
else:
map_word_count[word] = 0
return map_word_count
stream = ReadStream()
print(stream.getWordsCount("acacabcatghhellomvnsdb", ["aca","cat","hello","world"]))
import re
regex = r"aca|cat|hello|world"
test_str = "acacabcatghhellomvnsdbhellohellohellohello"
matches = re.finditer(regex, test_str, re.MULTILINE)
result = {}
for matchNum, match in enumerate(matches, start=1):
f = match.group()
if f in result.keys():
result[f] = result[f] + 1
else:
result[f] = 1
print(result)
First thought:
- David April 16, 2016dictionary made by Trie, in example, only 4 words. For each position in the input stream, along with the next k characters (k is the length of the longest word in the dictionary), we search in the dictionary and see which words appears, and increase its counter.
The complexity is than O(kn), k is the length of the longest word in the dictionary, and n is the length of the input stream.
Trie is hard to implement during an Interview though.