Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Problem Challenge 4: Words Concatenation (hard)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

Actually solution provided in the course with O(NML) is not amazing. This problem can be solved effectively in O(NL).

A

Anonymous

· 2 years ago

class Solution:
    def findWordConcatenation(self, text, words):
        result_indices = []  # List to store the starting indices of valid substrings
        word_len = len(words[0])  # Length of each word
        total_words = len(words)  # Total number of words
        word_freq = {}  # Hashmap to store word frequencies

        # Initialize word frequency hashmap
        for word in words:
            word_freq[word] = word_freq.get(word, 0) + 1

        # Slide the window through the text
        for i in range(len(text) - total_words * word_len + 1):
            curr_window = text[i:i + total_words * word_len]  # Current substring
            curr_word_count = {}  # Hashmap to store word frequencies in the current window

            # Count word frequencies in the cur
A

Anonymous

· 4 years ago

What is the pattern for longest palindromic substring?

A

Anonymous

· 4 years ago

public static List wordConcatenation(String inputString, String [] wordsList) { List resultIndices = new ArrayList(); Map givenWordsMap = new HashMap(); int noOfWords = wordsList.length; int wordLength = wordsList[0].length(); int resultStringLength = wordLength * noOfWords; for(String s : wordsList) givenWordsMap.put(s, givenWordsMap.getOrDefault(s, 0) + 1); for(int i = 0; i < wordLength; i++) { Map foundWordsMap = new HashMap(); int leftWindow = i; int matchCount = 0; for(int rightWindow = leftWindow; rightWindow

Show 1 reply
A

Anonymous

· 4 years ago

does anyone know what the OR 0 means in the JS code?

if (wordsSeen[word] > (wordFrequency[word] || 0)) {

thanks in advance!

Show 1 reply
A

Anonymous

· 5 years ago

The solution is not Sliding Window. For example, this is equivalent to Solution 1 in the equivalent Leetcode problem. Rather we should look to implement Solution 2 which is a true Sliding Window solution and has much better runtime. O(M + N*Len) as opposed to O(N * M * Len) https://leetcode.com/problems/substring-with-concatenation-of-all-words/solution/

A

Anonymous

· 5 years ago

This needs a code comment on the first loop's signature.

Show 4 replies
A

Anonymous

· 5 years ago

I'm wondering why the time complexity is O(N * M * Len) and not O(N * M)?

Show 1 reply

Reading Progress

0%

Vote for new content