Tag: Coding

Cracking the Coding Interview: Unscripted Interview Video Solutions

Anagram word search problem

import java.util.*;

class AnagramWordSearch {
	
	private static Set<String> dictionarySet;
	private static Map<String, Set<String>> anagramMap;
	
	static {
        //Not optimal to load every time would want to cache the anagramMap
		dictionarySet = loadDictionary();
		anagramMap = buildWordMatchMap();
	}
	
	public static Set<String> loadDictionary(){
		dictionarySet = new HashSet<>(Arrays.asList("may", "student","students","dog","studentssess","god", "cat", "act", "tab", "bat", "flow","wolf", "lambs","amy", "yam", "balms", "looped", "poodle"));
		return dictionarySet;
	}
	
	public static Map<String, Set<String>> buildWordMatchMap(){
		anagramMap = new HashMap<>();
		for (String dictionaryWord : dictionarySet){
			char[] chars = dictionaryWord.toCharArray();
			Arrays.sort(chars);
			String sortDictionaryWord = new String(chars);
			if (anagramMap.containsKey(sortDictionaryWord)){
				Set<String> existingWordMatch = anagramMap.get(sortDictionaryWord);
				existingWordMatch.add(dictionaryWord);
				anagramMap.put(sortDictionaryWord, existingWordMatch);
			} else {
				Set<String> newWordMatchSet = new HashSet<>(Arrays.asList(dictionaryWord));
				anagramMap.put(sortDictionaryWord, newWordMatchSet);
			}
		}
		return anagramMap;
	}
	
	public static Set<String> getWordsWithSameChars(String word){
		char[] wordChars = word.toCharArray();
		Arrays.sort(wordChars);
		String sortedWord = new String(wordChars);
		return anagramMap.get(sortedWord);
	}

	public static void main(String[] args) {
		Set<String> wordMatchSameChars = getWordsWithSameChars("cat"); 
		System.out.println(wordMatchSameChars); //cat, act
	}
}

Get derivative for Term

import java.util.*;

class Derivate {
	
	public static List<Term> getDerivative(List<Term> polynomials){
		List<Term> derivativeTerm = new ArrayList<>();
		for (Term polynomial : polynomials){
			int expVal = polynomial.getExponent();
			if (expVal>0){
				Term newTerm = new Term(polynomial.getCoefficient() * expVal, expVal-1);
				derivativeTerm.add(newTerm);
			}
		}
		return derivativeTerm;
	}
	
	public static void main(String[] args) {
		List<Term> terms = new ArrayList<>(Arrays.asList(new Term(3, 2), new Term(5, 1), new Term(9, 0)));
		System.out.println(getDerivative(terms)); //[{6, 1}, {5, 0}]
	}

    public static class Term {
		private int exponent;
		private int coefficient;
		
		public Term(int coefficient, int exponent){
			this.exponent = exponent;
			this.coefficient = coefficient;
		}
		
		public int getCoefficient(){
			return coefficient;
		}
		
		public void setCoefficient(int coefficient){
			this.coefficient = coefficient;
		}
		
		
		public int getExponent(){
			return exponent;
		}
		
		public void setExponent(int exponent){
			this.exponent = exponent;
		}
		
		public String toString(){
			return "{" + coefficient + ", " + exponent + "}";
		}
	}

}

Non Consecutive sequence with the largest sum

import java.util.*;

class HighestSumOfNonConsecutiveValues {
	
	public static Integer setOfConsecutiveElements(int[] intArr){
		
		Set<Integer> setOfValues = new HashSet<>();
		for (int k = 0; k < intArr.length;k++){
			setOfValues.add(intArr[k]);
		}
		
		Integer largestSum = 0;
		for (Integer setOfValue : setOfValues){
			Integer iteratorSum = setOfValue;
			for (Integer k = 1; k < setOfValues.size();k++){
				if (setOfValues.contains(setOfValue+k)){
					iteratorSum += (setOfValue+k);
				} else if ((setOfValues.contains(setOfValue-k))){
					iteratorSum += (setOfValue-k);
				} else {
					break;
				}
			}
			if (largestSum < iteratorSum){
				largestSum = iteratorSum;
			}
		}
		
		return largestSum;
	}
	
	public static void main(String[] args) {
		int[] arr = new int[]{1,3,5,6,12,11,62,7,101,102,41,37,2,52,2,31,5,69,71,32,33,7,100,11,4};
		System.out.println(setOfConsecutiveElements(arr)); //303 (100+101+102)
	} 
}

