CareerCup

This is hard to explain in words. Let me explain with an example:
str1= cPagQRjhfPQaRhgPanRbRc
str2= PQR

1. Create a frequency map of str2 i.e.
P => 1, Q=> 1, R=>1

2. Find the first window from the left in str1 that has all the chars from str2. This could be done in a single scan of str1. Found window is enclosed between square brackets below.
[cPagQR]jhfPQaRhgPanRbRc (window_size =6)

3. Now compress this window from left if possible by advancing the left pointer one step ahead when the character on the left isn't found in str2. So I get:
c[PagQR]jhfPQaRhgPanRbRc (window_size =5) 

4. Now advance the right pointer of the window to the right until I find the left char (which is P). so I get
c[PagQRjhf]PQaRhgPanRbRc (window_size =8)  (some steps skipped)

5. Advance the left pointer of the window when right character is same as left pointer character.
cP[agQRjhfP]QaRhgPanRbRc (window_size =8) 

6. Using rule from step 3, I get
cPag[QRjhfP]QaRhgPanRbRc (window_size =6) 
cPagQ[RjhfPQ]aRhgPanRbRc (window_size =6) (rule 5)
cPagQ[RjhfPQa]RhgPanRbRc (window_size =7) (rule 4)
cPagQR[jhfPQaR]hgPanRbRc (window_size =7) (rule 5)
cPagQRjhf[PQaR]hgPanRbRc (window_size =4) (rule 3)

cPagQRjhf[PQaRhg]PanRbRc (window_size =6) (rule 4)
cPagQRjhfP[QaRhgP]anRbRc (window_size =6) (rule 5)
(some steps skipped)

7. Return the minimum window size(which is 4 here) and its starting and ending pointer.
 cPagQRjhf[PQaR]hgPanRbRc (window_size =4) (rule 3)

Worst case time complexity is O(|str1|+|str2|).

If N is the number itself, then the number of bits is roughly equal to log(N). Since the obvious algorithm requires inspecting each bit, one could argue it's O(log(N)) where N is the decimal number itself.

The conventional partition algorithm isn't stable, so you'll end up ruining the original order of elements, which is a necessary condition for solving this problem.
You can make partition stable by using an extra O(n) memory, but that also isn't permitted here.

Worst case time complexity is O(n^2), where n is the input size.

If the number of query words is large and dictionary is static, here is what I propose:

Preprocessing:
Create a graph of all the dictionary words. Each word will get a node and there will be an edge between 2 nodes (or words) if one of the words is only one alphabet lesser than the other word. This should take O(M^2) time, but for practical purpose we can assume the number of words in dictionary are constant, so it could be assumed as a constant time preprocessing operation. (Note that M is the number of dictionary words)

