Sunday, 16 June 2013

Twitter Interview Questions

I came across some Twitter's personal interview questions asked for it's Software Engineering position during some discussion:


1) Find whether a string contains a contiguous palindromic substring in O(n) time. Can you solve the problem in O(1) time?

2) In an array, find the element which appears more than 50% of the time. Find element which appears more than 33% of the time in the array.

3) What is a distributed hashtable? How to make data persistent, prevent data loss, and still keep the access efficient?

4) What are the key differences between the data structures: Hashtable, Array, LinkedList, BST. For what kind of queries would a BST perform better than Hashtable?

5) How will you find the most frequently searched queries on Google in the last minute/last hour/last day from among a dynamic stream of queries?

2 comments:

  1. "1) Find whether a string contains a contiguous palindromic substring in O(n) time. Can you solve the problem in O(1) time?"

    Do you mean to use parallel algorithm to solve the problem, like O(n) time on n CPUs? Thanks.

    ReplyDelete
  2. I think that it doesn't require parallel algorithm to solve the problem. It asks for returning a yes/no answer based on the existence of a palindromic substring in O(n) time, probably the question expects us to use space and improve the time complexity.

    ReplyDelete