Ransome note

 public class Solution {

    private static final String YES = "Yes";
    private static final String NO = "No";

    static void checkMagazine(String[] magazine, String[] note) {
        Map<String, Integer> notesMap = new HashMap<>();
        for (String n : note){
            if (notesMap.containsKey(n)){
                Integer wordFreq = notesMap.get(n) + 1;
                notesMap.put(n, wordFreq);
            } else {
                notesMap.put(n, 1);
            }
        }

        for (String m : magazine){
            if (notesMap.containsKey(m)){
                Integer currentFreq = notesMap.get(m);
                if (1 < currentFreq){
                    currentFreq-=1;
                    notesMap.put(m, currentFreq);
                } else {
                    notesMap.remove(m);
                    if (notesMap.isEmpty()){
                        break;
                    }
                }
            } 
        }

        String foundAllWordsInMagazine = YES;
        if (!notesMap.isEmpty()){
            foundAllWordsInMagazine = NO;
        } 

        System.out.println(foundAllWordsInMagazine);
    }
}

Apex Coding Challenge Find Highest Frequency of Numbers

Problem: Find the number that has the highest frequency in a list of integers.

Input: 1,6,2,1,6,1

Output: 1 //because 1 occurs 3 times in the list

Option 1: Use Hashmap to iterate list

	List<Integer> nums = new List<Integer>{1,6,2,1,6,1};
		Map<Integer, Integer> numMap = new HashMap<>();
		for (Integer num : nums){
			if (numMap.containsKey(num)){
				Integer numFreq = numMap.get(num);
				numMap.put(num, numFreq+1);
			} else {
				numMap.put(num, 1);
			}
		}
		
		Integer biggestFreq = 0;
		Integer biggestVal = 0;
		for (Integer num : numMap.keySet()){
			if (numMap.get(num) > biggestFreq){
				biggestFreq = numMap.get(num);
				biggestVal = num;
			}
		}
		
		System.debug(biggestVal);

Option 2: Use wrapper class with compare to sort wrapper

List<Integer> nums = new List<Integer>{1,6,2,1,6,1};

Map<Integer, NumFrequencyWrapper> numMap = new HashMap<>();
for (Integer num : nums){
	if (numMap.containsKey(num)){
		NumFrequencyWrapper numFreqWrapper = numMap.get(num);
		numFreqWrapper.setFrequency(numFreqWrapper.getFrequency()+1);
		numMap.put(num, numFreqWrapper);
	} else {
		NumFrequencyWrapper numFrequencyWrapper = new NumFrequencyWrapper();
		numFrequencyWrapper.setNum(num);
		numFrequencyWrapper.setFrequency(1);
		numMap.put(num, numFrequencyWrapper);
	}
}
	
List<NumFrequencyWrapper> frequencyWrapperList = new List(numMap.values());
Collections.sort(frequencyWrapperList, new Untitled.NumFrequencyWrapperCompare());
System.debug(frequencyWrapperList.get(0).getNum());

public class NumFrequencyWrapper {
	private Integer num;
	private Integer frequency;
	
	public void setNum(Integer num){
		this.num = num;
	}
	
	public Integer getNum(){
		return num;
	}
	
	public void setFrequency(Integer frequency){
		this.frequency = frequency;
	}
	
	public Integer getFrequency(){
		return this.frequency;
	}
}
	
public class NumFrequencyWrapperCompare implements Comparator<NumFrequencyWrapper>{
	public int compare(NumFrequencyWrapper a, NumFrequencyWrapper b) { 
		return  b.getFrequency() - a.getFrequency(); 
	} 
}

Option 3: Using buckets to group index of frequencies together

List<Integer> nums = new List<Integer>{1,6,2,1,6,1};
Integer returnNums = 2;
Map<Integer, Integer> numMap = new Map<Integer, Integer>();
for (Integer num : nums){
	if (numMap.containsKey(num)){
		Integer numFreq = numMap.get(num);
		numMap.put(num, numFreq+1);
	} else {
		numMap.put(num, 1);
	}
}

Map<Integer, List<Integer>> mapOfBucketWithValues = new Map<Integer, List<Integer>>();
for (Integer num : numMap.keySet()){
	Integer numFrequency = numMap.get(num);
	if (mapOfBucketWithValues.containsKey(numFrequency)){
		List<Integer> existingIndexNum = mapOfBucketWithValues.get(numFrequency);
		existingIndexNum.add(num);
		mapOfBucketWithValues.put(numFrequency, existingIndexNum);
	} else {
		List<Integer> numList = new ArrayList<>();
		numList.add(num);
		mapOfBucketWithValues.put(numFrequency, numList);
	}
}

for (Integer k=nums.size(), returnedNums=0; 1<=k; k--){
	if (mapOfBucketWithValues.containsKey(k)){
		for (Integer numBucket : mapOfBucketWithValues.get(k)){
			if (returnedNums < returnNums){
				System.debug(numBucket);
				returnedNums++;
			}
		}
	}	
}