EOF
BAN USERWhat are you saying? 10^30*10*40 characters? Assume 1 byte for each character.
1GigaByte = 1024*1024*1024 bytes
10^32 bytes = 10^23 GigaBytes
You cannot have this much memory (or even secondary storage) available.
Now let us assume that somehow we manage to arrange this massive memory. You know that you have to visit each character at least once. To process 10^7 characters it takes an order of a second assuming O(1) for each character. Now to process 10^32 characters it will take 10^25 seconds means 10^17 years.
I remember this question was once asked in a "Long Contest" on codechef.com. Here is how I solved it.
You need an Associative Array (most suitably a HashMap) to solve this problem. Suppose each ticket is of the form "A->B" (means the ticket from 'A' to destination 'B').
Example input:
F->G
B->C
E->F
C->D
D->E
A->B
Output:
A->B->C->D->E->F->G
1) Make an associative array (or HashMap) which maps strings to strings. For
example the ticket "A->B" will be stored in associative array as
map["A"] = "B".
2) Find the starting station (the station which appears only as a key in the
map and not as a value).
Station s = starting station;
//while there is a destination corresponding to station s
while(map[s] != empty) {
print s;
s = map[s];
}
3) That's it. You did it :)
Although your solution is perfectly fine and can be used to solve more generalized equations but we can take advantage of the special assumptions given for the input. Thus we can avoid constructing a parse tree.
We scan the input and process LHS and RHS of the equation and identify tokens and processing them according to the operators encountered. After this the solution is trivial.
If there is no bound on time then one person is sufficient for identifying the poisonous bottle.
However if you need to determine the answer in exactly 60 minutes then a minimum of 2 persons are required. Label bottles as below.
Bottle1: 00
Bottle2: 01
Bottle3: 10
Bottle4: 11
No one drinks from 1st bottle. Person2 drinks from 2nd bottle. Person1 drinks from 3rd bottle. Both of them drink from 4th one.
If no one died then bottle1 is poisonous. If both died then 4th one is poisonous. If 1st died then 3rd one is poisonous. If 2nd died then 2nd bottle is poisonous.
Build separate suffix trees for author, name and publisher.
Insert all the suffixes of all the authors in the first suffix tree. Do the same for name and publisher. Here suffix trees are useful because:
* Suffix trees facilitate partial string matching.
* We can match the pattern in O(p) time, where p is the length of the pattern.
* They take linear extra space.
Partial string matching can be done as explained below.
Every substring of a given string is a prefix of one of its suffix. So we search the given query string starting from the root and match until the input is exhausted. Suppose we reach a node n. Then go to every leaf from node n and add that string to the list of suggestions.
There exists an online linear time construction algorithm for suffix trees, known as Ukkonen's algorithm
How can this be NP-complete? If I understood the problem statement correctly then the problem is "easy". If the entire file can fit in memory then the records can be sorted using any standard sorting algorithm. Otherwise the file can still be sorted using any external sorting algorithm. We just have to sort using the second field of each record.
- EOF October 26, 2013Since the matrix has O(n*n) elements thus the merge sort will take O(n^2 log n^2) = O(2*n^2 log n) time. Though it is true that O(n*n) is the asymptotic lower bound, but I doubt if the problem can be solved in O(n*n) time unless some special cases or some restrictions on input are given.
- EOF October 19, 2013Yes, it can be solved in O(n).
Construct a suffix tree for string s2 in O(n) time using Ukkonen's algorithm for constructing suffix trees - O(n) time and O(n) extra space.
Search string s1 in the suffix tree constructed in above step - O(n) time
The longest matched prefix of string s1 is the required substring.
Total time - O(n) and extra space used is O(n)
Method 1: Use a hashset:
Insert all the elements of Arr1[] in a hashset. Check which elements of Arr2[] are present in the hashset. This gives duplicates of Arr1[] and Arr2[]. Apply similar procedure for Arr3[].
Method 2: Use sorting:
Sort Arr1[], Arr2[], and Arr3[] and apply simple procedure like the merge-step of merge sort. Insert an element in Arr4[] only if it is present in all of the arrays.
Actually it is possible to merge in-place in O(n) time, but it's too complex to be asked in an interview. People are still researching on the topic and many research papers are available if you want.
Practically traditional merge algorithm (which uses auxiliary space) is better than in-place merge.
If asked in an interview you should mention the O(n^2) merging like insertion sort or the Quicksort. But that would defeat the goal of giving two sorted arrays as input.
@Chih.Chiu.19 and @Anonymus... Whether its NP-Hard or not, I can say that the time complexity is exponential in terms of k. Putting k=1 in this case seems "easy" just as in case of putting n=1 for polynomial-time algorithm in terms of n.
n=1 case is always "easy" for any algorithm, whether it be a poly-time or exponential time algorithm.
int i;
i = (int) f;
//convert this integer into string ... and put a decimal ...
.
.
f = f - i; //now f contains the fractional part ...
f *=10;
i = (int) f; //this is first digit to the right of decimal ...
.
.
f = f-i;
f *= 10;
i = (int) f; // this is second digit to the right of decimal...
// repeate above steps four more times ...
Inorder traversal is also a nice solution. I will try to explain the algorithm without using any auxiliary array.
Let prev = -INFINITY;
//function to check if tree is BST
boolean traverse(Node *n){
if(node n is NULL) return true;
else if node n is a leaf and prev <= n {
prev = n;
return true;
}
boolean flag = false, leftFlag = false, rightFlag = false;
leftFlag = traverse(n.left); //check left subtree
if(prev <= n.key) {
prev = n.key;
flag = true;
}
rightFlag = traverse(n.right); //check right subtree
return (leftFlag && flag && rightFlag);
}
Following is the pseudocode:
Triplet {
boolean isBST; //The tree is BST or not
int min; //Minimum value in the tree
int max; //Maximum value in the tree
}
//check if subtree rooted at "root" is a BST
Triplet checkBST(Node root) {
Triplet leftT, rightT;
//IGNORING BOUNDARY CASES LIKE LEAVES ...
leftT = checkBST(root.left);
rightT = checkBST(root.right);
//if both left and right subtrees are BSTs
if(leftT.isBST && rightT.isBST) {
//if this node is following the BST property then
if(leftT.max<=root.key && root.key<=rightT.min)
//the subtree rooted at this node is BST
return new Triplet(true, leftT.min, rightT.max);
}
return new Triplet(false, leftT.min, rightT.max); //not a BST
}
@Apostle ... It's not mentioned that you cannot use any extra space. And I think if you have to solve the problem in linear time then there is no choice except using O(n) extra space.
But if a linked list had been given then we could possibly solve the problem in O(n) time using O(1) space.
Why sort two arrays separately?
A better solution would be -->
Treat two arrays as one single array (how?) and then sort them. Thus return the mid element(s) of the combined sorted array.
The elements from each of the two arrays can jump into the other array while sorting.
Ahh!! The greedy algorithm!!
The above algorithm works as follows:
1. Let initial position be '0'.
2. If current position is 'i' then the frog can jump by atmost Array[i] cells. The frog will jump on one of the cells from Array[i+1] to Array[i + Array[i]]. Now from these cells choose the one which can take the frog to the farthest.
e.g { 3, 2, 4, 4, _ , _ , _ , _ , _ }. In this case, the frog will jump from '3' to second '4' because this second '4' will take it to the farthest. This "greedy choice" is right because the positions to which the frog can jump from second '4' also include all of the positions to which the frog can jump from '2' and first '4'.
3. Continue Step-2 till the frog jumps on/skips the last cell.
This algorithm runs in O(n) time because the frog considers each cell only once!
Also extra space used is O(1).
A Dynamic Programming solution you asked is here>>>
WORST CASE TIME: O(n^2)
EXTRA SPACE: O(n)
1. Create a Jumps[] array.
Jumps[i] = minimum number of jumps required from index i to reach end.
Assuming 0-based indexing, Jumps[n-1] = 0 (because "n-1" is the last
index of the array).
2. Now,
if (Array[i] == 0)
Jumps[i] = INFINITE; //once reached here, cannot jump further...
else if (Array[i] >= Array.length - i - 1)
jumps[i] = 1; //can reach the end in a single jump from here...
else let Array[i] = k (suppose) then
Jumps[i] = 1 + min(Jumps[i+1], Jumps[i+2], ... , Jumps[i+k])
3. Proceed from right to left and return Jumps[0] as the answer.
NOTE: MAY BE I'VE NOT CONSIDERED SOME BOUNDARY CASES!
This is called Maximum Subarray Problem.
If we want O(n) time complexity then we use Kadane's Algorithm.
//Kadane's Algorithm: O(n) time
function max_subarray(Array A){
max_ending_here = max_so_far = 0;
for (each x in array A) {
max_ending_here = max(0, max_ending_here + x);
max_so_far = max(max_so_far, max_ending_here);
}
return max_so_far;
}
Another solution (using divide and conquer) with O(n log n) time complexity exists.
//Divide and Conquer: O(n log n) time, (given in CLR book)
Given an array A. We want to find maximum continuous subarray. Divide the
array into two equal halves. The maximum subarray must lie in exactly one of
the following three places:
1) entirely in the left half of the array A,
2) entirely in the right half of the array A,
3) crossing the midpoint of the array A
We can check the third possibility in linear time and we check first two
possibilities recursively.
//T(n) = 2T(n/2) + cn = O(n log n)
We can use external quicksort. In an external quicksort, instead of heaving a single pivot element used for partitioning the array, we have a group of elements called 'middle group' or 'pivot group'. In a generalized algorithm, we use a Doubly Ended Priority Queue, (DEPQ).
1. Read in "maximum possible" elements and insert them into a DEPQ. The elements in the DEPQ will eventually be the middle group of elements.
2. Read in the remaining elements.
• If the next element is ≤ the smallest element in the DEPQ,
output this next element as part of the left group.
• If the next element is ≥ the largest element in the DEPQ,
output this next element as part of the right group.
• Otherwise, remove either the max or min element from the
DEPQ (the choice may be made randomly or alternately);
if the max element is removed, output it as part of the right
group; otherwise, output the removed element as part of the
left group; insert the newly input element into the DEPQ.
3. Output the elements in the DEPQ, in sorted order, as the middle group.
4. Sort the left and right groups recursively.
However, the question mentions that the range of integers is pretty much same as the number of elements and also the integers are unique.
Thus we can use 'counting sort' instead of a 'Doubly Ended Priority Queue' to sort the middle group elements.
As @Apostle said this solution too does not generate numbers with equal probability.
For example consider this:
Let P5(i) = Probability of generating i using rand5(). P5(i) = 1/6 for 0<=i<=5
Let P7(i) = Probability of generating i using rand7() and 0<=i<=7.
Now,
P7(0) = P5(0)*P5(0)*P5(0)*P5(0)*P5(0)*P5(0)*P5(0) = 1/(6^7)
Also,
P7(4) = P5(1)*P5(3)*P5(0)*P5(0)*P5(0)*P5(0)*P5(0) +
P5(2)*P5(2)*P5(0)*P5(0)*P5(0)*P5(0)*P5(0) + many more combinations ...
= 1/(6^7) + 1/(6^7) + ...
I came up with this >>>
//ASSUMING rand5() GENERATES A RANDOM 'i' SUCH THAT 1<=i<=5
int rand7(){
int r;
do{
r = 10*rand5() + rand5(); // Now r = a random number between 11 and 55;
r -= 10; // Now r = a random number between 1 and 45;
}while(r>=43);
// Now r = a random number between 1 and 42;
return r%7+1;
}
The above code can be easily generalized.
- EOF July 22, 2013@all who voted down.... could you please tell me where my solution lags? .... I think its better than generating all the permutations which has an exponential complexity.
And yes if length of the string is 10^6 then all the solutions which depend on generating permutations can never give the answer.
If the length of string is 'n' then number of permutations = n!
If length of string is 30 (a very very small number) then:
number of permutations = 30! = 2.6525286e+32
Thus on a modern machine it will require (nearly) 10^16 years to give the answer for string of length = 30 (Yes! THIRTY).
Then you can calculate factorials and inverse-factorials (modulo some large prime).
x/factorial(y) = x*inverse-factorial(y) (mod p), where p is a prime. See Fermat's Little Theorem.
To find the multiplicative-inverse of a number 'a', we do the following.
a^p = a (mod p) ->>> follows from Fermat's little theorem.
a^(p-1) = 1 (mod p)
a^(p-2) = inverse(a) (mod p)
You'll have to preprocess the factorials and inverse-factorials in arrays using the following relation:
factorial[i] = i*factorial[i-1];
Alternatively you could compute the actual answer without actually computing the factorials. Since the answer is integral, you can intelligently divide and multiply things so that the intermediate result never overflows the integer range.
- EOF July 07, 2013I think your question is >>> "Find the number of anagrams of a given string which are palindrome".
Here is how I approach:
We assume that the string will contain only lowercase characters of the English alphabet.
1) Let the length of the string be 'n'.
2) Declare a count[0...25] array and count the number of occurrences of each character in the string. Note that there can be atmost one character with odd number of occurrences and it has to be in the middle of palindrome. Fix this character at the middle of the anagram string and reduce its count by 1. Now every character has even number of occurrences.
3) Divide the count array by 2 (i.e. reduce the count of every character by half).
for i in range(0, 25)
set count[i] = count[i]/2.
4) We have to arrange these half of the characters in the first half of the anagram (and the other half has to be exactly the reverse of the first half). Now the problem reduces to >>> Find number of ways of arranging count[0] a's, count[1] b's, ... , count[25] z's in floor(n/2) positions.
m = floor(n/2);
Answer = m! / (count[0]! * count[1]! * ... * count[25]!);
//where, x! denotes factorial of x.
Please correct me if I've made a mistake.
- EOF July 06, 2013The following code prints a longest "strictly" increasing subsequence.
For example for {7, 7, 7, 7} it prints {7}. Only a little modification is required to print a longest non-decreasing subsequence.
Dynamic Programming. Time complexity O(n^2).
//lisLen[i] stores the length of longest increasing subsequence starting at index i.
//next[i] stores the index of next element in the longest increasing
//subsequence starting at index i.
int lisLen[SIZ], next[SIZ];
void printLIS(int a[], int len){
int i, j, max, index;
lisLen[len-1] = 1;
next[len-1] = -1; //-1 indicates that there is no next number after this one.
for(i=len-2 ; i>=0 ; i--){
lisLen[i] = 1;
next[i] = -1;
for(j=i+1 ; j<=len-1 ; j++){
if(1+lisLen[j] > lisLen[i] && a[i]<a[j]){
lisLen[i] = 1 + lisLen[j];
next[i] = j;
}
}
}
max = 0;
for(i=0 ; i<len ; i++){
if(lisLen[i] > max){
max = lisLen[i];
index = i;
}
}
while(next[index] != -1){
cout<<a[index]<<" ";
index = next[index];
}
cout<<a[index]<<"\n\n";
}
Hey eugene! are you the same guy who appears among the toppers list on codechef? I'm a fan :)
- EOF November 06, 2013