Given 2 strings find the common words along with the time and space complexity. How would you optimize the algorithm

Question

Anonymous · Accepted Answer

To get O(N) for time complexity, you can split each string by spaces, traverse the first string and put each word into a hash, then traverse the second string of words checking each word to see if it was in the hash.  Hash functions are O(1) and traversing each string is O(N), so, final time complexity is O(N).

Ozan Eren Bilgen · Answer

Here is what you need:

    public static ArrayList findCommonStrings(String s1, String s2)
    {
        ArrayList result = new ArrayList();
        String[] words1 = s1.split("\W");
        String[] words2 = s2.split("\W");
        int words1Length = words1.length;
        int words2Length = words2.length;

        for (int i = 0; i < words1Length; i++)
        {
            if (words1[i].length() == 0)
            {
                continue;
            }
            for (int j = 0; j < words2Length; j++)
            {
                if (words2[i].length() == 0)
                {
                    continue;
                }
                if (result.contains(words1[i]))
                {
                    continue;
                }
                if (words1[i].equals(words2[j]))
                {
                    result.add(words1[i]);
                }
            }
        }

        return result;
    }

grim face · Answer

Amazon

Amazon Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches