Skip to main content
Code Review

Return to Question

edited tags; edited tags
Link
200_success
200_success
  • 145.7k
  • 22
  • 191
  • 481
added 11 characters in body
Source Link
David says Reinstate Monica
David says Reinstate Monica
  • 411
  • 1
  • 5
  • 15
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

//Time Complexity: O(w + ws)
//Space Complexity: O(s)
//Where w is the number of words in the document, and s is the number of search terms
public class Solution {
    private Map<String, Integer> snippetDataPoints = new HashMap<String, Integer>();
    private String[] words, searchTerms;
    private int shortestSnippetStart = 0, shortestSnippetEnd, currentSnippetStart = 0;
    
    public static String solution(String document, String[] searchTerms) {
        AnswerSolution answersolution = new AnswerSolution (document.split(" "), searchTerms);//document.split isnt the most efficient, but we are already over O(n), and this keeps it simple
        return answersolution.solve();
    }
    
    private AnswerSolution(String[] words, String[] searchTerms){
        this.words = words;
        this.searchTerms = searchTerms;
        shortestSnippetEnd=words.length;
    }
    
    private String solve(){
        for(int i=0;i<words.length;i++){
            if(searchTermsContains(words[i])){
                addToSnippet(words[i], i);
            }
        }
        StringBuilder snippet = new StringBuilder();
        for(int i = shortestSnippetStart; i<=shortestSnippetEnd; i++){
            snippet.append(words[i] + " ");
        }
        snippet.deleteCharAt(snippet.length()-1);
        return snippet.toString();
    }

    private void addToSnippet(String word, int position) {
        Integer previousPosition = snippetDataPoints.put(word, position);
        if(previousPosition == null || previousPosition <= currentSnippetStart){
            currentSnippetStart = Collections.min(snippetDataPoints.values());
        }
        if(snippetDataPoints.size() == searchTerms.length){
            determineShortestSnippet(position);
        }
    }

    private void determineShortestSnippet(int currentPositionEnd) { 
        if(shortestSnippetEnd - shortestSnippetStart > currentPositionEnd - currentSnippetStart ){
            shortestSnippetStart = currentSnippetStart;
            shortestSnippetEnd = currentPositionEnd;
        }
    }

    private boolean searchTermsContains(String word) {
        for(String searchTerm : searchTerms){
            if(searchTerm.equals(word)) return true;
        }
        return false;
    }
}

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

//Time Complexity: O(w + ws)
//Space Complexity: O(s)
//Where w is the number of words in the document, and s is the number of search terms
public class Solution {
    private Map<String, Integer> snippetDataPoints = new HashMap<String, Integer>();
    private String[] words, searchTerms;
    private int shortestSnippetStart = 0, shortestSnippetEnd, currentSnippetStart = 0;
    
    public static String solution(String document, String[] searchTerms) {
        Answer answer = new Answer(document.split(" "), searchTerms);//document.split isnt the most efficient, but we are already over O(n), and this keeps it simple
        return answer.solve();
    }
    
    private Answer(String[] words, String[] searchTerms){
        this.words = words;
        this.searchTerms = searchTerms;
        shortestSnippetEnd=words.length;
    }
    
    private String solve(){
        for(int i=0;i<words.length;i++){
            if(searchTermsContains(words[i])){
                addToSnippet(words[i], i);
            }
        }
        StringBuilder snippet = new StringBuilder();
        for(int i = shortestSnippetStart; i<=shortestSnippetEnd; i++){
            snippet.append(words[i] + " ");
        }
        snippet.deleteCharAt(snippet.length()-1);
        return snippet.toString();
    }

    private void addToSnippet(String word, int position) {
        Integer previousPosition = snippetDataPoints.put(word, position);
        if(previousPosition == null || previousPosition <= currentSnippetStart){
            currentSnippetStart = Collections.min(snippetDataPoints.values());
        }
        if(snippetDataPoints.size() == searchTerms.length){
            determineShortestSnippet(position);
        }
    }

    private void determineShortestSnippet(int currentPositionEnd) { 
        if(shortestSnippetEnd - shortestSnippetStart > currentPositionEnd - currentSnippetStart ){
            shortestSnippetStart = currentSnippetStart;
            shortestSnippetEnd = currentPositionEnd;
        }
    }

    private boolean searchTermsContains(String word) {
        for(String searchTerm : searchTerms){
            if(searchTerm.equals(word)) return true;
        }
        return false;
    }
}

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

//Time Complexity: O(w + ws)
//Space Complexity: O(s)
//Where w is the number of words in the document, and s is the number of search terms
public class Solution {
    private Map<String, Integer> snippetDataPoints = new HashMap<String, Integer>();
    private String[] words, searchTerms;
    private int shortestSnippetStart = 0, shortestSnippetEnd, currentSnippetStart = 0;
    
    public static String solution(String document, String[] searchTerms) {
        Solution solution = new Solution (document.split(" "), searchTerms);//document.split isnt the most efficient, but we are already over O(n), and this keeps it simple
        return solution.solve();
    }
    
