Important concepts in C and C++ that should be learnt before a programming interview.

Forget C, use C++, and learn STL. 

Note: I used STL and the C++ Standard Library interchangeably in this answer (though I probably shouldn't have). All the below structures and algorithms are in the C++ Standard Library, so it's what you need to learn.

All of the following are must-knows:

Data Structures

You should know how to use all these + all their related functions + the time complexity of all these functions + (probably) how these functions work

• vectors

  (dynamic arrays) - know why push_back is amortized constant, not just that it is so

• maps

  and

  sets

  (red-black BSTs usually)

• unordered_maps

  and

  unordered_sets

  (hash tables)

• stacks

  /

  queues

  /

  deques

  /

  lists

• priority_queues

  (though I'd argue in an interview you should just use a

  map

  since it can do anything a

  priority_queue

  can do and more)

You should also know what iterators are and how to use them with the above data structures and below algorithms, because you need to when using STL.

Graphs are also important to know how to implement. For interviews, I usually use a vector of vectors for an adjacency-list (or even adjacency-matrix) representation just because it's fast to implement and usually is sufficient enough for you to write your algorithm, but alternatives are also feasible and some people may prefer building it from scratch using classes/structs/pointers. In many cases you can just forgo building the graph completely during an interview and assume you have it given, and in some cases you shouldn't build the graph at all, but rather have your algorithm dynamically generate the needed parts as it executes.

Algorithms

Aside from all the related functions for the data structures above, the

algorithm

library is extremely important, and you should probably know every function in it as well as how it's implemented and its time/space complexity (because all of these are fair game for interview questions and you might be asked to implement them from scratch, though probably without as much generalization as STL). Here are the most important ones, though, in my opinion:

• sort

• stable_sort

• nth_element

• lower_bound

• upper_bound

• merge

  /

  inplace_merge

• next_permutation

  /

  prev_permutation

• rotate

• reverse

Familiarizing yourself with the various math functions via the

cmath

library is probably also a good idea, just in case you need them, though if you need a

tan

function in an interview you can probably just tell your interviewer "I'm going to assume I have a function to calculate

tan(x)

" and it'd be fine.

Pointers, Classes/Structs, and OOP Concepts

You should know these at least enough to make a linked list and trie (which are the most useful data structure that is not implemented in STL) in about 5-7 minutes, complete with an insert (or search) function (and yes you may be asked to do this in an interview). You should be very comfortable with them - I doubt pointers and classes will be explicitly asked about (you might be asked about OOP Concepts though), but you may very well have to use them.

Why You Should Know All This

Read this answer for the full version: Jimmy Saade's answer to How do I get a job at Facebook or Google in 6 months?

But basically, there are a lot of questions which rely on you knowing/having/being able to use these data structures/algorithms directly, without implementing them - especially

sort

and

vectors

,

maps

, and

unordered_maps

. Your solution to the asked question may require a hash table or heap to achieve a decent time complexity, or require that you sort the input - are you really going to implement these in the span of a 45 minute interview? No, and neither are you expected to. You're expected to make it easy on yourself and use STL, because the rest of the algorithm you're coding up is already going to be complex enough, plus you're never going to that in real life, and it shows you know not to re-make stuff that's already at your disposal.

The exception to this is if you're explicitly asked to implement something already in STL. For example, if you're asked to implement the

next_permutation

function, you obviously shouldn't use the STL function, though you could (and probably should) note that there is such a function in STL. But basically the interviewer is looking for you to figure out the algorithm and code it yourself.

The theory version of this question is answered here: Jimmy Saade's answer to What should I know from CLRS 3rd edition book if my aim is to get into Google? and so they kind of go together in that what's listed in this answer is an implementation of the concepts listed in the other.