Qualcomm Interview Question
Software Engineer / DevelopersInterview Type: In-Person
There's no "the best" here. Gap buffers are a classical and practical solution (used by Emacs and many other editors), but they can display pathological O(n^2)-style behavior if you alternate inserting characters at the beginning and end of the buffer. However, that rarely occurs in practice with text editors. Ropes are algorithmically better behaved, but in practical text editing (as opposed to more general string manipulation situations you might find in bioinformatics) they are often beat handily by gap buffers or linked lists of lines or other "flatter" data structures.
Rope, see: http ://en.wikipedia.org/wiki/Rope_(computer_science)
- dan February 16, 2012