Tag: technical interview

Interview Basics: Multidimensional Arrays

Interview Basics: Multidimensional Arrays

Did you read last week’s article on static vs dynamic arrays? If not, catch up now! This week we’re continuing the arrays theme and discussing multidimensional arrays. This is another data structure that you absolutely have to know to succeed in technical interviews, which is why several of our array questions in Interview Practice feature them.

Multidimensional Array Basics

What makes a multidimensional array different from a plain old array? And just what is a multidimensional array, anyway? 

Basically, a multidimensional array is also a random-access data structure, but in this case the data is accessed by more than one index.

Some languages like C# have built-in support for multidimensional arrays. But other languages support multiple indices by creating an “array of arrays”. A multidimensional array in which you need </span><span style="font-weight: 400;">N numbers to reference a particular piece of data is an </span><span style="font-weight: 400;">N-dimensional array. In other words, N is the number of indices needed to locate a single element in the array.

How do you access elements in a multidimensional array? In the “array of arrays” model, the elements at arr[i] are arrays themselves. And element arr[i][j] is the jth element in the array arr[i]. These arrays can be dynamic or static.

The good: The item lookup by index for multidimensional arrays is </span><span style="font-weight: 400;">O(1), and it’s easy to iterate over every element stored in a multidimensional array. You can use multiple indices that make sense for the problem you’re solving (consider using rows and columns for a problem about a chess board, for example), which makes it easier for you to read and maintain your code.

The bad: It’s not easy or quick to rearrange the elements in a multidimensional array, and it requires a long time to change its size.

Meet the 2D Array

Technically, it’s possible to have a multidimensional array of any size. But for technical interviews, it’s most important for you to be familiar with 2D arrays. 2D arrays are often used to implement:

  • Matrices, where matrix[i][j] represents the element at row i and column j;
  • Game boards like chess or checkers boards, where board[row][col] represents the state of the board at the location (row, col);
  • Maps, in which the map is divided into cells to represent different locations.

Jagged vs Regular Arrays

As we mentioned earlier, different languages have different ways of representing multidimensional arrays. When implementing a 2D array as an “array of arrays” (i.e. </span><span style="font-weight: 400;">arr[i] is itself an array), there is no technical reason why </span><span style="font-weight: 400;">len(array[i]) == len(array[j]). If the subarrays have different lengths, we call this a jagged array.

jagged multidimensional array
A jagged multidimensional array

But when we talk about multidimensional arrays, we often mean regular (or rectangular) arrays, in which each dimension has a fixed length.

regular multidimensional array
A regular multidimensional array

TL;DR? Watch this video instead!

More of a visual learner? We get it. Watch this video to get up to speed on the basics of multidimensional arrays!

Up to speed on this handy data structure? Head on over to the arrays section of Interview Practice to solve some real multidimensional array-based technical interview questions!

Interview Basics: Reverse a Linked List

Interview Basics: Reverse a Linked List

Reversing a linked list is a very common task in technical interviews. That’s why we devote a whole section of Interview Practice to them! Being able to solve this question easily is a great way to demonstrate to an interviewer that you’re a capable, competent programmer. Let’s discuss two different ways of reversing the direction of a linked list: recursively and iteratively.Linked list refresher

A linked list can be modeled by Node objects, where each node stores a value and a next pointer to the next node in the list. The last node in the list points to NULL, to indicate that you’ve reached the end of the list. You access the linked list by having access to a head pointer at the beginning of the list.

Basic Linked List
A basic linked list

You need to apply a function reverse(head) that does two things:

  1. Reverses the direction of the arrows, changing the structure of the linked list, and
  2. Returns a pointer to the new beginning of the list.

So all the nodes will stay in place in memory, and only the direction of the pointers will change.

Linked List Reversed
What we want to get

You probably wouldn’t implement a linked list this way in an actual program. There might be a lot of different references to the linked list before you reverse it.

Linked List Multiple References
A linked list with multiple references

If you call reverse(head1), you would update head1. But all the other pointers would then be stuck at the end of the linked list, and only head1 would be a good head pointer.

Linked List Reversing With Multiple References
Only head1 was reversed

