getting started

Introduction

This section dives deep into practical tips for specific topics of algorithms and data structures which appear frequently in coding questions. Many algorithm questions involve techniques that can be applied to questions of similar nature. The more techniques you have in your arsenal, the higher the chances of passing the interview. They may lead you to discover corner cases you might have missed out or even lead you towards the optimal approach!

For each topic, study links are recommended to help you master the topic. There is a list of recommended common questions to practice which in my opinion is highly valuable for mastering the core concepts for the topic.

General tips:

Clarify any assumptions you made subconsciously. Many questions are under-specified on purpose.

Always validate input first. Check for invalid/empty/negative/different type input. Never assume you are given the valid parameters. Alternatively, clarify with the interviewer whether you can assume valid input (usually yes), which can save you time from writing code that does input validation.

Are there any time/space complexity requirements/constraints?

Check for off-by-one errors.

In languages where there are no automatic type coercion, check that concatenation of values are of the same type: int/str/list.

After finishing your code, use a few example inputs to test your solution.

Is the algorithm meant to be run multiple times, for example in a web server? If yes, the input is likely to be preprocess-able to improve the efficiency in each call.

Use a mix of functional and imperative programming paradigms:
  • Write pure functions as much as possible.
  • Pure functions are easier to reason about and can help to reduce bugs in your implementation.
  • Avoid mutating the parameters passed into your function especially if they are passed by reference unless you are sure of what you are doing.
  • However, functional programming is usually expensive in terms of space complexity because of non-mutation and the repeated allocation of new objects. On the other hand, imperative code is faster because you operate on existing objects. Hence you will need to achieve a balance between accuracy vs efficiency, by using the right amount of functional and imperative code where appropriate.
  • Avoid relying on and mutating global variables. Global variables introduce state.
  • If you have to rely on global variables, make sure that you do not mutate it by accident.

Generally, to improve the speed of a program, we can either: (1) choose a more appropriate data structure/algorithm; or (2) use more memory. The latter demonstrates a classic space vs. time tradeoff, but it is not necessarily the case that you can only achieve better speed at the expense of space. Also, note that there is often a theoretical limit to how fast your program can run (in terms of time complexity). For instance, a question that requires you to find the smallest/largest element in an unsorted array cannot run faster than O(N).

Data structures are your weapons. Choosing the right weapon for the right battle is the key to victory. Be very familiar about the strengths of each data structure and the time complexities for its various operations.

Data structures can be augmented to achieve efficient time complexities across different operations. For example, a hash map can be used together with a doubly-linked list to achieve O(1) time complexity for both the get and put operation in an LRU cache.

Hashmaps are probably the most commonly used data structure for algorithm questions. If you are stuck on a question, your last resort can be to enumerate through the common possible data structures (thankfully there aren't that many of them) and consider whether each of them can be applied to the problem. This has worked for me sometimes.

If you are cutting corners in your code, state that out loud to your interviewer and say what you would do in a non-interview setting (no time constraints). E.g., I would write a regex to parse this string rather than using split() which may not cover all cases.

References:

Arrays

Notes:

Is the array sorted or partially sorted? If it is, some form of binary search should be possible. This also usually means that the interviewer is looking for a solution that is faster than O(n).

Can you sort the array? Sometimes sorting the array first may significantly simplify the problem. Make sure that the order of array elements do not need to be preserved before attempting a sort.

For questions where summation or multiplication of a subarray is involved, pre-computation using hashing or a prefix/suffix sum/product might be useful.

If you are given a sequence and the interviewer asks for O(1) space, it might be possible to use the array itself as a hash table. For example, if the array only has values from 1 to N, where N is the length of the array, negate the value at that index (minus one) to indicate presence of that number.

Arrays are sequences:

Are there duplicate values in the array, would it affect the answer?

When using an index to iterate through array elements, be careful not to go out of bounds.

Be mindful about slicing or concatenating arrays in your code. Typically, slicing and concatenating arrays require O(n) time. Use start and end indices to demarcate a subarray/range where possible.

Sometimes you can traverse the array from the right rather than from the left.

Master the sliding window technique that applies to many subarray problems.

When you are given two arrays to process, it is common to have one index per array (pointer) to traverse/compare the both of them. For example, we use the same approach to merge two sorted arrays.

Corner Cases:

Recommended Leetcode Questions:

Additional Resources

  • 10-line template that can solve most 'substring' problems

    • Bit Manipulation

    Notes:

    Questions involving binary representations and bitwise operations are asked sometimes and you must be absolutely familiar with how to convert a number from decimal form into binary form (and vice versa) in your chosen programming language.

    Some helpful utility snippets:

    Corner Cases:

    Recommended Leetcode Questions:

    Study Links

    Theming

    Zeva Theming helps you Customize Zeva for changing the overall look of your Project.

    Light Theme

                        <body class="body-light">

    Custom Theme

                        <body class="body --bg-{your background color here} --text-{your main text color here}">
    Referece to Usage for using Theming

    Responsive

    Include this <meta> tag inside <head> before stylesheet link to ensure proper rendering and touch zooming for all devices.

    <meta name="viewport" content="width=device-width, initial-scale=1.0">

    Usage

    CDN Usage

    Include the stylesheet <link> inside <head>, same for other cdn links too

    <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/zeva-ui/zeva/dist/css/index.min.css">

    Zip Usage: CSS files

    • Unzip the files
    • Go to dist/css/
    • Import/Copy either the regular or minified CSS file to your working directory

    <link rel="stylesheet" href="zeva.css">

    Zip Usage: JS file

    • Unzip the files
    • Go to dist/js/
    • Import/Copy the minified js file to your working directory

    <script type="text/javascript" src="index.min.js"></script>

    Theming Usage

    Include the script <script> tag after all the content inside <body>

    <script type="text/javascript" src="https://cdn.jsdelivr.net/gh/zeva-ui/zeva/dist/js/index.min.js"></script>

    Include this for using icons

    Icons provided by fontawesome

    <link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.7.2/css/all.css" integrity="sha384-fnmOCqbTlWIlj8LyTjo7mOUStjsKC4pOpQbqyi7RrhN7udi9RwhKkMHpvLbHG9Sr" crossorigin="anonymous">