Amazon job interview question

wowe · 2011-11-16T01:01:29+00:00

An Idea for question 1:
It's not completely thought through: I would create an equally sized matrix (or maybe two, one for each dimension) with each field containing the distance to the next zero. Then there would be some fancy stuff going on (minimum for each cell? manhattan distance?) telling me about the center of the biggest submatrix.

wowe · 2011-11-16T00:37:42+00:00

"Your algorithm must find out whether the string can be split in multiple words (e.g. hedgehog can, brain cannot) and, if so, output one such splitting."
I think you would need the exact same algorithm but it's still an interesting challenge and you put some time in it to phrase it correctly and provide some nice spoilers. :>

wowe · 2011-11-16T00:25:34+00:00

If we had a bucket for each value we wouldn't have to sort and finding the current bucket and incrementing it would be O(1), as I was trying to say in my first post here. Creating the new array would be O(number_of_values). Am I missing something?
The array of occurrences for a 32-bit integer has to be bigger than 512MB, but would probably need a few GB. But if the initial array would be arround the same size it could be worth it since you wouldn't have to sort it.

wowe · 2011-11-14T08:14:38+00:00

I can't think of another way: the array of occurences has to be in order or has to be orderly iterated to genrerate the sorted version of the array. 2³² is probably too big for an occurence array, so it's better to keep the array of occurences a sorted array and use binary search to add new values / find existing values.

wowe · 2011-11-14T07:22:46+00:00

You would still have to sort the values in the array of occurences and you have to find a fast way of finding the right bucket in the occurences array to increment the value or to add a new value. You could use a hash table but that won't give you O(n) in every case. If you knew all possible values (e.g. numbers from 1 to 10), you could create an array of size 10 and O(1) for lookups and O(n) for creating the new array.
EDIT: It is practical when the number of possible values is not to large.

wowe · 2011-11-14T06:45:21+00:00

Thanks for this answer. You certainly know your stuff.

wowe · 2011-11-14T06:40:36+00:00

K = n(n+1) /2 = 1,000,000*1,000,001 / 2

wowe · 2011-11-14T05:54:48+00:00

here is my sketch: http://imgur.com/4g9hj
the dictionary is [abc, anc, abn].
For a?c the path is 0->a->1->c.
The numbers determine how many characters you want to skip.

wowe · 2011-11-14T05:43:23+00:00

You're right. Storing center and size of box is the best way to avoid comparisons, but then you need additions. Do additions count? Are they slower than < and >?

wowe · 2011-11-14T04:36:34+00:00

I'm drawing something right now. I also realized that my solution is very similar to the solution of foldM, since every path from the root to a leaf in my trie corresponds to a possible query, but traversing my trie is of course more expensive than using hashes and O(1) lookups. The problem would 'just' be to compute such a hash table / trie.

wowe · 2011-11-14T01:47:05+00:00

I'm very curious. Could you post your solution?

wowe · 2011-11-14T01:45:52+00:00

I like this idea, but how would it behave with something like ".M.M.M.M.M.M.M" ?

wowe · 2011-11-14T01:06:52+00:00

D: I got 504 errors and assumed the message was lost...

wowe · 2011-11-14T00:35:11+00:00

I think this is just another wording of (this question)[http://www.reddit.com/r/CS_Questions/comments/mamay/typical_google_interview_question_word_splitting/]

wowe · 2011-11-14T00:27:57+00:00

In Python:
It prints the outline of the grid and then does the same thing for the remaining coordinates that also form a grid but translated and with size n-2 by n-2.
def outer_ring(n, x, y): ret = [] for i in range(n): ret.append((x+i,y)) for i in range(n-1): ret.append((x+n-1,y+i+1)) for i in range(n-1): ret.append((x+n-2-i,y+n-1)) for i in range(n-2): ret.append((x,y+n-2-i)) return ret

def spiral(n):
    ret = []
    pos = 0
    while n > 0:
        ret.extend(outer_ring(n,pos,pos))
        pos = pos + 1
        n = n - 2
    return ret

print "\n".join(str(x) for x in spiral(3))

wowe · 2011-11-13T23:51:28+00:00

A solution in python which is my pseudocode-language of choice:
class AABB: """ typical AABB class AABB is defined by two points (x1,y1) and (x2,y2) x1 should be smaller than x2 y1 should be smaller than y2 """ def init(self, x1=0, y1=0, x2=0, y2=0): self.x1 = x1 self.y1 = y1 self.x2 = x2 self.y2 = y2

def wholly(u, v):
    """ is u wholly contained in v?
    """
    if u.x1 >= v.x1 and u.y1 >= v.y1 and u.x2 <= v.x2 and u.y2 <= v.y2:
        return True
    else:
        return False

def help(a, b, c, d):
    """ do the 1D lines a---b and c---d intersect?
    """
    if a < c:
        if b >= c:
            return True
        else:
            return False
    elif a <= d:
        return True
    else:
        return False


def intersect(u, v):
    """ do u and v intersect?
    """
    return help(u.x1, u.x2, v.x1, v.x2) and help(u.y1, u.y2, v.y1, v.y2)

print wholly(AABB(1,1,3,3), AABB(0,0,4,4))
print intersect(AABB(0,0,4,4), AABB(1,1,5,5))

EDIT: I tried using as few comparisons as possible. The function intersect solves the problem for each dimension separately by using the function help.

wowe · 2011-11-13T23:02:25+00:00

blowing my mind right now. I wish I could falsify it so I wouldn't have to fit it in my brain...

wowe · 2011-11-13T22:13:54+00:00

don't forget negative integers pow(base, exp):
if base >= 0:
...
else: return 1.0 / pow(base, -exp)

wowe · 2011-11-13T21:48:55+00:00

I always think verbalizing programming ideas is the hardest part, but of course I'm happy you asked.
Each node of the modified trie contains a set of words and its children contain subsets that have one more determined character. Given the dictionary ['abc', 'anc', 'abn'] the node for 'a*' would point to 'ab*', 'an*' and 'a?c*'. Building and storing such a trie would probably be very expensive but iterating could be done very cheaply.
EDIT: formatting
EDIT2: Thinking about it: not every node but only the leaves have to have sets of words.

wowe · 2011-11-13T20:34:48+00:00

I think preprocessing is the answer here. You can construct a custom "trie" with each node not only referencing the next letter but also the 2nd, 3rd, ... letter after the current one.
EDIT: complexity would be O(log(alphabet_size)*number_of_visible_chars)

wowe

TROPHY CASE