To get around this, you could make a LinkedList class, or a sentinel head that external references could point to that contains the pointer to the beginning of the linked list. Then you could safely update this reference without breaking any external references.

Linked List with Sentinel Head
A linked list with a sentinel head

But so that we can focus on just the core algorithm, the solutions in this video use a simple version of the linked list.

Why is reversing a linked list tricky?

Linked lists are designed to be easy to traverse in the forward direction, and once a node passes a particular point there is no way of going back to it. If you were in a position where reversing order was something you needed to do often, then a linked list would be a poor choice of data structure and you’d be better off choosing something else.

So this isn’t a problem that you’d really ever encounter on the job. In technical interviews, though, this kind of question is asked as a way of assessing how well you can perform tricky manipulations. That’s why sometimes the problems that interviewers ask can feel kind of artificial.

In this video, I demonstrate two different approaches to reversing a linked list: a recursive one, and an iterative one.

The code

Interview Practice: Graphs, Advanced Trees & RegEx

Interview Practice: Graphs, Advanced Trees & RegEx

We’ve just added three-brand new computer science topics to Interview Practice! Get ready to dive deep on Graphs, Trees: Advanced, and RegEx. We’ve added these topics to our Extra Credit learning plan, which covers all of the topics in Interview Practice. 

Why are these topics so important to know for technical interviews? Read on for a brief introduction to each concept!

Graphs

Graphs Interview Practice TopicA graph is an abstract data structure composed of nodes and the edges between nodes. Graphs are a useful way of demonstrating the relationship between different objects. For instance, did you know that you can represent social networks as graphs? Or that the 6 Degrees of Kevin Bacon game can be modeled as a graph problem? Graph questions are really common in technical interviews. In some cases, the question will be explicitly about graphs, but in other cases the connection is more subtle. Read our tutorial to get up to speed on this topic and to learn how to identify this kind of question. Then practice your skills on graph questions from real technical interviews!

Trees: Advanced

Trees: Advanced Interview Practice TopicA tree is a data structure composed of parent and child nodes. Each node contains a value and a list of references to its child nodes. Tree traversal and tree implementation problems come up a lot in technical interviews. Common use-cases for an interview are: needing to store and do searches on data that is sorted in some way; needing to manage objects that are grouped by an attribute (think computer file systems); or implementing a search strategy like backtracking. You need to be very familiar with how to deal with these kinds of questions! (The tasks in Trees: Advanced ramp up in difficulty from the ones you get in the Trees: Basic category, so make sure you finish those questions before moving on to these ones!)

RegEx

RegEx Interview Practice TopicA regex is a string that encodes a pattern to be searched for (and perhaps replaced). They let you find patterns of text, validate data inputs, and do text replacement operations. A well-written regex can make it easier to solve really tricky interview questions like “Find all of the 10-digit phone numbers in a block of text, where the area code might or might not be surrounded by parentheses and there might or might not be either a space or a dash between the first and second number groupings”. While the specifics of how to implement a regex can vary between languages, the basics are pretty much the same. In the topic tutorial, we cover regex character classes, quantifiers, anchors, and modifiers and how to use them to write a good regex.    

Start now

These topics might not get asked in every interview, but they’re important to know! Read the tutorials about each concept, then solve the real interview tasks to practice your skills and solidify your understanding of the topic. (Learn more about how we’ve updated the Interview Practice experience to make it an even better practice and preparation tool.)

If you’re signed up for the Extra Credit learning plan, these topics have been added to your Interview Practice page already. If you’re signed up for a different learning plan, you can switch over to Extra Credit. Or you can sign up for a customizable Freestyle plan and add these topics!

Ace Your Next Interview With CodeFights

Ace Your Next Interview With CodeFights

You know that you need to prepare for technical interviews – right? Of course you do! Companies rely on technical interviews to weed out people who can’t cut it. And for qualified candidates, they’re used to gauge aptitude, interest, and intelligence. So the stakes are really high, and you need to do everything you can to give yourself a competitive edge.

But it can be hard to know what exactly to study. There’s so much information out there, and sometimes it feels like you have to know everything. If you start studying without a plan, you risk wasting your time by preparing for the wrong sorts of questions, not studying enough, or any other issue that might hamper your ability to knock the interviewer’s socks off. And we want those interviewer’s socks to be knocked all the way off! In other words, we want to make sure that you ace your next technical interview.

