Epic_coder
BAN USER- 0of 2 votes
AnswersGiven an array of ints, find the most frequent non-empty subarray in it. If there are more than one such sub-arrays 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
What makes you think this is a classic Knapsack problem?
- Epic_coder May 03, 2013Sort all the denominations in increasing order and let Di denotes ith denomination.
Let N(i,K) = Number of ways of obtaining an amount K only using denominations from D1 to Di.
N(i,K) = Max ( N(i-1,K) , N(i-Di,K-Di) + Di )
Optimum solution for K=A is Max of all N(i, A)
This can be easily solved using dynamic programming, Be careful while initializing values.
This should work in O(n^2) time and O(n^2) space.
Why do you need a heap/BST? Why do you want to sort the data?
- Epic_coder November 18, 2012I think dynamic programming should be used here. I figured out a recurrence relation to solve this in O(n^5). Does anyone have a better idea?
- Epic_coder November 17, 2012Yeah, that should work. Just do a quicksort then do something similar to merge step in mergesort.
- Epic_coder November 08, 2012Simple DP problem,
Recurrence relation:
Ways(x)=Ways(x-6)+Ways(x-9)+Ways(x-20)
If Ways(n)>0 return true
else return false
Not a good idea to use recursion. Evolve your solution to use DP,
Recurrence relation:
Ways(x)=Ways(x-6)+Ways(x-9)+Ways(x-20)
If Ways(n)>0 return true
else return false
Not possible to do this in less than O(n^2) time, because in worst case there could be n^2 such pairs.
- Epic_coder November 04, 2012This solution is partially incorrect. It will work optimally with following modifications:
1. Sort the X so that we can do binary search every time.
2. When you look for an element in X and there is no element in X that is equal to the digit we are looking for, then you also need to consider the case when unused digit is smaller than the digit we are looking for
3. While doing binary search, if you find the desired digit multiple times, process it just once.
Optimum time complexity would be O(n*logn)
BFS should work here. The Y coordinate of both the robots will always be same. So it should be very simple to implement.
In real life, this kind of motion is equivalent to oscillating about the initial points linearly.
One possible solution:
1. Use a max heap of size K to get the maximum of K elements at any time.
2. Use a hash map that would let you directly access any element in the heap, with the index of that element in the array as key.
Why this works?
Lets suppose you have to find the maximum between index P and P-K, Now will have a heap that contains K elements between index P-1 and P-K-1,
--Pop element at index P-K-1 from heap and hashmap(Cost = O(1)+O(logK))
--insert element at index P in the heap and hashmap(cost = O(1)+O(logK))
--top element from the heap gives you maximum between index P and P-K (cost = O(1))
You would repeat above N-K+1 times so
total cost = (N-K+1) * O(logK) = O(N*logK)
Incorrect! Will not work for monotonically decreasing input.
- Epic_coder October 30, 2012First idea that came to my mind:
Assume the graph is represented in adjacency matrix format,
Serialize:
1. count the number of columns in the matrix. Say it's C.
2. Write C<delimiter> to file
3. Now traverse the matrix in row major way and write each value<delimiter> to the file.
Deserialize:
1. Read the first character from file, it's number of columns in the matrix. say it's C
2. Read C values from the file(ignore delimiter), that would be a row of adjacency matrix.
3. Keep doing 2 until end of file.
I would use a character array to store the result and do exponentiation by repeated squaring. It would require O(logn) operations. Of course you'll have to write code for multiplication using strings.
Also, I like the idea of using a reversed linked list, but to get the result you will have to perform O(n) operations on the linked list which I believe isn't very good.
This solution is correct and will work for all test cases.
- Epic_coder October 28, 2012This solution has O(n^2) time complexity and is correct.
- Epic_coder October 28, 2012This should definitely work!
- Epic_coder October 28, 2012Someone has already suggested this, I am just clarifying:
Do a BFS and at each step insert the left node before right node in the queue. The last node in the queue would be the answer.
How to check if an element is last element in the queue? When you pop element from the queue, if the popped element has no children and queue is empty after popping it, you have found the last element.
Could you explain you solution in english language a bit more?
- Epic_coder October 28, 2012Basically in every recursion, you have two choices, pick the first character of string A or that of string B. A and B are given input strings for first iteration of recursion and for making further calls we pass A+1 if we chose the character from A and so for B.
Following is compilable C++ code, though you might have to set the size of r to sizeof(a)+sizeof(b).
#include <iostream>
using namespace std;
void interleave(char a[], char b[], char r[], int len){
if(a[0]=='\0' && b[0]=='\0') {
cout<<r<<endl;
return;
}
if(a[0]!='\0') {
r[len]=a[0];
interleave(a+1, b,r,len+1);
r[len]='\0';
}
if(b[0]!='\0') {
r[len]=b[0];
interleave(a, b+1,r,len+1);
r[len]='\0';
}
}
int main(int argc, const char * argv[]){
char a[]={'A','B','\0'};
char b[]={'C','D','E','\0'};
char r[10];
r[0]='\0';
interleave(a, b, r, 0);
return 0;
}
Has anyone suggested a solution that runs in polynomial time(not exponential). If no, do anyone know what NP problem does this problem resemble to?
- Epic_coder October 26, 2012Was this asked by Google? Seriously?
- Epic_coder October 26, 2012My interpretation of the question: Given a website you have to find number of hits in the last second, last minute and last hour.
Idea:
Have all the counters as data member and two methods click() and query(), click updates the counter whenever the site gets a hit and query gives you hits in the last second, last minute or last hour.
Following is the pseudocode for member functions for second counter. Could be easily extended to minutes and hours.
class counter{
private:
int hitspersecond; //hits in last second
int lastsec; //last hit instant
public:
void click(){
currentsec = getcurrenttimeinsec() //absolute time in second, use standard library funtion to get that
if(currentsec == lastsec) hitspersecond++; //lastsec is last hit absolute time in seconds
else {
hitspersecond=1;
lastsec=currentsec;
}
//Similar code for minutes and hours
}
void Query(){
if(getcurrenttimeinsec() == lastsec) return hitspersecond;
else return 0;
//Similar code for minutes and hours
}
};
How do you plan to represent n points on number line where n is the sum fo all populations?
- Epic_coder October 23, 2012I think this might take lesser memory if GCD>1.
- Epic_coder October 23, 2012Just a thought: Could this be done using BFS, where each node in the graph would look like:
struct node{
int Person1X,Person1Y,Person2X,Person2Y,Person3X,Person3Y;
int steps;
}
While doing the BFS we could put a constraint,
if steps>min(sum of any two edges of the triangle with 3 persons as vertices) return;
Sorry, Updated the solution.
- Epic_coder October 23, 2012Another idea:
1. Find the GCD of population of all the countries.
2. Create an array and repeat name of country X, K times in the array where K=(population of country X)/GCD
3. Now pick up a random element from the array
It could be easily proved mathematically that probability of choosing a country with higher population is higher in appropriate proportion.
How does your solution guarantee minimum number of operations?
- Epic_coder October 23, 2012Well in 1st approach you would start from DAMP and generate following in the first step:
LAMP,DIMP,DAKP and DAME, and at the same time look up each of them in the dictionary, and proceed only with those nodes that exist in the dictionary.
While in approach 1 you already know what words could be obtained with one replacement exist, so you don't have to generate n combinations and don't have to lookup each of them in the dictionary at each step because you have direct nodes that you can follow.
This method will always work because the probability of the event where there would be an infinite loop is given by P(e)=(r/n)^k where k approaches infinity and r is the total number of unique words in the list that are in range (1,n).
So if you apply limits P(e) = 0 as long as all the numbers in range (1,n) aren't present in the blacklist(which is an invalid test case and should be checked before entering the loop)
2 solutions. First approach is the most scalable one:
Approach 1:
Preprocessing step: Create a graph of all the words in the dictionary such there is an edge between word X to Y only when they differ by one character replacement only.
1. Find the source word in graph.
2. From the source node run a BFS to find the target node.
Approach 2:
1. Do a BFS, but this time you have to generate all posible states at each step, so there would be additional cost of looking up the word in the dictionary.
Time complexity= O(n^n)
Tomonfire,
The space complexity depends on what approach you use, recursive or iterative. It would be same as the space complexity of BFS.
Time complexity would be O(1) amortized.
Does this problem become a NP-complete problem if I say find the minimum number of steps to convert one parking lot arrangement to other using 1 empty spot?
- Epic_coder October 22, 2012When would you post your solution? If it's not anytime soon, do you mind sharing what you are planning to do?
- Epic_coder October 22, 2012Number of elements that are not at its correct position could act as a good heuristic function here. But I don't know if it would give us the minimum number of steps.
- Epic_coder October 22, 2012Second attempt:
I compiled 2 solutions for this, the first one is just a modification of my earlier method and second one is using graphs, which I am pretty sure could be optimized further:
1. Approach one:
1. Remove all the elements(except 0) in the both the arrays that have the same position in source and target.
2. Hash all the values in the source array with value as key. This will tell us the index of value X in O(1) time.
3. Scan source and target arrays and if the position of 0 is same in both the arrays, swap the 0 in source with any other element in the array.(Print it)
4. do while(source array != destination array){
-- let X=index of 0 in source.
-- let V=number that is present at index X in destination array.
-- if(V==0) swap 0 in source array with any random element that isn't at it correct position and continue loop.(print it)
-- let Y=index of V in source array(obtained from hashmap)
-- swap(value at index Y with 0) (print it)
Running time complexity=O(n^2)
(Doesn't guarantee optimum solution I think)
2. Approach two:
This problem could be modelled as a graph problem where initial state is source array and final state is target array. We could find the steps to get the final step in minimum number of moves by using BFS. To make sure we aren't looping in a cycle, we have to hash nodes as Boris suggested.
Time complexity = O(n^n)
I believe this problem could be optimized a bit by using A* algorithm where heuristic could be the distance(Manhatten) between a given state and target state. So at every step choose the state that is least distant from final state. But that would give quickest solution, not the optimum solution.
If word Y comes after word X in dictionary then Y is lexicographically greater than X.
- Epic_coder October 21, 2012Input Garage Pattern is source array and Output Garage pattern is target array.
- Epic_coder October 21, 2012Yeah I didn't remove more than one car. In step 1, I am just ignoring the cars that are already at the desired position.
- Epic_coder October 21, 2012Alright, here is the first idea:
1. Remove all the elements(except 0) in the both the arrays that have the same position in source and target.
2. Hash all the values in the source array with value as key. This will tell us the index of value X in O(1) time.
3. Scan source and target arrays and if the position of 0 is same in both the arrays, swap the 0 in source with any other element in the array.(Print it)
4. do while(position of 0 becomes same in source and destination arrays){
-- let X=index of 0 in source.
-- let V=number that is present at index X in destination array.
-- let Y=index of V in source array(obtained from hashmap)
-- swap(value at index Y with 0) (print it)
Running time complexity=O(n)
Doubt:
Why have you used different numbers to denote cars? Is there any difference between output pattern 0 1 2 3 4 5 6 7 8 9 and 0 2 1 3 4 5 6 8 7 9?
What is the answer for given test case:
Input Garage Pattern : 1 2 3 4 0 5 6 7 8 9
Output Garage pattern : 0 1 2 3 4 5 6 7 8 9
Answer?
How large? I can't tell that without having any knowledge of the dataset this data structure is going to support.
Cost of resizing? O(1) amortized
(Theoretically speaking you could choose an array of any size and when you run out of memory, allocate twice as much memory. It would still be O(1))
I chose a large array because if you take a large array, the number of resize operations could be minimized.
- Epic_coder October 20, 2012Hi Ajit,
In this problem, it doesn't matter where you insert/delete the element because the only read operation defined for this data structure is get_random().
If there was an operation defined where you have to lookup the index of a particular element(say get element at ith position), in that case I would bother about inserting/deleting at a particular position.
Please explain your solution in english language because it's easier to follow than Java.
- Epic_coder October 20, 2012I never like the idea of suggesting hash table for such problems because implementing a hashtable that gives you O(1) insertion and deletion is a big problem in itself. In this problem we are not required to lookup the element in O(1) time and we should exploit that fact.
My idea is to use a very large array and use it to implement a stack using this array. So
1. you can insert only at the top, O(1) time,
2. you can delete only from the top again O(1) time and
3. for finding random element, suppose that we have n elements in the array at the instant we have to generate a random number. Random number would be rand(n)th element of the array, where rand(n) is a random number generator between 0 and n-1. Again O(1) time.
Note that there is always a possibility of running out of space and in that case we'll have to expand the array(which could be visualized as equivalent of rehashing in hash tables)
^^ You are right.
For making this to work, we'll have to flip all the 1s in a group when we find the first 1 in a group. A recursive function could be written to keep flipping all the neighbor ones. So,
Do for each element that is 1
--if all of its neighbors are 0, count=count+1,
--otherwise, count=count+1 and call flipbits()
flipbits() would flip all the 1s in a group when we find the first 1 in the group.
flipbits(i,j){
bit(i,j)=0;
if(bit(i+1,j)==1) flipbits(i+1,j);
if(bit(i,j+1)==1) flipbits(i,j+1);
if(bit(i,j-1)==1) flipbits(i,j-1);
if(bit(i-1,j)==1) flipbits(i-1,j);
return;
}
count is the result.
I think it's still O(n*m)
Well use a+b = (a^2 - b^2)/(a-b)
If a=b, just do a+b=2*a
as simple as that!
RepI am a good learner
Repannavhedge4, AT&T Customer service email at ABC TECH SUPPORT
Hi everyone, I am from Worcester,USA. I currently work in the Argus Tapes & Records as Scientific illustrator . I love ...
I guess the number of subarrays with number of 0s equal to number of 1s is proportional to n^2. How is it feasible to find all such subarrays in less than O(n^2) time.
- Epic_coder May 04, 2013Example test case: 01010101010101