from:"Dumanshu"

[algogeeks] Re: google question

2012-02-26 Thread Dumanshu

You are assuming is to be a binary tree, its not. Some nodes will
share a common pour.

On Feb 25, 9:24 pm, atul anand atul.87fri...@gmail.com wrote:
 i guess this would work...
 n=number of nodes
 h=height;
 pour=quantity poured;
 capacity = capacity of each cup

 n=pow(2,h+1) -1;
 call(capacity,pour,0,n)

 node* fillCup(float capacity,float pour,int left,int right)
 {
 node *root;
 int mid;
 if(left  right)
 return NULL;

 root=(node *)malloc(sizeof(node));
 if(left==right)
 {
 if(pour =capacity)
 root-data=capacity;
 else
 root-data=pour;
 root-left=root-right=NULL;}

 else
 {
 mid=left+(right-left)/2;
 if(pour = capacity)
 {
 root-data=capacity;
 pour=pour-capacity;
 pour=pour/2;}

 else
 {
 root-data=pour;
 root-left=root-right=NULL;
 return root;

 }

 root-left=fillCup(capacity,pour,left,mid-1);
 root-right=fillCup(capacity,pour,mid+1,right);

 }

 return root;

 }

 On Sat, Feb 25, 2012 at 5:05 PM, Ravi Ranjan ravi.cool2...@gmail.comwrote:







  |_|
  |_| |_|
  |_| |_| |_|
  |_| |_| |_| |_|
  |_| |_| |_| |_| |_|

  Each cup has capacity C and once a cup gets full, it drops half extra
  amount to left child and half extra amount to right child

  for Eg : let' first cups get 2C amount of liquid then extra amount C(2C-C)
  will be divided equally to left and right child cup of next level

  i.e. C/2 to left child and C/2 to right child

  Write a function which takes input parameter as amount of liquid poured at
  top (L) and height of particular cup (h) index of that cup (i) and it
  should return amount of liquid absorbed in that cup.

  source

 http://www.careercup.com/question?id=12770661

  whats exactly the qestion???

  --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Google Question--Suggest Algo

2011-11-28 Thread Dumanshu

Hi

I may not have understood your solution properly. But i think that
your solution is an implementation of brute force where you are
dealing with all cases valid in the range n/2k and 3n/2k without any
optimization with regard to DP. Am i right?

On Nov 28, 2:17 am, sourabh sourabhd2...@gmail.com wrote:
 Consider the example that you have given:
 [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3

 Now we need to partition the array into 3 contiguous sub arrays such
 that :
 a) The expected sum value is maximum
 b) and the size of each sub array should be between 2 and 6, both
 inclusive. In case, this constraint is not satisfied then its not a
 valid candidate for the solution even if the partition produces the
 max value.

       2 = ceil (n / 2k) = ceil (12/6)
       6 = floor (3n / 2k) = floor (36/6)
 -
  As mentioned above the following equation :
 F(n,k) = MAX for all r such that ceil(n/2k) = r =  floor(3n/2k)
 { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
 k-1) }

 /**
 For understanding how partitioning of the array is represented by the
 above equation:

 Say there is an array denoted by A[i] and it needs to be divided into
 3 contiguous parts, one of the ways to do so would be to take the
 following steps :

 Let K(partition no.) be initialized to 3.
 Let array size N be 12.

 a) If N is 0, the goto step 'f'
 b) If K == 1 then call it as partition K and goto step 'e'.
 c) Lets take X no. of elements from the end of array A of size N and
 call it partition K.
 d) Decrement K by 1 and N by X { --K; and N-=X;}
 d) Goto step 'a'
 e) Valid partition and End.
 f) Not a valid partition and End.

 Now if the above set of steps is run for all values of X such that
 2=X=6 , then it will generate all possible candidates (partitions)
 as per the given problem statement. And for all the valid
 partitions(the ones that will hit step 'e') we need to calculate the
 expected sum value.
 **/

 can be translated into,
 // I am using 1-based array indexing for better clarity
 // A[x .. y] means all elements from A[y] to A[x]..

 F(12, 3) = MAX
                        {
                           ExpVal (A[12 .. 11])  +  F(10, 2) ,
                           ExpVal (A[12 .. 10])  +  F(9, 2) ,
                           ExpVal (A[12 .. 9])    +  F(8, 2) ,   //
 this will yield the maximum sum..
                           ExpVal (A[12 .. 8])    +  F(7, 2) ,
                           ExpVal (A[12 .. 7])    +  F(6, 2)
                        }

 which is nothing but,
 F(12, 3) = MAX
                        {
                           1/2  +  F(10, 2) ,
                           2/3  +  F(9, 2) ,
                           2/4  +  F(8, 2) , // this will yield the
 maximum sum..
                           3/5  +  F(7, 2) ,
                           4/6  +  F(6, 2)
                        }

 Trace the above equation and you should get it..

 On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:







  Hey Sourabh

  Could you please explain the solution in a bit detail perhaps using an
  example or so..It wud be really helpful ..Just logic not code

  On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote:
   Looks like a dynamic programming problem

   Say F(n,k) denotes the maximum expected sum value for an array of n
   elements and partition k , then

   F(n,k) = MAX for all r such that ceil(n/2k) = r =  floor(3n/2k)
   { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
   k-1) }

   Base condition:
   1) F(N, 1) = expected value for array A[n] such that  ceil(n/2k) = N
   =  floor(3n/2k)
   2) If any of the sub problems where the array size is not between
   ceil(n/2k) and  floor(3n/2k) , both inclusive, then its not a valid
   candidate for the final solution. This is can be handled by giving
   initial value to all such combination a value of -1.

   To store that the intermediate computations take an array Max[N][K],
   F(N,K) = Max[N][K]

   On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.

