Amazon Interview Question
Software Engineer / DevelopersCountry: United States
thumb up.
It feels like a big program to write for an interview, as it needs to handle input, sort, evaluate expressions and do the output...
Companies having good demand are following a pre-filter method to screen chaps who can code rather than just yap.
Its less headache for the company which is getting way too many resumes.
I believe they would give you ample amount of time, say 1 hour to code this problem and submit to their online judge.
Actually you don't need to do any sorting, just start evaluating cells one by one, and during the expression computation (a stack) you just reference the cells you need and ask them for their values. If a value for a cell has been computed before, just return it, otherwise calculate it - so the function call stack will do all the work for you
Use topological sort and start evaluating the cell values using stack in that order
- rixcat February 02, 2013