    private Solution(String[] words, String[] searchTerms){
        this.words = words;
        this.searchTerms = searchTerms;
        shortestSnippetEnd=words.length;
    }
    
    private String solve(){
        for(int i=0;i<words.length;i++){
            if(searchTermsContains(words[i])){
                addToSnippet(words[i], i);
            }
        }
        StringBuilder snippet = new StringBuilder();
        for(int i = shortestSnippetStart; i<=shortestSnippetEnd; i++){
            snippet.append(words[i] + " ");
        }
        snippet.deleteCharAt(snippet.length()-1);
        return snippet.toString();
    }

    private void addToSnippet(String word, int position) {
        Integer previousPosition = snippetDataPoints.put(word, position);
        if(previousPosition == null || previousPosition <= currentSnippetStart){
            currentSnippetStart = Collections.min(snippetDataPoints.values());
        }
        if(snippetDataPoints.size() == searchTerms.length){
            determineShortestSnippet(position);
        }
    }

    private void determineShortestSnippet(int currentPositionEnd) { 
        if(shortestSnippetEnd - shortestSnippetStart > currentPositionEnd - currentSnippetStart ){
            shortestSnippetStart = currentSnippetStart;
            shortestSnippetEnd = currentPositionEnd;
        }
    }

    private boolean searchTermsContains(String word) {
        for(String searchTerm : searchTerms){
            if(searchTerm.equals(word)) return true;
        }
        return false;
    }
}
Source Link
David says Reinstate Monica
David says Reinstate Monica
  • 411
  • 1
  • 5
  • 15

Finding the shortest substring containing keywords

Problem: Write a function that takes a String document and a String[] keywords and returns the smallest substring of document that contains all of the strings in keywords.

Notes:

  • document will contain at least 1 word
  • document will separate words by a single space
  • A word can only contain [a-z] and can appear multiple times in the document
  • keywords will be a distinct list of words
  • Matches must be perfect (ie bat and batman do not match)
  • If there are multiple shortest substrings, pick the first one
  • keywords can appear in the substring in any order
  • The substring length is counted in words, not characters
  • Must be written in Java 7 and provide a class called Solution with a method solution

Examples

Input:

document: "a b c d a"
keywords: ["a", "c", "d"]

Output: "c d a"

Input:

document: "world there hello hello where world"
keywords: ["hello", "world"]

Output: "world there hello"

My attempt:

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

//Time Complexity: O(w + ws)
//Space Complexity: O(s)
//Where w is the number of words in the document, and s is the number of search terms
public class Solution {
    private Map<String, Integer> snippetDataPoints = new HashMap<String, Integer>();
    private String[] words, searchTerms;
    private int shortestSnippetStart = 0, shortestSnippetEnd, currentSnippetStart = 0;
    
    public static String solution(String document, String[] searchTerms) {
        Answer answer = new Answer(document.split(" "), searchTerms);//document.split isnt the most efficient, but we are already over O(n), and this keeps it simple
        return answer.solve();
    }
    
    private Answer(String[] words, String[] searchTerms){
        this.words = words;
        this.searchTerms = searchTerms;
        shortestSnippetEnd=words.length;
    }
    
    private String solve(){
        for(int i=0;i<words.length;i++){
            if(searchTermsContains(words[i])){
                addToSnippet(words[i], i);
            }
        }
        StringBuilder snippet = new StringBuilder();
        for(int i = shortestSnippetStart; i<=shortestSnippetEnd; i++){
            snippet.append(words[i] + " ");
        }
        snippet.deleteCharAt(snippet.length()-1);
        return snippet.toString();
    }

    private void addToSnippet(String word, int position) {
        Integer previousPosition = snippetDataPoints.put(word, position);
        if(previousPosition == null || previousPosition <= currentSnippetStart){
            currentSnippetStart = Collections.min(snippetDataPoints.values());
        }
        if(snippetDataPoints.size() == searchTerms.length){
            determineShortestSnippet(position);
        }
    }

    private void determineShortestSnippet(int currentPositionEnd) { 
        if(shortestSnippetEnd - shortestSnippetStart > currentPositionEnd - currentSnippetStart ){
            shortestSnippetStart = currentSnippetStart;
            shortestSnippetEnd = currentPositionEnd;
        }
    }

    private boolean searchTermsContains(String word) {
        for(String searchTerm : searchTerms){
            if(searchTerm.equals(word)) return true;
        }
        return false;
    }
}

My Analysis: This was written with a time constraint, so it manages to keep simplicity without losing too much efficiency. The document.split() is unnecessary - I could have done the parsing on the fly, but it would have been more complicated. Similarly, I could have created a better implementation of searchTermsContains, perhaps using a tree of character nodes to minimize search time. However, it would be really great if I could significantly reduce the usage of searchTermsContains altogether since its adding a wsto my time complexity, but I cant think of anyway.

I also could have used a more efficient data structure for the snippetDataPoints. I think a parallel array would have worked just as well and used significantly less memory (though still technically O(s)?). And finally, a lot of my code runs under the assumption that all input is perfectly valid - something Im willing to accept given time constraints and the nature of the problem.