That’s why we’ve made some changes to Interview Practice that make it an even better interview prep tool. Now you can join a study plan that gives you a timeline and a way to track your progress (or you can create your own plan). Each study plan has essential topic overviews and real interview questions from real companies. This makes it easy to know what topics to cover and how much to study.

Choose a study plan

Each study plan covers the most commonly-asked interview topics that you should prepare for, given the amount of time before your interview.

  • Crash Course: As the name implies, the Crash Course is perfect for when you have a technical interview coming up soon! This study plan will get you up to speed on computer science fundamentals. These are common topics that you must know in order to do well on interviews. Choose this plan if you have two weeks (or less) to prepare for an interview.
  • Fundamentals: If you have an interview coming up in the next 2-6 weeks, this is the perfect study plan for you. Since you’ve got a little more time to prepare, the Fundamentals plan covers some other common topics like bits, strings, sorting algorithms, and useful problem-solving techniques.
  • Extra Credit: If you plan to start interviewing at some point in the future, but don’t have any specific plans yet, check out the Extra Credit study plan. Extra Credit covers big topics like number theory, counting, and geometry. These concepts are really important but don’t get asked as often in interviews.
  • Freestyle: If none of these options is exactly what you need, don’t worry. It’s quick and easy to create a Freestyle plan! Just select the topics that you need to study and the amount of time you have before your interview, and our system will create a customized study plan for you to follow.

Once you’ve chosen a study plan, Interview Practice keeps you on track by recommending a minimum number of coding tasks to solve each day – and reminding you to start hustling if you’re not meeting your daily quota!

Study important concepts

A mainstay of the technical interview process is asking questions that help the interviewer determine how well you understand computer science fundamentals like data structures and algorithms. The interviewer is also assessing whether you can implement these concepts appropriately, and whether you take time and space complexity into account. Depending on where you are in your career, some of these topics might be ones that you haven’t touched since you were in school. Or maybe you’ve never formally studied them.

Interview Practice gives you a refresher course on these common interview topics. You need to be strong on these in order to do well in technical interviews, whether you’re a junior developer or have been in the field for years.

Study important interview concepts.

Solve actual coding problems

The questions you get asked in technical interviews are aimed at making sure that you have a fundamental understanding of how to write code. The interviewer also wants to make sure that you take edge cases and optimization into account. While you’re whiteboarding, interviewers are also gauging how you think while you’re working through a problem.

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!

Each topic in Interview Practice has real interview questions from real companies for you to practice on, ordered by difficulty. As you solve them, you’re solidifying your knowledge of the topic and becoming familiar with this kind of problem.

Get going!

Interview Practice gives you a plan and helps you stick to it. This eliminates the guesswork about what you need to study,  how much you needs to study, and how you should organize your time. Work your way through each topic, reviewing each concept in the overview and solving the questions. As you practice, you’re becoming a better programmer. You’re also giving yourself a serious advantage in technical interviews!

Time to get started! Head to CodeFights and get started on the new and improved Interview Practice today.

Do you need to prepare for technical interviews?

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 CodeFights, 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.

Technical interviews make me cry.

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

Create your timeline

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.

Create your routine

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 CodeFights forum!

CodeFights Solves It: chessQueen

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

Ready? Great, let’s get started!

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.

position of the queen in Adobe technical interview question
Queen at D4

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

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.

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

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:

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 CodeFights forum!

CodeFights Solves It: goodStringsCount

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

combinatorics interview question solution
The new MacBook Pro looks really nice!

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:


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

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

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:

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:

  • , 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 gives zero. Now we can rewrite:
  • You might remember from Pascal’s triangle that

    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:

Putting it all together

From our overall strategy, we had 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:

…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:

Footnote: Ways of choosing r objects from n objects

How do we get the formula for 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:

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 ways. The number of combinations for picking r=4 things from n items is:

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:

Tell us…

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

Interview Practice Task of the Week

Interview Practice Task of the Week

Have you been using our Interview Practice module to prepare for technical interviews? If not, you definitely should be!

Interview Practice has over 100 questions that get asked by top companies during real interviews. (Which companies, you ask? Oh, you know. Just lil’ companies like Apple, Facebook, Google, Microsoft, Twitter, and more.) The topics are ones that you’ll definitely encounter – coding patterns, algorithms, and data structures. You need to be strong these topics in order to do well in technical interviews, whether you’re a junior developer or have been in the field for years.

We’re adding more questions on more topics from more companies all the time, so you’re not going to run out of questions any time soon. In fact, it can be a little bit overwhelming – which challenge should you tackle first? A general rule of thumb is to choose questions based on where you’re interviewing and on topics that you need to study.

Where you’re interviewing

Interviewing at Facebook? Then it’s a given that you should practice using the Facebook Interview Practice questions!

But if we don’t have questions from the company that you’re interviewing with, use the resources at your disposal to find out what sort of questions typically get asked during their interviews. Glassdoor often has this kind of info, so it’s a good place to start researching. And leverage your professional network! Do you know anyone who’s interviewed at (or worked for) the company? Reach out to them and get the inside scoop.

Topics that you need to study

The list of things that you need to study will be largely informed by the research that you’ve done about the company you’re interviewing with. If you know that a company is likely to ask you questions about graph traversal, you can start working on graph traversal interview questions to prepare.

This is an instance in which knowing and being honest with yourself about your skills is critical too. For example, you may have known basic data structures inside and out as a computer science undergraduate. But if you’ve been working as a front-end developer for the past two years you might be a little rusty. Time to start practicing!

Studying != cheating

It’s pretty unlikely that you’ll be asked the exact same questions that we have here in Interview Practice or that are listed on Glassdoor. But researching questions that have been asked in the past is just plain smart, and a great way to set yourself up for success. The goal here isn’t to memorize the answers to a narrow set of questions. You’re not cheating! And really, even if that was your goal, interviewers pick up on that sort of thing really quickly. Rather, the goal is to be as prepared as possible for your interview.

Task of the Week

If you’re not sure where to start, we suggest that you tackle the Interview Practice Task of the Week! Every week, CodeFights content engineers select a new challenge to feature. They choose these interview questions because they’re tough ones that will get you into an interviewing mindset. Once you’ve solved the challenge, check out other CodeFighter’s solutions. It can be extremely instructive to see how other people have solved the same problem. Speaking of which…

CodeFights Explains It

Every Thursday, our content engineer Damien Martin writes a CodeFights Explains It editorial that breaks down how to solve the past week’s Task of the Week. He also tackles issues that are likely to come up during an interview. (Think optimizing your solution and working with interviewer-imposed restraints.) Make sure that you’re reading this series every week! It’s a great supplement to your interview preparation routine.

Tell us…

Have you solved an Interview Practice Task of the Week yet? How are you fitting Interview Practice (and CodeFights in general) into your interview preparation? Let us know over on the CodeFights forum!

CodeFights Solves It, Interview Practice Edition: groupsOfAnagrams

CodeFights Solves It, Interview Practice Edition: groupsOfAnagrams

This week’s featured Interview Practice challenge was groupsOfAnagrams. It’s a Twitter interview question, and they’re known for their difficult technical interviews! If you haven’t solved it yet, go ahead and do that first, then head back here and we’ll discuss how to get to a solution with a good runtime.

…Done? Okay, let’s dig into this coding challenge!

The technical interview challenge

You are given a list of n words. Two words are grouped together if they are anagrams of each other. For this interview question, our task is to determine how many groups of anagrams there are.

For example, if the list words = [listen, admirer, tea, eta, eat, ate, silent, tinsel, enlist, codefights, married], we should have groupsOfAnagrams(words) return 4 because there are 4 groups:

  • listen, silent, tinsel, enlist are all anagrams of each other.

  • tea, eta, eat, ate are all anagrams of each other.

  • married and admirer are anagrams of each other.

  • codefights is not an anagram of anything in words except itself.

In the challenge, we are guaranteed that each word only consists of lowercase letters. So we don’t need to worry about the rules regarding spaces and punctuation. Each word is guaranteed to be at most 10 letters. The hard part is that we have to do this on lists containing up to 10^5 words!

First attempt: Determining if two words are anagrams

