## JP Morgan Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#!/usr/bin/env python

import sys
import pprint

def combinationsStartingAt(matrix, start, maxLength, combs):
inRange = lambda point: point[0] in range(len(matrix)) and point[1] in range(len(matrix))

(i, j) = start
words = set()
for dr, dc in ( (0, -1), (-1, -1), (1, -1), (0, 1), (-1, 1), (1, 1), (-1, 0), (1, 0)):
next = (i + dr, j + dc)
if inRange(next):
earlierCombs = combs[maxLength - 1][next]
#print '----- earlier:', maxLength - 1, ' on next:', next, ' is', earlierCombs
#print '====', filter(lambda x: len(x) < 2 or x[1] != (i, j), earlierCombs)
tempWords = set(((i, j),) + tempWord for tempWord in filter(lambda x: len(x) < 2 or x[1] != (i, j), earlierCombs))
words = words.union(tempWords)

return words

def combinationsOf(matrix, maxLength, combs):
words = set()
#print 'max:', maxLength
for i in range(len(matrix)):
for j in range(len(matrix)):
start = (i, j)
if maxLength == 1:
combs[1][(i, j)] = set([((i, j),)])
else:
words = combinationsStartingAt(matrix, (i, j), maxLength, combs)
combs[maxLength][(i, j)] = words

return words

def toWords(matrix, combs):
def toWord(x):
return ''.join(matrix[i][j] for i, j in x)

result = {}
for key in combs.keys():
result[key] = set()
for index, poss in combs[key].iteritems():
for word in poss:
return result

def combinations(matrix):
maxLength = 5
combs = {}
for length in range(1, maxLength + 1):
combs[length] = {}
combinationsOf(matrix, length, combs)
combs = toWords(matrix, combs)
pprint.pprint(combs[maxLength])

matrix = [
[ 'A', 'B', 'C', 'D' ],
[ 'E', 'K', 'L', 'A' ],
[ 'C', 'A', 'M', 'N' ],
[ 'D', 'I', 'N', 'G' ]
]
combinations(matrix)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use backtracking to store all possible words that can be formed in trie and then answer each query of presence of words in O(world length)

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.