## CodeSignal Solves It: houseRobber

This week’s Interview Practice Task of the Week is houseRobber, a technical interview question that’s been asked at LinkedIn. In this challenge, we’re asked to assist a robber in stealing from houses. Not something that we recommend you do in real life, of course! We will be looking at an (inefficient) recursive solution and then seeing how we can speed it up using memoization (not a typo!) or dynamic programming.

In this task, we are given an array loot, where loot[i] represents the total value of goods we can take from house i. Each house is connected to its neighbors, so the robber isn’t willing to rob two neighboring houses. This means if we take the loot from house i, houses i-1 and i+1 are off limits! Our task is to write a function houseRobber(loot) that returns the maximum amount of loot the robber can steal given loot.

For example, if loot = [5,10,12,2] then the maximum amount of loot that the robber can take is 17 (stealing 5 from house 0 and 12 from house 2). If we had the same values in a different order such as loot = [5,10,2,12], then the maximum amount the robber can take jumps up to 24 (stealing 10 from house 1 and 12 from house 2).

These examples are a little misleading, however. They suggest that we look at stealing from the even numbered houses, and compare that to what we would get stealing from the odd numbered houses. While stealing from evens or odds will ensure we visit the maximum number of houses, it doesn’t guarantee maximum value. For example:

loot = [10,5,2,12]
strategy: stealing from even houses nets 10 + 2 = 12
stealing from odd houses nets 5 + 12  = 17
best solution is to rob first and last house: 10 + 12 = 22


In the problem we are guaranteed that each house has a non-negative amount of money.

## Recursive solution

Let’s start by looking at a few cases. First, we’ll look at a few trivial cases:

1. If there are no houses (i.e. loot = []) then the robber is out of luck and gets nothing. We return 0.
2. If there is only one house, then the solution is obvious: take whatever is inside, so we return loot[0].
3. If there are two houses, then the robber should steal from the house that has the most money, so we should return max(loot[0], loot[1]).

These are called our base cases.

Here comes the magic part: what if we have N houses, where N > 2? Let’s start at the first house: we have to decide whether the robber should rob this house or not. Our two choices are:

1. Steal from the first house. Then we cannot steal from the second house. The best we will be able to get is the value from this house (loot[0]) plus whatever we can get from house 3 onward (because the second house is off-limits). So our payoff is loot[0] + houseRobber(loot[2:]).
2. Don’t steal from the first house. Then this problem is identical to ignoring the first house altogether, and evaluating houseRobber(loot[1:]) (ignoring the first house, and solving the same problem from second house).

We should evaluate both choices, and return the larger of the two. Notice that regardless of which step we make, the problem gets smaller on each step. Eventually we’ll end up with 0, 1, or 2 houses in our list, and the base cases will actually evaluate our solution.

Here’s the recursive solution in code:

def houseRobber(loot):
# our base cases
if len(loot) == 0:
return 0
if len(loot) == 1:
return loot[0]
if len(loot) == 2:
return max(loot[0], loot[1])

#option 1: steal from house 0, and then take
#          the most we can from house 2 onward
valueSteal = loot[0] + houseRobber( loot[2:] )
#option 2: don't steal from house 0, take the
#          best we can from house 1 onward
valueLeave = houseRobber(loot[1:])

return max(valueSteal, valueLeave)


Running this code passes the first 24 tests, but then times out on test 25.

The problem is for all cases except the base cases, houseRobber calls itself 2 more times. This tells us that we can expect houseRobber to be O(2^N), where N is the number of houses. To see the calls, and to find a possible remedy, let’s walk through what our code is doing for the input loot = [4, 1, 2, 7, 5, 3, 1]. Each node here represents a call to houseRobber with the input in the box. The boxes have been color-coded, so each different input is represented with a different color.

One of the things that should jump out at you is that we are evaluating the same function many times. For example, houseRobber([5,3,1]) shown in red is called 5 times! Each time it returns the same value 6 (as robbing the first and the last house gets the most loot from houses with values [5, 3, 1]).

## Improving with memoization

To reduce the amount of redundant work we have to do, one technique is to memorize the answer of each calculation as we do it. This is called memoization, as in “to write down the answer on a memo so we can get it later”. (Actually, memoization comes from the Latin “to be remembered”, but that makes it sound like we should be using the term “memorization” instead!) Basically, the first time we encounter a particular input we will store it in a hash table.

We will not call a helper function for two reasons: not to pollute the global namespace with our previously memoized answers, and because we need to convert loot to a tuple (we cannot use lists as keys to a hash table).

# memoized version of house robber
def _houseRobberRecursive( loot, memo_ans ):
# have we worked it out already?
if loot in memo_ans:
return memo_ans[loot]
# No? Is it a base case?
if len(loot) == 1:
memo_ans[loot] = loot[0]
if len(loot) == 2:
memo_ans[loot] = max(loot)

#option 1: steal from house 0, and then take
#          the most we can from house 2 onward
valueSteal = loot[0] + _houseRobberRecursive( loot[2:], memo_ans )
#option 2: don't steal from house 0, take the
#          best we can from house 1 onward
valueLeave = _houseRobberRecursive(loot[1:],memo_ans)

memo_ans[loot] = max(valueSteal, valueLeave)
return memo_ans[loot]

def houseRobber(loot):
# our place to store answers
memo_ans = { (): 0}
new_loot = tuple(loot)
return _houseRobberRecursive(new_loot, memo_ans)


When we run this version, it passes all the tests. We can show the tree of calls to _houseRobberRecursive for this new variation. Note there are many fewer calls, as we are able to reuse anything we have already calculated. (It is important to note the left branch of each note is executed first, because of the order we evaluated valueSteal and valueLeave in _houseRobberRecursive).

## Dynamic programming solution

We already have a solution, but it’s a little messy. We created a helper function to keep our hash table memo_ans outside of the global namespace, because it would be bad if someone else had also written a function that used memo_ans to store their results.

Notice that memoization started with the full list [4, 1,2, 7, 5, 3, 1] and broke it down to smaller and smaller cases. This is called a top-down approach. Our next approach will be a bottom-up approach, where we start from the small cases and work up to the final solution.

We will introduce an array steal[i], where steal[i] is the best we can do if we are only allowed to steal from the last i+1 houses. If loot = [4, 1, 2, 7, 3, 1] then