There are a few standard ways to determine whether or not words are anagrams of each other. One way is to go through each letter of the alphabet, and check that it appears the same number of times in each word.

What is the runtime of this algorithm? Suppose a typical word has L characters. In calling word.count(char), we are asking the computer to scan word to count the number of times character char appears. This is an O(L) operation. Technically, this makes areAnagrams an O(L) algorithm because we do this count operation for each letter of the alphabet, which doesn’t depend on the size of the word. However, big O notation suppresses the really bad constants hiding in the runtime! Consider that our words have at most 10 letters, and some may be repeats. That means that of our 26 iterations of the loop, at least 16 of them are wasted looking for letters that don’t appear. If we call the number of letters in the alphabet A, then the runtime of this algorithm is O(AL).

Interview Tip:

Asymptotic, or “big O”, notation misses constants. Analysis such as treating the size of the alphabet as a parameter is useful to estimate the size of the constants. This is particularly true in this case, where L is guaranteed to be less than the size of the alphabet A.

If the interviewer questions why you’re doing this (after all, English is almost certainly going to have 26 lowercase letters for our lifetimes!) you have the chance to impress them by saying that you’re considering what happens if punctuation is allowed, or if the company decides to look at large unicode character sets. This shows that you’re forward thinking, and have design on your mind – two things that it’s important to emphasize in technical interviews.

Basically, if using a constraint in the problem helps you significantly reduce the problem, feel free to use it. If you need time while you’re working on your solution, or are doing something odd like considering the number of letters in the alphabet as a variable, you can always defend your move as considering the design implications of the constraint!

We can reduce this runtime of our solution significantly by going through each letter in word1 one at a time. This is at most 10 letters, rather than 26. Here’s one way of implementing it:

While the code is longer, and it’s still O(L), it is no longer O(AL). Note that we are no longer assuming the strings are only made of lowercase letters!

Approach 1: Works, but too slow…

We have an anagram checker that will tell us if any pair of words are anagrams.

What is the runtime here? We run through the loop O(N) times, where N is the number of words. If we are lucky, we remove a lot of words early. However, if each word is not an anagram of any other word, the while loop runs exactly N times. Inside the loop, we scan the remaining words for anagrams. So this is an O(N^2) algorithm. Since we can have up to 10^5 words in a list, O(N^2) probably won’t work. Sure enough, this code doesn’t pass the tests on CodeFights – and it’s not an answer that will knock the interviewer’s socks off during a technical interview. We can do better!

Approach 2: Precomputing invariants

We are going to find an invariant that all the words that are anagrams share with each other, but don’t share with any words they are not anagrams of. We will use these as keys in hash tables with dummy values. At the end, we will simply count the number of keys in the hash table.

What are the invariants that we can use? A simple invariant is the number of as, the number of bs, …, etc. Any two words that are anagrams will have the same invariant, and any two words that aren’t anagrams will have different invariants.

For each word, this is an O(AL) process, as we are iterating through both the letters in the word and in the alphabet. The gain is going to occur because we only calculate it once per word.

Our algorithm is then:

Because calcInvariant is O(AL), where L is the number of letters in the word, we see this algorithm has time complexity O(NAL). Note that we never compare invariants. Instead, we use the magic of hash tables to set the value of 1 to the appropriate entry. If that key already exists, we overwrite the value. If it doesn’t exist, a new value is created. It was the comparison between keys that gave us our problematic O(N^2).

A cleaner, faster, invariant

There is another natural invariant for the words: sorting the letters that occur in the words. We could use:

This has the advantage of being easy to understand, and not making any assumptions about the underlying algorithm. It is a sorting algorithm, so it is O(L log L) instead of O(AL). (Technically we can’t compare algorithms using big O notation like this, because we don’t know the constants involved.) The sorted string can then be used for the invariant. In fact, the code for groupsOfAnagrams doesn’t have to change at all!

This is faster because our sorting algorithm on small words is much faster than our O(AL) dictionary. If the words are long (e.g. we are comparing novels) then our compression of the string to count the number of times the characters are repeated would win. When accessing the hash table hash_of_invariants we need to use the hash function, which depends on the length of the keys. Since L < 10, we know that each key is at most 10 characters long, so the sorting invariant is elegant and understandable.

