# Finding number of times each string in an Array of strings occurs in a large stream of characters (i.e large string)

Interview problem:

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 ).

This solution works functionally. Please let me know if there is a faster more optimized algorithm or if there are some corner scenarios I did not take care of.

#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) ;


Given that you stated this was for an interview, I'm going to focus not on how to make this code as fast as possible, but instead, the types of things I'd be looking for in an interview candidate.

First, and most concerning, there is not function or method definition here. Presumably, you just typed this code straight into the main function. That'd be the first worrying thing for me if I'm in this interview.

Upon hearing the acceptance criteria, I'd immediately expect a function signature to be written out:

NSDictionary<NSString *, NSNumber *> * _Nonnull findStringsInString(
NSArray<NSString *> * _Nonnull,
NSString * _Nonnull
);


You're already getting bonus points from me if you type this out.

1. You've demonstrated that you have some understanding of what is expected. At a minimum, you're completely clear on what sort of inputs and outputs make sense. And the function name will give some indication that you know what's going on.
2. You've demonstrated above knowledge in the form of a function. The next step of the interview could be writing some unit tests around the function. Even if we don't get that far, even if you're not familiar with unit testing, if you can write your code in a testable manner, that's a plus.
3. You've taken into account Swift annotations so this method will show up nicely in Swift. Even if it's not used from Swift, these annotations help self-document the function and lessen the need for comments.

I'd also be okay if you wrote this as an extension method on NSString.

- (NSDictionary<NSString *, NSNumber *> * _Nonnull)occurencesOfStrings:(NSArray<NSString *> * _Nonnull)strings;


Second problem (get ready to notice a theme here), you haven't broken your problem down into logical sub-problems. How can we count the occurrences of an array of potential substrings if we can't yet even count the occurrences in a single potential substring?

The body of your findStringsInString function needs to really look simply like this:

NSDictionary<NSString *, NSNumber *> * _Nonnull findStringsInString(
NSArray<NSString *> * _Nonnull substrings,
NSString * _Nonnull string
) {
NSDictionary * results = [NSMutableDictionary dictionary];
for (NSString * substring in substrings) {
results[substring] = countOccurrencesOfSubstringInString(substring, string);
}
return results;
}


Why should it be this simple? Because the countOccurrencesOfSubstringInString also needs to be a very simple function that is easy to write tests around. Finding the count for multiple strings is just a simple expansion over the problem of finding the count for a single string.

For the problem of finding the count of a substring in a string, I'll just point you toward this Stack Overflow question which has multiple good answers.

As for actually writing the unit tests for either of these functions, I wouldn't necessarily expect it during an interview, but I'd be delighted to hear the candidate ask about it. Whether or not we did it would depend on whether the candidate asked about it, and completed the first part relatively quickly. But the combination of writing easily testable functions and asking me about testing itself would be enough information about the candidate's attitude toward testing (which I find important).

You notice how I still haven't really addressed any performance issues? As an interviewer, I simply have never cared. When candidates ask me if I want to fastest possible solution to a programming challenge, I always respond with something like this:

I want the solution that works with the least amount of your time invested. After we have a working solution, we can talk about optimizations.

We'll usually have specific criteria on the minimum acceptable performance of our code. That criteria is never phrased as "as fast as possible". It comes with a benchmark. It must perform in less than some measurable amount of time. It's either below that and good enough or above that and not good enough. For almost all things you do, there is never the requirement that a solution work as fast as possible. (There is usually the requirement that it not be slow, and slow is a concrete value.)

#define VALUE_KEY 1
#define COUNT_KEY 2


These #defines are weird and unnecessary. As you'll read later, a better data structure makes these completely obsolete, but if we must use them, I much prefer solutions that aren't preprocessor find & replace.

I'd prefer

NSNumber * const kKeyValue = @1;
NSNumber * const kKeyCount = @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];


This is an absolute mess on so many levels.

First of all, a little bit of whitespace breaks cleans this up a lot.

NSMutableArray *stringsToSearchFor = [@[
[@{kKeyValue: @"cat", kKeyCount: @0} mutableCopy],
[@{kKeyValue: @"aca", kKeyCount: @0} mutableCopy],
[@{kKeyValue: @"hello", kKeyCount: @0} mutableCopy],
[@{kKeyValue: @"world", kKeycount: @0} mutableCopy]
] mutableCopy]


But this is still far from ideal. Read the problem statement again.

Given a stream of characters (e.g. acacabcatghhellomvnsdb) and a list of words (e.g. ["aca","cat","hello","world"] )