• steal[0] = 1 (if we can only steal from the last house, then the best we can do is taking the last house’s loot)
• steal[1] = 3 (we can either steal 3 or 1; 3 is clearly better)
• steal[2] = 8 (given [7,3,1] stealing 7 and 1 is clearly more than just stealing 3).
• steal[3] = 8 (best we can do from [2,7,3,1])
• etc.

The answer we actually want is the last element of the steal array.

Remember our magic step for this problem? It was when deciding whether to steal from house i, all we had to do was compare loot[i] + (most you could steal from house i+2 on) and (most your could steal from house i+1 on). But note that steal[i] tells us the best we can do from the last i houses. This suggests we can find steal[i] using the following technique:

# we are trying to decide whether to rob house with loot[-i-1] or not
steal[i] = max( loot[-i-1] + steal[i - 2], steal[i-1] )


This won’t give us steal[0] or steal[1], but these are our base cases. Note how much simpler our code becomes:

# a dynamic programming solution
def houseRobber(loot):
if len(loot) == 0:
return 0
if len(loot) == 1:
return loot[0]

# go from the end back to the beginning
loot.reverse()

# the base cases: take everything in the only house, or
# rob the house with more valuables
steal = [loot[0], max(loot[0],loot[1])]

for currValue in loot[2:]:
# steal[-2] and steal[-1] are second-to-last and last
# elements of steal
take = currValue + steal[-2]
leave = steal[-1]
steal.append(max(take,leave))
return steal[-1]


This is much tidier, but we can reduce this code even more. Notice that steal[i] depends only on the current value of the loot and the last two values of steal. This means we don’t need to keep an array steal. Instead, we just need to keep track of the last two entries.

Warning: At the moment, we are still going to accomplish our goal of finding the maximum value that our robber could take. If you wanted to be able to produce a list of houses for the robber to pilfer to achieve the maximum, the steal array is incredibly useful. There is a “backtracking” algorithm to reconstruct which houses the robber should steal from. The optimized version below reduces the space complexity of our solution from O(N) to O(1), but at the cost of being able to efficiently reconstruct the list of houses that have been hit.

Our new code is:

def houseRobber(loot):
if len(loot) == 0:
return 0
if len(loot) == 1:
return loot[0]

# go from the end back to the beginning
loot.reverse()

# the base cases: take everything in the only house, or
# rob the house with more valuables
oldBest, newBest = loot[0], max(loot[0],loot[1])

for currValue in loot[2:]:
# steal[-2] and steal[-1] are second-to-last and last
# elements of steal
take = currValue + oldBest
# oldBest is the same as leaving most recent house
oldBest = newBest
newBest = max(take,oldBest)
return newBest


So far we have implemented the bottom-up technique literally. We have made our way from the “end of the street” and worked backward. However, all that matters in this problem are which houses are next to each other. There isn’t a reason to reverse the houses. We could consider steal[i] as being the most we could steal from the first i houses (instead of the last i houses). The only reason we did it that way is it’s a little easier to conceptualize “running out of houses” at the end of the list.

def houseRobber(loot):
if len(loot) == 0:
return 0
if len(loot) == 1:
return loot[0]

# the base cases: take everything in the only house, or
# rob the house with more valuables
oldBest, newBest = loot[0], max(loot[0],loot[1])

for currValue in loot[2:]:
# steal[-2] and steal[-1] are second-to-last and last
# elements of steal
take = currValue + oldBest
# oldBest is the same as leaving most recent house
oldBest = newBest
newBest = max(take,oldBest)
return newBest


We can make our problem look a little more like a standard problem with the following observation: if we initialize oldBest and newBest to zero, and go through every house, then the first pass through the loop sets oldBest and newBest to the correct value. This simplifies our base cases and makes the problem more familiar:

# eliminate bases cases and simplify
def houseRobber(loot):
oldBest, newBest = 0,0
# go through every house
for currValue in loot:
take = currValue + oldBest
oldBest = newBest
newBest = max(take, oldBest)
return newBest


## Similar problems

This problem is a recursively defined series in disguise. This is a series where you calculate the next value using the previous values. One of the most famous examples is the Fibonacci numbers:

0, 1, 1, 2, 3, 5, 8, 13, ...


where the first two numbers are 0 and 1. After the first two numbers, we get the next number by summing the previous two numbers in the sequence. For example, the seventh number in the sequence is 8 because 5 + 3 = 8. The mathematical expression for the Fibonacci numbers F[n] is given by

$F[n] = F[n-1] + F[n-2], {\quad}{\quad}{\quad}{\quad} n \geq 2$

and where F[0] = 0 and F[1] = 1. This definition leads to a recursive function call:

# Warning: this function is O(2^n)
def fib(n):
"Returns the nth Fibonacci number"
if n == 0 or n == 1:
return n
return fib(n - 1) + fib(n-2)


Because we see each call to fib(n) (except the base cases n=0 and n=1) call fib two more times, we are not surprised to find an O(2^n) running time. We can memoize this function (and this is good practice!), but we can also write an iterative or dynamic programming solution:

# This is O(n)
def fib(n):
"Returns the nth Fibonacci number in reasonable time"
if n == 0 or n == 1:
return n
old, new = 0,1
for _ in range(n-1):
old, new = new, old + new
return new


Note how similar the program is to houseRobber. Many problems that involve making a choice to explore two different paths, such as rob house i or not, will given rise to these recursive sequences. This is a good pattern to know!

The overall approach:

1. Usually we are iterating through our problem, and have to decide whether or not to include the current element. In this case our decision was whether or not to rob a house, but in other instances it might be whether or not to pack a certain item, or whether we use a road to get to our destination.
2. Start by relating this problem to “smaller” instances of the problem. If it helps, write a recursive solution first (although usually these will have bad run times). Usually these smaller instances are related to the different possible choices you could have made. In this case, the smaller instances were “making the best value from the remaining houses”.
3. Look at how many of the “smaller” instances you have to use to solve the next instance. In this case, we only used the last two instances. This can help you write the solution as an iterative solution.

## Tell us…

Have you ever gotten a question like this in a technical interview? What strategy did you take to solve it? Let us know on the CodeSignal forum!

## CodeSignal Solves It: pressingButtons