Dictionaries where we don’t care about the value: Sets

In our hash table, we didn’t really care about the values assigned to the keys. We were only interested in the number of distinct keys we had, as that told us how many groups of anagrams we had.

There is nothing wrong with this, except that someone reading your code may wonder what the significance of the 1 is when you wrote:

The comments certainly help. But Python has a built-in data structure for this case called set. If we made a set of invariants instead, we would simply have:

There is not a visible dummy value that might confuse future maintainers of your code. Under the hood, the Python set is implemented as a dictionary (hash table) with hidden dummy values with a few optimizations, so the real reason for doing this is readability. Because hash tables are used more frequently than sets, there is a valid argument that the hash table is more readable for more programmers.

The final solution

Here is our final, compact solution! Any interviewer would be happy to see this solution during a technical interview.

Timing all the methods

In an interview, you always have to consider the runtime. As you could see, a lot of the effort in creating a solution for this interview question was finding an algorithm that was quick enough! I timed the algorithms for two cases:

  • Our first example, words = [listen, admirer, tea, eta, eat, ate, silent, tinsel, enlist, codefights, married]

  • A pathological example, where each word was its own group of 10 letters, starting with abcdefghij, abcdefghik, …, to abgilnoz (this is a total of 10^5 words)

I didn’t include the raw times, as that tells you more about my computer than the algorithm. Instead I normalized to the time for Method D on the list words (i.e. Method D has a time of 1 by definition).

Method Description Time for words (compared to D on words) Time for 10^5 words (compared to D on words)
A O(N^2) method 5.4 Too Long to Time
B Using precalculated tuple invariant for hash table 6.4 70300
C Using sorted words for hash tables 1.2 10450
D Using sorted words for sets 1.0 7000

Tell us…

Did your solution for this Interview Practice challenge look different than mine? How did you approach the problem? Let us know over on the CodeFights forum!

Make Your Engineering Resume Stand Out

Make Your Engineering Resume Stand Out

Love ’em or hate ’em (and we’re guessing you don’t love them), resumes are still part of the typical job search process. But putting your resume together can feel like one of the hardest parts of the whole thing! What should you include? What should you leave out? And do you need to include your home address? (Hint: City and state? Sure. Street address? NO.)

A typical engineering job posting can generate hundreds of applications. Only a relatively small percentage of those resumes ever make it in front of a recruiter – and the percentage of those applications that lead to interviews is tiny.

Make your resume stand out
This monkey is having trouble with his resume.

With odds like those, you need to ensure that your resume stands out.

Caity Barnes, recruiter extraordinaire at CodeFights, is going to let you in on some insider knowledge: exactly what she looks for when she’s looking at resumes for engineering roles.

“In a lot of ways, writing a good engineering resume isn’t any different than writing any other kind of resume – make sure it’s well-formatted and that everything’s spelled right. But there are some really specific things that I look for when we’re trying to fill engineering roles.”

Format

  • Recruiters tend to scan resumes in a very specific order. They look at your geographic location, the last job you had, and your education, then the skills list. If they get past that point, that’s when they’ll dive into the other jobs that you’ve listed, and then at projects, achievements, and anything else you’ve included. 
  • If you try to get creative with formatting, fonts, or layout, Caity says that many recruiters will glance at it, decide that it’ll be too hard to scan, and toss it. Don’t let this happen to you! (This applies less if you’re applying for a design job, of course, but most CodeFighters are probably applying for engineering jobs.)
  • A one-page resume is best. If you just can’t cut it down that much, at least make sure that the most important stuff is on the first page. Many recruiters won’t make it further. Hook their attention by putting the most eye-catching stuff first.
  • For every job you list, make it easy for the recruiter to see the company’s name, your title, and how long you were there.
  • Bullet points are your friend! Instead of writing in paragraphs, use bullet points. They’re much easier for recruiters to scan.
  • Don’t talk about yourself in the third person – who are you, the Queen of England? Instead of saying “Bart designed and implemented a user feedback module using Django”, say “I designed and implemented…” Or better yet, since you’re using bullet points, say “Designed and implemented…”
  • In Caity’s opinion, it’s not necessary to include an objective statement at the top of your resume. They’re usually so generic that they’re not useful, and recruiters tend to gloss over them. If you do choose to include one, make it a statement about the kind of company culture that you’re looking for, instead of the kind of work you want to do.
  • Caity says, “I don’t care if you went to the best school in the country – your work experience is more important!” If you’re a very recent grad, you can put the Education section at the top, but otherwise put it at the bottom of the page.
  • Run your resume through spell check and grammar check, and get a few different people to proofread it. While it might seem unimportant – damn it, Jim, you’re an engineer, not an editor! – in some cases a typo or incomprehensible sentence might disqualify you immediately.
