String Array Searching

Question

I had an interview for a Jr. developer position a few days ago, and they asked:

"If you had an array of letters "a" and "b" how would you write a method to count how many instances of those letters are in the array?"

I said that you would have a for loop with an if else statement that would increment 1 of 2 counter variables. After that, though, they asked how I would solve that same problem, if the array could contain any letter of the alphabet. I said that I would go about it the same way, with a long IF statement, or a switch statement. In hindsight, that doesn't seem so efficient; is there an easier way to go about doing this?

cerkiewny · Accepted Answer · 2014-08-13 13:10:15Z

You could declare the array of size 256 (number of possible character codes) zero it and simply increase the one which corresponds to a char code you read.

For example if you are reading the 'a' the corresponding code is ASCII 97 so you increase the array[97] you can optimize the amount of memory decreasing the code by 97 (if you know the input is going to be characters only) you also need to be aware what to do with capital characters ( are you conciser them as different or not) also in this case you need to take care to decrease the character by 65.

So at the end code would look like this:

int counts[122 - 97] = {0}; // codes of a - z
char a = get_next_char();
if ( is_capital(a)){
    counts[a - 65]++;
}
else 
{
    counts[a - 97] ++;
}

this code assumes the 'A' = 'a' if its not the case you need to have different translation in the if's but you can probably figure out the idea now. This saves a lot of comparing as opposed to your approach.

Marc Gravell · Accepted Answer · 2014-08-13 13:10:19Z

2

Depending on whether the objective is CPU efficiency, memory efficiency, or developer efficiency, you could just do:

foreach(var grp in theString.GroupBy(c => c)) {
    Console.WriteLine("{0}: {1}", grp.Key, grp.Count());
}

Not awesome efficiency, but fine for virtually on non-pathological scenarios. In real scenarios, due to unicode, I'd probably use a dictionary as a counter - unicode is to big to pre-allocate an array.

Dictionary<char, int> counts = new Dictionary<char, int>();
foreach(char c in theString) {
    int count;
    if(!counts.TryGetValue(c, out count)) count = 0;
    counts[c] = count + 1;
}
foreach(var pair in counts) {
    Console.WriteLine("{0}: {1}", pair.Key, pair.Value);
}

answered Aug 13, 2014 at 13:10

Marc Gravell

1.1m273 gold badges2.6k silver badges3k bronze badges

Comments

user3661927 · Accepted Answer · 2014-08-13 13:21:45Z

1

You can create Dictionary<string, int>, then iterate through array, check if element exist as key in dictionary and increment value.

Dictionary<string, int> counter = new Dictionary<string, int>();
foreach(var item in items)
{
    if(counter.ContainsKey(item))
    {
        counter[item] = counter[item] + 1;
    }
}

answered Aug 13, 2014 at 13:21

user3661927

112 bronze badges

2 Comments

Marc Gravell Over a year ago

That will result in an empty dictionary, no?

user3661927 Over a year ago

Yes, but this was just idea how to resolve the problem. You can add else statement like this else { counter[item] = 1; } @MarcGravell

Rajamohan Rajendran · Accepted Answer · 2014-08-13 13:07:33Z

0

Here is wonderful example given, it may resolve your query.

http://www.dotnetperls.com/array-find

string[] array1 = { "cat", "dog", "carrot", "bird" };</br>
//
// Find first element starting with substring.
//
string value1 = Array.Find(array1,
    element => element.StartsWith("car", StringComparison.Ordinal));</br>
//
// Find first element of three characters length.
//
string value2 = Array.Find(array1,
    element => element.Length == 3);
//
// Find all elements not greater than four letters long.
//
string[] array2 = Array.FindAll(array1,
    element => element.Length <= 4);

Console.WriteLine(value1);
Console.WriteLine(value2);
Console.WriteLine(string.Join(",", array2));

answered Aug 13, 2014 at 13:07

Rajamohan Rajendran

3691 gold badge3 silver badges13 bronze badges

Collectives™ on Stack Overflow

String Array Searching

4 Answers 4

Comments

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related