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

  • Two Sum - [Easy]
  • Longest Common Prefix - [Easy]
  • Longest Substring Without Repeating Characters - [Medium]
  • Conclusion
  • References

Two Sum - [Easy]

Problem description

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15] and target = 9 it should return  [0, 1]:
Because nums[0] + nums[1] = 2 + 7 = 9

Solution

The naive solution here is very straightforward: Loop through each element of nums, x and find if there is another value that equals to target - x.

def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    for ind1,el1 in enumerate(nums):
        el = target - el1
        for ind2,el2 in enumerate(nums):
            if el == el2 and ind1 != ind2:
                return [ind1,ind2]

Complexity Analysis

  • Time complexity: O(n^2). For each element, we try to find its complement by looping through the rest of array which takes O(n) time. Therefore, the time complexity is O(n^2).
  • Space complexity: O(1).

It turns out we can do it in one-pass. While we iterate through the list we insert elements into a dictionary, we also look back to check if current element's complement already exists in the dictionary. If it exists, we have found a solution and return immediately.

def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    d = {}
    for ind,el in enumerate(nums):
        if target-el not in d:
            d[el]=ind
        else:
            return [d[target-el],ind]

Complexity Analysis

  • Time complexity: O(n) we traverse the list containing n elements only once. Each look up in the dictionary costs only O(1) time.
  • Space complexity: O(n) the extra space required depends on the number of items stored in the dictionary, which stores at most n elements.

Longest Common Prefix - [Easy]

Problem description

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:
All given inputs are in lowercase letters a-z.

Solution

The naive solution here is very straightforward utilizing the built-in all() and startswith() functions. It first finds the shortest word in the input array, then it iterates each character of the shortest word to find out whether the character is common to the rest of words.

def longestCommonPrefix(strs):
    prefix = []
    if strs: 
        shortest_str = min(strs, key=len)
        for i,_ in enumerate(shortest_str):
            if all([x.startswith(shortest_str[:i+1]) for x in strs]):
                prefix = shortest_str[:i+1]
            else:
                break
    return ''.join(prefix)

A similar solution is the one below where we use enumerate and nested for loop to check each char for each word.

def longestCommonPrefix(strs):
    if strs: 
        shortest_str = min(strs, key=len)
        for i, char in enumerate(shortest_str):
            for other in strs:
                if other[i] != char:
                      return shortest_str[:i]
        return shortest_str
    return ""

Complexity Analysis

  • Time complexity:O(S) where S is the total number of characters for all words in the array
  • Space complexity: O(1).

Another solution is to use zip(*str) which returns a zip object where each tuple has characters with the corresponding index from each word.

def longestCommonPrefix(strs):
    """
    :type strs: List[str]
    :rtype: str
    """
    prefix=[]
    num = len(strs)
    for x in zip(*strs):
        """
        for strs = ["flower","flowe","flightowe"] 
        returns
        ('f', 'f', 'f')
        ('l', 'l', 'l')
        ('o', 'o', 'i')
        ('w', 'w', 'g')
        ('e', 'e', 'h')
        """
        if len(set(x)) == 1:
            prefix.append(x[0])
        else:
            break
    return "".join(prefix)

Complexity Analysis

  • Time complexity:O(S) where S is the total number of characters for all words in the array
  • Space complexity: O(1).

Longest Substring Without Repeating Characters - [Medium]

Problem description

Given a string, find the length of the longest substring without repeating characters.

Example 1:
Input: "abcabcbb"
Output: 3  
Explanation: The answer is "abc", with the length of 3.

Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.              

Solution

The naive solution is to check all the substring one by one to see if it has no duplicate character. In order to do that we use two nested loops with i from 0 to n and j from i+1 to n.

To check if one substring has duplicate characters, we use a list. As we iterate through all the characters in the substring we put them into the list one by one. Before putting one character, we check if the list already contains it. If so, we break out of the loop.

def lengthOfLongestSubstring(s):
    length = 0
    for ind1,el1 in enumerate(s):
    	p = []
    	for el2 in s[ind1:]:
    		if el2 not in p:
    			p.append(el2)
    		else:
    			break
    	if len(p) > length:length = len(p)
    return length

Complexity Analysis

  • Time complexity:O(n^2) as we use two nested loops and each look up in the list costs only O(1) time.
  • Space complexity: O(n).

The naive approach is very straightforward. But it is too slow. So how can we optimize it?

In the naive approaches, we repeatedly check a substring to see if it has duplicate character. But it is unnecessary and we can do better by using a sliding window.

A sliding window is an abstract concept commonly used in array/string problems. A window is a range of elements in the array/string which usually defined by the start and end indices. A sliding window is a window "slides" its two boundaries to the certain direction.

We use a string to store the characters in the current window.

def lengthOfLongestSubstring(s):
        ans = 0
        sub = ''
        for char in s:
            if char not in sub:
                sub += char
                ans = max(ans, len(sub))
            else:
                cut = sub.index(char)
                sub = sub[cut+1:] + char
        return ans

Complexity Analysis

  • Space complexity: O(min(m, n)) it is upper bounded by the size of the string n and the size of the charset/alphabet m.
  • Time complexity:O(n*k) as we use only one loop and each look up in the string costs time k.

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