Solving a Job Application Code Challenge

As I discussed in an earlier post, I recently graduated from the Flatiron School's online immersive full stack bootcamp. For the past few weeks I have been involved in trying to find work that is nested within the triple formula of work I love, work I am good at and work where I could make a meaningful impact. Thankfully, I have discovered that this industry is abundant in opportunities to contribute to exciting endeavors that seek to impact people's lives for the better, whether that is about efficiency, communication, financial planning and many more areas.

One of the integral parts of the interview process is demonstrating your technical skillset to prospective employers. This part of the interview process can be terrifying for recent bootcamp grads, especially liberal arts programmers (a term I coined for people who come to coding from a non-math or non-science background). For this week's installment of coding concepts for liberal arts programmers we are going to break down a code challenge presented in a real job application.

This is the challenge:

Sort the characters in the following string:

abcdefghijklmnopqrstuvwxyz_

by the number of times the character appears in the following text (descending):

...

Now take the sorted string, and drop all the characters after (and including) the _. The remaining word is the answer.

I did not include the very long string of text in the quote above for the sake of brevity. It was a very long string of text.

The challenge does not specify a language to solve this challenge with, so we are going to do it with Javascript. Why Javascript? It is an incredibly popular language used for all sorts of roles and showing some proficiency with it is an asset in an application.

