iictarpit
BAN USER- 0of 0 votes
AnswersIn a circle there are N number of Gas filling stations which can provide you will gas of capacity C1, C2…CN. Distance between filling station is D1, D2, D3……DN. Considering your vehicle will consume 1 volume of gas per distance. Find the filling station from which you should start the journey so that you will never get short of Gas.
- iictarpit in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
Create a bitmap of c_set. size of this bitmap would depend upon on the Universal set of characters we are expecting and only those bits corresponding to characters in c_set will be set.
For each word in w_set create a bitmap similar to the one for c_set. Then if AND of bitmap(c_set) & bitmap(w in w_set) == bitmap(c_set). Then c_set covers w_set else continue with other words in w_set.
This method has one shortcoming.
It can not handle the situation when c_set contains characters more than once.
Complexity : O(n)
First find the differences C1-D1, C2-D2,C3-D3…..CN-DN. Differences represent the excess gas or gas shortage of gas to reach the next station. Ideally we should start from a station which will give us maximum cumulative excess gas.
If we apply variant of Kadane Algorithm(maximum subsequence algorithm) for circular List. Then we will get the starting point.
We need to take care of one more corner case that sum of all (cx-dx) is negative then there is no solution possible.
Approach 1:
Use a circular linked list, for the first N calls keep adding items to the LL.
Maintain pointer to currently added element. From N+1th call see if the oldest item (currentElement.next) timestamp is less than current item – X. if it’s the case replace the timestamp and move the currentElement pointer to this element. If it’s not the case return false.
Time Complexity O(1)
Space Complexity O(N).
Approach 2:
If we take first call time as a reference (t0) then in idealistic case when events are generated with N/X frequency then function should return all true.
From this reference, suppose last event occur in interval t0 + (N/X)x, then if next occur after t0 + (N/X)x + N/X return true else false.
So we need to store interval of only last event, thus space complexity O(1)
Time Complexity O(1)
for 1 dimension array this problem can be solved with complexity O(m), (www(dot)geeksforgeeks(dot)org/archives/20586) m being the length of each row. if we make nc2 combination of rows and sum them up and apply the same algorithm as for 1D row. Hence Complexity O(n^2*m).
- iictarpit November 27, 2012We need to fix backtracking with memorization. for the example given in the question if f(n) represents the number of paths from nth node. then f(1) = f(2)+f(3) + f(5) directly connected nodes.
f(1) = f(2)+f(3) + f(5)
f(1) = (f(3) + f(5)) + (f(4) + f(5)) + f(5)
f(1) = ((f(4) + f(5)) + f(5)) + (f(5) + f(5)) + f(5)
f(1) = ((f(5) + f(5)) + f(5)) + (f(5) + f(5)) + f(5) = 6 as f(5) = 1.
here we are calc f(3) twice which we can store and reduce calc
There is a problem with your solution. while creating array containing combination of sum of two numbers, we may end up having sum with overlapping number.
for example 3, 5, 7, 4,... is array and we are searching for 20 then we may have generated sum (3+5= 8), (5+7 =12) and both will sum to 20 which have count 5 two times.
if we start writing from right we may loose information
example a1b1c3
abccc
if we start writing from left we may loose information
example a3b1
aaab
better example would be the combination
Ques: a 3 b 1 a 1 c 3
I No. of char can be written: 1 2 3 4 5 6 7 8
II No. of char req to be written :1 3 4 4 5 5 6 8
III = I - II: 0-1-1 0 0 1 2 3
ans: a a a b a c c c
fill right to left until III is negative and fill left to right until III is positive
if we start writing from right we may loose information
example a1b1c3
abccc
if we start writing from left we may loose information
example a3b1
aaab
better example would be the combination
Ques: a 3 b 1 a 1 c 3
I No. of char can be written: 1 2 3 4 5 6 7 8
II No. of char req to be written :1 3 4 4 5 5 6 8
III = I - II: 0-1-1 0 0 1 2 3
ans: a a a b a c c c
fill right to left until III is negative and fill left to right until III is positive
RepI am working as a Software quality assurance analyst in Turtle's Records company. I look for flaws and weaknesses ...
Reptanyamayst, Android Engineer at ABC TECH SUPPORT
I am an experienced project support officer seeking a team focused on excellence and accelerated performance in a BMO company ...
Repnatetouche, Applications Developer at Alcatel Lucent
My name is NateTouche . I currently live in Seattle . One desire that has always been a constant since As a ...
RepHelanZelda, Consultant at Advent
HelanZelda from Atlanta, GA, United States. I have a passion for exploring/sharing new ideas and experiences throughout the interdisciplinary ...
traverse each node and merge edges in this order.
- iictarpit February 15, 20131. with both vertices -ve and (*) op, as this will increase the +ve vertices in polygon.
2. with one vertices +ve and one -ve and op (+). this will try to nullify the -ve of nodes.
3. with one vertices +ve and one -ve and op (*).
4.with both vertices -ve and (+) op,
as in 4 pass we will merge all the edges with maximum result.