Google Interview Question
Hi bro,
Thanks for starting this thread.. I saw string problems you mentioned aboive and some of them are new to me, and I havn't implemented suffix tree as well..
I will keep updating on the thread, as in when I kept solving above problems.
Also, if possible do you have a list of problems which uses Divide and Conquer Strategy, dynamic programming.. I just learnt the art of solving problems using this divide and conquer strategy, so just want to see few more problems on these topics. Kindly help.. :)
Few divide-and-conquer problems:
- nearest pair of points (2D) in O(nlogn)
- counting inversions in an array
- array shuffling
input : a1,....an,b1,...bn
output: a1,b1,....an,bn
Few DP problems:
- Max contiguous sum in array
- Max subset sum of non-adjacent elements in array
- longest increasing subsequence
- longest common subsequence
- shortest common supersequence
- longest oscillating subsequence (google interview question)
- longest accelerating subsequence
- longest Arithmetic Progression subsequence for unsorted array (google interview question)
- Matrix chain multiplication
- maximum value of expression consisting + and *
- minimum number of palindromic substring
- cutting stick (ACM UVA problem)
- 0/1 Knapsack
- counting ways of making a change
- Min. number of coins for a change
- 2-partitioning a set with/without repeations of items minimum sum difference
- Edit distance
- convert string to palindrome with minimum deletions /insertions
- Max. rectangle sum
- Max rectangle/square submatrix of 0 and 1
Also, look in CORMEN and SKIENA's book.
Thanks bro... :)
Do keep updating this post as in whenvr you get any solutions to mentioned problem here.. I will keep tracking this thread.. :)
Suffix Tree & Suffix Array Both Can be created in O(N) & thus most of d problems u have listed can be solved in less then O(N^2)
Hi bro,
Thanks for starting this thread.. I saw string problems you mentioned aboive and some of them are new to me, and I havn't implemented suffix tree as well..
I will keep updating on the thread, as in when I kept solving above problems.
Also, if possible do you have a list of problems which uses Divide and Conquer Strategy, dynamic programming.. I just learnt the art of solving problems using this divide and conquer strategy, so just want to see few more problems on these topics. Kindly help.. :)
@Wgp: I know it's possible in O(n) time and space - which is not trivial. The simplest approach of suffix trie (not suffix tree) takes O(n^2) complexity - which is doable in an interview. The problem with suffix trie is that as number of nodes in the whole tree is O(n^2), almost all problems take that much time - which may be acceptable for some problems.
I expected more people are participating in this type of thread. I had an impression that CC is like StackOverflow (or even like WU riddle) portals. But, the quality of participation is not really very much here. Most people just post solutions even w/o an explanation. Only few people illustrate idea to help others!
The funny thing is that a lot of these people write long blocks of code when it's not clear how they will have time and space to do the same on an actual interview. Most of the code does not have explanations because it is either completely wrong, not properly thought out, or just plain inefficient. In my humble opinion, these folks are just wasting their own time and their interviewers' time.
Many string problems can be solved efficiently using the above 2 data structures. Yet, it's hard to implement these during an interview. Suffix tree is easier to implement, but trivial implementation takes O(n^2) time and O(n^2 |A|) space, where n = string length, |A| = size of alphabet. Similarly, simple suffix array implementation (as given in Bentley's programming perals book) takes O(n^2 logn) time and O(n) space. How could we achieve this below O(n^2), say O(n logn) complexity?
So, let's we discuss our approach to solve different string problems using these DS. You can either share your idea, or post link to useful references, or give link to your own code (with brief explanation). I believe it'd be very helpful for many of jobseekers. Pls no offense.
Here just few common problems on string for which above DS are quite useful. Feel free to add more problem to the list. Thanks.
- jobseeker July 05, 2011- substring search in O(p logn) time, p = pattern size, n = text size - minimum lexicographic rotation of a given string for example, the rotations of the string “alabala” are: alabala labalaa abalaal balaala alaalab laalaba aalabal and the smallest among them is “aalabal”. - longest palindrome in a string - all palindromes (of length >=2) in a string - longest common substring of 3 given strings - number of distinct substrings of a given string - longest unique substring of a given string - longest substring that repeats atleast k times - most frequent substring in a given string