On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote:

 Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
 Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
 why this is not the optimal split???

 On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
   wrote:
  You have an array with *n* elements. The elements are either 0 or 1.
   You
  want to *split the array into kcontiguous subarrays*. The size of
   each
  subarray can vary between ceil(n/2k) and floor(3n/2k). You can
   assume that
  k  n. After you split the array into k subarrays. One element of
   each
  subarray will be randomly selected.

  Devise an algorithm for maximizing the sum of the randomly selected
  elements from the k subarrays. Basically means that we will want to
   split
  the array in such way such that the

[algogeeks] Re: Facebook Campus Test Question

2011-11-04 Thread Dumanshu

plz post a samle input output..

On Nov 4, 10:24 am, sunny agrawal sunny816.i...@gmail.com wrote:
 What can be a better solution than a Brute Force O(N^2* No of iteration)

 --
 Sunny Aggrawal
 B.Tech. V year,CSI
 Indian Institute Of Technology,Roorkee

  fb1_input.txt
  1KViewDownload

  facebook.jpg
 119KViewDownload

  fb1_output.txt
  1KViewDownload

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Facebook Campus Test Question

2011-11-04 Thread Dumanshu

is ur brute force O(1) for space?

On Nov 4, 10:24 am, sunny agrawal sunny816.i...@gmail.com wrote:
 What can be a better solution than a Brute Force O(N^2* No of iteration)

 --
 Sunny Aggrawal
 B.Tech. V year,CSI
 Indian Institute Of Technology,Roorkee

  fb1_input.txt
  1KViewDownload

  facebook.jpg
 119KViewDownload

  fb1_output.txt
  1KViewDownload

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Intersection of arrays

2011-10-28 Thread Dumanshu

I think Dan's solution is the best one here. TC O(n log n) and SC O(1)
where n is the maximum no. of elements in any array
Instead of starting with K given arrays, just take the first 2.
Sort both of them - time is nlogn
Now run two pointers on each array to save the common elements as they
are and clear the rest in 1st array. Discard 2nd array now.
We have 1st array with intersection elements only.
Now continue the same thing - With 1st array and 3rd array. Sort 3rd
array. Keep common elements in 1st array and clear the rest.

Keeping common elements in 2 arrays and clearing the other elements
can be done in O(n) TC.

On Oct 25, 11:17 am, kumar raja rajkumar.cs...@gmail.com wrote:
  Find intersection of K unsorted array of N elements each. Intersection
 consists of elements that appear in all the K arrays.

 what data structure is useful here??

 --
 Regards
 Kumar Raja
 M.Tech(SIT)
 IIT Kharagpur,
 10it60...@iitkgp.ac.in

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Amazon OS question

2011-10-28 Thread Dumanshu

How are we going to write a program which if fed the data gives the
answer?

Any ideas for the algorithm?

My approach:
We have a graph here.
We have vertices with indegree 0 and outdegree 1. - call it set A
(start points) (m vertices)
We have vertices with indegree 1 and outdegree 0. - call it set B (end
points) (n vertices)
The paths from set A to set B can be run on multiple processors (m x n
paths possible).
if no. of processors = m x n then no. of steps will be maximum no. of
elements in any path.
In the above ques, m = 1 and n = 3.

