Epic Systems Interview Question


Country: United States




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

DFS

- S O U N D W A V E February 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not really... How would that solve this problem? The order of traversal matters, because otherwise you might not find the given word, besides, would you start a DFS from all positions in the grid? Not very efficient...

- Zoli February 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why not simply to search for the first letter of word and start propagation in all possible directions if we found it? Don't understand how DFS will help in this situation.

- GK February 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

GK, that's an obvious choice (brute force), but I think we're supposed to find a solution that is more efficient.
Brute force in this case is O(n^3), we should be aiming for O(n^2)
(To make it simple, I considered the grid to be n x n and the searched word to be O(n)).

- Zoli February 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Zoli, it is essentially DFS(grid position).
Just try starting it at every grid position.
There are implicit arcs from every grid position to every adjacent grid position.

"return" if you meet a character on the grid that doesn't match the corresponding level of character in the given word to allow for a different path to be search

A match is hit when all characters in the given word are exhausted.

- S O U N D W A V E February 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

BigKdotAtTdot, I see, so that means n^2 DFS runs.

I see 2 problems with this approach:
1. It is not efficient: the overall algorithm would be O(n^3)
2. It still does not solve the problem. I think the original problem meant that the word has to be straight, that is, the whole word has to be readable in one of the 8 directions. Your DFS "breaks" the word, so it might go right 2 positions, then down 2 positions. This way it might find occurences which shouldn't be considered.

- Zoli February 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

KMP pattern search algorithm should be used.
Time: O(n*m) where n*m is size of matrix

- cptjack February 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good idea.
To refine the solution a bit, I suppose you were thinking the following:

Take the first line, do a KMP pattern matching on it using the given word. Do this for every line in the matrix. Then do this same thing in all 4 directions (left-right, up-down, top left - bottom right, bottom left - top right). After this, take the reverse of the word and do the whole algorithm again (to check the inverse directions). Of course this last step is not necessary, you can just implement the 8 directions as well.

This will go over the matrix 8 times with the KMP algorithm, which will still keep it at O(n^2) which is the best possible achievable time complexity given that we need to read the grid at least once.

- Zoli February 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Something similar to this appeared in Code Chef:

Here is the problem statement:
Given a M by N grid of letters, (1<=M,N<=50), and a
list of words, find the location in the grid at which the word can be found. A
word matches a straight, uninterrupted line of letters in the grid. A word can
match the letters in the grid in the grid regardless of case (i.e. upper and
lower case letters are to be treated as the same). The matching can be done in
any of the eight directions either horizontally, vertically or diagonally
through the grid.

Input
The input will contain one or more test cases. The
first line of each test case begins with a pair of integers, M followed by N,
1<=M,N<=50 on a single line. The next M lines contain N letters each; this is
the grid of letters in which the words of the list must be found. The letters in
the grid may be in upper or lower case. Following the grid of letters, another
integer K appears on a line by itself (1<=K<=20). The next K lines of input
contain the list of words to search for, one word per line. These words may
contain upper and lower case letters only (no spaces, hyphens or other
non-alphabetic characters).The input will end with two zeroes for M and N.


Output

For each word in the word list, output a pair of integers representing the
location of the corresponding word in the grid must be output. The integers must
be separated by a single space. The first integer is the line in the grid where
the first letter of the given word can be found (1 represents the topmost line
in the grid, and m represents the bottommost line). The second integer is the
column in the grid where the first letter of the given word can be found (1
represents the leftmost column in the grid, and n represents the rightmost
column in the grid). If a word can be found more than once in the grid, then the
location which is the output should correspond to the uppermost occurrence of
the word (i.e. the occurrence which places the first letter of the word closest
to the top of the grid). If two or more words are uppermost, the output should
correspond to the leftmost of these occurrences. All words can be found at least
once in the grid. Separate the output of each test case with a blank line.


And here is the best solution submitted by bsakthikumar

#include <stdio.h>
#include <ctype.h>
#include <string.h>

char a[50][50];

int in_range(int cur_n, int cur_m, int max_n, int max_m)
{
        if (cur_n < 0 || cur_n >= max_n || cur_m < 0 || cur_m >= max_m)
                return 0;
        else
                return 1;
}

void next(int *x, int *y, int dir)
{
        switch (dir) {
        case 0:
                *x = *x - 1;
        break;
        case 1:
                *y = *y + 1;
        break;
        case 2:
                *x = *x + 1;
        break;
        case 3:
                *y = *y - 1;
        break;
        case 4:
                next(x, y, 0);
                next(x, y, 1);
        break;
        case 5:
                next(x, y, 0);
                next(x, y, 3);
        break;
        case 6:
                next(x, y, 2);
                next(x, y, 1);
        break;
        case 7:
                next(x, y, 2);
                next(x, y, 3);
        break;
        }
}

void find(char *s, int n, int m)
{
        int i, j, k;
        int ci, cj;

        for (i = 0; i < n; i++) {
                for (j = 0; j < m; j++) {
                        for (k = 0; k < 8; k++) {
                                int t, flag = 0;

                                ci = i;
                                cj = j;

                                for (t = 0; t < strlen(s); t++) {

                                        if (!in_range(ci, cj, n, m)) {
                                                flag = 1;
                                                break;
                                        }

                                        if (s[t] == tolower(a[ci][cj]) || s[t] == toupper(a[ci][cj])) {
                                                next(&ci, &cj, k);
                                        } else {
                                                flag = 1;
                                                break;
                                        }
                                }

                                if (!flag) {
                                        printf("%d %d\n", i + 1, j + 1);
                                        return;
                                }
                        }
                }
        }
}

int main()
{
        int r, c, i, t;
        char s[50];

        while (1) {
                scanf("%d%d", &r, &c);

                if (r == 0 && c == 0)
                        break;

                for (i = 0; i < r; i++) {
                        memset(a[i], 0, 50);
                        scanf("%s", a[i]);
                }

                scanf("%d", &t);

                while (t--) {
                        memset(s, 0, 50);
                        scanf("%s", s);
                        find(s, r, c);
                }

                printf("\n");
        }
        return 0;
}

Can we do better than this in complexity ?

- Anonymous March 01, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More