## lambda2fei

BAN USERand i don't know whether there is an O(n) or O(nlogn) algorithm. my algorithm can be done in O(n^2).

- lambda2fei August 22, 2012here the greedy approach doesn't work, that is, in each decision, we can not just choose the longest palindrome ended at i. example: abcbab

- lambda2fei August 22, 2012f[i] = minimum number of palindrome can be made from str[0,...,i]

f[i] = 1 + min(f[k]), where 0 <= k < i and str[k+1,...,i] is a palindrome.

let len=strlen(str), then the answer is f[len-1].

for each url build an index which contains all n-grams of that url. given a query, split the query into separated part by '*', and find the urls containing each part, then merge them together (i mean find the intersection which the different part occur in the same order as the query).

- lambda2fei August 22, 2012i quite don't understand hot mst is related to this problem?

- lambda2fei August 22, 20127 is the minimum number, and it can be proved that each way in which every student achieve maximum grace mark is isomorphic to a circle permutation, so the number of ways should be the number of different circles which could be made by 7 different elements, i.e. 6!

- lambda2fei August 22, 2012tank: 16

volume of container: 2, 3

why not use check point?

- lambda2fei August 10, 2012yes, in any cases.

- lambda2fei August 03, 2012there is an O(n) algorithm. use n bucket with the same size of (max-min)/(n-1) and hash each element into the corresponding bucket, then the maximum distance would >= (max-min)/(n-1), which would only appear in neighbor bucket (skipping empty buckets). then you know what to do.

- lambda2fei August 03, 2012my answer is, find the DAG with source 's' and destination 't' produced by dijkstra. if the removed edge is a cut in this DAG, then..I think you need to run dijkstra again... and if not, the shortest path is not changed.. I can't figure out better solutions..

- lambda2fei August 02, 2012is that mean the graph is in fact a tree?

- lambda2fei August 02, 2012this problem could be done in O(length of file) as follows:

maintain a trie and put the name of the bands into it. when finished putting a band into the trie, add the corresponding college name into the last trie node's college list.

each time you put a new band into the trie, you either found that this is a new band, or this band also belongs to some other college. so if you maintain a hash table for each college, you can find the required pairs in O(1).

When you find the longest palindrome, you find the number.

- lambda2fei August 01, 2012use kmp as follows:

1. cut down the head and tail which is not '*' from the pattern, and match the head and tail with the text. If match, cut down the text head and tail and go on to 2; returns false otherwise.

for example, text: abcdadabaccdba, pattern: ab*dad*ba*dba, then head = 'ab' and tail = 'dba', both match the text head and tail correspondingly. so the new text would be 'cdadabacc' and new pattern '*dad*ba*'.

2. split the remaining pattern by * and build the kmp for each part, then use them to match the text one by one.

in the above case, '*dad' matches 'cdad', then '*ba' matches 'aba', the last '*' is for the tailing 'c'. done.

just use a recursive function to do brute force search.. since we have:

1<= N<=8

3<= K<=5

and the problem statement guarantees that the answer will never be greater than 7. So.

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

this is exactly the same as std::lower_bound

- lambda2fei August 22, 2012