Menu
Recently I was asked this question in an interview. The exact question was
What data structures will you use to implement a text editor. Size of editor can be changed and you also need to save the styling information for all the text like italic, bold etc ?
At that point of time, I tried to convince him using many different approaches like stack, Doubly Linked list and all.
From that point of time,This question is bugging me.
548
The gap buffer data structure is commonly used by text editors for storing the files that are currently being edited. The data structure is simply an array that stores the contents of a file plus some extra empty space. This empty space is called the gap.
For example, the original vi used an array of lines, which sort of explains some of its quirky line-oriented idioms. The BSD clone of vi, nvi, uses an entire database to represent buffers. Vim uses a fairly complex rope-like data structure with page-oriented blocks, which may be stored out-of-order in its swap file.
This program implements a text editor using Linked List and Stack data structures. Each line of text is saved into a linked list node, which consists of a data portion holding the text and a pointer to the next node of the linked list, which is the next line of the text.
It looks like they'd like to know if you were aware of the flyweight pattern and how to use it correctly.
A text editor is a common example while describing that pattern.
Maybe your interviewer was a lover of the GOF book. :-)
133
In addition to the previous answers, I would like to add that in order to get to the data structures, you need first to know your design - otherwise the options will be too broad selected.
As example let's assume that you'll need an editing functionality. Here the State and Memento design patterns will be a good fit. Very suitable structure will be the Cord, since it's
composed of smaller strings that is used for efficiently storing and manipulating a very long string.
In our case the text editing program
may use a rope to represent the text being edited, so that operations such as insertion, deletion, and random access can be done efficiently.
31
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