Now to search if a word can be broken down to smaller words (until the word becomes null) do this:
1. Find the word in the graph. Let this node is called N(word). This step takes O(M) time where M is the number of dictionary words.
2. Do a depth first or breadth first traversal starting at N(word). You can stop traversing when you find a node with length zero and return True. (You'll only to traverse at most lengthOf(word) deep nodes from N(word)). If you couldn't reach a node with length 0, return False.
If L is the length of the query word, this step will take O(L*L) worst case time.

I didn't get this question completely. Did you mean return all the palindromic anagrams of a string?

The obvious solutions to this problem is doing a recursive or non-recursive (using stack) DFS like everyone else has suggested. However I observed the performance of this the algorithm could be optimized by using this trick:

Assumption: All the characters in the input are ASCII characters.
1. Create a 256*256 neighbor matrix where there is one row for all possible characters and one column for all possible characters. Each row for a particular character will contain a true for all the characters that are its neighbor in the input matrix and false for all the characters that aren't its neighbor. (You could actually optimize the space used here since each character can have at most 8 neighbors.
2. Now if you have to lookup "DEF". Simply check if the neighbor matrix contains a true for ['D','E'] and ['E','F'] both of which would be O(1) operations. So you can actually check if a string exists given matrix in the time proportional to the length of the string.
3. Above method fails if there are repeated characters (it gives False positives). So if step 2 gives you True then fall back to traditional DFS approach, but if it gives you False, you can exit.

Oxford English Dictionary is known to have about 200,000 words. If you assume the average word size is 5, you need to store 200,000*5 characters in the main memory which is about 1 megabyte of data. Lets say our hash table is really very sparse so add a factor of X10, this pushes the memory requirement to 10megabyte. Almost all modern data computers and mobile phones have at least this much main memory.

@Rahul, lookup in hashmap take O(1) time. Insertion may take larger time but it's a one time cost.

Since we are required to just check whether a spelling is correct or not, I would use a hashmap. Just insert all the words from the dictionary in a hashmap and consequently the lookup would take contant time.
I would use trie only when I have to suggest the spelling using the string that user has entered as a prefix. Lookup in trie takes time proportional to the length of the query string.

No. You have to find the the most frequently occurring substring first and then within those return the longest ones.

@Dumbo
Can you throw some light on why you chose to use suffix array and not suffix tree? I believe creation of suffix array is at least as complex as creation of suffix tree. Using suffix tree we just have to find the deepest internal node than has at least n children, where n is the frequency of the most frequent character in the array.

How does this reduce to longest repeated substring problem? I could have a sub-array of size 10 that repeats 3 times and a sub-array of size 4 that repeats 20 times. If these are the only candidates, the sub-array of size 4 is the answer.

Use quick select algorithm to find nth largest number. It runs in O(n) average case time and O(n^2) worst case time. If you really want to improve worst case performance to O(n), use median-of-medians algorithm to ensure a good split in quick select algorithm.

May be do this:

1. Normalize each number to equal length by appending zeroes at the end. So we get something like:
{21,90,23}
2. Now sort it. We get:
{90,23,21}
3. Now reverse-normalize them i.e. remove the zeros that we appended in step 1. So we get: {9,23,21} which is the desired result.

Time complexity = O(nlogn) for sorting + O(n) pre-processing + O(n) post-processing = O(nlogn)
Space complexity = O(n)
where n is the number of elements in the array.

Tip: For performing step 1 of the algorithm, you'll need to find the number with max number of digits. You can find the number of digits in a number by taking log to the base 10.

I like your solution. But what makes you think average case time complexity might be O(n). We generally don't talk about the average case time complexity for deterministic algorithms.

Duplicate of: /question?id=19114716

I think the there will be multiple queries for searching a number at various times. It's possible that the number that you want to search now had been read t minutes ago.

It would make an interesting question if you were asked to find the number of unique dictionary words, otherwise it's just a simple permutations problem.

1. I would use an abstract class for SPACE and then specialize it to concrete classes APARTMENT, STORE, OFFICE and what not.
2. FLOOR will be another class that will be composed of collection of SPACE objects.
3. BUILDING will also be a class and will be composed of collection of FLOOR objects.

In order to properly identify properties and methods I need to know what is the purpose of this design? What functionality are we intending to provide?

This will run in exponential time. You should optimize your solution by using DP.

I would use dynamic programming to solve this. This one of those classic DP problems.

Let's say C[] is the sorted coins array and C[i] denotes value of ith coin and M[k] denotes the minimum number of coins required to get a sum of k.
Then

M[k] = min ( M[k-C[i] ) +1

Running time = O(NS) where N is the number of coins and S the desired sum.

This is a greedy strategy and could return -1 even when there are solutions. You need to use dynamic programming to get the optimum solution.

It would make an interesting problem if data structure was a binary tree with no parent pointers.

Why do you think time complexity is O(n)? Just initializing all the elements to -1 in a nxn matrix takes O(n^2) time.

Time complexity is O(k+(N-k)logk) which is equivalent to O(Nlogk). Note that N is sum of the total number of elements in all k arrays.

However if you say n is the average number of elements per array, you could also express the time complexity as O(nklogk).

Why don't you use hash-map instead of BST for indexing userid=>timestamp?

Since both the files have billion lines, I assume they are stored in the secondary memory.

I would initially do an external merge sort on both the files. Note that this will be lexicographic sorting.

Next, I'll match each line from file 1 with file 2. The matching will now be efficient because both the files are sorted. since you can't keep both the files in the main memory, you'll have to do matching in chunks.

Needless to say this will run in O(nlogn) time, but it is guaranteed to work for big files.

Let's say all the products in the array overflow, in that case your product array will be almost as big as the input array. Consequently, the algorithm will run in O(n^2) time.
The sure shot way of ensuring O(n) time complexity is to fall back to hash-map solution whenever an overflow occurs.

You need to keep track of people inside it because elevators have a max limit of number of people it can move safely.

Here is my attempt at OO design. Main classes are: Elevator, Request and Person. Request is an abstract class and the classes that implement/extend it are upRequest, downRequest, emergencyExitRequest and whatever you want. ElevatorSystem is the driver class. My design closely resemble the strategy pattern as I am choosing the serviceRequest implementation at runtime.

Haven't thought about an algorithm to service requests efficiently. Will do it later.

Class Elevator{
     Private:

          Person *in; //List of persons inside the elevator
          int destinationFloor;  //Floor to which the elevator is going;
          int currentFloor;
          enum {UP, DOWN, STATIONARY} stateOfMotion;
      
     Public:
          makeRequest(Request *){
               //Handle various types of requests and reset destinationFloor and stateOfMotion based on the  request by calling serviceRequest. Hook for implementing efficient algorithm for servicing requests of different priorities.

          }

          enterElevator(Person){
               //Open door, allow to enter a person and add Person to in
          }

          exitElevator(Person){
               //Open door, allow to exit a person and remove Person from in
          } 
} 

Class Person{
     Private:
          int floor;
     
     Public:
          requestElevator(Request *){
               //Make a request to the elevator
          }

          setFloor(int floor){
               //set floor
          }
     
}


Class Request{
     Private:
          int priority;
	  timeStamp;
     
     Public{
          virtual void serviceRequest(int &destination){};
          void setPriority(){
          }
}


Class UpRequest : public Request{
//Implement go up request, this will be made typically from outside the elevator
}


Class DownRequest : public Request{
//Implement go down request, this will be made typically from outside the elevator
}

Class EmergencyExitRequest : public Request{
//Implement emergency exit request, this will be made typically from inside the elevator
}

Class DestinationFloorRequest : public Request{
//Implement go to specific floor request, this will be made typically from inside the elevator 
}


Class ElevatorSystem{
//Main class for the system
//This will be responsible for creating an Elevators and Persons
}

Sorry for taking liberties with C++ syntax.

Why do you want to use BST for that? Why not just sort the array? Or use hash map to detect duplicates? Why aren't you leveraging the fact that all the elements are prime numbers?

This is incorrect. It is possible that both left and right subtree have all their leaves at the same level and still it's not true for the whole tree.

Before writing the code I would like to clarify that a leaf node must always have 0 children.
I would use recursive postorder traversal as follows:

/*Function returns -1 if all the leaf nodes are NOT at the same level, something else otherwise. A wrapper could be written to map these returned values to bool */
int sameLevel(Node *root){
    if(!root) return 0;
    
    int left = sameLevel(root->left);
    int right = sameLevel(root->right);
    
    if(left == -1 || right == -1) return -1; 
    if(left == right) return left+1;
    if(left == 0 || right == 0) return (left != 0? left+1:right+1);  //This is the case when exactly one of the children of a node is NULL
    
    return -1;
}

Time complexity = O(n)
Space complexity = O(1)

I'll explain my algorithm with an example:

Input intervals (or lifetimes): [5, 11], [6, 18], [2, 5], [3,12]

1. Put the end and start times of the intervals in one array. Sort it!. Always put the start time before end time in case they are equal. Maintain flags to identify a start/end interval. For above input I'll do something like:
2S, 3S, 5S, 5E, 6S, 11E, 12E, 18E

2. Now scan the array from left to right keeping track of how many intervals we are in. (This would be equal to total numbers of start intervals - total number of end intervals encountered so far). For above input I'll get something like:
1, 2, 3, 2, 3, 2, 1, 0

3. Now pick the maxima points from step 2. All the maxima points will be Start intervals and the point next to a maxima point will always be an end interval (which will be the end of the maxima start interval). So we'll get:
[5S,5E] and [6S,11E].

Hence the result is [5,5], [6,11]

Time complexity = O(nLogn), because of sorting in step 1.
Space complexity = O(n)

That would only work when both the arrays are sorted.

1. If it's a perfect binary tree and total number of nodes in the tree are known, then we can find the Kth largest or smallest element in log(n) time, because at each step we can reject one subtree. In fact we can predict the path just by using simple maths.
2. If it's just any binary search tree then doing the inorder traversal is the most optimum solution and will take O(n) time (obviously).

Your time complexity analysis is flawed.

Worst case time complexity should be O(n). However I don't think you would ever need to check more than ceil(n/2) elements where n is the total number of elements in the array.

Whateva' - If the tree doesn't have a right subtree, the height of right would be 0 and height of left subtree would be non-zero. That will return False.

thushw - Your solution has a subtle bug. I want you to figure it out.

How about using O(n) extra space to do partition in-place? Let quicksort's partition algorithm decide the correct position of an element only (Create a backup of original array before passing it to partition algorithm, then use it to partition stably).
Time complexity would be O(nlogn) which is same as original algorithm and space complexity would be O(n).

For each node check if the height of left subtree is same as that of right subtree. If true for all nodes return True otherwise return False.
Using a botton up approach this could be solved in O(n) time and constant space.

Everyone here is talking about the linked list implementation of graph. How would the solution change for adjacency matrix representation of the graph? I believe just returning a copy of adjacency matrix should do it.

My attempt at it. Salient features of my solution:
1. I am using no auxiliary memory.
2. Code is more readable as I am only flipping signs for 2 cases.
3. I am scanning the string from left to right.
Following is a C++ solution.

int AssociatedValue(char c){
    switch (c){
        case 'I': return 1;
        case 'V': return 5;
        case 'X': return 10;
        case 'L': return 50;
        case 'C': return 100;
        case 'D': return 500;
        case 'M': return 1000;
    }
    return 0;
}

int Roman2Int(string s)
{
    int i;
	if(s.length()==0)return 0;

	int result = 0;
    for(i=0;i<s.length()-1;i++)
	{
		if(AssociatedValue(s[i]) < AssociatedValue(s[i+1]))
			result -= AssociatedValue(s[i]);
		else
			result += AssociatedValue(s[i]);
	}
    result += AssociatedValue(s[i]);

	return result;
}

Time complexity = O(n) where n is the length of input string.
Space complexity = O(1)

You could avoiding using hashmap by creating a separate function and using case statements in it. But I like your solution, it's compact yet so readable.

Why would a vertex have more than 8 neighbors?

Why waste so much memory?

This solution works for the given problem, but if I say the given tree is balanced, your algorithm will run in O(n) time while Prasanna's algorithm will run in O(logn).

Interesting question.
This is how I would solve this:

1. Store the left-most node and right most node. <<Takes O(n) time.
2. Print the path from root to left most node. (slightly tweaked Pre-order traversal) <<Takes O(n) time.
3. Do an inorder traversal of the tree and print the node whenever it is a Leaf node (i.e. left and right children are NULL). Don't print anything if this leaf node happen to be the left or right most node that we saved in step 1. <<Takes O(n) time.
4. Print the path from right most node to root. (slightly tweaked Post-order traversal) <<Takes O(n) time.

Of course, we can do minor optimizations but the worst case time complexity would be O(n) and space complexity would be O(1)

Well build a trie of all the lines in file A and before actually starting to match lines from file B, make sure both of these files have equal number of lines.

Well for the second part, replace all 0s by -1, now this problem reduced to finding the longest size subarray with sum=0. We can use a hashmap to keep track of cumulative sums and easily find that in O(n) time.
However we can't do better than O(n^2) for solving first part because in worst number of subarrays with equal no of 0s and 1s could be proportional to n^2. Consider this test case: 0101010101.