Epic_coder
BAN USER 0of 2 votes
AnswersGiven an array of ints, find the most frequent nonempty subarray in it. If there are more than one such subarrays return the longest one/s.
Note: Two subarrays are equal if they contain identical elements and elements are in the same order.
 Epic_coder in United StatesFor example: if input = {4,5,6,8,3,1,4,5,6,3,1} Result: {4,5,6}
 Report Duplicate  Flag  PURGE
Amazon Software Engineer / Developer Algorithm
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.
 Epic_coder October 26, 2013The 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.
 Epic_coder August 25, 2013If 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?
 Epic_coder July 06, 2013The obvious solutions to this problem is doing a recursive or nonrecursive (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.

Epic_coder
July 06, 2013 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.
 Epic_coder July 03, 2013@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 subarray of size 10 that repeats 3 times and a subarray of size 4 that repeats 20 times. If these are the only candidates, the subarray of size 4 is the answer.
 Epic_coder June 29, 2013Use 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 medianofmedians algorithm to ensure a good split in quick select algorithm.
 Epic_coder June 29, 2013May 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 reversenormalize 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) preprocessing + O(n) postprocessing = 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.
 Epic_coder June 26, 2013Duplicate of: /question?id=19114716
 Epic_coder June 25, 2013I 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.
 Epic_coder June 22, 2013It 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.
 Epic_coder June 21, 20131. 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.
 Epic_coder June 19, 2013I 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[kC[i] ) +1
Running time = O(NS) where N is the number of coins and S the desired sum.
 Epic_coder June 19, 2013This is a greedy strategy and could return 1 even when there are solutions. You need to use dynamic programming to get the optimum solution.
 Epic_coder June 19, 2013It would make an interesting problem if data structure was a binary tree with no parent pointers.
 Epic_coder June 18, 2013Why do you think time complexity is O(n)? Just initializing all the elements to 1 in a nxn matrix takes O(n^2) time.
 Epic_coder June 17, 2013Time complexity is O(k+(Nk)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 hashmap instead of BST for indexing userid=>timestamp?
 Epic_coder June 16, 2013Since 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 hashmap 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.
 Epic_coder June 16, 2013Here 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.
 Epic_coder June 16, 2013Why 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?
 Epic_coder June 14, 2013This 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.
 Epic_coder June 09, 2013Before 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.
 Epic_coder June 07, 20131. 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.
 Epic_coder June 06, 2013Worst 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.
 Epic_coder June 05, 2013Whateva'  If the tree doesn't have a right subtree, the height of right would be 0 and height of left subtree would be nonzero. 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 inplace? 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.
 Epic_coder May 15, 2013My 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.
 Epic_coder May 15, 2013Why would a vertex have more than 8 neighbors?
 Epic_coder May 14, 2013Why waste so much memory?
 Epic_coder May 14, 2013This 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).
 Epic_coder May 06, 2013Interesting question.
This is how I would solve this:
1. Store the leftmost node and right most node. <<Takes O(n) time.
2. Print the path from root to left most node. (slightly tweaked Preorder 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 Postorder 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)
 Epic_coder May 05, 2013Well 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.
 Epic_coder May 04, 2013Well 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.
Open Chat in New Window
This is hard to explain in words. Let me explain with an example:
str1= cPagQRjhfPQaRhgPanRbRc
str2= PQR
Worst case time complexity is O(str1+str2).
 Epic_coder November 16, 2013