Amazon Interview Question for Software Engineer / Developers
- 0of 0 votes
Round3 | Q2 : Given a Cache of k-length Strings of size n,. Given a String X, We can to convert to another String Y using the following two Rules:- dutta.dipankar08 February 02, 2012 in India for SDE
R1:you can change only one character at a Time in stepwise Transformation
R2: All intermediate String in the transformation must be also in cache.
Cache has also an API : Called Is_Transformable(X,Y) return Ture if it is possible to transform X to Y, without violating the Above rule.
Assume that Cache is fixed size and there is a sequence of Query of Checking the possibility of Transformation is coming to The API of Cache.
the Question is : What Data-Structure U can use to implement Cache ? It might need some Initial Complexity to Organize the data , for efficient lookup, and provide service to APIs.
How can u implement the API in O(1).
Suppose we add one more API which calculate minimum number of Steps required to transform X to Y, How do u solve this problem in O(1).
[Hints: Graph Algorithms and Transitive closure ]
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer
Interview Type: In-Person
Open Chat in New Window