Time to call 1-800-CODEFIGHTS (that’s 1-800-2633344487)! Given a number, your job is to find all the possible strings that the number could represent on a telephone’s number pad. This week’s Interview Practice Task of the Week was pressingButtons. This programming problem has been asked in technical interviews at Google, Amazon, Uber, and Facebook. In other words, this is a classic question!

In classic CodeSignal Solves It fashion, I’m going to tell you to go solve the problem yourself first. After all, you have to actually practice solving interview questions in order to become a better coder! Once you’ve solved it, head back here and I’ll talk you through two variations on a solution.

Done? Okay, let’s get dialed in!

## The technical interview question

We are given a picture of a standard number pad to help us:

Given a number as a string, for example “42”, we are supposed to write a function pressingButtons that returns a (sorted) list of all possible strings associated with that number. In the case of “42”, the “4” maps to a “g”, “h”, or “i”, and the “2” maps to an “a”, “b”, or “c”, so:

print pressingButtons("42")
["ga","gb","gc","ha","hb","hc","ia","ib","ic"]


### The politics of programming languages

One of the interesting things about this challenge is that we have written our solutions in Python. In Python, there is a very easy way of approaching this problem using the itertools package. When solving a problem in the real world (i.e. not in a technical interview) it is great when your problem is solved in a standard package! But in an interview setting, an interviewer asking you to sort a list is probably wanting you to implement a sorting algorithm instead of just using the language’s built-in sorting method.

Itertools is a borderline package. On the one hand, it’s built into the language. You need to show that you understand iterators in order to use it. It is also typically not taught in computer science classes, where they want you to make iterators by hand. So the fact that you know about itertools shows your real-word experience. Making your own custom solution when interviewing for a position that needs 3 years of Python experience might leave your interviewer wondering “doesn’t this candidate know about itertools?”

On the other hand, we try to serve a wide audience here at CodeSignal. Knowing that the itertools package is built in to Python doesn’t help when you are applying for that senior Java engineer position! I will show the itertools solution, and then show a solution that will work in a broader range of lower level languages.

Even if you are using Python in a technical interview, my advice would be to ask your interviewer if you are allowed to use the itertools package. Chances are your interviewer will say “no”, but at least you’ve demonstrated to her that you know the standard way of approaching one of these problems.

## A solution using itertools

Here is the Python code that uses itertools:

from itertools import product

def pressingButtons(buttons):
numPad = [""   ,""    ,"abc","def" ,"ghi","jkl",
"mno","pqrs","tuv","wxyz"]
charArr = [numPad[int(digit)] for digit in buttons]

return [''.join(s) for s in product(*charArr) if s]


The array numPad stores the possible letters for each character. There are no letters associated with 0 or 1, so the entries are empty strings. We see numPad[4] = "ghi" and numPad[2] = "abc", for example. Next, we make an array of all the possible numbers we can substitute in charArr. Continuing with the example of 42, we would have charArr=["ghi","abc"].

So far, everything looks the same as it does in the more general solution. We now have to find a way of getting all the possible ways of getting a single letter from each of these strings. This is where the itertools product function does all the heavy lifting.

What product does is take an arbitrary number of iterables (think lists or strings) and returns a generator. Generators are really cool – they allow us to produce values “on demand” so we don’t have to stress the machine too much – but they are a whole other topic on their own. For the moment, we can force product to produce a list by casting it. The product operator is easy to understand from an example:

list(product([1,2,3],"ab")) = [(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b'), (3, 'a'), (3, 'b')]


i.e. list(product( it1, it2, it3, ..., itN ) ) returns a list where each element is a tuple where the first element is from it1, the second elements is from it2, the third is from it3, and so on. Every possible combination is represented once.

Notice that if we have charArr = ["ghi","abc"] that list(product(charArr)) doesn’t give us quite what we want:

list(product(charArr)) = [('ghi',), ('abc',)]


This is because we have passed only one argument, charArr. It is iterable since there are two elements (“ghi” and “abc”), so it takes the first element and then the second. Python’s notation for a tuple with a single element looks strange: ("ghi",) is a tuple with only one element "ghi". The comma shows that this is a tuple and not just standard parenthesis. Notice that if we pass the two strings "ghi" and "abc", we get a different result:

list(product("ghi","abc")) =  [('g', 'a'), ('g', 'b'), ('g', 'c'),
('h', 'a'), ('h', 'b'), ('h', 'c'),
('i', 'a'), ('i', 'b'), ('i', 'c')]


The Python star operator (*) allows us to “unpack” a list, and pass the entries directly to a function. So we can write:

# charArr = ["ghi","abc"] as before
list(product(*charArr)) =  [('g', 'a'), ('g', 'b'), ('g', 'c'),
('h', 'a'), ('h', 'b'), ('h', 'c'),
('i', 'a'), ('i', 'b'), ('i', 'c')]


Now we just have to join each of these tuples such as ('g','a') into a string such as "ga". We can accomplish this with the join functions:

[''.join(s) for s in list(product(*charArr))] = ['ga', 'gb', 'gc',
'ha', 'hb', 'hc',
'ia', 'ib', 'ic']


We can get rid of the list statement now since we are feeding the output of product to a for loop. This is just the thing that generators were built for!

We have covered almost all the code in the return statement in our original function. The only missing piece is an if s at the end! The if s at the end deals with the corner case of what happens when you pass in an empty string for buttons (i.e. “” instead of “42”). The comments section on this question are all addressing what the answer should be – you should have a look and see what you think the question statement instructions say about what should happen with the empty string – but our tests only pass if pressingButtons("") returns an empty list []

## Recursive approaches to this question

Let’s try to do this without resorting to itertools. We want a function allStrings that takes a list of strings charArr, and returns a list of all the possible strings with the first character from charArr[0], the second character from charArrr[1], etc. Our approach will be:

1. If charArr only has one element, then return a list of the letters of charArr[0]. For example, if charArr=["abc"] then return ['a','b','c'].
2. If charArr has more than one element, find the list of all the strings of every element except for the first by using the recursive call allStrings(charArr[1:]). Then append every string in this list with every letter from charArr[0].

In code, we have:

def allStrings(charArr):
# base cases: charArr only has 0 or one element
if len(charArr) == 0:
return []
if len(charArr) == 1:
return list(charArr[0])

# find the list of strings
remaining = allStrings(charArr[1:])
output = []

for start_char in charArr[0]:
# place start_char at the beginning of each string in
# remaining
output.extend([start_char + s for s in remaining])
return output


Putting our solution together, we have:

# uses the earlier function allStrings
def pressingButtons(buttons):
numPad = [""   ,""    ,"abc","def" ,"ghi","jkl",
"mno","pqrs","tuv","wxyz"]
charArr = [numPad[int(digit)] for digit in buttons]

return allStrings(charArr)


## Tell us…

Have you ever been in an interview where you could have used a built-in method to solve a challenge, but were told not to? Or the opposite – the interviewer told you to go ahead and use it? Let us know over on the CodeSignal forum!

## Do you need to prepare for technical interviews?

If you’re already working as a software engineer, you might think that you don’t need to do any preparation for your next technical interview. Maybe you write C++ that’s pure poetry, or perhaps your SQL queries are so efficient that they make grown men weep. So when you’re looking for a new job, it’s easy to fall into the trap of assuming that you’re ready for interviews right away – no prep needed. But are you?

Sidebar: If you’re not working as a software engineer yet, don’t stop reading! A lot of this applies to you too. And we’re going to be posting another article about preparing for coding interviews specifically for you very soon. Stay tuned!

Think back to your last interview experience.

What kind of questions did you get asked? Some of the questions might have been pretty straightforward, aimed at evaluating how well you could do the task at hand. And if that task was something you were already pretty comfortable doing, you probably didn’t have too much trouble getting it done.

But chances are good that you also got some pretty esoteric or challenging questions. Questions that were more about testing whether you remembered how to implement certain algorithms or data structures… potentially ones that you hadn’t touched since you were in school.

Let’s face it: You’re good at your job, but that doesn’t necessarily mean you’re good at interviewing. Interviews are a completely different beast.

Bottom line: If you’re looking for a new job, you might not be as prepared as you think you are.

Tigran Sloyan, the founder of CodeSignal, puts it this way:

“The reality is that the interview questions you’ll face at most companies are miles away from what you do at your day job, so make sure to do some research and practice using real questions that the company uses in its interviews.”

You might think that traditional technical interviews don’t effectively measure how well you would actually perform on the job, and you’re not alone in that. But the fact is that for now, most companies rely on them to weed out people who can’t cut it. They also use them to gauge the aptitude, interest, and intelligence of those who can.

### What should you practice?

A mainstay of the technical interview process is asking questions that help the interviewer determine how well a candidate understands computer science fundamentals like data structures and algorithms, whether they can implement them appropriately, and whether they take time and space complexity into account.

A great way for you to revisit these concepts and get those rusty skills back up to snuff is solving Interview Practice challenges on CodeSignal. All 100+ of these questions are pulled directly from actual interviews at top tech companies. You can filter by company and by question topic, which gives you a personalized experience that lets you focus on the topics you need to practice the most.

The list of topics you need to study will be largely informed by research that you’ve done on the companies you are interviewing at (or would like to interview at). If you know that a company is likely to ask you questions about tree traversal, you can start working on tree traversal interview questions to prepare! It’s really important to be honest with yourself about the current state of your skills and knowledge. For example, you might have been a dynamic programming expert in college. But if you’ve been a front-end developer working strictly in HTML, CSS, and JavaScript for the past few years, you probably need a refresher.

### Finding time

One common issue that we hear from professionals who are starting to look for new programming jobs is that they don’t have time to practice technical interview questions. It’s true that adding yet another commitment on top of your job and your real life can be daunting. Once you’ve determined what it is that you need to study, you’ll need to carve time out to make that happen.

This is going to look different for everyone. Do you actually have an interview in three weeks? Then that’s your timeline. If you’re just at the contemplation stage and don’t have any interviews lined up yet, then your timeline might be more in the month to two months range. In general, though, it’s best to keep your timeline fairly short. Having a longer timeline means that you risk losing focus and drive.

Now that you know your timeline and what you need to study, it’s time to set your routine. A routine benefits most people because it becomes a built-in framework to adhere to, which in turn creates accountability. There are countless different schools of thought about what constitutes an effective routine, but they all have one thing in common: consistency. You have to practice consistently in order to see the benefits from it. For most people, at least an hour a day is ideal. If your timeline is short, try to spend more time daily. You may have to scale back on some other commitments while you’re in interview preparation mode!

#### Stick to it!

Once you’ve got a routine that works for you, stick to it. This is the hard part, because it usually involves scaling back on other, more fun parts of your life. But stick to your guns and protect the time you’ve set aside for practice. Remember, this isn’t a forever commitment! Once you’ve gotten to your goal, you can lay off on the interview preparation and get back to whatever it was that you had to scale back on to find the time, whether it’s watching Friends reruns or running marathons.

### Practice pays off

We know you’re a good engineer. You know you’re a good engineer! But technical interviews require different skills – and like any other skill, you have to work to get better. Actually writing code that solves the actual technical interview questions makes you more comfortable with the process. We can’t emphasize this enough: The absolute best way to ensure that you’re good at interviewing is to practice solving coding interview problems!

Now go get ’em, tiger. You’re going to knock that interviewer’s socks off!

### On the job hunt? Read these articles too:

Resumes. Not fun, right? But in a lot of cases, they’re a necessary part of the job search process. Read Make Your Engineering Resume Stand Out to find out how to write a resume that really highlights your programming skills and experiences and makes you stand out from the crowd of applicants.

Once you’re on a company’s radar, there’s still a few steps before you make it to the in-person technical interview! First, you have to get past the recruiter phone screen. Read Ace Your Phone Screen By Telling Your Story, Pt. 1  to learn how to create a personal elevator pitch that resonates with recruiters. Then check out Ace Your Phone Screen By Telling Your Story, Pt. 2 for tips on how to wow the recruiter during the phone screen itself.

## Tell us…

What’s your take on preparing for interviews? If you do prepare (and we hope you do), what does your process look like? Let us know over on the CodeSignal forum!

## CodeSignal Solves It: chessQueen

Our latest Interview Practice Task of the Week was chessQueen, which has been asked in technical interviews at Adobe. This question might seem fairly easy at first: Given the location of a queen piece on a standard 8 × 8 chess board, which spaces would be safe from being attacked by the queen? But as with any “easy” technical interview question, it’s imperative that you think it through fully, watch out for potential traps, and be able to explain your reasoning as you solve it!

This question is a variation on a classic problem, Eight Queens. It’s very possible that you’ve encountered Eight Queens or a common variation, nQueens, in computer science classes or interviews in the past. Chess-based problems like this one come up a lot in interviews, there’s a good reason for that! If you think about a chess board, what does it look like? A grid. And chess pieces follow specific rules, making chess scenarios a great framework for questions that test your basic problem-solving and implementation skills.

If you haven’t solved chessQueen yet, now’s the time! Once you’ve written your own solution, head back here. I’ll discuss my solution, and why I chose it over other possible solutions to the problem.

## The technical interview problem

chessQueen gives us the location of the queen in standard chess notation (e.g. “d4”). Our solution needs to return a list of all the locations on the board that are safe from the queen. The diagram below shows the locations that the queen could move to on her next move, which means that these cells are not safe from the queen.

In this example, we’d need to have our function chessQueen("d4") return the following list:

chessQueen("d4") =
["a2","a3","a5","a6","a8",
"b1","b3","b5","b7","b8",
"c1","c2","c6","c7","c8",
"e1","e2","e6","e7","e8",
"f1","f3","f5","f7","f8",
"g2","g3","g5","g6","g8",
"h1","h2","h3","h5","h6","h7"]


Keep in mind that the output above has been formatted nicely to help us visualize the solution when looking at the diagram. The native output would put line breaks at locations dictated by the size the window.

## What can the queen attack?

Remember that in chess, a queen can move any number of squares vertically, horizontally, or diagonally.

The rows are already numbered, so let’s number the columns as well. Internally, we can think of column A as ‘0’, column B as ‘1’, etc. We will call the queen’s location (qx,qy). Then the queen can take any location (x,y) that is:

1. Anything in the same row (i.e. qy == y)
2. Anything in the same column (i.e. qx == x)
3. Anything on the up-and-right diagonal from the queen’s location. (i.e. slope 1 lines though the queen’s location: qx - qy == x - y)
4. Anything on the down-and right diagonal from the queen’s location. (i.e. slope -1 lines though the queen’s location: qx + qy == x + y)

Any other location on the board is safe from the queen.

## Our strategy

We see that we have to report and return all the squares that are safe from the queen for our solution. If we think of the chess board as N × N, we see that there are N squares excluded from the row, N excluded from the column, and at most N excluded from each of the diagonals. We are expected to return O(N^2) elements, so we know that we aren’t going to find a solution shorter than O(N^2).

The creative parts of this solution will be how you choose to map between the column letters and the numbers – basically, how you do the arithmetic! My choice below was to use the hard-coded string "abcdefgh", where the position in the string maps to the index. I’ll mention some alternatives below, as well as their advantages and disadvantages.

def chessQueen(q_loc):
cols = list("abcdefgh")
rows = range(1,9)

# get the [numerical] location of the queen
qx,qy = cols.index(q_loc[0]), int(q_loc[1])

# remove the row that the queen is in
#(none of those locations are safe)
rows.remove(qy)

# place to put "safe" squares
safe = []

# note that I want to maintain correspondence
# between location in cols, and the column number.
# If I remove an entry in cols, I eliminate this
# correspondence!

for colnum, colname in enumerate(cols):
if colnum == qx:
continue # don't bother with this column
for row in rows:
# we don't have to check row or column (the queen's row
# was removed, and we skip this loop on the queen's col)
if (qx + qy != colnum + row) and (qx - qy != colnum - row):
safe.append( colname + str(row) )

return safe


### Other approaches to this coding challenge

My approach to translating between the column’s names and the numbers won’t be everyone’s favorite way. My approach to listing the elements isn’t elegant, but it gets the job done! And a lot of times, that’s exactly that an interviewer needs to see.

Here are some alternatives, and why I didn’t choose them:

• Using the built-in string library
We can get rid of the hardcoded string by writing
cols = list(string.lowercase[:8])


You have to be a little careful that people running different locales will still have the same “first 8 characters” that you have! Note that you can use cols = list(string.ascii_lowercase[:8]) instead to be safe, but at that point I’d rather be explicit about the letters I’m using.

• Using “ASCII math”
We can find the column numbers by subtracting the character code a from the letter. In Python, ord('a') will return the code for the letter ‘a’ (97 in ASCII). In C, the function casting the character to an integer does the same thing. So we can actually write code that is a lot smaller:
# using character codes, instead of a list to with indices
def chessQueen(q_loc):
cols, rows = range(8), range(1,9)

qx,qy = ord(q_loc[0]) - ord('a'), int(q_loc[1])

# remove the queen's row and column
cols.remove(qx)
rows.remove(qy)

safe = []

for col in cols:
for row in rows:
# check that we are not on the dangerous diagonals
if (col - row != qx - qy) and (col + row != qx + qy):
safe.append( chr(col + ord('a')) + str(row) )
return safe


Because we aren’t relying on the position in the list, and have a direct translation between the column letters and numbers, we’re able to remove the column directly, instead of having to use the continue keyword. I avoided this because I get nervous doing encoding math (what about the locales?!) but the Python documentation assures me I’d actually be fine!

• Using a dictionary for the conversion
If I wanted to be fully explicit, I could make a dictionary {'a':0,'b':1, ..., 'h':7} to encode the values, and a separate dictionary to decode. This is a very flexible approach, but I would worry about what my interviewer might read into me setting up two hash tables for something that really only needed a little arithmetic! This is probably the easiest version to internationalize, so if you have a technical interview at a company that works in many different character sets, you could use this flexible code as a selling point. (“Oh, you want the names of the columns in Chinese? No problem, I just have to change the keys in this dictionary…”)

## Tell us…

As you’ve seen, this is a challenge that can be solved in a number of different ways! How did you tackle it? How would you describe your reasoning for taking that approach to an interviewer? Let us know over on the CodeSignal forum!

If you were a small business owner and someone offered you a free billboard on the freeway, you’d take it in a heartbeat, right? Free advertising in a high traffic area! That’s a no-brainer – of course you’d want that.

And that, friends, is pretty much exactly what LinkedIn is: a free billboard for YOU.

Recruiters from tech companies are on LinkedIn all the time, plugging in keywords, looking for leads. The search interface makes sourcing on LinkedIn easy for them, so of course they use it. They’re looking for you! They want to give you a job!

So it just makes sense that you, whether you’re an active or passive job seeker, should also be on LinkedIn. Building your profile up into your own personal billboard makes it easy for all those searching recruiters to find you! It’s a hugely valuable tool that makes you visible and accessible to employers who are actively seeking candidates with the skill set that you have.

Fixing your LinkedIn profile can take a little bit of time, depending on how empty or out of date it is, but it’s totally worth it to spend some quality time putting it together. If you’re actively looking for new programming jobs or maybe just open to considering new options, LinkedIn is going to help you out.

Connie Kehn, Lead Talent Engineer at CodeSignal, sees a lot of LinkedIn profiles while she’s working with engineers who are using CodeSignal to find new jobs. And she used to be a recruiter for Tesla, so she knows what people on the other end of the equation are looking for too! She says, “Take advantage of your LinkedIn. It’s a free billboard space for you to talk about your strengths, your history, your skills, and what kind of work you’re looking for. Recruiters use that! When you’re on the hunt, build it up. You can always take it down later.”

So without further ado, here are CodeSignal’ top 10 tips for making your LinkedIn work for you!

1. Fill out the entire profile. If you leave sections of your LinkedIn profile blank, not only are you missing out on opportunities to tell recruiters who you are and showcase what you’ve done, but you also might be hidden in searches. The LinkedIn platform actually prioritizes complete profiles! So if you’re not filling it out, your profile might not be surfacing in recruiters’ searches.
2. Stand out with a good headline. Since this is one of the first things someone looking at your LinkedIn profile will see, make it count! Your headline should be descriptive and highlight your interests or specializations. Think specific, not general. And while you can get a little creative if you want to, don’t go overboard. The recruiter needs to be able to quickly decide whether or not you fit the bill. So a headline like Experienced Scala Wrangler Seeking New Pastures is eye-catching but still descriptive, while one like Programming Mermaid doesn’t really give a recruiter much of a sense of what you do.
3. Sum yourself up. Your summary should be 40 words or more in order to rank in searches, but don’t go overboard in the other direction either! If your summary is too long, pertinent information might get lost as recruiters skim through. Write in the first person about yourself (“I’m a web developer” vs “Janet is a web developer”), and keep your language natural! Use the old writing adage of “show, don’t tell.” Instead of saying that you’re enthusiastic about Python, be specific: “I taught myself Python two years ago and have been using it whenever possible ever since.”
4. Add keywords. Whether recruiters are doing searches or already looking at your profile, they’re looking for certain, specific things. You can think of these as your own personal search keywords, and you should make sure that you’ve got these keywords in your Summary, Skills, Experience, Projects, and Recommendations sections. Obviously you don’t want to misrepresent yourself or try to do some keyword-stuffing that looks unnatural. But you do want to make sure that you’re showing up in the right searches! So if you’re looking for a job as a Rails developer but you don’t list Ruby or Rails anywhere in your profile, you may as well not be looking for a Rails dev job at all.
6. Show off your education! Remember how we said to fill out your entire profile? Yeah, that goes double for the Education section. Maybe you didn’t go to school for computer science or a related field. Or maybe you didn’t go to school at all. Not a problem! Chances are good that you’ve got some relevant coursework, certifications, or seminars under your belt that you could add to your profile. Recruiters like to see this because it’s a little confirmation for them that you’re qualified and competent enough to do the programming jobs they’re working on filling.
7. Hide the competition. You know that sidebar on the right side of your LinkedIn profile that says “People also viewed” and has a list of other people? You’re going to want to hide that. Go to Settings, then Privacy, and change this to “No”. Because those other people that LinkedIn users are also looking at probably look a lot like you in terms of work or educational history and/or skills, meaning they show up in the same searches… meaning they’re the competition.
8. Get endorsements. While you’re busy adding your own personal keywords to your Skills section, ask coworkers, classmates, clients, or acquaintances who are familiar with your work to endorse you for those skills. While this actually won’t rank you any higher in searches, it does give the recruiter who’s looking at your profile some very positive cues: Not only do you say that you know Sass, Emily who you worked with at your last company says you know Sass too!
• Optional: Get recommendations. On a related note, it looks really good when you have recommendations from supervisors, clients, or teachers, especially if they reference specific projects you’ve worked on or things you’re really good at.
9. Order your sections. By now, you’ve probably noticed that you can move the sections of your profile around. Use this to your advantage! If you just got out of school or you’re switching careers and you don’t have much work experience yet, move your Education and Projects sections up to the top. Been in the tech industry for ages? Keep your Experience section at the top.
10. Personalize your URL. Which URL would you rather have a recruiter send to a hiring manager: linkedin.com/in/joe-cool-20a70070 or linkedin.com/in/josephcool? While this isn’t a make-or-break situation, having a good personal URL can give your profile an extra layer of professionalism and help build your personal brand.

Bonus: Don’t leave your LinkedIn profile picture blank! Recruiters respond to photos because it helps them create a more complete picture of a candidate in their minds. You don’t have to go get professional headshots unless you want to, but you should make sure that the photo is clear, well-lit, and work-appropriate (no bar-hopping pictures, please). And while you’re at it, add a banner picture too! It makes your profile look more professional, more complete, and more you. After all, what’s a billboard without an eye-catching image?

Doable, right? And once you’ve got your LinkedIn profile fully set up, it’s just a matter of upkeep: adding new jobs, certifications, and skills as you get them. Whether you’re actively looking for new tech jobs or just interested in seeing what comes your way, your personal LinkedIn billboard is a sure-fire way to make sure that recruiters see you for the talented, savvy programmer that you are.

### On the job hunt? Read these articles too:

Resumes. Not fun, right? But they’re a necessary part of the job search process a lot of the time. Read Make Your Engineering Resume Stand Out to find out how to write a resume that really highlights your programming skills and experiences and makes you stand out from the crowd of applicants.

Once you’re on a company’s radar, there’s still a few steps before you make it to the in-person technical interview! First, you’re going to have to get past the recruiter phone screen. Read Ace Your Phone Screen By Telling Your Story, Pt. 1  to learn how to craft a personal elevator pitch that will resonate with recruiters. Then check out Ace Your Phone Screen By Telling Your Story, Pt. 2 for tips on how to wow the recruiter during the phone screen itself.

## Tell us…

Have you ever found a job opportunity through LinkedIn? Have any great tips for making your LinkedIn profile stand out from other engineers’ profiles? Let us know on the forum!

## CodeSignal Solves It: goodStringsCount

Our Interview Practice challenge this week is goodStringsCount, a combinatorics problem. As the name suggests, combinatorics deals with combinations of objects that belong to finite sets, and it’s one of those topics that come up a lot in technical interviews. This specific coding problem is from Apple, which makes sense since they’re known for asking combinatorics questions in their technical interviews!

If this isn’t your first CodeSignal Solves It rodeo, I bet you know what I’m going to ask next: Have you solved goodStringsCount yet? If not, hop to it! Once you’ve got your solution, come back and we’ll walk through the problem together.

Done? Great! Let’s get into it.

## The technical interview problem

For this programming interview question, our job is to write a function that counts “good strings” of length n. A “good string” is defined as a string that satisfies these three properties:

1. The strings only contain the (English) lowercase letters a – z.
2. Each character in the string is unique.
3. Exactly one letter in the string is lexicographically greater than the one before it.

The first two conditions tell us that any string made up of lowercase letters qualifies. For example, there are no good strings of length 1, because the single letter doesn’t have anything to be greater than! In other words, goodStringsCount(1) should return 0.

## Looking at good strings of length 3

Strings of length 2 are actually a little misleading, because they don’t really allow us to dig into the third condition on good strings. It just tells us that the characters have to appear in ascending order, as the second character has to be greater than the first. So let’s start by looking for good strings of length 3 instead!

The third condition tells us that “bfg” is not a good string because all the letters appear in ascending order. But “bgf” is a good string since:

• looking at the first two characters: ‘b’ < ‘g’ (so there is a letter greater than the one that precedes it)
• looking at the next two characters: ‘g’ > ‘f’ (so there is only one letter greater than the one that precedes it)

From the letters b, f, and g, there are six possible strings, of which 4 are “good strings”.

“bfg”, “bgf”, “fbg”, “fgb”, “gbf”, “gfb”

There is nothing particularly special about the characters b, f, and g. We could use a, h, and k as well (just replace b with a, h with k, and g with k in the list above). In fact, any three distinct letters would do, since the only property we used was their relative order. So we have:

${\text{numGoodStringsOfLength3}} = 4 \times (\text{numWaysOfPicking3LettersFrom26}) = 4 \times {{26}\choose{3}} = 4 \times \frac{26!}{4! 22!}$
where $n \choose {r}$ is n choose r, the function for counting the number of ways of choosing r elements from n. This is a common function in combinatorics problems, so I’ve included a discussion of it as a footnote to this article! We’ll be using this function a lot, so if you haven’t come across it before skip to the end and read about it now.

## Overall strategy for this problem

After looking at a specific case, we get an idea of the structure of this problem. For finding the good strings of length n:

• We need to find the number of ways of picking n letters, which is 26 choose n.
• Given the numbers 1, 2, …, n, we need to find the number of ways we can arrange them in a “good sequence”. A “good sequence” is when exactly one number is greater than the one before it. We will call the number of good sequences of 1, 2, …, n good(n).

The idea is that for each set of n letters, we can put them in alphabetical order, and label the letters from 1 to n by their order in this array. Any good string then gives a “good sequence” of 1 to $n$, and any “good sequence” corresponds to a unique string (from these letters). For example, using n=3 and the letters b,f, g:
* The good sequence [2,3,1] corresponds to the good string “fgb”
* The good string “gbf” corresponds to the good sequence [3,1,2]

The number of good strings of length n is then ${{26}\choose{n}} \times \text{good}(n)$.

## Finding good(n)

Let’s call our sequence [ a[1], a[2] , ..., a[n] ], where each a[i] is distinct and takes a value from 1 to n, inclusive. If this is a “good sequence”, then there is exactly one element a[j-1] that is greater than the element before it, a[j]. Note that this means that:

• a[1] > a[2] > a[3] > … > a[j], i.e. the elements before a[j+1] make a decreasing sequence
• a[j+1] > a[j+2] > a[j+3] > … > a[n], i.e. the elements from a[j+1] onward make a decreasing sequence

For example, a good sequence [4,2,5,3,1] can be broken into the two decreasing sequences [4,2] followed by [5,3,1]. In the notation above the value of j in [4,2,5,3,1] is 2 because a[2+1] = 5 is the only element bigger than the previous element.

Given the list of n numbers, there are n-1 choices for a[j]. (You can’t use the very last element, because there is no a[j+1].) Another way of seeing this is that we are splitting the array into two decreasing subarrays, and the only places that we can split on are the locations of the commas!

For now, let’s pick a particular value of j and ask how many good sequences of 1 through n we can make with this value of j. Given a set of distinct numbers, there is only one way of making them into a decreasing sequence, so really we just need to pick which j numbers go in the first decreasing sub-array, and which n-j numbers go in the second decreasing array. Note that once we pick the j numbers for the first array, the remaining numbers automatically go into the second array, so the number of distinct ways of splitting these numbers up is really just ${{n}\choose{j}}$. (We have counted one problematic sequence in here, which we’ll come back to.)

In case you got lost in the n and js, here’s an example to help you out. Let’s pick n = 5 and j=2. Instead of counting all the good sequences, we are just counting the ones where the split happens at position 3. So we have:

[a[1], a[2]] make a decreasing sequence, and [a[3],a[4],a[5]] make a decreasing sequence.

How many sequences like this are there? I need to split 1,2,3,4,5 up into two pieces: two elements (i.e. j) become a[1] and a[2], while the remaining three elements (n-j) become a[3] through a[5]. But once I pick a[1] and a[2], whatever is left over has to go into the other array. There are ${{5}\choose{2}} = 10$ ways of picking a[1] and a[2]:
* a[1] and a[2] are 1,2: the sequences are [2,1] [5,4,3] -> [2,1,5,4,3]
* a[1] and a[2] are 1,3: the sequences are [3,1] [5,4,2] -> [3,1,5,4,2]
* a[1] and a[2] are 1,4: the sequences are [4,1] [5,3,2] -> [4,1,5,3,2]
* …
* a[1] and a[2] are 3,5: the sequences are [5,3] [4,2,1] -> [5,3,4,2,1]
* a[1] and a[2] are 4,5: the sequences are [5,4] [3,2,1] -> [5,4,3,2,1] (UH OH!)

The last one is problematic, because all the numbers are decreasing! So while there are 10 ways of making the split into two decreasing sequences with n=5 and j=2, there are only 9 good sequences (with n=5 and j=2) because these is one sequence where all the numbers are decreasing.

The example shows us the problem with the way we have counted by splitting into two decreasing arrays: We never made sure that a[j+1] was bigger than a[j]. Fortunately there is only one arrangement that doesn’t work: the arrangement [n,n-1,...,1], so we have over-counted by exactly one. The number of good sequences split of 1 through n, split into arrays of length j and n-j is therefore ${{n}\choose{j}} – 1$.

To determine good(n), we just need to add up all the different good sequences we can get by putting the cutoff between the two arrays at different locations j. We get:

$\text{good(n)} = \large\sum_{j=1}^{n-1} \bigg[{{n}\choose {j}} – 1\bigg]$

This gets us to a point where we can write a program that will run quickly enough, so if you’re totally “mathed out” you can stop here! We can do a little bit better, through. Here are a couple of clever tricks:

• ${{n}\choose0} = {{n}\choose {n}} = 1$, because there is 1 way of not choosing anything from n objects regardless of n – just don’t pick any of them! – and 1 way of choosing all n objects from n objects. So putting j=0 and j=n into $\bigg[{{n} \choose {j}} – 1\bigg]$ gives zero. Now we can rewrite:
$\text{good(n)} = \large\sum_{j=1}^{n-1} \bigg[{{n}\choose {j}} – 1\bigg] = \large\sum_{j=0}^{n} \bigg[{{n}\choose {j}} – 1\bigg] = \large\sum_{j=0}^{n} \bigg[{{n}\choose {j}}\bigg] – (n+1)$
• You might remember from Pascal’s triangle that
$\large\sum_{j=0}^{n} \bigg[{n\choose {j}}\bigg] = 2^n$
One way of seeing this result is: The sum is asking us about the number of ways we can select a subset of n elements by figuring out the number of subsets with 0 elements, the number of subsets with 1 element, et cetera. Since each element is either in a subset or not, there are 2^n different subsets.

After all this work, we get:

$\text{good}(n) = \text{(number of good sequences of [1, 2, 3, …, n])} = 2^n – (n+1)$

## Putting it all together

From our overall strategy, we had ${26\choose {n}}$ ways of picking the n characters, and for each of our choices we had good(n) ways of arranging those characters into good strings. So the number of good strings of length n is:

${26\choose {n}} \times (2^n – n – 1)$

## …and now, some code!

The hard part about this problem isn’t writing the code, but figuring out how to count efficiently. The code is pretty small in this case:

from math import factorial as fact

def nChooseR(n,r):
# there are better ways that don't involve using
# dealing with large integers. For the moment,
# I am opting for pragmatism.
return fact(n)/((fact(n-r)*fact(r)))

def goodStringsCount(n):
return nChooseR(26,n)*(2**n - n - 1)


## Footnote: Ways of choosing r objects from n objects

How do we get the formula for ${n\choose {r}}$ in the first place? Suppose we have n=6 objects: a flag, a cookie, a laptop, a pen, a cup of coffee, and an orange. Note that we have picked easy-to-distinguish items! We want to select r = 4 of them. How many different sets of items could we come up with?

We have n choices for which item we pick first. We have n-1 choices for the second item, and so on. So it seems like the result is n(n-1)(n-2)(n-3). This becomes a little inconvenient to write for a general r (in this case, we know that r = 4), but notice that:
$n(n-1)(n-2)(n-3) = n(n-1)(n-2)(n-3)\times \frac{(n-4) \ldots (2)(1)}{(n-4)\ldots(2)(1)} = \frac{n!}{(n-4)!}$
This formula over-counts the number of different sets of items we could have because selecting the laptop, then the coffee, then the orange, and then the pen would give you the same set of items as selecting the coffee, followed by the orange, the pen, and the laptop. In the formula above, we have counted these two arrangements separately! (This is called a permutation of selecting 4 items from n, and is another useful formula to have under your belt).

How many different orders are there for selecting these 4 items? This is the number of times we have over-counted each set of items we could end up with. We’ll have 4 choices for whichever one we could have picked first (laptop, coffee, orange, or pen) without affecting the items we end up with. With the first item selected, we have 3 items to choose from for the second item, 2 choices for the third item, and then the last item is the 1 thing left over. So we can rearrange these 4 items in $4\times 3 \times 2 \times 1 = 4!$ ways. The number of combinations for picking r=4 things from n items is:

${n \choose 4} = \frac{n!}{(n-4)!4!}$

You can (and should!) run through this argument for a general value of r, and convince yourself that the number of ways of choosing r items from n is:

${n \choose {r}} = \frac{n!}{(n-r)!r!}$

## Tell us…

How did you solve this combinatorics interview question? Did you solution differ from mine? Let us know over on the CodeSignal forum!

## April Marathon Recap

As you may have heard (from us, because we won’t stop talking about it), CodeSignal hosts a monthly coding competition that we call the Marathon. CodeSignal Marathons, unlike their IRL counterparts, only last for one hour. And while you may not get a medal and a free banana afterwards, the top ten participants do get \$50 Amazon gift cards, not to mention coins and XP! Our content engineers create brand new challenges for each Marathon, all tricky, fun, and guaranteed to get your brain in gear.

We had a great turnout this month. Over 800 people registered! But of course, there could only be 10 top coders… and only one winner.

[table id=12 /]

Congrats to our top ten competitors, and a big high five to CodeFighter Alex_2008 for coming out on top!

CodeSignal CEO and founder Tigran Sloyan and Content Engineer Damien Martin (author of our awesome new CodeSignal Solves It and CodeSignal Explainer series) provided live commentary during the competition. If you missed the tournament or the live broadcast, we’ve got you covered. You can take a look at the questions from the Marathon and watch a video of the commentary at the same time!

Thank you to everyone who participated and/or watched the live broadcast!

The May Marathon will be here before we know it, so mark May 27 off on your calendar! We’ll post the registration link soon.

The monthly Marathon is a great way to get in some solid coding during the weekend. We love seeing repeat competitors getting better each month they participate in a Marathon. Practice makes perfect! Whether you’re preparing for technical interviews or just becoming the best coder you can be, competition is a great way to hone your skills.

#### Previously on CodeFight On!

March Marathon Recap

## Tell us…

Did you watch the April Marathon? Did you participate? Either way, let us know what went well and what we can do better!