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

  • Implement Trie (Prefix Tree)
  • Longest Substring with At Most K Distinct Characters
  • 3Sum
  • Conclusion
  • References
London
Photo by Eva Dang / Unsplash

Implement Trie (Prefix Tree) - [Easy]

Problem description

Implement an autocomplete system. That is, given a query string s and a set of all possible query strings, return all strings in the set that have s as a prefix.

For example, given the query string de and the set of strings [dog, deer, deal], return [deer, deal].

Hint: Try preprocessing the dictionary into a more efficient data structure to speed up queries.

Solution

The naive solution here is very straightforward: we need to only iterate over the dictionary and check if each word starts with our prefix. If it does, then add it to our set of results and then return it once we're done.

def match_prefix(s,l):
    results = set()
    l = set(l)
    for word in l:
        if word.startswith(s):
            results.add(word)
    return results

s = 'de'
l = ['dog', 'deer', 'deal']
match_prefix(s,l)

This runs in O(N) time, where N is the number of words in the dictionary. Let's think about making this more efficient. We can preprocess the words, but what data structure would be best for our problem?

If we pre-sort the list, we could use binary search to find the first word that includes our prefix and then the last, and return everything in between.

Alternatively, we could use a tree for this. Not a binary tree, but a tree where each child represents one character of the alphabet. For example, let's say we had the words 'a' and 'dog' in our dictionary. Then the tree would look like this:

  x
 / \
a   d
     \
      o
       \
        g

Then, to find all words beginning with 'do', we could start at the root, go into the 'd' child, and then the 'o', child, and gather up all the words under there. We would also some sort of terminal value to mark whether or not 'do' is actually a word in our dictionary or not. This data structure is known as a trie.

So the idea is to preprocess the dictionary into this tree, and then when we search for a prefix, go into the trie and get all the words under that prefix node and return those. While the worst-case runtime would still be O(n) if all the search results have that prefix, if the words are uniformly distributed across the alphabet, it should be much faster on average since we no longer have to evaluate words that don't start with our prefix.

Before presenting the solution let's revise what trie is by showing an image and also giving the definition. Remember also that the nice feature from your mobile keyboard, where you start typing a word and it starts showing you suggestions is due to trie.

How on earth, do you think, computer (yes! your smart-phone is also a computer) figures out these suggestions?

"Trie is an efficient information retrieval data structure using which search complexities can be brought to an optimal limit." It was created as a compromise between running time and space — two things that we’re pretty familiar with in the context of Big O notation.

So, the code would look like:

class Trie():
    
    def __init__(self):
        self._trie = {} 
    
    def insert(self,word):
        trie = self._trie
        for char in word:
            if char not in trie:
                trie[char] = {}
            trie = trie[char]
        trie['*'] = True
    
    def elements(self,prefix):
        trie = self._trie
        for char in prefix:
            if char in trie:
                trie = trie[char]
            else:
                return []
        return self._element(trie)
    
    def _element(self,b):
        results = []
        for s,v in b.items():
            if s == '*':
                subresult = ['']
            else:
                subresult = [s + k for k in self._element(v)]
            results.append(subresult[0])
        return results
            
    

s = 'de'
words = ['dog', 'deer', 'deal']
trie = Trie()
for word in words:
    trie.insert(word)

def match_prefix(s):
    suffixes = trie.elements(s)
    return [s + w for w in suffixes]
match_prefix(s)

Longest Substring with At Most K Distinct Characters - [Hard]

Problem description

Given an integer k and a string s, find the length of the longest substring that contains at most k distinct characters.

For example, given s = "abcba" and k = 2, the longest substring with k distinct characters is "bcb".

Solution

The most obvious brute force solution here is to simply try every possible substring of the string and check whether it contains at most k distinct characters. If it does and it is greater than the current longest valid substring, then update the current one. This takes O(n2 * k) time, since we use n2 to generate each possible substring, and then take k to check each character.

def longest_substring_with_k_distinct_characters(s, k):
    current_longest_substring = ''
    for i in range(len(s)):
        for j in range(i + 1, len(s) + 1):
            substring = s[i:j]
            if len(set(substring)) > k:
                break
            if len(substring) > len(current_longest_substring):
                current_longest_substring = substring
    return len(current_longest_substring)

s = "abcba" 
k = 2
longest_substring_with_k_distinct_characters(s, k)

We can improve this by instead of keeping a running window of our longest substring. We'll keep a dictionary that maps characters to the index of their last occurrence. Then, as we iterate over the string, we'll check the size of the dictionary. If it's larger than k, then it means our window is too big, so we have to pop the smallest item in the dictionary and recompute the bounds. If, when we add a character to the dictionary and it doesn't go over k, then we're safe -- the dictionary hasn't been filled up yet or it's a character we've seen before.

def longest_substring_with_k_distinct_characters(s, k):
    if k == 0:
        return 0

    # Keep a running window
    bounds = (0, 0)
    h = {}
    max_length = 0
    for i, char in enumerate(s):
        h[char] = i
        if len(h) <= k:
            new_lower_bound = bounds[0] # lower bound remains the same
        else:
            # otherwise, pop last occurring char
            key_to_pop = min(h, key=h.get)
            new_lower_bound = h.pop(key_to_pop) + 1

        bounds = (new_lower_bound, bounds[1] + 1)
        max_length = max(max_length, bounds[1] - bounds[0])

    return max_length

s = "abcba" 
k = 2
longest_substring_with_k_distinct_characters(s, k)

This takes O(n * k) time and O(k) space.

3Sum - [Medium]

Problem description

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Solution

The naive approach is that run three loops and check one by one that sum of three elements is zero or not if the sum of three elements is zero then print elements otherwise print not found.

def threeSum(nums):
    result = []
    for i in range(0,len(nums)):
        for j in range(i+1,len(nums)):
            for k in range(j+1,len(nums)):
                cand = [nums[i], nums[j], nums[k]]
                cand.sort()
                if (sum(cand) == 0) & (cand not in result) :
                    result.append(cand)
    return result
nums = [-1, 0, 1, 2, -1, -4]
threeSum(nums)

This takes O(n3) time. We can improve this by iterating through every element. For every element arr[i], we find a pair with sum “-arr[i]”. This problem reduces to pairs sum and can be solved in O(n2) time.

def threeSum(nums):
    nums =sorted(nums)# O(nlogn)
    result = []
    for i in range(len(nums)):
        target = - nums[i]
        k,j = i+1,len(nums)-1
        while k < j:
            if nums[k]+nums[j] < target:
                k+=1
            elif nums[k]+nums[j] > target:
                j-=1
            else:
                cand = [nums[i], nums[j], nums[k]]
                cand.sort()
                if cand not in result:
                    result.append(cand)
                k+=1
                j-=1
    return result

nums = [-1, 0, 1, 2, -1, -4]
threeSum(nums)

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