Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Keeping that in mind, we could a line by line comparison between matrix m and the file present in the memory(this can be made more efficient, by hashing for instance)
If we overrun the the chunk present in the mem, there can be two cases.
1. If we had a partial match i.e. part of m was present in the current chunk. In that case, bring in the next chunk, and continue the search
2. If no match, bring in the next chunk, and start afresh.
Maybe a stupid question, but how large is the file? Too large to be entirely on memory? And what is the exact format of the file? Is it like n lines each separated by a newline character where each line is n characters of '+' or '.'?
If original bigger matrix is M, smaller matrix to be found is m.
- puneet.sohi April 21, 2014Since file is too large to be in memory, it will have to be broken down and brought in chunk by chunk
I think there are two parts to this question:
1. If a piece of file/matrix M is present in the memory, how would we find the pattern m in it, most efficiently
2. If the patter m is present in two chunks i.e. if a chunk is present in the memory, m could be partly present in that and partly in the incoming chunk.