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);
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: