A great way to improve your coding skills is by solving coding challenges. Solving different types of challenges and puzzles can help you become a better problem solver, learn the intricacies of a programming language, prepare for job interviews, learn new algorithms, and more.

This post, listed some recent interview coding problems asked by top companies like Google, Amazon, Uber, Facebook, Twitter etc.  Note that Python is the programming language used to solve the below coding challenges.

This post is the second article of the Interview Coding Problems series. You can find the rest of the posts here:

https://gdcoder.com/interview-coding-problems/


Table of Contents

  • First Challenge
  • Second Challenge
  • Third Challenge
  • Conclusion
  • References
Photo by José Alejandro Cuffia / Unsplash

First Challenge - [Hard]

Problem description

Given a list of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the list. The list can contain duplicates and negative numbers as well.

For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3.

Solution

Our lives would be easier without the linear time constraint: we would just sort the list, while filtering out negative numbers, and iterate over the sorted list and return the first number that doesn't match the index.

def min_int(l):
    pos_l = [item for item in l if item > 0]
    pos_l.sort()
    if pos_l == []:
        return 1
    for i in range(len(pos_l)):
        if i+1 != pos_l[i]:
            return i+1
    return i+2

However, sorting takes O(n log n), so we can't use that here as you need to get it running in linear time.

Another way we can do this is by adding all the numbers to a set, and then use a counter initialised to 1. Then continuously increment the counter and check whether the value is in the set.

def min_int(l):
    s = set(l)
    i = 1
    while i in s:
        i += 1
    return i

This is much simpler, but runs in O(N) time and space.

Clearly we have to use some sort of trick here to get it running in linear time. Since the first missing positive number must be between 1 and len(array) + 1 (why?), we can ignore any negative numbers and numbers bigger than len(array). The basic idea is to use the indices of the array itself to reorder the elements to where they should be. We traverse the array and swap elements between 0 and the length of the array to their value's index. We stay at each index until we find that index's value and keep on swapping.

By the end of this process, all the first positive numbers should be grouped in order at the beginning of the array. We don't care about the others. This only takes O(N) time with zero space complexity, since we swap each element at most once.

Then we can iterate through the array and return the index of the first number that doesn't match.

def first_missing_positive(l):
    if not l:
        return 1
    for i in range(len(l)):
        while i + 1 != l[i] and 0 < l[i] <= len(l):
            v = l[i]
            l[i], l[v - 1] = l[v - 1], l[i]
            if l[i] == l[v - 1]:
                break
    for i in range(len(l)):
        if l[i] != i+1:
            return i+1
    return len(l) + 1

Second Challenge - [Medium]

Problem description

cons(a, b) constructs a pair, and car(pair) and cdr(pair) returns the first and last element of that pair. For example, car(cons(3, 4)) returns 3, and cdr(cons(3, 4)) returns 4.

Given this implementation of cons:

def cons(a, b):
    def pair(f):
        return f(a, b)
    return pair

Implement car and cdr.

Solution

This is a really cool example of using closures to store data. We must look at the signature type of cons to retrieve its first and last elements. cons takes in a and b, and returns a new anonymous function, which itself takes in f, and calls f with a and b.

Indeed, when running cons(3,4) we get back a function as displayed below:

So the input to car and cdr is that anonymous function, which is pair. To get a and b back, we must feed it yet another function, one that takes in two parameters and returns the first (if car) or last (if cdr) one.

def car(pair):
    return pair(lambda a, b: a) # another alternative would be to feed min or max

def cdr(pair):
    return pair(lambda a, b: b) # another alternative would be to feed min or ma

Third Challenge - [Medium]

Problem description

Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded.

For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'.

You can assume that the messages are decodable and that the given data string has only digits between 0 and 9 . For example, '001' is not allowed.

Solution

This looks like a problem that is ripe for solving with recursion. First, let's try to think of a recurrence we can use for this problem. We can try some cases:

  • "3" should return 1, since we can parse it only as "c".
  • "", the empty string and our base case, should return 1.

So what if you've been given more complex inputs for example:

Let's decode "12345" from left to right sequentially. Immediately we understand that they exist two choices:

  • Decode the first digit "1" and then the remaining string "2345" or
  • Decode the first two digits "12" and then the remaining string "345"

So decode("12345") is equivalent of decoding decode("2345")+decode("345").So,

decode("12345") = decode("2345") + decode("345")

In other words,  the number of ways of decoding the message "12345" is equal to the sum of the number of ways we can decode "2345" and the number of ways we can decode "345".

However, when decoding "27345" using the same methodology we notice a different behaviour:

  • Decode the first digit "2" and then the remaining string "7345" or
  • Decode the first two digits "27" and.. but wait a minute this is not possible as the last letter z maps to 26.

Thus, the number of ways of decoding the message "27345" is equal only to the sum of the number of ways we can decode "7345".

decode("27345") = decode("7345")

Finally, decoding "011" should return 0, since no letter starts with 0 in our mapping.  "602" should also return 0 for similar reasons.

We have a good starting point. We can see that the recursive structure is as follows:

  • If string starts with zero, then there's no valid encoding.
  • If the string's length is less than or equal to 1, there is only 1 encoding.
  • If the first two digits form a number k that is less than or equal to 26, we can recursively count the number of encodings assuming we pick k as a letter.
  • We can also pick the first digit as a letter and count the number of encodings with this assumption.
def num_ways(s):
    if s.startswith('0'):
        return 0
    elif len(s)<=1:
        return 1
    result = num_ways(s[1:])
    if int(s[:2]) <= 26:
        result += num_ways(s[2:])
    return result

num_ways(s)

However, this solution is not very efficient. Every branch calls itself recursively twice, so our runtime is O(2n).  But let's see that with an example:

Let's decode the string "111111":

decode("111111") = (decode("1") + decode("11111")) + (decode("11")+decode("1111"))

However:

  • decode("11111")=(decode("1") + decode("1111")) + (decode("11")+decode("111"))
  • decode("1111")=(decode("1") + decode("111")) + (decode("11")+decode("11"))

Obviously, this is not the most efficient approach because we repeat some of the computations over and over again.

We can do better by using dynamic programming and memoization.

"Memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again."

All the following code does is repeat the same computation as above except now we store the computation in a list whose length is the original string length plus one (initialising it with Null values) starting from the base case and building up the solution. We now passing this list as argument. Since each iteration takes O(1), the whole algorithm now takes O(n).

def num_ways(s,memo):
    if s.startswith('0'):
        return 0
    elif len(s)<=1:
        return 1
    if memo[len(s)] != None:
        return memo[len(s)]
    result = num_ways(s[1:],memo)
    if int(s[:2]) <= 26:
        result += num_ways(s[2:],memo)
    memo[len(s)]=result
    return result

num_ways(s,[None]*(len(s)+1))

Please see below difference in their performance.

Conclusion

Hope you find it interesting and please remember that a great way to improve your coding skills is by solving coding challenges.

Thanks for reading and I am looking forward to hearing your questions :)
Stay tuned and Happy Coding.


References