if no. of processors  m x n, then run a BFS on the graph and find the
number of vertices at each level.
In the above question, the vertices at levels are 1, 1, 3 , 1.
((Max of these i.e. 3) / number of processors) + maximum no. of
elements in any path  = would be the answer.
Now this part would have a problem if m!=1;
Another problem would be how to find the maximum no. of elements in
any path possible.



On Sep 25, 9:03 am, sivaviknesh s sivavikne...@gmail.com wrote:
 A parallel program consists of 8 tasks – T1 through T8. Each task requires
 one time step to be executed on a single processor. Let X - Y denote the
 fact that task X must be executed before task Y is executed. Suppose only
 the tasks X, Y are to be executed. On any multiprocessor machine it would
 require at least 2 time steps since in the first step X could be executed,
 and Y could be executed in the next time step (since it requires X to
 complete first). Now, suppose the following dependencies exist between the
 tasks T1 – T8:

 T1 - T2

 T2 - T3

 T3 - T6

 T2 - T4

 T4 - T7

 T2 - T5

 T5 - T8

 What is the minimum number of time steps required to execute these 8 tasks
 on a 2 processor machine and a 4 processor machine?

 a)4  2

 b)5  2

 c)5  4

 d)6  2

 --
 Regards,
 $iva

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: google os ques on pipelining

2011-09-26 Thread Dumanshu

@bharat:
for the second part where u multiplied (160+5) with 999, it should be
160*999 because it is max of (150,120,160,140,5). Correct me if i am
wrong.

On Sep 26, 4:02 pm, bharatkumar bagana bagana.bharatku...@gmail.com
wrote:
for the first instruction : 150+5+120+5+160+5+140=585 ns
for the rest of the instructions , though pipeline
max(150,120,160,140)=160

(160+5)*999=164835 ns
we assume that there will be no extra stalls existed in our system
-585 + 164835 =165420 ns =165.4 us...
correct me if I'm wrong .

On Sun, Sep 25, 2011 at 9:25 AM, siva viknesh sivavikne...@gmail.comwrote:

A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 ns
(nano seconds)
respectively. Registers that are used between the stages have a delay
of 5 ns each. Assuming
constant clocking rate, the total time taken to process 1000 data
items on this pipeline will
approximately be
a. 120 us (micro seconds)
b. 165 us
c. 180 us
d. 175 us

...plz give detailed explanation for the ans

--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.

**Regards
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com

[algogeeks] Re: convert a word into a palindrome with minimum addition of letters to it

2011-09-07 Thread Dumanshu

@Victor:

Instead of 0 and 1, shouldn't it be like DP[i-1][j-1]  + 0 and DP[i-1]
[j-1] + 1


On Sep 7, 1:10 am, Victor Manuel Grijalva Altamirano
kavic1.mar...@gmail.com wrote:
 Try with DP, a little modicated of Edit Distance algorithm

 State i=the begin of the word , j=the end of the word

 DP[i][j]=   0           if i==j
                0          if(i+1)==j   word[i]==word[j]
                1          if(i+1)==j   word[i]!=word[j]
             min(DP[i+1][j]+1,DP[i][j-1]+1)   otherwise
 If you have any question ask!!!
 Good luck!!!

 Victor Manuel Grijalva Altamirano
 Universidad Tecnologica de La Mixteca

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: convert a string into another in minimum number of steps

2011-08-31 Thread Dumanshu

how to check if intermediate words are dictionary words or not?? Also
what would be the approach for that?