Jim, your resume is a mess.
Jim, your resume is a mess.

Content

  • Make sure that you include relevant keywords in your resume. Caity says that when a recruiter’s skimming, they need to be able to pick out important items immediately. And these keywords will change depending on the type of jobs you’re applying for. Think about the skills you’d be highlighting if you were applying for front end jobs vs Java engineering jobs.
  • Be thoughtful about how you include skill items like languages or frameworks. If you list Go, there’s a big difference having used it daily on the job vs having taken a 30 minute seminar on it 2 years ago. Recruiters want to be able to get a sense of how proficient you are. It’s also helpful if you can talk about what you did with these tools so that the recruiter can weight them accordingly.
  • Keep in mind that recruiters tend not to be super technical. From Caity: “We know more about impact than super technical details, so focus on business outcomes that you were a part of.” It’s also helpful to quantify your contributions. (For instance: Were you an individual contributor or part of a team? Was it a big or small team? How many concurrent users did your tool support? How much data did it process daily/weekly?)
  • Try to highlight solo projects or projects to which you contributed a lot, whether they’re for work or side projects. Creating something from scratch is huge and shows initiative, and it’s a great signal to recruiters that you’re a problem solver.
  • “Spell as much out for the recruiter as possible,” Caity says. They are not going to have time to do internet detective work, at least on the first pass. If you worked at a small startup, a short blurb about what the company is helpful. What industry is it in, what size is it, what sort of funding did it get? And if there’s a short tenure on your resume (less than a year), call it out and explain why you left – contract ended, company went under, etc.
  • Put links to your GitHub and your LinkedIn, because they give the recruiter a good overall picture of you. Including other social media can be a little tricker. What does your Twitter feed look like? If you tweet about work-appropriate and relevant topics, go for it. Otherwise, leave it off your resume. Same goes for your blog.
  • Speaking of GitHub, make sure that your profile is something that you’re proud of. Caity says that most recruiters will share it with their hiring managers or interviewing teams to review before taking next steps with candidates. So take some time to clean yours up. Repos that are your own work, rather than forks off other people’s, are good, as is a strong commit history.
  • For recent grads or students – if your GPA is lower than 3.5, don’t include it. If you’ve taken advanced courses on really relevant topics (especially if they were practical, rather than theoretical), you can list them in your Education section. And remember that class projects or coursework aren’t the same thing as side projects, and recruiters won’t weigh them the same.
  • Feel free to put your personality into the resume. What are your hobbies and special interests? Caity says that recruiters love being able to get a sense of who you are! But this stuff should go at the bottom of the page. Remember, recruiters scan top to bottom. You need to put all of the important, must-see stuff at the top of the page.

tl;dr

To boil all of these down into a few principles: Your resume should be clear, concise, and easy to digest. Keep the layout simple and easy to scan. In terms of content, include information that makes it so the recruiter doesn’t have to guess about your history or do extra digging on the internet.

Remember, recruiters aren’t maliciously ignoring your resume! They’re trying to optimize the number of resumes that they can look at for any given engineering job in order to quickly find the most qualified candidates. If you follow these guidelines, your resume stands a much better chance of making it into the “follow-up” pile.

Your resume looks amazing
Your resume looks amazing!

You’re reading an article about how to make your resume stand out, so my spidey senses tell me you might be looking for a job! Did you know that CodeFights can connect you with hundreds of tech companies that are actively seeking qualified engineers – all with only one application? Head to codefights.com/jobs and start finding that dream job today!  

Tell us…

Do you have any tried-and-true tips on how to make your resume stand out? Head over to the CodeFights forum and let us know!