The first thing we are going to do is create a new function that will .reduce() our very long string of text. (Wait, we were given a string, not an array, how we will use .reduce() on that? We'll get there.) What does .reduce() do? According to the MDN Web Docs, .reduce() does the following:

The reduce() method applies a function against an accumulator and each element in the array (from left to right) to reduce it to a single value.

We want to use .reduce() simply because it will calculate for us the total for the number of times each of the characters appear in the long string of text. So let's do it:

function findTheWord(array) {
  let newArray = array.reduce((total, char) => {
    if (total[char] === undefined) {
      total[char] = 0;
     }
    total[char] += 1
    return total
  }, {}); 

What did we do here?

First, we created a new variable newArray to hold the result of our .reduce() action. Then we first check to see if the value is undefined and if so we assign it a value of 0. Otherwise, for each time we encounter that character we increment by 1. Finally, we return the total as an object containing key-value pairs.

Now that we have an object list of each letter with how many times it appears, what do we do next? Well, the challenge says that it needs to be in descending order, thus let's do that:

...

let descendingOrder = Object.keys(newArray).sort((a, b) => newArray[b] - newArray[a])

Here we create a new variable called descendingOrder, which will organize the contents of our object keys (the characters) according to descending order by providing an argument to the .sort() function of sorting by newArray[b] - newArray[a].

The last step is to return what we arrived at with only the characters before and up to, but not including the "_" character. We will do that with a .slice(), specifying where we want to start from and where we want to end:

...

return descendingOrder.slice(0, descendingOrder.indexOf("_")).join('');

In this action we only return the value of descendingOrder from the first index point until we reach the "_" character. The .join() method joins all elements of an array into a string, which we need to do here because, if you remember, we somehow turned that initial long string into an array in order to do what we did with it.

Our function in its entirety now looks like this:

function findTheWord(array) {
  let newArray = array.reduce((total, char) => {
    if (total[char] === undefined) {
      total[char] = 0;
     }
    total[char] += 1
    return total
  }, {}); 
  let descendingOrder = Object.keys(newArray).sort((a, b) => newArray[b] - newArray[a])
  return descendingOrder.slice(0, descendingOrder.indexOf("_")).join('');
}

In order to convert our long string of characters into an array we simply just need to turn it into an array first before running our new function, so something like this:

let array = Array.from(longString);
findTheWord(array);
// returns the word hidden in that long string of initial characters

That concludes our walkthrough of a way to solve that application challenge. The great part about coding is there are so many ways to accomplish anything. Please share how you would address the challenge in the comments!

Comments

[Ryan Palo]

Do you have the big long string of text? You've got me hooked and I want to solve it, but it seems like it would be more fun to actually get the secret word at the end :)

[Ben Greenberg]

Hey Ryan,

Not sure why, but my paste of the long string in this comment did not come in correctly as was mentioned below. You can find it on repl.it at repl.it/MivX.

Enjoy! :)

Ben

[Ryan Palo]

Victory! I found an interesting performance quirk, at least for Ruby. Thanks for a great puzzle and write-up!

[Ben Greenberg]

Your solution in Ruby is awesome. I also love the dedication to benchmarking your two different variations and very interesting results on .count and it's optimization. I didn't know that before. Overall, Ruby is just plain awesome.

[Ryan Palo]

Thanks! Yeah, I was super sure the way you did it would be faster. Ruby is one of my favorite things!

[Richard Orelup]

Running against the blob above it seems the answer is a word followed by some misc character (the last 4 almost spelling out an f-bomb). Did I get the right answer or is something off? I did a codepen with your code and it seems to give the same answer.

[Ben Greenberg]

For those interested, I put this up on repl.it. I'm not sure why but my paste in the comment above of the very long string did not paste correctly. The repl.it has the correct long string: repl.it/MivX

[Miguel Ángel García]

My solution. In python.

from collections import Counter

with open('test.input') as fd:  # the string is in the "test.input" file
    c = Counter(fd.read())

string = ''.join(sorted(c.keys(), key=lambda x: -1 * c[x]))
print(string[:string.index('_')])

[Marco Alka]

Probably not the most elegant way... I really need more practice with Rust :D

fn main() {
    let blob = "...";

    let mut result = blob
        .chars()
        .fold(vec![(None, 0); 27], |mut counter, c| {
            if c == '_' {
                if counter[26].0.is_none() { counter[26].0 = Some('_'); }
                counter[26].1 += 1;
            }
            else {
                let pos = (c as u8 - 'a' as u8) as usize;

                if counter[pos].0.is_none() { counter[pos].0 = Some(c); }
                counter[pos].1 += 1;
            }

            counter
        })
    ;

    result.sort_by(|a,b| b.1.cmp(&a.1));
    let result = result
        .iter()
        .fold(String::new(), |mut s, c| { s.push(c.0.unwrap_or(' ')); s })
    ;

    let result: Vec<&str> = result
        .split('_')
        .collect()
    ;

    println!("{}", result[0]);
}

[Matt Weingaertner]

Great Post! Thanks!

My C# approach would be something like this:

static void Main(string[] args) {
    var sortedString = longString
        .OrderBy(x => x.Equals('_') ? 2 : 1 )
        .ThenBy(x => x)
        .ToArray(); 
    Console.WriteLine(sortedString); 
}

[Matt Weingaertner]

The problem with fast shooting, is always the same, mistakes! :/

static void Main(string[] args) {
    var keyString = new string(longString
        .OrderByDescending(x => longString.Count(c => c.Equals(x)))
        .Distinct()               
        .ToArray());             
    Console.WriteLine(keyString.Split('_')[0]); 
}

[Peter Kim Frank]

@benhayehudi this is a great write-up. Really highlights the way you approached and then solved the problem. As a Javascript novice myself, I appreciated the step-by-step explanation of the decisions you made.

How did this coding challenge compare to others you've taken?

[Ben Greenberg]

Thanks Peter!

This coding challenge ranked as a bit more involved for an initial challenge, i.e. as a requirement for inclusion with a resume submission and not something to do after an initial phone screen. I think it's actually a smart way for a place to be more upfront about their needs and skills required before taking up too much time of the people interested and their own time.

[darkdoc]

Hey!
Can someone check my python solution? Any hints where/how can the code be better?

repl.it/Mnem/0

TY

[Ryan Palo]

Hi! A couple of notes that you can take or leave.

You don't necessarily have to loop through and initialize each key for strngs manually. Here's a couple of alternatives.

# Your version
strngs = {}
for char in initchar:
    strngs[char] = 0

# you can create a dict out of a sequence of keys and starting value
# credit: @edh_developer
strngs = dict.fromkeys(initchar, 0)

# you can also use a defaultdict, which creates the key with a default value
# if it doesn't find the key there on access
from collections import defaultdict
strngs = defaultdict(int) # defaults to zero

You can use shorthand notation if you're modifying a value inplace.

# Your version
strngs[char] = strngs[char] + 1

# shortcut
strngs[char] += 1

You can use dict.items to get a list of pairs out of a dict that is much easier to sort. Then you don't have to manually sort and delete items out of your dict.

# Your version
while (strngs != {}):
    maximum = max(strngs, key=strngs.get)
    word = word + maximum
    del strngs[maximum]

# Could be
pairs = strngs.items()
desc = sorted(pairs, key=lambda x: x[1]) # the key= argument lets us
                                        # sort by the second item
desc_letters = ''.join(x[0] for x in desc) # Grab the first value (letter) from each pair

Some things to look up here for more information:

• Sorting with a custom key
• Using lambda functions
• Generator comprehensions like 'x[0] for x in desc

In general, when you're building a string, it's usually more performant, easier, and less error prone to build the whole thing as a list and join it at the end.

# Instead of this:
word = ""
for item in things:
    word = word + complicated_process(item)

# Since strings are immutable, this forces you to throw away
# your old string and create a new one *each time* which is expensive

# More efficient:
word  = []
for item in things:
    word.append(complicated_process(item))

letters = ''.join(word)

# Use list comprehensions (see link below) for even faster,
# cleaner, more pythonic code :)

word = [complicated_process(item) for item in things]
letters = ''.join(word)

# Use a generator expression (like above) for *even better* results!
letters = ''.join(complicated_process(item) for item in things)

Here's a link on list comprehensions

Hopefully this helps. I'm not sure how comfortable you are with Python, so I tried to cover everything. Let me know if you have any questions 😁

[Dimitar Venkov]

Here's a py3 version using the builtin dict and iterators:

from operator import itemgetter
long_string = "..."

counter = dict()
for c in iter(long_string):
counter[c] = counter.get(c, 0) + 1

sorted_chars = [k for (k, v) in sorted(counter.items(), key=itemgetter(1), reverse=True)]
word = "".join(sorted_chars[:sorted_chars.index('_')] )

print(word)