Google Interview Question: Give a string of words. Find ... | Glassdoor

Interview Question

Software Engineer Interview Urbana, IL

Give a string of words. Find anagram words and put them

  into the same list, then output the list of anagram words lists. input: [add, dad, care, race] output: [[add, dad], [care, race]]
Answer

Interview Answer

4 Answers

0

<?php

print_r(an(array('add','dad','race','care')));

function an($a) {
    for($i=0;$i<count($a);$i++) {
        for($j=$i+1;$j<count($a);$j++) {
            if (isan($a[$i], $a[$j])) {
                if (is_array($a[$i])) {
                    $a[$i][] = $a[$j];
                } else {
                    $a[$i] = array($a[$i], $a[$j]);
                }
                unset($a[$j]);
            }
        }
        $a = array_values($a);
    }
    return $a;
}

function isan($w1, $w2) {
    if (is_array($w1)) $w1 = $w1[0];
    if (strlen($w1) != strlen($w2)) return false;
    for($i=0;$i<count($w1);$i++) {
        $w2 = str_replace($w2, $w1[$i], '');
    }
    return (strlen($w2) == 0);
}

sman on Nov 25, 2013
0

l = ['add', 'dad', 'care', 'race']
dic = dict()
for w in l:
    v = ''.join(sorted(w))
    dic.setdefault(v, []).append(w)
print dic.values()

Christian on Dec 10, 2013
0

In Ruby

    def anagrams(arr = Array.new)
      anagrams = []
      arr.each_with_index do |w, i|
        set = w.split('').to_set
        arr.delete_at(i)
        anagram = [w]
        arr.each_with_index do |w2, j|
          next if w.length != w2.length
          if set == w2.split('').to_set
            anagram 1
      end
      anagrams
    end

Shawn on Dec 12, 2013
0

Same solution Christian using collections module

def listAnagrams(L):
    h = collections.defaultdict(list)
    for word in L:
        h[tuple(sorted(word))].append(word)
    return h.values()

Miguel on Jan 11, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.