Vicky, Yup! you got it there.
BTW you might like to do binary search again instead of sequential
search when you hit the break condition.
to indeed make it O(logn).
Infact if M=3^n is given then this algo would be of complexity O(log
log M)
_dufus
On Sep 23, 11:59 am, vicky wrote:
> ok i can
html <http://www.seeingwithc.org/%0Atopic1html.html>]
> > would give 2000=1000+1000.
>
> > Thats not the case with an ATM machine.
>
> > On Sep 20, 10:21 am, Dufus wrote:
> > > Is it different from classic Coin Denomination problem?
>
> > > _dufus
>
&
Is it different from classic Coin Denomination problem?
_dufus
On Sep 19, 11:20 pm, eSKay wrote:
> for example: if I draw 2000, what I get is
> 1000+500+100+100+100+100+100.
>
> What algorithm can be used to decide how to break up the entered
> amount?
--~--~-~--~~~
It seems it is possible to have unreachable destnation matrix.
However I have last query.
Is it possible to use initial and final matrix to determine if one is
reachable from other through toggle operations without actually
performing them?
_dufus
On Sep 19, 8:21 pm, Dufus wrote:
> Does
Does it means that every M*N matrix is reachable from a given M*N
matrix.
In other words is it possible that there is no sequence of toggle
operation using which the final matrix can be reached?
_dufus
On Sep 19, 5:54 pm, MrM wrote:
> its a beautiful classical problem :)
> first its easier to f
here every time I proposed a solution the interviewer
came up with an explanation that the probability is not 1/7 :(
_dufus
On Sep 8, 5:36 pm, ankur aggarwal wrote:
> @dufus
>
> tell me 1 thing
> do we have to make algo so that the prob is 1/7 or do we have to make so
> that
refer to
http://quantfinanceinterviews.com/resources/sample1.pdf
_dufus
On Sep 14, 2:16 pm, ankur aggarwal wrote:
> @dufus
> plz clearify
> i know u have something in mind..
>
> thanxs
>
> On Sun, Sep 13, 2009 at 11:26 PM, Dufus wrote:
>
> > Old wine in new bottle.
&
@Anil
Thats right O(n,n) time complexity for k=O(n).
Still it is better than Rama's O(n*m*log k)
which would be order O(n.n.logn) in worst case.
// sorry for the delay in response. I was away for a week with no
access to internet
_dufus
On Sep 15, 11:19 am, Anil C R wrote:
> @du
Old wine in new bottle.
Try induction.
_dufus
On Sep 13, 10:23 pm, Dave wrote:
> Except that the craftiest demon only pretends to take a bite. When the
> others fall asleep, he chows down.
>
> Dave
>
> On Sep 13, 7:24 am, jaspreet singh
> wrote:
>
> > the demons share the sleeping man amongst
@Dave : DFS doesnt work that way. you might like to brush up tree
traversal :D
_dufus
On Sep 13, 10:27 pm, Dave wrote:
> Suppose the graph consists of three nodes in a triangle. You number
> your starting node at level 1 and the other two at level 2. How do you
> proceed?
>
> Dave
>
> On Sep
Cant agree more!
_dufus
On Sep 13, 10:10 pm, Dave wrote:
> The following assumest that n >= 5. Find the 3 largest positive
> numbers and the two largest-in-magnitude negative numbers (i.e., the
> two smallest signed numbers).
>
> If there are not two negative numbers, the 3 largest positive num
@Gene : Smooth :)
How did I miss such an elegant solution..Duh
_dufus
On Sep 13, 7:27 am, Gene wrote:
> On Sep 6, 5:28 am, ankur aggarwal wrote:
>
> > google question : find triangle in a graph Given an undirected graph,
> > design a O(V+E) algo to detect whether there is a triangle in the
@Ankur:
Sorry I didnt get your point.
Did you mean that there will be repeated elements in Z[]?
If that so is that a problem?
_dufus
On Sep 12, 6:51 pm, ankur aggarwal wrote:
> @dufus
>
> lokking at your soln of young tableau
> i think there is a problem of repition of some nu
Hardest part of this problem is to prove that the generated number
INDEED follow uniform distribution :D
_dufus
On Sep 8, 6:57 am, Dave wrote:
> Use the rejection technique, something like this:
>
> do
> {
> do
> U1 = random_1_to_5();
> while( U1 == 5 );
> // At this point, U1
, 2009 at 9:02 PM, Dufus wrote:
>
> > The following approach might work.
> > Let K be the maximum degree of a vertex in the graph
> > Enumerate each of the n vertex as 1...n
> > Enumerate undirected edge between vertex i and j (i.e. i--j) as
> > (i,j)
>
&g
@ Ankur,
IMHO suffix tree is ONE of the solution.
_dufus
On Sep 3, 7:37 am, ankur aggarwal wrote:
> only suffix tree is the soln i think..
>
> On Wed, Sep 2, 2009 at 11:20 AM, nitin mathur
> wrote:
>
>
>
>
>
> > Hi everybody..
>
> > I am sorry as the algorithm I proposed takes O(n^2) and not
How about counting sort in O(N+K) time and O(K) space.
_dufus
On Sep 6, 1:06 pm, ankur aggarwal wrote:
> You have N balls having one of K colors. Arrange them into groups of same
> colors. e.g.
>
> RRGRG
> can be arranged as
> RRRGG (Answer)
> GGRRR
--~--~-~--~~---
The following approach might work.
Let K be the maximum degree of a vertex in the graph
Enumerate each of the n vertex as 1...n
Enumerate undirected edge between vertex i and j (i.e. i--j) as
(i,j)
Sort all the |E| edges in O(|V| + |E|) time // radix sort.
Now (i1,i2,i3) form a triangle iff
If Z[] is allowed to modify then i think we can do in O(1) space //
quite clear from the link I have posted above
else we need O(k) space to restore Z[].
_dufus
On Sep 6, 2:32 pm, ankur aggarwal wrote:
> @dufus
> wat is your complexity ??
>
> On Sat, Sep 5, 2009 at 8:17 PM,
In that case I would sacrifice a little bit on time complexity and
instead of storing I would recompute the values.
_dufus
On Sep 5, 5:10 pm, ankur aggarwal wrote:
> @dufus..
> if there is constant space requirement then ??
> wat will be your soln ??
>
> On Sat, Sep 5, 2009 at
It seems EXTRACT_MIN for Z[n^2] can be done in O(n) time.
http://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pdf
Then using it we can find the kth smallest element in O(nk) time.
_dufus
On Sep 4, 10:03 pm, ankur aggarwal wrote:
> Find nth smallest inO(n) Given two arrays of length
Try http://en.wikipedia.org/wiki/Fourier_division
_dufus
On Sep 4, 10:36 pm, ankur aggarwal wrote:
> Write an algorithm two divide two extremely large numbers, which cannot be
> stored in an int, long int, float, double etc. Find the remainder and
> quotient .
--~--~-~--~~---
I think in order to in O(logn) we need to find the end point of the
sorted sequence.
Unless we know more about the unsorted part (ex can unsorted contain
small sorted sequences)
I do not think we can do it in O(logn).
What if I have sequence like..
[1,2,3,4,5,6,0,8,9,10,...]
here n = 6 (but no
I don't this would work for all cases.
Infact the problem is not with your solution but with question
statement.
An unsorted sequence might contain small sorted sequence interleaved
by unsorted sequences. (Nothing in the problem statement rules out
this possibility)
So if you have something like
Nice :-)
That doesnt even require O(k) extra space.
_dufus
On Sep 1, 8:36 pm, Shishir Mittal <1987.shis...@gmail.com> wrote:
> @Nagendra : As earlier told Refer Pg 189, Cormen, an algorithm is given to
> find the Kth largest element in O(n) *worst* time complexity.
>
> @Dufu
e of the element and the median found ie
>
> int compare (int a, int b, int median){
> return ( abs(median - a) - abs(median - b)) ;
>
> }
>
> Overall time complexity : O(n), space complexity : O(1).
>
> On Sun, Aug 30, 2009 at 8:36 PM, Dufus wrote:
>
> > I
@Nitin, your algorithm, as you know takes O(n) extra space.
Arguably the next step of the interviewer would be to ask for O(1)
space algorithm :D
_dufus
On Aug 31, 5:37 pm, nitin mathur wrote:
> We can use the concept of longest common substring. For that use following
> steps:
> 1) take the
This is one of the most difficult dynamic programming problem I have
faced so far.
A good discussion on this problem and different solutions can be found
at
http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/
_dufus
On Aug 31, 6:01 pm, ankur aggarwal wrot
Rama, can you explain your O(1) time and additional O(n) space
algorithm to check if a node is in a locked state.
Trust me it is more difficult then it sounds.
_dufus
On Aug 31, 4:01 am, Ramaswamy R wrote:
> To begin with I find the invariant doesn't hold in the system progressively.
> Forget
Rama, I cannot agree with you more here.
On Aug 31, 5:34 am, Ramaswamy R wrote:
> When we talk of a binary search tree having O(log n) complexity for search,
> that does assume that the tree is fairly balanced. And of course the that
> fact we talk of average case. For any tree the worst case wo
Is it acceptable if I
find the median in O(logn) time and then,
find k numbers closest to the median in O(k) space and O(n) time?
_dufus
On Aug 30, 4:38 pm, Nagendra Kumar wrote:
> Given a set S of n distinct numbers and a positive integer k <= n.
> Determine the k numbers in S that are closes
y locked).
otherwise node i is in a unlocked state
}
Phewthat was one long post.
I hope I made myself clear.
_dufus
On Aug 30, 4:21 pm, Nagendra Kumar wrote:
> @Dufus.
> if d is locked then only b,a,g,h cannot be locked .But
> c,f,e,i,j can be locked.
>
>
>
> On
. once d is locked no other node in the
tree can be locked)!!!
I think something is wrong here.
Nagendra/Priya any comments?
_dufus
On Aug 30, 11:10 am, priya k wrote:
> @Dufus: You mean to say do preprocessing and hash all the nodes that cannot
> be locked, if am not wrong. And again, Eve
Priya, as mentioned by you your isLock() takes O(logn) time.
We need to use Hash table as auxillary DS for O(1) query time.
_dufus
On Aug 30, 8:35 am, priya k wrote:
> // Data Structure for the n-ary tree
>
> struct node
> {
> int data;
> node * child[m];
> bool lockFlag; // Indicates
Hi Nima,
I think what you are doing is finding the NUMBER OF PATHS rather then
THOSE PATHS as sequence of nodes.
Counting number of paths between two given nodes is pretty straight
forward using DFS (Refer CLRS)
You might be using this information to yield the paths as sequence of
nodes but could
@ Ankur,
This problem looks deceptively simple but unfortunately its not and
DFS alone cannot solve this problem.
Consider the following case in point :-
C
A-->B / \D--->E
\ F/
Directed Edges are {A->B, B->C, C->D, D->E, B->F, F->D}
If we want to find all the possible path
Vivek, you did pretty good there.
I tried solving it through dynamic programming but failed to find the
optimal substructure.
_dufus
On Aug 26, 9:57 pm, Vivek S wrote:
> let A[i+1] = a[0] + a[1] + ... + a[i];
> let B[i+1] = b[0] + b[1] + ... + b[i];
> A[0] = B[0] = 0;
> sum of nos from i to j
I think this problem is same as topological sorting with n1 as start
node and n2 as finish node.
Can be done using DFS.
_dufus
On Aug 26, 1:33 pm, ankur aggarwal wrote:
> given a directed graph and node n1 and n2
> find all possible path between them
>
> i think graph is acyclic ..
> otherwis
Lets say the given matrix M is :-
a1,1 a1,2 a1,c
a2,1 a2,2 . a2,c
.
.
.
ar,1 ar,2 ...ar,c
I think matrix M can be converted to a null matrix if,
i) all the elements of a row i are of the form (Ki+2^q) for some
constant Ki and any non negative integer q.
ii) Property (i) is
wer then would be N-1 th Catalan Number,
i.e (2N-2)!/N!(N-1)!.
If the companies aren't identical ,with some permutations also getting
into the picture, then the solution isn't straightforward and we
couldn't figure it out.
/dufus/
On Aug 24, 11:58 pm, ankur aggarwal wrote:
>
, Nagendra Kumar wrote:
> How are u doing with xor. Can u post ur thought here.
>
> Thanks
> Nagendra
>
>
>
> On Sun, Aug 23, 2009 at 2:07 AM, Dufus wrote:
>
> > We can count or XOR but I couldnt find any advantage of XORing except
> > for preventing overflow.
>
>
Aug 22, 2009 at 11:21 AM, Dufus wrote:
>
> > I can think of a naive algorithm which takes O(n) time and O(n) space.
> > or O(nlogn) with O(1) space.
>
> > May be someone else might come up with a better algo.
>
> > _dufus
>
> > On Aug 21, 3:01 pm, nagendra kuma
I can think of a naive algorithm which takes O(n) time and O(n) space.
or O(nlogn) with O(1) space.
May be someone else might come up with a better algo.
_dufus
On Aug 21, 3:01 pm, nagendra kumar wrote:
> Given an array of integers,Print the integers whose appareance are in
> odd times.
>
AFAIK, searching an element in sorted matrix (Young's Tableau) takes O
(n) time.
So I am not sure if O(logn) is actually possible.
_dufus
On Aug 20, 6:41 pm, nagendra kumar wrote:
> How can we find an element in the matrix [n*n] which is sorted row
> wise and column wise in O(log n).
--~--~-
ts and increment its
frequency count. Else create a new node with frequency count 1 and
character = and add i to the heap.
Given the above description above I think the input cases pointed out
by you can be worked out.
_dufus
On Aug 17, 12:15 am, richa gupta wrote:
> @dufus :
>
> su
Reverse Array sum problem
Suppose you had two arrays A and B of length n in reverse sort order
and computed the array C of length n*n by taking all possible sums of A
(i) + B(j) and then you sorted array C.
Find an algorithm to reverse the process to find A and B given C and
assuming you already
we can search for the existence or non-existence of a new
character in O(1) time. Hence the only bottle neck would be heapify
operation O(log N) time (instead of O(N) time).
_dufus
On Aug 17, 12:15 am, richa gupta wrote:
> @dufus :
>
> suppose the words occurs like ( at the last of the
= m ; j>=0 ; j--)
> if(DP[j]) break;
>
> so the answer is
>
> j and SUM - j
>
> Arun,
>
>
>
> On Sat, Aug 15, 2009 at 1:02 PM, Dufus wrote:
>
> > Plz refer to
> > Balanced Partition Problem or
> > Integer Partition Problem at
&g
(1)
Inserting the new typed element at root O(1)
heapifying O(K)
_dufus
On Aug 14, 10:45 pm, richa gupta wrote:
> @ Dufus,
> suppose words A, B,C, D occurs at the frequacny 4, 2, 7 ,1 then the code
> shud be able to list it like C, A, B, D .
>
> On 2009-08-14, Dufus wrote:
>
Plz refer to
Balanced Partition Problem or
Integer Partition Problem at
http://people.csail.mit.edu/bdean/6.046/dp/
On Aug 14, 10:26 pm, fundoonick wrote:
> @DufusCan u pls give the algorithm about how to do this?
>
>
>
> On Fri, Aug 14, 2009 at 8:56 PM, Dufus wrote:
>
&
@Arun: Did you get the job? (No offence meant)
@Richa: Could you please elaborate what decreasing order means?
Assuming decreasing order means ..last word should be printed in the
end..and if the user adds (appends) new word then it should also be
printed,
this can be done quite elegantly using si
I totally agree with manish here.
question is missing the "key element" which makes it the "aha
question".
Without its just plain question doing it in O(n) space is no fun.
_dufus
On Aug 11, 11:21 pm, manish bhatia wrote:
> Well instead of using extra memory, we can in-place sort the arraay in
If the range is given then it get reduced to a standard problem which
can be solved by DP in O(k.n^2) time..where n integers within range
0...K have to be partitioned in two sets S1 and S2 such that the
difference of sum of their elements is min.
_dufus
On Aug 14, 6:27 pm, fundoonick wrote:
> P
53 matches
Mail list logo