We're not going to get this mutable array of mutable dictionaries as our input. You just assumed this would be the input. At this point, as an interviewer, I'd be a little irritated. Your code is going to either take the time to build out this overly complicated data structure, or worse, you're going to expect input in this overly complicated data structure. I say the latter is worse because it demonstrates no technical empathy (or indicates you misread the requirements, which is also very bad). Be clear on the requirements, and if you're unsure, ask. It won't make you look bad during an interview--it will make you look good to get clarification on anything that's unclear. The 30 seconds it takes to ask a question can save days of work in the real world.

And the worst part is that as my earlier code snippet demonstrates, there's a very easy solution here for what our data structure looks like. And you should never be creating dictionaries whose keys roughly translate into @"key", @"value".

Any time you have a dictionary with two key value pairs that looks something roughly like this:

@{@"key": someKey, @"value": someValue}


You've messed up. Especially because you probably have an array of these dictionaries. And it's extraordinarily hard to extract values out of an array of dictionaries that look like this (believe me, the current project has to deal with an API that provides some user settings to me in this format).

The dictionary should instead simply look like this:

@{someKey: someValue}


And now you don't need an array of these dictionaries. You can just have a dictionary:

@{
someKey: someValue,
anotherKey: anotherValue
}


On most lines (but not all), you have placed a space before the semicolon. These seems very strange to me. It is generally preferred not to have this space.

else
{
break ;
}


Given that there's nothing else in the while loop, these four lines of code are entirely unnecessary.

if(currentStringNumFound)
{
nextDict[@COUNT_KEY] = @(currentStringNumFound) ;
}


I know this technically works, but I've got a couple issues with it. First of all, this is hard to follow. We're relying on the fact that in C, non-zero equates to true, and then we're immediately inserting that same variable into a dictionary as a count. I'd much prefer it if we just wrote:

if (currentStringNumFound > 0)


This more clearly mirrors the actual logic you're applying here. You only want to insert the value if it was found at least once.

So that can make the readability and intent more clear. But I'm a little concerned here that this is perhaps not the intended behavior. If I passed in a string and it wasn't found in the dictionary, how can I be confident that it was even checked at all?

In fairness, the result would give me nil for whatever key I was looking for, and that'd really translate equivalently to 0. But it doesn't translate equivalently in the case that I wanted to call some prettify NSNumber extension I wrote on it.

So, for example, if I had an NSNumber extension something like this:

- (NSString * _Nonnull)prettifiedCount;


I might expect the result of calling this on an NSNumber representing zero to be @"zero", but if I called it on what I got out of your result for a string that wasn't found, I'd get nil.

And the thing is, it won't be nil in your dictionary because of that very strange data structure you set up in the beginning, but that data structure definitely needs to change, so keep this part in mind when you're changing your data structure.

Finally, logging.

I really don't want my utility functions spitting out logs. Yeah, you probably need that log to demonstrate to the interviewer that it's working, but to be clear, if you rewrite this per the guidelines I've set forth throughout this answer, you'll have all of your logic wrapped up in these functions. There shouldn't be any logging within those functions. If you want to log the results after the fact, sure, go ahead... but not within the functions themselves.

• Great review. The only things to add are: a discussion of algorithmic complexity, and the nature of streams. If the interviewee has a good sense of the complexity of the problem, then (s)he will have a good shot of writing a near optimal solution the first time. When the problem discusses a "stream" of characters, I would expect a solution that accepts the input one character at a time. – Daniel T. Apr 17 '16 at 17:47
• That's very true. Of course, the solution there could just wrap around the two functions I proposed and take all of the character in to a string and then call these functions. This isn't the fastest, most optimal solution, but step one is always to just make it work. Make it work, and then you can write tests to confirm it works, even as you refactor to improve performance. But yes, arguably the function takes NSInputStream as an argument rather than NSString. – nhgrif Apr 17 '16 at 17:51
• Thanks, for the review. Definitely helps in what I need to be looking for other than just functionally working. Could you also point me to some documentation on how to augment this with unit-tested. An example would be better (I will eventually read the Apple doc) since my interview is tomorrow! – Smart Home Apr 17 '16 at 18:37
• @SmartHome one of the links in there points to how to do Swift unit tests. Objective-C ones look almost identical. You still use XCTAssert functions. – nhgrif Apr 17 '16 at 18:50
• Thanks. One more issue I have is that coderpad.io does not like the "type hints", I.e it complains when I use a type like NSMutableArray <NSString *> *XXX. When I copy the same code on to Xcode, no issues. Are you familiar with coderpad.io. if yes, do you know if there is some setting I am missing or if this is expected? – Smart Home Apr 17 '16 at 18:57