Thys Michels Blog

Apex Coding Interview Challenge #10

Posted on July 6, 2020     Leave a Comment

Given a string of round, curly, and square open and closing brackets, return whether the brackets are balanced (well-formed).

For example, given the string “([])[]({})”, you should return true.

Given the string “([)]” or “((()”, you should return false.

There is are Stack implementation currently available in Apex so we can use a List to push and pop characters

Solution

public class Stack {
    private List<Object> items {get; set;}
    
    public Stack() {
        this.items = new List<Object>();
    }
    
    public Integer size() {
        return this.items.size();
    }

    public Boolean isEmpty() {
        return size() == 0;
    }
        
    public void push(Object itemToPush) {
        this.items.add(itemToPush);
    }
    
    public Object pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        
        return this.items.remove(size() - 1);
    }
    
    public Object peek() {
        if (isEmpty()) {
            throw new EmptyStackException('Stack is empty');
        }
        
        return this.items.get(size() - 1);
    }    
}

public class EmptyStackException extends Exception {}

public static Map<String, String> mapBrackets(){
    Map<String, String> bracketMap = new Map<String, String>();
    bracketMap.put('}', '{');
    bracketMap.put(')', '(');
    bracketMap.put(']', '[');
    return bracketMap;
}

public static Boolean checkClosingBrackets(String bracketStr) {
    Map<String, String> bracketMap = mapBrackets();
    Stack customStack = new Stack();
    
    for (Integer i=0; i < bracketStr.length(); i++){
        String str = bracketStr.substring(i,i+1);
        System.debug('> ' + str);
        if (!bracketMap.containsKey(str)){
            customStack.push((String)str);
        } else {
            String pop = (String)customStack.pop();
            String mappedVal = bracketMap.get(str);
            
            if (!mappedVal.equals(pop)){
                return false;
            }
        }
    }
    
    if (!customStack.isEmpty()){
        return false;
    }
    
    return true;
}

Testing

System.debug(checkClosingBrackets('([])[]({})')); //true
System.debug(checkClosingBrackets('([])[]({}'));  //false

Apex Coding Interview Challenge #9

Posted on July 6, 2020     Leave a Comment

Given a list of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative.

For example, [2, 4, 6, 2, 5] should return 13, since we pick 2, 6, and 5. [5, 1, 1, 5] should return 10, since we pick 5 and 5.

Follow-up: Can you do this in O(N) time and constant space?

Solution

public Integer sumLargestNonAdjacentNumbers(List<Integer> lstNumbers){
      Integer exclusive = 0;
      Integer inclusive = lstNumbers.get(0);
      for (Integer i = 1; i < lstNumbers.size(); i++) {
        Integer temp = inclusive;
        inclusive = Math.max(exclusive + lstNumbers.get(i), inclusive);
        exclusive = temp;
      }
      return inclusive;
}

Testing

System.debug(sumLargestNonAdjacentNumbers(new List<Integer>{5, 1, 1, 5})); //10

System.debug(sumLargestNonAdjacentNumbers(new List<Integer>{2, 4, 6, 2, 5})); //13

Complexity Analysis
Time complexity: O(n)
Space complexity: O(1)

Apex Coding Interview Challenge #8

Posted on June 29, 2020     2 Comments

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

public Map<String, List<String>> mapOfDictionary(List<String> wordsLst){
    Map<String, List<String>> dictionaryMap = new Map<String, List<String>>();
    
    for (String w : wordsLst){
        List<String> wordChars = new List<String>(w.split(''));
        String concatChars = '';
        for (String wordChar : wordChars){
            concatChars += wordChar;
            if (dictionaryMap.containsKey(concatChars)){
                List<String> wordsForChars = dictionaryMap.get(concatChars);
                wordsForChars.add(w);
                dictionaryMap.put(concatChars, wordsForChars);
            } else {
                dictionaryMap.put(concatChars, new List<String>{w});
            }
        }   
    }
   
    return dictionaryMap;
}

public List<String> getWordsForAutoComplete(String word){
    Map<String, List<String>> dictionaryMap = mapOfDictionary(new List<String>{'dog', 'deer', 'deal'});
    return dictionaryMap.get(word);
}

Testing

System.debug(getWordsForAutoComplete('de')); //(deer, deal)

Complexity Analysis
Time complexity: O(n^2)
Space complexity:  O(m*n) //m – max length of string, n – amount of words

Apex Coding Interview Challenge #7

Posted on June 25, 2020     Leave a Comment

Given an array 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 array. The array 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

public Integer lowestIntMissingFromLst(List<Integer> intVals){
  Integer missingNum = 0;
  Integer maxVal = 0;
  Integer maxMin = 0;
  Integer maxMax = 0;
  for (Integer k = 0; k < intVals.size(); k++){
      if (k == 0){
          maxVal = intVals.get(k);
      } else if (maxVal < intVals.get(k)){
          maxVal =  intVals.get(k);
          maxMin = intVals.get(k) - intVals.size();
          maxMax = intVals.get(k) + intVals.size();
      }
      
      Integer plusOne = intVals.get(k)+1;
      Integer minusOne = intVals.get(k)-1;
      
      if (plusOne < maxMax && !intVals.contains(plusOne)){
          missingNum = plusOne;
      } else if (minusOne < maxMin && !intVals.contains(minusOne)){
          missingNum = minusOne;
      }
  }
  return missingNum;
}

Test

System.debug(lowestIntMissingFromLst(new List<Integer>{3, 4, -1, 1})); //2

System.debug(lowestIntMissingFromLst(new List<Integer>{1, 2, 0})); //3

Complexity Analysis
Time complexity: O(n)
Space complexity: O(1)

Apex Coding Interview Challenge #6

Posted on June 24, 2020     Leave a Comment

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

Solution

public List<Integer> productOfNumbers(List<Integer> intVals){
   List<Integer> productLst = new List<Integer>();
   for (Integer k = 0; k < intVals.size(); k++){
     Integer sumOfVals = 1; // it's 1 because multiplying by 0 will always be 0
     for (Integer j = 0; j < intVals.size(); j++){
      if (j != k){
        sumOfVals *= intVals.get(j);
      }
     }
    productLst.add(sumOfVals);
   }
  return productLst;
}

Test

System.debug(productOfNumbers(new List<Integer>{1, 2, 3, 4, 5})); //(120, 60, 40, 30, 24)

System.debug(productOfNumbers(new List<Integer>{3, 2, 1})); //(2, 3, 6)

Complexity Analysis
Time complexity: O(n2)
Space complexity: O(n)