Amazon Interview Question Software Engineer / Developers
Team: AWS
Country: United States
Interview Type: Phone Interview
I really don't know the answer. But my guess would to break the Large string into smaller strings and store them in linkedlists. Appending is simple as we can just change the pointer's value.
How would breaking up the large string help you at all? If anything you should break up the small string, since that's what the specification requires.
I think what he meant was use linked lists which store
dynamically allocated character arrays. Each node holds
a character pointer and size of array.
Inserting in position i would be:
1. Mark size=i in first node.
2. Allocate node with pointer=input_string and size=strlen(input_string)
3. Allocate node with pointer=head->pointer+i and size
head_size-i
Concatenation is trivial i.e. head->next=target
Better insert small string in the larger one.first part before the larger string and second part at the last.
It seems like an ArrayList would work well in both places. ArrayLists are inefficient at inserting small strings into arbitrary positions since the complexity depends on the size of the string already there + the size of the string being inserted. But from this problem statement, the size of the string already there will probably be smaller than the string being inserted, so the complexity will be close to that of simply copying the giant string being inserted. Since copying the giant string is a required part of any solution, this algo compares well with any other algorithm one could devise.
Appending is pretty much always efficient with an ArrayList, so the second case works too.
How do we get the 1 GB string as an input parameter to the function? The only reasonable explanation would be to store them in Disk as files. Also since we are dealing with files of very large magnitude we dont want to clog the memory with this process. So I would go with a linked list of File pointers that contains a list of files in the sequence as the string. When inserting a new string in middle of old string. split the old string and write them to a file and update the file pointers appropriately.
- Anonymous March 31, 2012