-1

I am preparing for an interview for a company at the silicon valley. I am brushing up my data structures. I am just curious to know, is it reasonable to expect the interviewer to expect me to write code for something like, a remove operation on a splay tree?

At a conceptual level I know how these work, but I am not sure if I could write code to achieve that in a 1 hour interview if the interview was today.

  • What kind of job are you applying to? The likelihood of them asking about these data structures might depend on that. – Brandin May 30 '16 at 7:17
  • Could happen. In my area, you should know what an array, a dictionary, and a set are, and what their performance characteristics are, and how you use them. Any knowledge about implementation would show that you are interested. Being able to implement them would be pointless for most jobs. – gnasher729 May 30 '16 at 11:36
  • It's reasonable to expect this, but I'd say it's unreasonable for an interviewer to ask these questions. Few software devs are implementing data structures. They are instead writing, debugging, and maintaining code. Questions should focus on these topics. Interviewers that ask you to implement data structures are being lazy. – user2023861 May 31 '16 at 16:03
3

In past interviews, I have been asked to implement:

  • A linked list
  • A BST
  • A hashtable/hashmap
  • A trie
  • A k-d tree

More importantly, I've been asked to implement data structures that augmented the basic structures mentioned above (e.g. a hashmap with a constraint on the number of entries, with evictions based on LRU status).

The point of these questions was not to see if I had memorized the precise implementation details; when implementing the hashmap I did not bother trying to rehash when the number of entries crossed a threshold. Rather, it was to verify that:

  • As a programmer, I at least have a familiarity with these structures
  • As an engineer who is going to need to solve a problem, I can utilize and extend these structures in order to fit the needs of the solution

If you can describe the operations that occur on accessing a node in a splay tree, you can probably write passable code to implement them. What's much more important, though, would be to be able to speak intelligently about why you would be using a splay tree in the first place: what shape of data and patterns of data access would lead you to choose the structure, and what features of a splay tree would enable good performance in relevant metrics where other solutions would not.

1

It's definitely a reasonable question. I've never been asked about splay trees before...but I've definitely had similar questions about Binary Search Trees, HashMaps/Tables, Arrays, Linked Lists, and most notably an alphabitrie.

What I have found though is that most interviewers don't care if your implementation is runnable and absolutely correct (especially in a whiteboard interview)...they mostly want to see you reason about the data structure in question. I would start by explaining what you know about the structure on a conceptual level and then start writing stuff. Talk out loud, use a lot of first-person plural pronouns (What if WE did this, do you this thing would work for US). It usually prompts your interviewer to want to solve the problem with you and give you some hints. They care more about how you can work towards a solution together than if you memorized data structure operations in the weeks leading up to your interview.

good luck. :)

Not the answer you're looking for? Browse other questions tagged or ask your own question.