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?

3 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
  3. Latest Google Recruitment 2018 notification will be released soon, apply online for google Vacancy by last date.

    ReplyDelete