On Aug 31, 3:10 am, icy` vipe...@gmail.com wrote:
 Yea, I hope the intermediate words are dictionary words; it's  more
 fun that way.   I played such a game before, where you and a friend
 try to convert some 4-letter word into another, using legal words.

 BIKE -  LAZY

 BIKE
 BAKE
 RAKE
 RAZE
 LAZE
 LAZY

 On Aug 30, 2:25 am, kARTHIK R k4rth...@gmail.com wrote:







  So the intermediate words need not be dictionary words?

  Karthik R,
  RD Engineer,
  Tejas Networks.

  On Tue, Aug 30, 2011 at 11:50 AM, PRATEEK VERMA prateek...@gmail.comwrote:

   edit distance algorithm

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: How to save a binary search tree space efficiently

2011-08-30 Thread Dumanshu

Level Order traversal if you are ok with the Nulls being stored.
Otherwise its pre order traversal.

On Aug 30, 12:34 pm, Vidit Sinha vidit.it...@gmail.com wrote:
 whats the final answer guys? Level order traversal??







 On Tue, Aug 30, 2011 at 12:56 AM, Don dondod...@gmail.com wrote:
  I'm not sure if this is what you are looking for, but I once came up
  with a way to save a binary tree in such a way that when it is
  rebuilt, it will be balanced. You don't get back the exact same tree
  with all the nodes in the same position, but you do get the same nodes
  in a balanced configuration.

  Start by doing an inorder traversal and storing each node sequentially
  in an array.
  Then call a recursive function called saveTree(first, last), where
  first and last are the first and last indices of the array.
  saveTree does the following if:
  write middle item of array to the file
  call saveTree on left half of array
  call saveTree on right half of array

  When you rebuild the tree adding the nodes in the order in which they
  occur in the file, the resulting tree will be balanced.

  Don

  On Aug 28, 1:29 am, rohit rajuljain...@gmail.com wrote:
   How to save a binary search tree space efficiently and built it
   again , just tell any idea.

  --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: stack using bst

2011-08-26 Thread Dumanshu

So, in short you are using a BST and a FIFO linked list. Whereas, a
Stack is actually a LIFO linked list. Am i right?

On Aug 25, 11:37 pm, Don dondod...@gmail.com wrote:
 You will have to keep two pointers, one to the root of the tree and
 one to the head of the FIFO linked list.
 To push, insert the item into both the bst and the linked list.
 To pop, set a pointer to the first item in the linked list. Delete it
 from the bst. It will always be a leaf, so deleting should be easy.
 Follow the parent pointer up one level and set the appropriate left or
 right pointer to null. Then set the head of the linked list to the
 next item in the list. Return the pointer to the former first item.

 push(node n)
 {
   tree.insert(n);   // O(log n)
   n-next = stack;
   stack = n;

 }

 node pop()
 {
   node result = stack;
   if (result-parent-left == result) result-parent-left = 0;
   else result-parent-right = 0;
   stack = result-next;
   result-next = 0;
   return result;

 }

 I was mistaken when I said push was O(1). Later on I said O(log n)
 which is correct.

 Don

 On Aug 25, 1:25 pm, shady sinv...@gmail.com wrote:







  @don how will you keep track of the latest element inserted in a bst ?
  O(1) for pop ? similarly how to get O(1) for push ?

  Stack can be implemented with bst but the time complexity will increase.

  Anyone with different views ?

  On Thu, Aug 25, 2011 at 11:37 PM, Don dondod...@gmail.com wrote:
   The only way I see to be able to search in O(log n) and push/pop in
   O(1) would be to have each node contain 4 pointers: left, right, and
   parent pointers for the binary search tree and next pointer for the
   stack linked list. The stack would be a linked list using the next
   pointer, and the search tree would allow quick searching. Insertion
   and searching would be O(log n) as with any binary search tree. Pop
   would be O(1).

   If you don't need to be able to search, just use the left pointer to
   make a linked list. Push and pop are both O(1), but you don't have a
   binary search tree any more.

   Don

   On Aug 25, 12:00 pm, prasanth n nprasnt...@gmail.com wrote:
how to implement a stack(push and pop) using binary search tree??

--
*prasanth*

   --
   You received this message because you are subscribed to the Google Groups
   Algorithm Geeks group.
   To post to this group, send email to algogeeks@googlegroups.com.
   To unsubscribe from this group, send email to
   algogeeks+unsubscr...@googlegroups.com.
   For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: print all paths which sum up to a value.

2011-08-24 Thread Dumanshu

Any help regarding the preprocessing required for O(1) operation for
LCA??? I read the wiki's article involving eulers traversal.. but its
nt clear.

On Aug 24, 1:12 am, DK divyekap...@gmail.com wrote:
 Hmm.. Interesting question.

 *Here's a solution:*

 There are n elements in the tree and therefore n^2 paths in the tree
 (duplicate endpoints allowed and 2 endpoints correspond to exactly 1 simple
 path in the tree).
 1. For each node in the BST, store the sum of node values on the path to the
 root. Can be done using a simple DFS in O(N).
     Also perform preprocessing for the LCA function (required below).

 2. For each pair of nodes (u, v) in the BST: - O(N^2)
     Cost of path = Cost(u, root) + Cost(v, root) - Cost(LCA(u,v), root)
     If(Cost of path == value) print_path(u,v)

 The LCA is the lowest common ancestor of the given nodes 
 (See:http://en.wikipedia.org/wiki/Lowest_common_ancestor)
 LCA(u,v) is an O(1) operation given O(N) preprocessing of the tree.

 Therefore, we know for sure that we can do this problem in worst case
 O(N^2).

 *Optimizations: *I'm not sure any of these yield worst case bound
 improvements but here are a few things that you can do:
 1. Get rid of symmetry: (u, v) is the same as (v, u). Choose u  v always.
 2. For a chosen u, skip all children of v if target cost  v

 Time Complexity: O(N^2)
 Space Complexity: O(N)

 --
 DK

 http://twitter.com/divyekapoorhttp://www.divye.inhttp://gplus.to/divyekapoor

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Longest palindrome

2011-08-22 Thread Dumanshu

So, suggest some approach plz for this ques.

On Aug 22, 12:59 am, Dave dave_and_da...@juno.com wrote:
 @Sanjay: Will method 1 really work? What would it return on the string
 abraxyzarba? The longest common substring between this string and
 its reverse is abra, but how does that relate to the fact that the
 longest palindrome is any single letter of the string? What am I
 missing?

 Dave

 On Aug 21, 1:46 pm, anurag saxena anurag.saxen...@gmail.com wrote:







  method 1) : we can reverse the string and find the longest common
  substring occurring in reversed string and original string.

  method 2) : making a generalized suffix tree of string and reversed
  string and each node should depict whether the suffix  belongs to
  string or reversed string .. then the deepest node having both the
  marker will be longest palindrome.

  On 8/21/11, Sanjay Rajpal srn...@gmail.com wrote:

   i hvn't read about suffix trees. will u plz post a useful link ?

   Sanju
   :)

   On Sun, Aug 21, 2011 at 11:21 AM, MAC macatad...@gmail.com wrote:

   suffix tree will solve it .

   On Sun, Aug 21, 2011 at 11:46 PM, priya ramesh 
   love.for.programm...@gmail.com wrote:

   how abt goimg with brute force?? check  starting from first character if
   first 2 chars frm a palin, then chck if first 3 form a palin... continue
   until the end of string.

   Now starting from 2nd char, do the same.

   keep a var max to store the max value.

   --
   You received this message because you are subscribed to the Google 
   Groups
   Algorithm Geeks group.
   To post to this group, send email to algogeeks@googlegroups.com.
   To unsubscribe from this group, send email to
   algogeeks+unsubscr...@googlegroups.com.
   For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.

   --
   thanks
   --mac

   --
   You received this message because you are subscribed to the Google Groups
   Algorithm Geeks group.
   To post to this group, send email to algogeeks@googlegroups.com.
   To unsubscribe from this group, send email to
   algogeeks+unsubscr...@googlegroups.com.
   For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.

   --
   You received this message because you are subscribed to the Google Groups
   Algorithm Geeks group.
   To post to this group, send email to algogeeks@googlegroups.com.
   To unsubscribe from this group, send email to
   algogeeks+unsubscr...@googlegroups.com.
   For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text -

  - Show quoted text -

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: another q on ds!

2011-08-21 Thread Dumanshu

first option is correct. Because we are not allowed to use any extra
space.

On Aug 21, 6:36 pm, priya ramesh love.for.programm...@gmail.com
wrote:
 A Most efficient data structure is designed to optimize the following
 operations. Pop, Push, Min. The best possible time-complexities with no
 extra space, respectively would be:

 ·  Pick one of the choices

 O(1), O(1), O(N)

 O(1), O(N), O(1)

 O(N), O(1), O(1)

 O(1), O(1), O(1)

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: amazon q

2011-08-21 Thread Dumanshu

We can't use a heap. Balanced BST is correct because Deletion of the
smallest element Insertion of an
element if it is not already present in the set - for this we need
to search for the element and searching in heap is O(n).

On Aug 21, 6:16 pm, priya ramesh love.for.programm...@gmail.com
wrote:
 A data structure is required for storing a set of integers such that each of
 the following operations can be done in (log n) time, where n is the number
 of elements in the set. Deletion of the smallest element Insertion of an
 element if it is not already present in the set Which of the following data
 structures can be used for this purpose?

 ·  Pick one of the choices

 A heap can be used but not a balanced binary search tree

 A balanced binary search tree can be used but not a heap

 Both balanced binary search tree and heap can be used

 Neither balanced binary search tree nor heap can be used

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Algorithm complexity

2011-08-03 Thread Dumanshu

Check interpolation which is a substitute for binary search for a
uniformly sorted array. It has complexity of this order.

On Aug 3, 7:31 pm, Ajai Sathyan ajaisath...@gmail.com wrote:
  Can you suggest a sample program which has complexity O(log log n)?

 Regards
 Ajai Sathyan

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Subsequence with Sum S

2011-07-30 Thread Dumanshu

Given an array of length n of integer numbers. Output 1 or 0 depending
on whether or not there exists a sub sequence in the array with sum S.
Suggest a fastest algorithm plz.

e.g. say given an array with numbers as 10 20 30 40 50 60 70
Sum = 110

Output is 1 because 20+30+50 is 110.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: interview ques

2011-07-27 Thread Dumanshu

Use multilevel indexing

On Jul 27, 11:07 pm, himanshu kansal himanshukansal...@gmail.com
wrote:
 if u hv say 20 million records and u have to create a b+ tree then you
 might be storing 20 million pointers at the leaf levelhow can u
 optimize this(using b+ tree only)???

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: MS

2011-07-20 Thread Dumanshu

check the above solution.. urs is O(logn) mine is O(log k).

On Jul 19, 11:35 pm, sagar pareek sagarpar...@gmail.com wrote:
 well i dont think so...any better solution will be there compare mine one









 On Wed, Jul 20, 2011 at 12:00 AM, Dumanshu duman...@gmail.com wrote:
  heres the code
 http://ideone.com/rX130

  On Jul 19, 9:35 pm, swetha rahul swetharahu...@gmail.com wrote:
   Hi,
           Find the kth smallest element in O(logk) given 2 sorted arrays.
   Merging the arrays is not allowed. I can do it in O(k).. How to do in
   O(logk)..

  --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

 --
 **Regards
 SAGAR PAREEK
 COMPUTER SCIENCE AND ENGINEERING
 NIT ALLAHABAD

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Whats the complexity?

2011-07-20 Thread Dumanshu

Given an infinite length list. u got to find index of an element k.
use this approach-
initially, take length as 2^x where x increases from 1 to ...
while (still not found)
{
now if arr[2^x-1]  k,
 increment x
else
binarysearch on length 2^(x-1) to 2^(x)
}

Please help me to find the complexity of this particular approach...

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Axis Aligned Rectangles

2011-07-20 Thread Dumanshu

Describe  an  algorithm  that  takes an  unsorted  array  of  axis‐
aligned  rectangles  and returns  any  pair  of  rectangles  that
overlaps,  if  there  is such  a  pair.   Axis‐aligned means  that
all  the  rectangle  sides  are  either  parallel  or  perpendicular
to  the  x  and y‐axis.  You  can  assume  that each  rectangle
object  has  two  variables  in  it :  the  x‐y coordinates  of  the
upper‐left  corner  and  the  bottom‐right  corner.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Whats the complexity?

2011-07-20 Thread Dumanshu

that is why m confused. how would u rate this algo? in what order?

On Jul 20, 10:44 pm, Ankur Khurana ankur.kkhur...@gmail.com wrote:
 when n is not defined , you want complexity in terms of ?





 On Wed, Jul 20, 2011 at 3:16 PM, Dumanshu duman...@gmail.com wrote:
  Given an infinite length list. u got to find index of an element k.
  use this approach-
  initially, take length as 2^x where x increases from 1 to ...
  while (still not found)
  {
  now if arr[2^x-1]  k,
   increment x
  else
  binarysearch on length 2^(x-1) to 2^(x)
  }

  Please help me to find the complexity of this particular approach...

  --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

 --
 Ankur Khurana
 Computer Science
 Netaji Subhas Institute Of Technology
 Delhi.- Hide quoted text -

 - Show quoted text -

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Whats the complexity?

2011-07-20 Thread Dumanshu

it should involve the exponential increment! somebody plz help

On Jul 20, 10:56 pm, Ankur Khurana ankur.kkhur...@gmail.com wrote:
 in my opinion , it is log(indexof(k))





 On Wed, Jul 20, 2011 at 11:23 PM, Dumanshu duman...@gmail.com wrote:
  that is why m confused. how would u rate this algo? in what order?

  On Jul 20, 10:44 pm, Ankur Khurana ankur.kkhur...@gmail.com wrote:
   when n is not defined , you want complexity in terms of ?

   On Wed, Jul 20, 2011 at 3:16 PM, Dumanshu duman...@gmail.com wrote:
Given an infinite length list. u got to find index of an element k.
use this approach-
initially, take length as 2^x where x increases from 1 to ...
while (still not found)
{
now if arr[2^x-1]  k,
 increment x
else
binarysearch on length 2^(x-1) to 2^(x)
}

Please help me to find the complexity of this particular approach...

--
You received this message because you are subscribed to the Google
  Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
   http://groups.google.com/group/algogeeks?hl=en.

   --
   Ankur Khurana
   Computer Science
   Netaji Subhas Institute Of Technology
   Delhi.- Hide quoted text -

   - Show quoted text -

  --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

 --
 Ankur Khurana
 Computer Science
 Netaji Subhas Institute Of Technology
 Delhi.- Hide quoted text -

 - Show quoted text -

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Ever growing sorted linked list

2011-07-19 Thread Dumanshu

Some please give the TC for exponential + logarithmic search method
pointed out by Swathi.

On Jul 19, 11:51 am, Ankur Khurana ankur.kkhur...@gmail.com wrote:
 @sagar: you might have proposed a solution but it ever occured to you that
 (ptr-next)-next  means that you have gone through two diferent nodes. For
 saving one comparison , we are doing lot of un necessary computations which
 , IMHO is not good or feasible . Linked list are not made for searching
 purpose, for that arrays were made.

 On Tue, Jul 19, 2011 at 12:13 PM, sagar pareek sagarpar...@gmail.comwrote:







  hey
  check my algo...i mentioned all the possible cases   :)

  On Tue, Jul 19, 2011 at 11:31 AM, oppilas . 
  jatka.oppimi...@gmail.comwrote:

   Yes we can avoid integer comparison.

  But for jumping  we will need to check whether the next node is null or
  not.
  So, depending upon the jump size, the number of comparison in worst case
  can be very large if our jump size is increasing exponentially. So, why not
  just compare with the next node instead of jumping.

  On Tue, Jul 19, 2011 at 10:47 AM, sunny agrawal 
  sunny816.i...@gmail.comwrote:

  yes Alok u r right that in any case we will traverse k times if k is the
  position if the element that need to searched
  but by jumping we can save the time of avoiding unnecessary comparisions

  On Tue, Jul 19, 2011 at 10:44 AM, Alok Prakash 
  alok251...@gmail.comwrote:

  If i am not wrong, in a linked list to move to any number of position,
  say n, we have to traverse all intermediate nodes of the linked list.

  So, it does not matter if we are moving pointer by 2,4,8,... positions,
  we have to scan all intermediate nodes.

  Is it not a simple searching

  On Tue, Jul 19, 2011 at 9:17 AM, sumit sumitispar...@gmail.com wrote:

  Here is the idea I was thinking of:

  - start from the root: if(root-data  k) move to position 2 in the
  list.
  - in this way every time move the pointer to the position double the
  current position and compare th eelement of node with k( moving here
  is form 1 - 2 , 2-4, 4-8 ,8-16 ..)
  - suppose you found a certain node at position n whose node-data 
  k , then now u only have to search for k between index n/2 to n (i.e.
  if you found 16th element k then search for k between 8th and 16ht
  element)..

  correct me if any flaws.

  On Jul 19, 3:38 am, Dumanshu duman...@gmail.com wrote:
   @Gaurav: Ever Increasing means that you don't know the length of the
   list. So you have to assume some index n, traverse the list upto that
   point and check the results. If not found increment the n to some
   higher value.
   We are basically trying to improve the complexity by taking higher
  and
   higher jumps for n.

   On Jul 19, 2:03 am, Gaurav Popli abeygau...@gmail.com wrote:

yeah...im saying to reach position n at which k is placed we have
  to
trverse n positions from head or not...??
and i didnt understand the use of ever increasing...please
  elaborate on it..

On Tue, Jul 19, 2011 at 2:08 AM, Dumanshu duman...@gmail.com
  wrote:
 @Swathi: plz give the TC of ur algo (exponential plus log)

 On Jul 18, 10:14 pm, Swathi chukka.swa...@gmail.com wrote:
 The solution to this problem will be a combination of
  exponential increase
 and the binary search..

 start = 0;
 end = 0;
 index =0;
 middle = 0;
 while (1)
 {
   if(a[start] == data)
     return start;
   if(a[end] == data)
     return end;
   if(data  end)
   {
    start = end;
    end = pow(start,2); // here we are consider exponential for
  faster
 search.
    // no need to check any boundary conditions as the array is
  infinite
    continue;
   }
   else
   {
     // do binary search between start index and end index
  because data is
 inbetween a[start] and a[end]
   }

 }

 Hope this helps...

 On Mon, Jul 18, 2011 at 10:32 PM, Gaurav Popli 
  gpgaurav.n...@gmail.comwrote:

  i dont understand it..if k is at position an let supposeso
  to
  check at that position dont you have to traverse till that
  position
  ...is thr anything else than the head of list...??or i
  understood
  wrongly...??

  On Mon, Jul 18, 2011 at 9:55 PM, sagar pareek 
  sagarpar...@gmail.com
  wrote:
   Update on 2nd line

   2.    if( ptr2=ptr1-next-next...(5 or 10 times) ) goto
  3.
  else
   make linear search till NULL encounter and exit with the
  solution

   On Mon, Jul 18, 2011 at 7:41 PM, sagar pareek 
  sagarpar...@gmail.com
  wrote:

   i have one approach :-

   first compare root-data  and k
   if k is very much greater than root-data then set
  next=5or10 ur choice

   else set next 2or3  ur choice
   take two pointers ptr1 and ptr2

   now lets take k is much greater than root-data
   then
   1. set ptr1=root //initially
   2. if( ptr2=ptr1-next-next...(5

[algogeeks] Re: Amazon

2011-07-19 Thread Dumanshu

What is the answer to the first one?

On Jul 19, 10:07 am, sagar pareek sagarpar...@gmail.com wrote:
 1. Let's say

 S=D=N

 repeat

 D=(floor)D/2;

 S=S-D;

 till D=0

 From the above logic, figure out which algorithm is followed by 'S'

 2. How can you divide a triangle, to 5 equal triangles?

 3. There are  players for a chess tournament, having every game as a
 knock out game (a player will

 be out of the tournament if he/she loses a game), how many games need to be
 conducted to determine a
 winner of the tournament.

 --
 **Regards
 SAGAR PAREEK
 COMPUTER SCIENCE AND ENGINEERING
 NIT ALLAHABAD

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: MICROSOFT

2011-07-19 Thread Dumanshu

@Surender: sorry, i had missed a case. We need a 3 way comparison.
heres the correct version

btree* max_tree(btree *root)
{
if(root == NULL)
return root;
btree * current = root;
while(current-right != NULL)
{
current = current-right;
}
return current;
}

btree * min_tree(btree *root)
{
if(root == NULL)
return root;
btree * current = root;
while(current-left != NULL)
{
current = current-left;
}
return current;
}

void binarytreetobst(btree *root)
{
//base-case tree is empty
if(root == NULL)
return;
else if(root-left == NULL  root-right == NULL) //base-case
tree
of size 1
return;
else
{
binarytreetobst(root-left);
binarytreetobst(root-right);
btree* max = max_tree(root-left);
if(max  max-data  root-data)
{
int temp = root-data;
root-data = max-data;
max-data = temp;
binarytreetobst(root-left);
}
btree* min = min_tree(root-right);
if(min  min-data   root-data)
{
int temp = root-data;
root-data = min-data;
min-data = temp;
binarytreetobst(root-right);
max = max_tree(root-left);
if(max  max-data  root-data)
{
 int temp = root-data;
 root-data = max-data;
 max-data = temp;
 binarytreetobst(root-left);
}
}
}
}

On Jul 19, 8:38 am, surender sanke surend...@gmail.com wrote:
 @Damanshu for
         1
       /   \
      2     3
     /  \
    4   5
   /  \
 6    7

 im ending up at some non BST

 surender







 On Tue, Jul 19, 2011 at 4:06 AM, Dumanshu duman...@gmail.com wrote:
  @Gaurav: The best solution would be to manipulate the given BTree in
  place and get the BST. We don't need a separate tree but convert the
  existing one using the same space occupied by nodes of BT already in
  BST.

  On Jul 19, 2:06 am, Gaurav Popli gpgaurav.n...@gmail.com wrote:
   cant we just dotraverse using recursion and instead of printing it
   just pass to function which is making BST??
   and is this right as someone above said first sort it and then make
  BST...
   dont we want that root of both Tree to be same or something like
  that...??

   On Tue, Jul 19, 2011 at 2:17 AM, Dumanshu duman...@gmail.com wrote:
@Balaji: for third question, were u asked to write the code?

On Jul 18, 10:04 pm, Balaji S balaji.ceg...@gmail.com wrote:
wats the mistake..

--
You received this message because you are subscribed to the Google
  Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group athttp://
  groups.google.com/group/algogeeks?hl=en.- Hide quoted text -

   - Show quoted text -

  --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: MS

2011-07-19 Thread Dumanshu

heres the code
http://ideone.com/rX130



On Jul 19, 9:35 pm, swetha rahul swetharahu...@gmail.com wrote:
 Hi,
         Find the kth smallest element in O(logk) given 2 sorted arrays.
 Merging the arrays is not allowed. I can do it in O(k).. How to do in
 O(logk)..

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

1 2 >

1 - 100 of 125 matches

Mail list logo