Amazon Interview Question
Senior Software Development EngineersTeam: Kindle
Country: India
Interview Type: In-Person
I think we can do it by using double linked-list, which is hold pointers pointing a fix-size of buffer. Insertion\Delete\Edit may have O(1) complexity(),also could add hash_map whose key is line number and value is pointers belong to the linked-list.
About search forward or backwards, firstly we must locate the current position and using KMP to finishing searching, and the complexcity is O(L*N), L is line size and N is charcter number average.
How about using a two dimensional array...we can move to a particular location in O(1),also we have flexibility of deviding it in number of lines of RAM compatibility
Use Rope data structure and do searching with any string searching algorithm like KMP.
- googlybhai April 03, 2013