You are given a String number containing the digits of a phone number.Divide the number into groups such that the quality is maximized.Design an efficient algorithm to return the solution that maximizes the quality.

You are given a String number containing the digits of a phone number
(the number of digits, n, can be any positive integer) . To help you memorize the number, you want to divide it into groups of contiguous digits. Each group must contain exactly 2 or 3 digits. There are three kinds of groups:
• Excellent: A group that contains only the same digits. For example, 000 or 77.
• Good: A group of 3 digits, 2 of which are the same. For example, 030, 229 or 166.
• Usual: A group in which all the digits are distinct. For example, 123 or 90.
The quality of a group assignment is defined as 2 × (number of excellent groups) + (number of good groups)
Divide the number into groups such that the quality is maximized.
Design an efficient algorithm to return the solution that maximizes the quality.

Determine whether the Singly Linked List loops back or ends at a null location in time proportional to the length of the list

You are having a pointer to the head of singly linked list. The list either terminates at null pointer or it loops back to some previous location(not necessarily to the head of the list). You have to determine whether the list loops back or ends at a null location in time proportional to the length of the list. You can use at most a constant amount of extra storage.

Design a Data Structure of size O(n) (e.g. of Given Tree Size n) so that you can answer any such query in O(log n) time.

Given a rooted tree of size n . You receive a series of online queries : "Give nearest common ancestor of u,v " . Your objective is to preprocess the tree in O(n) time to get a data structure of size O(n) so that you can answer any such query in O(log n) time.

Give a data-structure which will guarantee O(log n) time per operation.

Complete binary tree as an efficient data-structure

You are given an array of size n(n being a power of two). All the entries of the array are initialized to zero. You have to perform a sequence of the following online operations :

* (i) Add(i,x) which adds x to the entry A[i].
* (ii) Report sum(i,j) = sum of the entries in the array from indices i to j for any 0 < i < j <= n.

It can be seen easily that we can perform the first operation in O(1) time whereas the second operation may cost O(n) in worst case. Your objective is to perform these operations efficiently. Give a data-structure which will guarantee O(log n) time per operation. (The title of the problem is a hint).

Merge the two Binary Search Trees in time O(log m + log n)

You are given two height balanced binary search trees T and T', storing m and n elements respectively. Every element of tree T is smaller than every element of tree T'. Every node u also stores height of the subtree rooted at it. Using this extra information how can you merge the two trees in time O(log m + log n) (preserving both the height balance and the order)?

Determine whether the kth largest element of the heap is greater than x or not.

Consider a binary heap containing n numbers (the root stores the greatest number). You are given a positive integer k < n and a number x . You have to determine whether the kth largest element of the heap is greater than x or not. Your algorithm must take O(k) time. You may use O(k) extra storage.

Searching for a friend

You are standing at a crossing from where there emerge four roads extending to infinity. Your friend is somewhere on one of the four roads. You do not know on which road he is and how far he is from you. You have to walk to your friend and the total distance traveled by you must be at most a constant times the actual distance of your friend from you. In terminology of algorithms, you should traverse O(d) distance, where d is the distance of your friend from you.

Searching For Celebrity

Celebrity is a person whom everybody knows but he knows nobody. You have gone to a party. There are total n persons in the party. Your job is to find the celebrity in the party. You can ask questions of the form Does Mr. X know Mr. Y ?. You will get a binary answer for each such question asked. Find the celebrity by asking only O(n) questions.

You are given n real numbers in an array. A number in the array is called a decimal dominant if it occurs more than n/10 times in the array. Give an O(n) time algorithm to determine if the given array has a decimal dominant.

Generating lexial predecessor of a k-subset of set of n elements