Traversal is a process to visit all the nodes of a tree and may print
their values too. Because, all nodes are connected via edges (links) we
always start from the root (head) node. That is, we cannot randomly
access a node in a tree. There are three ways which we use to traverse a
tree −
In-order Traversal
Pre-order Traversal
Post-order Traversal
Generally, we traverse a tree to search or locate a given item or key in the tree or to print all the values it contains.
In-order Traversal
In this traversal method, the left subtree is visited first, then the
root and later the right sub-tree. We should always remember that every
node may represent a subtree itself.
If a binary tree is traversed in-order, the output will produce sorted key values in an ascending order.
We start from A, and following in-order traversal, we move to its left subtree B. B
is also traversed in-order. The process goes on until all the nodes are
visited. The output of inorder traversal of this tree will be −
D → B → E → A → F → C → G
Algorithm
Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.
Pre-order Traversal
In this traversal method, the root node is visited first, then the left subtree and finally the right subtree.
We start from A, and following pre-order traversal, we first visit A itself and then move to its left subtree B. B
is also traversed pre-order. The process goes on until all the nodes
are visited. The output of pre-order traversal of this tree will be −
A → B → D → E → C → F → G
Algorithm
Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.
Post-order Traversal
In this traversal method, the root node is visited last, hence the
name. First we traverse the left subtree, then the right subtree and
finally the root node.
We start from A, and following Post-order traversal, we first visit the left subtree B. B
is also traversed post-order. The process goes on until all the nodes
are visited. The output of post-order traversal of this tree will be −
D → E → B → F → G → C → A
Algorithm
Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.
Java enables you to manipulate integers on a bit level, that means
operating on specific bits, which represent an integer number. In some
cases, it can be really handy.
Bitwise operators
You are no doubt familiar with arithmetic operators such as + - * /
or %. You also know for sure logical operators such as & or |. Turns
out there is another, a slightly less known set of operators, which
manipulate numbers on bit level. Internally, every number is stored in a
binary format - that is 0 and 1.
These operators can be performed on integer types and its variants - that is
byte (8 bit)
short (16 bit)
int (32 bit)
long (64 bit)
and even char (16 bit)
Unary bitwise complement operator [~]
This fancy name basically means bit negation. It takes every single
bit of the number and flips its value. That is - 0 becomes 1 and vice
versa. Unary means that it needs just one operand. The operator is ~ and
it is just placed before the number:
~someVariable
or
~42
For example, let's use ~42:
The binary representation of 42 is 101010.
Because 42 is int, it is represented as a 32-bit value, that is 32x ones or zeros.
So all the positions to the left of 101010 are actually filled with zeros up to 32 bits total.
That is 00000000 00000000 00000000 00101010
Flipped value of the number above would then be 11111111 11111111 11111111 11010101
Bitwise AND [&]
Unlike bitwise complement operator, other bitwise operators need two operands.
A & B means that all the bits of both numbers are compared one by
one and the resulting number is calculated based on values of the bits
from numbers A and B. Bitwise AND is similar to logical AND in a sense
that it results in 1 only when the two compared bits are both equal to
1. Otherwise, it results in 0.
For example: 1010 & 1100 would result in 1000 as the first bit from the left is the only one where both operands contain 1.
Bitwise OR [|]
Bitwise OR results in 1 when at least one of the compared bits is 1 (or both), otherwise it results in 0.
Bitwise Exclusive OR (XOR) [^]
Exclusive OR (XOR) results in 1 only if both the compared bits have a different value, otherwise, it results in 0.
Bitwise Operators comparison
Below is a table showing a comparison of results of all the bitwise
operators mentioned above based on different values of the compared bits
(A and B).
A
B
A & B
A | B
A ^ B
1
0
0
1
1
0
1
0
1
1
1
1
1
1
0
0
0
0
0
0
Bit Shift Operators
Signed Left Shift [<<]
Signed Left Shift takes two operands. It takes the bit pattern of the
first operand and shifts it to the left by the number of places given
by the second operand. For example 5 << 3: What happens in this
case - Every bit in the binary representation of the integer 5 is
shifted by 3 positions to the left. All the places on the left are
padded by zeros. That is:
00000000000000000000000000000101
becomes
00000000000000000000000000101000
You can note that the integer result of 5 << 3 is 40. That
shows that shifting a number by one is equivalent to multiplying it by
2, or more generally left shifting a number by n positions is equivalent to multiplication by 2^n.
There are several additional interesting aspects to this:
Even though you can use shifting of byte, short or char, they are promoted to 32-bit integer before the shifting
Bit-shift operators never throw an exception
The right operand (the number of positions to shift) is reduced to
modulo 32. That is 5 <<35 is equivalent to 5 << 3.
Negative Integers in Java
There are actually two types of right shift. Signed and unsigned. The
difference is how they treat negative numbers. To understand the
difference, it is necessary to know how negative numbers are represented
in Java. Binary representation on its own does not provide information
whether the number is negative. There needs to be a special rule to
define how to represent negative numbers in binary. There are several
approaches to this problem.
One solution is that the leftmost (Most Significant) bit is a sign
bit. That means that its value indicates whether the number is positive
or negative. This has, however, some disadvantages such as that there
are two ways of representing zero.
Java uses another approach, which is called two's complement.
Negative numbers are representing by negating (flipping) all the bits
and then adding 1. Still, if the leftmost bit is 0, the number is
positive. Otherwise, it is negative.
Signed Right Shift [>>]
Signed right shift moves all the bits by given number of positions to
the right. However, it preserves the sign. Positive numbers remain
positive and negative ones remain negative. Similar to left shift, the
right shift of n positions is equivalent to division by 2^n. Or division by 2^n -1 in case of odd numbers.
Unsigned Right Shift [>>>]
Unlike the signed shift, the unsigned one does not take sign bits
into consideration, it just shifts all the bits to the right and pads
the result with zeros from the left. That means that for negative
numbers, the result is always positive. Signed and unsigned right shifts
have the same result for positive numbers.
Compound Assignment Operators
Java offers a shorter syntax for assigning results of arithmetic or bitwise operations. So instead of writing this:
x = x +1;
You can use a shorter version, which will handle both addition and assignment with just one operator:
x +=1;
You are probably familiar with compound assignment operators for arithmetic operations such as +=, -= or *=. But in addition to these, Java also offers variants for bitwise operators:
Operator
Example
Is equivalent to
|=
x |= 5
x = x | 5
^=
x ^= 5
x = x ^ 5
&=
x &= 5
x = x & 5
<<=
x <<= 5
x = x << 5
>>=
x >>= 5
x = x >> 5
>>>=
x >>>= 5
x = x >>> 5
Note that there is no compound assignment operator for Unary bitwise complement operator [~].
Conclusion
Bit manipulation can be very handy in some cases and is really
efficient. Increased performance, however, comes at its cost. The
readability suffers a lot at it can be really puzzling for somebody who
is not familiar with the bit manipulation concept. If the scenario you
are using is not performance-critical, you may want to consider, whether
the tradeoff of performance for readability is really worth it and
maybe rewrite your solution in a more readable way. Don't use bit
manipulation everywhere possible just because you learned a cool new
concept.
Disclaimer: This post is in no way affiliated with Leetcode, or endorsed by Leetcode. I am just a user/ fan of Leetcode.
Lately, I’ve had a number of people asking me for advice on how to improve at answering the style of questions found on Leetcode.
I’m not an expert in job interviewing—in fact, my experience in it is
quite limited. But I think my experiences and improvement with solving
Leetcode questions means I can give some useful advice to others. So,
for what it’s worth, I’m going to share some tips on how I think I’ve
gotten where I have with it.
I started doing Leetcode questions when I wanted to get better at competitive programming, after really enjoying the Google Code Jam
but never doing well beyond the 1st round. Fast forward to a few months
later, and I’ve now solved almost 600 Leetcode questions, with the
ultimate goal of solving them all. I take part in the Leetcode weekly
competitions, where I have seen my weekly ranks slowly but surely go up.
I went from only solving 1 - 3 questions per week, up to
more-often-than-not, solving all 4. I went from getting only 5
participation coins per week, to getting 50 most weeks for being in the
top 200. Hopefully soon I'll be in the top 100.
So with that, here we go. My 20 best tips that I hope will help you achieve the same!
1. Know your motivations
Why do you want to "get good at Leetcode"? Do you want to get your
dream job? Win programming contests? Learn more about algorithms?
Without a good motivation, you may struggle. If your only motivation is
to get your dream job, then you might also struggle to stay motivated,
especially with the "risk" of not getting the job. If you don’t enjoy
solving the questions, it might not be worth doing the advanced ones.
There are plenty of good companies out there where you won’t need to be
able to solve medium-level and hard-level Leetcode questions to get into
them.
So, think about what motivates you, and keep that motivation in mind!
2. Set realistic goals for yourself
Multiple times, I’ve seen people ask how many questions they should
solve in a day. This is the wrong question to ask though. You shouldn’t
have a number-of-questions-per-day target. Instead, you should decide
how much time you are willing and able to put towards your
learning, and then make it your goal to use that time as productively as
you can, aiming to improve. You can only do your best, and you should
be aiming to do your best, so comparing to other people won’t be helpful here.
Aim to divide your time between learning new skills, mastering old
skills and general problem solving (tackling questions without initially
knowing what skills you'll be applying).
3. If you don't have a CS degree, do an online data structures and algorithms course
If it wasn't for the first year data structures and algorithms course
I did back when I was in university, I don't think I would have known
where to start. Getting started can be daunting, and knowing what
exactly to focus on can be even more so. As a rough guide, you'll need a
course that takes you over key ideas such as Arrays, Sorting,
Searching, Linked Lists, Trees, Graphs, Stacks, Heaps, Queues, Hashing
(maps, sets, and dictionaries), Big-O notation, and complexity analysis
(cost). By the end of it, you should know the use cases for each data
structure, and be able to justify the reasons in terms of cost.
A good online course will have assignments and quizzes that'll help
you know whether or not you're on track and picking up the most
important ideas. This will then help you as you move towards
self-directed learning on more advanced concepts.
There are also many good resources on the more basic programming
skills. Find one that suits your style and language of choice. Make sure
you can design programs with loops and conditionals (if statements)
with ease, as this is central to algorithm design.
4. Find some good resources for learning more advanced algorithms
It really does help to have a good resource to look at when needed. I use the CLRS algorithms book.
I’d highly recommend it, either go for the e-book version on Amazon or
look for it in the library (if you’re a university student with access
to a library) if the cost is a concern. The Leetcode Explore modules are fantastic too. Geeks For Geeks
also has some useful content, although the writing quality varies a lot
and the lack of proofreading on some of the articles can make it
painful to read. If you can ignore that, great, if not, then you might
need to find another resource. Wikipedia also has some good articles,
although quality and clarity varies a lot.
5. Learn techniques, not solutions
I’ve seen a few people on the Leetcode forums and beyond asking how
many Leetcode questions they’d need to have done to have a good chance
of seeing all the questions they’ll get in their interview, and it
amazes me that anybody thinks this is a good idea. Leetcode itself
doesn't help the cause by providing lists of questions sorted by company
(for subscribers).
If in an interview you’ve already seen the question, it’d be dishonest
to pretend you hadn’t. You’d also have to be pretty good at faking the
“solving a novel problem” thought process your interviewer is looking
for.
Instead, you should be aiming to do enough questions to learn about
the common data structures, algorithms, and techniques that you’re
likely to need to use. Your goal is to get yourself to a point where if
you’re given a problem you’ve never seen before, you can work through it
and decide which data structures, algorithms, and techniques you could
apply to solve it. It will take a lot of practice to get to this point,
and sometimes there’ll be a question where it takes you a few minutes to
even know where to start. But the more you learn and practice, the
better you will become.
6. Learn the fundamental data structures (Basic)
These next 3 points are concerned with specific concepts you'll need
to learn. I've split them into 3 general categories, based on difficulty
and how often they tend to come up. I'd recommend mastering all in one
category before moving up to the next. The lists aren't exhaustive, and
the order isn't absolute, but this is roughly the order I worked on
learning and mastering concepts.
If you have a lot of trouble with even the simplest questions in the
fundamental data structures section (some are hard, I’m not saying you
have to find them all easy!), then you might need to find an
introduction to data structures and algorithms course to work through.
Most of these topics have a
Leetcode Explore
module, I highly recommend using them. After that, find more problems by
searching the problem list by the relevant tag. Focus mostly on
easy-level questions for now.
Arrays and Strings: Leetcode's module for Arrays and Strings is where you should start. This is a fundamental topic, so practice lots until you're really confident.
Linked Lists: Again, check out the module for Linked Lists.
Don't worry about the solution guides that are subscribers only—you
don't need them. Check out the discuss forum instead, click on posts
until you find a good one. Linked lists can be confusing at first, but
they’re easy as once you get your head around the idea of the next
pointers.
Trees: Focus on the N-ary trees module and then the Binary Trees
module. Don't worry about Binary Search Trees yet, you can look at
those a bit later. For some reason, the information documents about
traversals are subscribers only. Don't worry about this though, there
are plenty of great free resources around, such as this overview and these widgets that get you to click on nodes in the correct order. You'll find lots more by googling.
Hashing: This is dictionaries/maps, and sets, and is covered under the Hash Tables
module. This is one of the most useful topics you’ll learn, so be sure
to get lots of practice in, as most challenging questions use these data
structures as part of the solution. Don't worry about the few bits that
are subscribers only.
Stacks, queues, and heaps (priority queues): These are also fairly versatile, coming up in a lot of problems. Stacks and Queues have a module, although heaps/ priority queues don't yet. Have a look on Geeks For Geeks for some good articles on heaps, and then find some questions on Leetcode that are solved with a heap. Check if your programming language of choice has a built-in heap type, it will be called either a heap or a priority queue.
Two pointer technique: If you didn’t do this with arrays, you should do it now. It comes up a lot.
Make sure you know complexity costs of these basic data structures,
for example, that finding whether or not something is in a linked list
is O(n), but finding whether or not its in a dictionary is O(1).
You should understand the costs inside and out, knowing exactly why
they are what they are. Simply memorizing the costs won’t help you much.
7. Learn the more advanced data structures and some famous algorithms (Intermediate)
There are some algorithms and a few more data structures that will
come up over and over again. It is well worth putting time into studying
each of these, much like with the fundamental data structures. Some of
them will be in the easy category and some in medium. The hard ones tend
to combine multiple concepts.
Recursion: This alternative to iteration is helpful
for solving some problems, and once you’re used to it, is often quicker
to write than iteration. Leetcode has a module for recursion. Just do this module, don't worry too much about recursion 2 yet, there are more important concepts for you to learn first.
Graphs and graph algorithms: Graph algorithms come
up everywhere. I've heard that in the interview processes of top
companies, getting at least one graph question is inevitable. The main
things they are looking for is that you know the 3 main ways of representing a graph: linked, adjacency list, and adjacency matrix,
choosing the best one for a given situation, and then running
algorithms over it such as breadth-first search, depth-first search, and
topological sort. Often graph questions aren't explicitly listed as
such—you'll be given some data as an input that you need to convert into
a valid graph format, and then run the appropriate algorithm over it.
You must get really good at recognizing graph questions instantly. Be
aware too that a 2D array can represent a special kind of graph where
each cell represents a node linked to its neighboring cells. Often these
are breadth-first search questions. You should have already seen some
of this in stacks and queues, and trees. But be sure you're super
confident with graphs. You should be able to BFS and DFS both
iteratively and recursively, and with your eyes closed (okay, maybe not
that extreme, but you should be really confident with them!).
Union find: This algorithm can initially seem
scary, but it’s not. It’s useful for finding the connected components of
graphs and solving a number of other problems. Have a look on Geeks for Geeks to get started or the CLRS textbook if you own a copy. There is no Leetcode module on it yet, but there are lots of relevant questions.
Learn the simple optimizations, in particular path compression, as
while they sound advanced, they're actually really simple and lead to
huge efficiency gains.
Binary search: People tend to get quite bothered by
this algorithm and its edge cases and resort to guessing and checking
loop and conditional conditions. I’d recommend doing the binary search
module, but also trying to build intuition around the algorithm. Be
cautious on relying too heavily on the templates given in the module,
they are good to get started, but trying to memorize the templates will
only lead to edge-case bugs that you will struggle to debug. It helps to
know whether your “middle index” formula is getting the lower-middle or
upper-middle (when there’s an even sized list) and then whether or not
your low and high moving will definitely converge instead of infinite
looping. Sometimes making it converge is as simple as using the
upper-middle instead of lower-middle, but it depends on how you’re
changing low and high. Overall, you must build an intuition rather than trying to memorize the algorithm. I might write a blog on this at some point.
Binary search trees: These, along with generic
binary trees (i.e. not sorted tree), seem to come up almost every week
in the weekly competition. Being able to quickly write a recursive
function to traverse the tree and get the information you need is
possibly the single biggest thing you can do to improve your competition
performance. They tend to be medium-level questions, but if you know
what you're doing, they are easy to do in under 5 minutes! Start with
the Binary Search Tree module, and then look for more questions on trees. Make sure to do lots of medium-level questions.
Tries and advanced string algorithms: Leetcode has a module on Tries for you to work through. As for other string algorithms, Google them or look in the CLRS algorithms book.
Interval trees: These are probably the most
advanced data structure you’ll see on a semi-regular basis. I’d
recommend trying to code one. Unfortunately, Leetcode doesn't have an
Explore module on them.
8. Learn the versatile algorithmic design techniques (Advanced)
This is the stage I’m currently at. It was working on these
techniques that has really driven my improved performance in the
competitions. They are not easy, and you’ll need to work and work and
work at them. You’ll need to start by practicing questions where you
already know which technique you’ll be using, and then on ones where you
don’t. The competitions are useful for that, as you don’t get to see
the tags until the end.
Bit manipulation: This isn’t that difficult once you get your head around it, and it’s also pretty fun. Leetcode has many questions on bit manipulation,
although no module for it at the time of writing. To get started,
Google a guide for your programming language of choice, then have a go
at some of the questions. Note that while it can be used standalone for
most of the easy and medium level questions, it tends to be an
optimization technique combined with other concepts in hard-level
questions.
Backtracking: This is a strategy that many advanced
recursive algorithms use, especially when coming up with solutions for
NP-Complete problems. Before I learned how to do backtracking correctly,
my exponential time algorithms would also use exponential space, with
lists and sets getting copied everywhere. I see many hard-level
questions that are straightforward with backtracking. Leetcode has a
section on it, tucked inside the Recursion 2 module.
Divide and conquer: This is another strategy that many advanced recursive algorithms use, in particular, those that run in O(n log(n))
time (quasilinear). Mergesort and Quicksort are the most well-known
examples of divide and conquer algorithms. Leetcode has a section on
them, also tucked inside the Recursion 2 module.
Dynamic programming: This may be the hardest
technique, and unfortunately I’m still looking for a good resource on
it. The CLRS algorithms book has some good content on it though, and
Leetcode has many awesome dynamic programming questions. Come on Leetcode, add an Explore module for this topic!
Memoization: This is an alternative to dynamic
programming that instead uses recursion. It tends to be easier to reason
about (for most people), so it might save you for the more challenging
dynamic programming problems. In saying that, your goal should
ultimately be to do as many questions as possible using dynamic
programming instead of memoization. Leetcode has on it, tucked inside
the Recusion 1 module.
Keep in mind too that there’s often more than one approach for a
question, and the tags aren’t always exhaustive. For example, the Smallest Sufficient Team problem
is tagged as two of these techniques, but also has really nice
solutions with one of the others. I’m being intentionally vague as I
don’t want to give spoilers.
9. Be aware of the intractable problems, particularly the NP-Complete ones.
A computer scientist’s idea of a practical joke is to give the
unsuspecting victim an NP-Complete problem to solve and watch them go
around in circles, possibly discovering what they think is a solution
and then discovering that it fails in some cases. Okay, maybe we’re not
that mean. But I have definitely heard of people in interviews trying to
come up with an efficient solution for a problem which is NP-Complete,
and if they DID find a good solution, they wouldn’t be needing the job
they’re interviewing for (as they’d be rich for it!). I have even heard
of companies trying to solve them, not realizing. Or apps that promise
to give you the shortest path between multiple stops.
So, know what they are. Wikipedia has some good lists of them.
Know what the best way to solve them is—sometimes it’s a brute force,
but with clever optimizations. Other problems have dynamic programming
solutions which are what we call pseudo-polynomial. The knapsack problem
is a good example of this. Sometimes an assumption you're allowed to
make (specified in the problem limits) will mean there's a
polynomial-time solution (or pseudo-polynomial).
10. Brush up on those math skills
If you feel a bit rusty in math, or you didn’t enjoy it in school, it
might be time to get out the grid paper and pencil. I did this last
year, and wrote a blog post on it.
Overall, it was a lot of fun, and it helped to improve my programming
and algorithm skills too. I could ramble about this topic for hours, but
we don’t have time for that, so here are some free resources I used and
recommend:
Khan Academy: I can’t
recommend this strongly enough. It covers all of primary (elementary)
and high school math in great depth, and it’s actually really fun. It’s
not just for school students, it’s equally awesome for adults. Sal has a
talent for explaining things and the quizzes and content are broken up
into manageable chunks. If you aren’t sure where your weaknesses are,
have a go at the initial quizzes. They’ll tell you where you have work
to do. Don’t be ashamed if you find there are a few primary school-level
concepts that you need to work on. It happened to me, and I was amazed
at how much addressing those weaknesses helped me with the more advanced
stuff. If you aren’t already confident with it, I especially recommend
the geometry stuff. The proofs and problem-solving there is a similar
kind of thinking to the thinking you’re trying to develop on Leetcode.
Introduction to Mathematical Thinking:
If you feel you possibly have some amount of math-PTSD from school,
Keith Devlin is the doctor for you. Keith’s mission is to enlighten the
general public on what it actually is mathematicians do (i.e. not
arithmetic and solving pages and pages of equations for y’s x). Aside
from that, the course goes over logic and proofs and aims to get you to
see the difference between school math and being a mathematician. It’s
helpful, especially if you aren’t keen on tackling the MIT OCW stuff
yet.
MIT OCW Mathematics for Computer science:
This is more advanced, but well worth tackling if it aligns with your
goals, i.e. being a top competitive programmer or getting into a top
tier tech company. If you did a degree in computer science, you probably
already did some discrete math. Unless you did discrete math beyond an
introduction at a top school though, then this course will be helpful as
there’ll almost certainly be stuff you didn’t know. At the very least,
it’s great revision. Note that you’ll need to put hours into doing ALL
of the “in class” questions to get the maximum benefit. We all learn
best from doing, and the questions are of high quality.
11. Be confident knowing the asymptotic complexity of an algorithm,
and don't write code until you know your algorithm will be good enough.
When given a question in an interview or a contest, don't dive into
writing code. The first thing you'll need to do is think and brainstorm
possible ways of solving it. For each one, you need to know how to
determine the asymptotic complexity, paying particular attention to the
worst cases. You'll then need to look at the problem limits and make a
judgement call as to whether or not your algorithm is likely to be fast
enough. Over time, you'll build a sense for how long things take. For
me, I start to worry when plugging the maximum value into the big-O
formula evaluates to over a million or so. It's a very crude
measurement, but it seems to serve me well.
Sometimes you'll need to come up with a better algorithm from
scratch. Sometimes, you can optimize a bad algorithm so that it's a lot
better. But you'll need to be fairly confident before you start coding,
otherwise you'll risk wasting time writing and debugging code, only to
get the dreaded Time Limit Exceeded error that can only be fixed with a
full re-design and re-write.
12. Read the problem limits well.
Often, you’ll be told what the maximum input sizes to expect are.
These will give you a lot of clues about the kind of algorithm you might
be writing. As a very rough rule of thumb:
If the limits are tiny, i.e. all under 50 or so, then your algorithm
will probably be non-polynomial (and this is a “smell” for intractable
problems).
If it’s under about 1000, then you might be looking at quadratic or around that.
If it’s over that, but under 1,000,000, then it’s probably linear or quasilinear.
Over that, and it’s quite possibly logarithmic. If it’s ridiculously
high (e.g. billions or trillions) like sometimes seen in the Google
Code Jam, that can be a sign of being able to shrink it with modular
arithmetic or even a constant time algorithm.
These aren’t certain rules, but they definitely give a good
indication. On the other hand, if your quadratic algorithm needs to run
on sizes of 2000 or more, it’s probably not going to pass. Usually, but
not always, quadratic algorithms can be replaced with quasilinear ones
taking a divide and conquer approach, or using binary search somehow.
13. Choose the best variable to scale up on.
Sometimes, what seems to be the main variable (e.g. number of items)
is quite high, but another variable is surprisingly lower. Going back to
one of my favourite questions -- Smallest Sufficient Team -- we are told this:
1 <= req_skills.length <= 16
1 <= people.length <= 60
1 <= people[i].length, req_skills[i].length, people[i][j].length <= 16
Elements of req_skills and people[i] are (respectively) distinct.
req_skills[i][j], people[i][j][k] are lowercase English letters.
It is guaranteed a sufficient team exists.
The interesting detail here is that the maximum number of required
skills is a lot lower than the maximum number of people. This is a big
clue. It suggests that the cost will primarily scale with the number of
skills required, not with the number of people. Instead of an approach
that considers including or not including each person, we should instead
be looking at a solution where the main looping is over the skill list.
This is common in Google Code Jam questions. It’s worth having a
really good look and think about the limits, especially if one seems
unusually low/ is a surprising constraint. It can often mean there’s a
good solution that wouldn’t have worked as well if it was bigger.
14. Share your solutions and teach others
It’s widely known that to master something, you have to teach it.
Writing up high-quality solutions and explanations on the discussion
forums is a great way of doing this. It will also help you develop other
software engineering skills, such as writing and explaining. Make sure
you post with the goal of helping others, and not showing off. Nobody likes a code dump with no comments or explanations.
Take pride in the code you share. Very few people like reading code
where all the variable names appear to have been taken from the lyrics
of the famous alphabet song.
When writing your post and the code to put in it, pretend potential
employers might be reading it. If you’re wanting to get into a top tech
company, then write the kind of code you’d be expected to write there.
For example, use descriptive variable names. During my Google
internship, I noticed this in the Google codebase and my partner James
also tells me that Canva’s codebase is the same. ABOVE ALL OTHER ADVICE, put 3 backticks before and 3 backticks after your code.
This will make it format nicely. It amazes me how many people don’t
know to do this/ don’t bother to find out how when their code looks
hideous and unreadable from the lack of it.
15. Practice general problem solving
When learning algorithms, data structures, and techniques, I
recommend you use the tags to find relevant problems. After all, your
goal is to master a specific skill.
But after that, you need to practice “problem solving”. This is where
you have a problem to solve, and you do not know which of your skills
you’ll be applying to it. To do this, the weekly contests and mock
interview feature are amazing.
Remember that sometimes a question will require a technique you've
never seen before, or will require a major adaptation to one. You'll
need to learn to be creative and think outside the box if this doesn't
come naturally to you, memorizing solutions will not help you. A great
example of this is questions such as Minimize Max Distance to Gas Station. There is a quasilinear solution using binary search. It's not at all what you might initially think.
16. Do the weekly contests
These are great fun, and a great chance to practice your general
problem solving, although they can be buggy as the questions are new to
the site. Cheating is also an issue, particularly in the form of people
hardcoding the answers to the largest test cases. This has reduced a lot
though since Leetcode stopped displaying the answer to test cases where
the result was Time Limit Exceeded. There are also issues with some
programming languages being faster than others. Sometimes, a poor
solution will slip through with C++ and Java, but not Python, for
example.
There is no rule against using previous code, although at the end of
the day, one needs to decide what their goal is. Using previous code is
not helping you learn. Most of the winners seem to be using previous
code, their goal is generally to accumulate Leetcoins so that they can
get their yearly subscription and a T-shirt (or so it seems)
It also takes a lot of practice. Over time, you’ll get better at it. I wasn’t getting in the top 200 at first, it took practice.
17. Use the mock interview feature
I have a Leetcode subscription, so in theory, I could do the
company-specific interviews. I actually never do though, I much prefer
the random sets. They seem to be taken from the company-specific ones,
with the difference being you don’t know which company it’s from. So
don’t worry about not having a subscription, you’ll still find this
feature useful.
As a general rule, the 3 levels (screening, phone interview, and
onsite) are more difficult than the last. So, start with the screening
ones and then move up from there. Unfortunately, Leetcode will sometimes
give you a mock interview you’ve seen previously, there’s not much you
can do about this. Once it seems to be happening a lot though, that
probably means you’ve done most of their mock interviews of that type.
Because there is a finite number of them, it's also best to not use them
until you've done some practice (i.e. mastered at least the basic and
intermediate skills I've listed above).
Fun question: If there are 25 mock interview problem sets, and each
has the same probability of appearing, around how many mock interviews
will you need to do to see them all? How many repetitions can you expect
to see?
In all seriousness, the mock interview feature is great for keeping
you focused (it’s timed!) and for forcing you to solve some problems
without seeing their tags. Remember what I said about practicing your
general problem solving?
18. Don’t spend all your time doing easy-level questions
I used to fall into this trap, I would do easy level questions,
trying to do them as fast as I could. Then I realized that was a big
waste of time, as it was the medium and hard level questions that I was
struggling on in the weekly competitions, not the easy ones. Getting the
easy ones solved quickly doesn’t mean much compared to getting the
points of the hard ones.
You need to do questions that are challenging, even if they take you
over an hour. This is how you’ll learn and improve. As you get better at
them, your speed will go up. Focus first on accuracy and skill, and
then secondly on speed. Remember that if you can at least get to the
point of answering all 4 competition questions in the 90 minutes
available, you're already doing better than most people.
19. Try to avoid writing bugs in the first place
We all know debugging sucks when you're timed and seeing those
precious minutes tick by. The best solution is to not write bugs in the
first place. By programming mindfully, with your full attention, you'll
be able to consciously ensure each line is doing what you want it to.
For particularly tricky lines of code, such as binary search
boundaries, make a quick example if you have to, and make sure your
code does what it's supposed to on it. Do this as you're writing the
algorithm, not at the end. If you don't remember the details of a
particular library function perfectly, quickly look it up, don't guess.
In an interview, tell your interviewer you can't remember. Most people
forget these things, and there's a chance they won't remember either.
They can tell you what assumption to make. Also, in competitions, it can
help to have a shell up with your chosen language if it's interpreted.
Sometimes I forget how particular things in Python work (especially when
it involves complex splicing) so being able to quickly type in an
example really helps!
Something else that helps me is writing code on paper first. I find
there are less bugs, as I can't handwrite as fast as I can type.
20. You must have fun!
You’ll burn out in no time if you don’t enjoy it. Don’t go about your
studying in a way that makes it feel like a torturous chore. Do what
you need to enjoy it.
And if you still just can’t enjoy it, then perhaps it isn’t for you, which is fine. We all have things we do and don’t enjoy. Feel free to leave any questions or further tips you might have in the comments!
We start from A, and following in-order traversal, we move to its left subtree B. B
is also traversed in-order. The process goes on until all the nodes are
visited. The output of inorder traversal of this tree will be −
We start from A, and following pre-order traversal, we first visit A itself and then move to its left subtree B. B
is also traversed pre-order. The process goes on until all the nodes
are visited. The output of pre-order traversal of this tree will be −
We start from A, and following Post-order traversal, we first visit the left subtree B. B
is also traversed post-order. The process goes on until all the nodes
are visited. The output of post-order traversal of this tree will be −