[algogeeks] Openings in Mentor Graphics,Noida Location
Anybody interested to join Mentor Graphics Noida having 1-10 years of experience in C/C++/DS/Algo can forward his/her resume to me. Please understand that the opening needs to be closed urgently.So,Hurry up. Note: Please ignore if inappropriate for this forum. -- Regards, Ashish -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Openings in Adobe India !!!
There are multiple openings in Adobe India for Developer position. Send me your resume ASAP. Here is the list of urgent openings. - · 31639_Member of Technical Staff / Computer Scientist https://workspaces.acrobat.com/?d=fYIUCfXMqBAaj0T8JrUMKA ·31497_Member of Technical Staff / Computer Scientist https://workspaces.acrobat.com/?d=U5lgab7ocxgSbz0CjInfyw ·26279_ Member of Technical Staff / Computer Scientist https://workspaces.acrobat.com/?d=hgTkxxHjX-jEcKNXOpxJBw ·30965_Member of Technical Staff / Computer Scientist https://workspaces.acrobat.com/?d=H7s2s7lpI3YK*RhWvOrU*Q ·31344_Member of Technical Staff / Computer Scientist https://workspaces.acrobat.com/?d=z6oIOM05vEdN6aZ76w1NXg ·30759_Member of Technical Staff / Computer Scientist https://workspaces.acrobat.com/?d=iYfB3oGLK*cP-GdYbRYqRA ·32543_Member of Technical Staff / Computer Scientist https://workspaces.acrobat.com/?d=DQ-WKuGH8byLQ9Z5p8vWWQ ·27526_Security Czar https://workspaces.acrobat.com/?d=2lXPky*D8qGxQbm9KDHdIw ·30262_Member of Technical Staff / Computer Scientist - MAC Developer https://workspaces.acrobat.com/?d=8MDJ3-8PpjXLwSN8sZe2lQ ·30976 Member of Technical Staff / Computer Scientist https://workspaces.acrobat.com/?d=AzpXN7cZ1Zh9l1usUsUMEQ Conditions for freshers: - Candidate should be from a premier college i.e. IIT/IIIT/NIT/BITS or equivalent. - In case of any college from where Adobe does not hire developers. I would recommend that you have something concrete in your resume so that I can talk to HR with confidence. :) Do mention this in the mail. Regards, Ashish -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] MS written Reasoning question
Ans is 1 M.A + 2 B.Tech + 2 MBA + 1 MCA. Explanation: (1) Exactly one must be an MA. (2) Given: 2 b.tech are seleceted and the statement if at least one btech is selected then exactly 2 MBA are selected (vice versa condition) So exactly 2 MBA will be selected. (3) Remaining 1 would be MCA. So ans would be (d) option (b) is not correct as it says that only 2 mba and only 1 mca are selected but the total no of selected candidates are 6. -- Ashish On Fri, Apr 26, 2013 at 11:32 PM, rahul sharma rahul23111...@gmail.comwrote: 10 candidates appear for an interview and 6 selected. 2-M.A 2-MCA 4-BTECH 2-MBA. If at least one MBA is selected then exactly 2 btech are selected and vice versa. Of six candidates,exactly one must be an MA cndidate question:- which of the following statementsis definitely true:,if 2 btech are selected: a- two mca and 2 ma are selected. b- only 2 mbas and only one mca is selected c-one MBA and two MAs are selected. d- Two MBAs are selected. My approach:- we are with 2 btech,one ma,one mba remaining two can be 1 mba+1mca or 2 mcas But correct option is d. How is this definitely true and b is not?? plz comment -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] MS Question:WAP to print last n lines of a log file
Q1. Given a log file, pirnt last n lines. Note that the Log file is being written into. Q2. Implement Circular Buffer. Best Regards Ashish Goel Think positive and find fuel in failure -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: HOW TO CALCULATE THA size of union
union A{
long int y[5];
union B{
double g;
union C{
int k;
union D{
char ch;
int x[5];
};
};
};
};
just removed the instances of unions from the given declaration and
tested on dev
A 20
B 8
C 4
D 20
On Sat, Dec 8, 2012 at 6:39 PM, shiv narayan narayan.shiv...@gmail.comwrote:
but when i compile it on Dev C it gives 24..whats the reason ?
On Fri, Dec 7, 2012 at 7:19 AM, Don dondod...@gmail.com wrote:
The actual size is system dependent because the language doesn't
specify the size of int or long int.
I'll assuming the common convention that sizeof(int)=4 and sizeof(long
int)=8.
The size of a union is the size of the largest element in the union.
So sizeof(D) = 5*sizeof(int)=20
C and B will be the same, because there is nothing bigger in any of
them.
sizeof(A) will be 40 which is the size of an array of eight long ints.
Don
On Dec 7, 5:42 am, zerobyzero narayan.shiv...@gmail.com wrote:
what will be the size of union A ,B,C and D. also please explain the
logic.
* union A{*
* long int y[5];*
* union B{*
*double g;*
*union C{*
* int k;*
* union D{*
*char ch;*
*int x[5];*
* }s;*
*}a;*
* }b;*
*}*p;*
--
--
Shiv Narayan Sharma
Jt. Secretary CSI-DTU
+919971228389
www.jugadengg.com
--
--
Regards,
Aashish Mann
--
[algogeeks] substring in big string
there is a big string which needs 2GB memory to fit in but you have only 100mb. Find a substring in the big string. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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.
Re: [algogeeks] spoj problem EASYMATH
thanks for your reply.. actually i was thinking the same thing.. but I am facing problems in finding the unique multiples of a+3d and a+4d as applying inclusion exclusion principle in this way is getting too difficult due to large no of factors to be added and subtracted.. is der any other approach or any way to simplify the process.. -- 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.
Re: [algogeeks] Data Structure
stack Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Sep 18, 2012 at 3:55 PM, Sheetal Naidu kartiknaid...@gmail.comwrote: sqlite database for mozilla...maybe hashtable On 18 September 2012 13:20, Navin Kumar algorithm.i...@gmail.com wrote: Which data structure is used to maintain browser history? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/MCj-0bFwvV0J. 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. -- - A.Sheetal B.tech, Final yr, Department Of Information Technology, NIT, Durgapur -- 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.
Re: [algogeeks] Re: adobe question help
this is from KR exercise :)
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Sep 12, 2012 at 4:14 PM, Navin Gupta navin.nit...@gmail.com wrote:
int temp = {[1(j-+1)]i-1};
Here temp is a number with all the bits set between positions i j
[both inclusive]
temp = ~temp;
N = N temp; // here we are clearing all the bits of N from
position i to j
temp = temp | M; // now we are taking the bit pattern from M into
temp in the given positions
N = N | temp;// now again we are setting the same pattern from
temp into N.
Note :- clearing bit means bit set to zero , while setting bit means bit
is 1
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/QTXreMoSy6gJ.
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.
Re: [algogeeks] Finding top 10 most frequent repeated word
hashmap for word to count mapping and a heap will have count and corresponding words (will get updated at run time) Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Sep 11, 2012 at 2:07 PM, Navin Kumar algorithm.i...@gmail.comwrote: @ashish: will you use HashMap or any other mapping technique? please throw some light on map? On Tue, Sep 11, 2012 at 11:09 AM, Ashish Goel ashg...@gmail.com wrote: map + heap for 10 most occurred words.. external sort for not sufficient memory if the words are dynamically added/deleted, the first map+heap should succeed. Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, Sep 8, 2012 at 8:06 PM, Kumar Vishal kumar...@gmail.com wrote: if it can be loaded we can use map , else look for external sorting coming to second point it dynamically changing leads lot of other questions before going give algo . On Sat, Sep 8, 2012 at 7:43 PM, Navin Kumar algorithm.i...@gmail.comwrote: Given a file which has billions of words and file can be loaded in memory. Now find 10 most frequent words in file. What if file is dynamically changing means words are continuously added to it. What if file cant be loaded in memory. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/UcdJKQHPGzoJ. 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 Kumar Vishal _ *http://wethecommonpeople.wordpress.com/ * *h**ttp://kumartechnicalarticles.wordpress.com/http://kumartechnicalarticles.wordpress.com/ * _ -- 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. -- 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.
Re: [algogeeks] Finding top 10 most frequent repeated word
map + heap for 10 most occurred words.. external sort for not sufficient memory if the words are dynamically added/deleted, the first map+heap should succeed. Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, Sep 8, 2012 at 8:06 PM, Kumar Vishal kumar...@gmail.com wrote: if it can be loaded we can use map , else look for external sorting coming to second point it dynamically changing leads lot of other questions before going give algo . On Sat, Sep 8, 2012 at 7:43 PM, Navin Kumar algorithm.i...@gmail.comwrote: Given a file which has billions of words and file can be loaded in memory. Now find 10 most frequent words in file. What if file is dynamically changing means words are continuously added to it. What if file cant be loaded in memory. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/UcdJKQHPGzoJ. 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 Kumar Vishal _ *http://wethecommonpeople.wordpress.com/ * *h**ttp://kumartechnicalarticles.wordpress.com/http://kumartechnicalarticles.wordpress.com/ * _ -- 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.
Re: [algogeeks] MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space.
what is right to left inorder? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Sep 3, 2012 at 1:13 PM, atul anand atul.87fri...@gmail.com wrote: @Dave : algo seems fine...but it seems to me that it would difficult to maintain both left to right and right to left parallel way :( :( . it would be gr8 if you can provided little bit of coded algorithm for it. On Mon, Sep 3, 2012 at 10:36 AM, Dave dave_and_da...@juno.com wrote: @Atul007: No need to destroy the BST. Perform two simultaneous inorder traversals of the BST, one from left to right (the usual direction) and one from right to left. At any stage you have selected two nodes. If the sum is less than the given number, advance the left-to-right traversal; If the sum is greater, advance the right-to-left traversal. Quit with success when the sum equals the given number or with failure when the two traversals have reached the same node. Dave On Sunday, September 2, 2012 11:00:42 PM UTC-5, atul007 wrote: convert BST to sorted DLL.. now it is a double linked list , so we can find 2 number in O(n) time by keeping 2 pointers(one at start and one at end) from sorted DLL. now convert DLL to BST. On Mon, Sep 3, 2012 at 1:32 AM, Navin Kumar algorit...@gmail.comwrote: MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/oizd-5CSfuoJ. 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. -- 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] LOGIC!!!
Q. A company organizes two foreign trips for its employees yearly. Aim of
the trip is to increase interaction among the employees of the company and
hence company wants each of his employee to see new people on the trip and
not even a single person with whom he has worked in past. Therefore it is a
rule in company that in any of the trips, all the employees should be new
to each other and no two of them should have worked together in past.
Given the work history of each employee (which people he has worked with
sometimes in past), you have to tell whether all of the employees can be
accommodated within trips without violating the above rule or not. Each
employee is given a unique integer ID by which they are recognized. You can
also assume that each employee has worked with at least one other employee
in past.
*Note: *No employee can be in both trips and every employee must be part of
one trip.
*Example: *
i) Suppose the work history is given as follows: {(1,2),(2,3),(3,4)}; then
it is possible to accommodate all the four employees in two trips (one trip
consisting of employees 1 3 and other having employees 2 4). Neither of
the two employees in the same trip have worked together in past.
ii) Suppose the work history is given as {(1,2),(1,3),(2,3)} then there is
no way possible to have two trips satisfying the company rule and
accommodating all the employees.
--
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] Amazon Q
Q1. Design a data structure for the following operations: I.Enqueue II. Dequeue III. Delete a given number(if it is present in the queue, else do nothing) IV. isNumberPresent All these operations should take O(1) time. Q2. Check if a linked list (each char is a node) is palindrome, recursively. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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.
Re: [algogeeks] Re: MS interview
yes, that is correct. O(mn) to form multimap and then O(m) to tell all anagram groups Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Aug 23, 2012 at 5:11 PM, kings dns.bhar...@gmail.com wrote: Dear GC, The efficient data structure in my opinion is Hash Table. 1. For a given word in the dictionary we need to form an anagram dictionary i.e. take a given word sort it which forms the key for the hashtable , then start forming the different anagrams for that word and insert it into the hash table with the corresponding key. 2. Once the hash table is ready for the given word sort it find the key and print all the anagarams i.e. values associated to that key. we will get all the anagrams for a given word. Coming to time complexity... sorting of a word can be done in a O(nlogn). building of anagram will take O(n). hash complexity O(n) worst case. so total time complexity is O(nlogn) for whole execrcise. Thanks Bhargava On Wednesday, 22 August 2012 23:39:02 UTC+5:30, GC wrote: Ques.. Given a m-word dictionary ... and a n-sized word... .. now suggest DS for dictionary such that you can find out all the anagrams of the given word present in dictionary... -- Regards, G C -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/ySPUSvS0Sh0J. 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.
Re: [algogeeks] MS interview
O(n) convert each string into format a1b2and then insert into multimap wityh this a1b2...as key and original word as value. All words with same key are anagrams Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Aug 22, 2012 at 11:39 PM, GAURAV CHAWLA togauravcha...@gmail.comwrote: Ques.. Given a m-word dictionary ... and a n-sized word... .. now suggest DS for dictionary such that you can find out all the anagrams of the given word present in dictionary... -- Regards, G C -- 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.
Re: [algogeeks]
what is the rational to do 5*rand5()
why not 4*rand5 or 6 *rand5??
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Fri, Jun 22, 2012 at 10:13 AM, Anant Sharma black.b...@gmail.com wrote:
The reason why finding a solution to this question is difficult is because
the combinations of rand5() function which we use ( eg. rand5() + rand5()%2
) leads to some numbers being generated more frequently than others. So the
problem would be solved if we could find a function which leads to each
output being generated an equal number of times ( once, or maybe more. )
5 * rand5() + rand5()
Looking at this function, it is easy to see that each value from 0 to 24
will be generated only once for every respective value that first and
second rand5() returns.
Suppose the first rand5() returns 0, then the second rand5() can return
any value from 0 - 4. Now see that no value from 0-4 could be generated by
any other combination. When the value returned by the second rand5() is 1,
corresponding to the value returned by second rand5(), we could get 5 - 9.
Now we have each number from 0-24 appearing once. But simply returning the
mod of this value with 7 wouldn't lead to equal probability distribution as
the values 0 - 3 would be returned more times than 4-6. So to fix this
inequality, we ignore when the value of the function is more than 20. Now
doing mod with 7 will result in every number 0 - 6 being returned with
equal probability.
We could even have ignored the values above 6, or the values above 13, the
only difference being that it would take more number of calls to return a
rand7() result.
This way is non-deterministic i.e. we cannot say how many times the
function will be called before we get the rand7() result, but we can be
sure that whenever the function returns a value, it would have been as
probable as any other value from 0 - 6. Taking the mod of the result of the
function, there would be 3 ways in which each digit 0 through 6 can be
generated.
Implementation:
int rand7 ( ) {
int num = 5 * rand5 ( ) + rand ( ) ;
if ( num 20 )
return rand7 ( ) ;
else
retutrn num % 7 ;
}
On Thu, Jun 21, 2012 at 12:44 PM, Abhishek Sharma abhi120...@gmail.comwrote:
@umer
it's not random,but biased
On Wed, Jun 20, 2012 at 11:16 AM, Umer Farooq the.um...@gmail.comwrote:
Hmmm, true. That's what I expected in this solution. Similarly, we can
get 3 by (3,3) (1,2)
However, did you take a look at the other solution I proposed? I guess
that solves the problem to some extent.
On Tue, Jun 19, 2012 at 7:18 PM, Sourabh Singh singhsourab...@gmail.com
wrote:
@Umer and Navin :
1 is generated by (1,3) only.
2 is generated by (1,1) and (2,3).
so given solution is wrong
On Tue, Jun 19, 2012 at 5:17 AM, Sourabh Singh
singhsourab...@gmail.com wrote:
@ *ALL*
please. post along with your method .
proof than it make's equal distribution over the given range.
On Tue, Jun 19, 2012 at 4:47 AM, Navin Kumar algorithm.i...@gmail.com
wrote:
@Umer:
rand(5) + (rand(5)%2): = it will never give 6 because for rand(7)
range will be 0-6.
So better try this: rand(5) + (rand(5)%3).
On Tue, Jun 19, 2012 at 2:45 PM, Umer Farooq the.um...@gmail.comwrote:
rand(5) + (rand(5)%2);
On Tue, Jun 19, 2012 at 12:30 PM, Sourabh Singh
singhsourab...@gmail.com wrote:
@ sry
condition should be:
if(20*prob = 500/7) :-)
On Tue, Jun 19, 2012 at 12:26 AM, Sourabh Singh
singhsourab...@gmail.com wrote:
@ALL
Given a random number generator say r(5) generates number between
1-5 uniformly at random , use it to in r(7) which should generate a
random
number between 1-7 uniformly at random
i have seen this on many site's but not a single correct solution.
all solution's posted got rejected by someone else.:
plz.. suggest some algo :
my aprroach:
let's assume a rectangle :
100 |___
|___|__
500/7 | ||
| ||
|___|__|
0 1 2 3 4 5 67
now :
let : num = rand(5);
prob = rand(5);
if(prob = rand(5))
print num
else
print 5 + num*(2/5)
--
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
[algogeeks] AMAZON: given col id, print col name in excel
Imagine a sequence like this: a, b, c...z, aa, ab, ac...zz, aaa, aab, aac aax, aaz, aba, abc... (Its same as excel column names). Given an integer (n), generate n-th string from the above sequence. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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.
Re: [algogeeks] Re: DE Shaw written test
Test
{ 30,40,15,35,10,20 } using the logic specified as
Find the min and max element in the array.
If the min comes before max, then return the dates- min to buy and max to
sell.
But if the min comes after max,
find the max element that comes after min i.e. maxRight
find the min element that comes before max i.e. minLeft
Now find the difference (max - minLeft)( maxRight - min)
return the dates for which the difference is higher.
It does not work. The assumption that either one of real max or real min
has to be part to compute max profit does not seem correct.
alternatively
after findiing a profit, if we find a min, save the previous computations
(imagine previous array is not part anymore and apply the same rule of
findling min and then maxProfit.
int minIndex = 0;
int maxProfit = 0;
int maxIndex = -1;
int finalMinIndex = -1;
int finalMaxIndex = -1;
for (int i=1; in;i++)
{
if (a[i] - a[minIndex] maxProfit) { maxProfilt = a[i] - a[minIndex];
maxIndex = i; continue;}
if (a[i] a[minIndex]) {
if (maxIndex ==-1) minIndex = i; //safely ignore previous min as for
upcoming max, the diff will be more now with this new min
else { finalMinIndex = minIndex; finalMaxIndex = maxIndex; maxIndex
= -1;}
}
}
if (maxIndex !=-1) {finalMinIndex = minIndex; finalMaxIndex = maxIndex;}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sun, Aug 5, 2012 at 11:36 PM, Navin Kumar navin.nit...@gmail.com wrote:
This is a linear time constant space algorithm.
Assume the stocks prices are given in an array where index represents the
day no . For ex a[365] represents stock price on 365th day of year.
Find the min and max element in the array.
If the min comes before max, then return the dates- min to buy and max to
sell.
But if the min comes after max,
find the max element that comes after min i.e. maxRight
find the min element that comes before max i.e. minLeft
Now find the difference (max - minLeft)( maxRight - min)
return the dates for which the difference is higher.
Code:--
void FindDaytoBuySellStock(int stocks[], int N) // here N = 365
{
int minPos = findMinPos(stocks);
int maxPos = findMaxPos(stocks);
if(minPos maxPos ) { BuyDate = minPos,SellDate = maxPos; }
else{
minLeft = find min in array from 0 to maxPos-1
maxRight = find max in array from minPos+1 to N
int d1 = max - minLeft;
int d2 = maxRight - min;
if(d1 = d2 ) {BuyDate = minLeft,SellDate = max; }
else{ BuyDate = min ,SellDate = maxRight; }
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/dSJCOIuUuKUJ.
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.
Re: [algogeeks] DE Shaw written test
As i understand the question says, one time buy and one time sell, buy
preceeds sell...
if multiple such transactions allowed, we may need DP
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, Aug 6, 2012 at 7:16 AM, umesh kewat umesh1...@gmail.com wrote:
The sequence of price is make more sense if buy price is less than next
value then you can buy even its not the min and next day you can sell all
and
Buy again when min price stock come.
Eg 6, 10, 5, 7, 2,7.
There are many case need to consider the above is the only one scenario.
Other like random order profits and loss so need to decide min n max for a
interval.
Here is no profit
9 8 7 6 5 4 3 2 1 :(.
Sent from my Windows Phone
--
From: Mukul Gupta
Sent: 08/05/2012 8:47 PM
To: algogeeks@googlegroups.com
Subject: Re: [algogeeks] DE Shaw written test
Thanks for pointing out the mistake.Though my code will correctly
calculate the max_profit but I must keep track of the buying_day.I have
made some modification in my code.Hope it works fine now.
int min = a[0]; // initialized to first element
int max_profit = 0; //when you buy and sell on same day
int buying_day = a[0];
for ( int i = 1; i n; i++ ){
if ( max_profit (a[i] - min ) ){
max_profit = a[i] - min;
buying_day = min;
}
if ( a[i] min )
min = a[i];
}
Finally. I'll have buying_day and max_profit, so if you need to find the
selling day you can easily calculate :
Selling day = buying_day+max_profit;
Correct me if I'm wrong.
On Sun, Aug 5, 2012 at 5:43 PM, Arun Kindra arunkin...@gmail.com wrote:
@harsha : yes, the problem is if u r finding only min and max value, it
might happen that u sell the stock before buying. Ex- int a [ ] = { 5, 10,
4, 6, 7 }; the min value is 4 and max is 10 and 10 comes before 4, means u
sell the stock before buying.
and i think the sol given by mukul does the same mistake.we need to keep
track this case also whether the day(array index) i m buying is not more
than the day(array index) we are selling the stock.
*correct me if m wrong*.
--
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.
--
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.
Re: [algogeeks] Local Minima in Unsorted Array
can you give an example of what do you mean by Local minima? From Dave's example, it looks like the minima of the whole array.. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Fri, Aug 3, 2012 at 10:32 PM, shady sinv...@gmail.com wrote: Hi, Can anyone tell how to find local minima in an unsorted array ? Recommended solution : O(log(n)) Shady. -- 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.
Re: [algogeeks] Re: Microsoft online questions : DLL to bst??
Ishan, i am assuming that the list to BST should give a inorder traversal, and the logic of yours does not seem to give a right solution. try two different trees with 7 nodes, convert into LL and then back to BST, the answer is not same as the trees that we start with. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jul 31, 2012 at 5:19 PM, Ishan Sood sood.ishaan2...@gmail.comwrote: 1. get the middle of the linked list and make it root 2. same for left half and right half recursivly a. get the middle of left half and make it left child. b. get middle of rite half and make it rite child. this is must b he logic for the qstn. :) Thank You, Ishan Sood. 9805660301 On Tue, Jul 31, 2012 at 3:09 PM, Ashish Goel ashg...@gmail.com wrote: how would you do convert sorted doubly linked list to bst using same nodes as in DLL Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Jul 29, 2012 at 10:30 PM, Purani Sekar nagapur...@gmail.comwrote: convert sorted doubly linked list to bst using same nodes as in DLL -- 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. -- 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.
Re: [algogeeks] Re: Microsoft online questions : DLL to bst??
can you give the link within geeksforgeeks please Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jul 31, 2012 at 4:13 PM, a g ag20071...@gmail.com wrote: check on geeksforgeeks.org On Tue, Jul 31, 2012 at 3:09 PM, Ashish Goel ashg...@gmail.com wrote: how would you do convert sorted doubly linked list to bst using same nodes as in DLL Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Jul 29, 2012 at 10:30 PM, Purani Sekar nagapur...@gmail.comwrote: convert sorted doubly linked list to bst using same nodes as in DLL -- 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. -- 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.
Re: [algogeeks] Microsoft first round interview question.
lets call the additional pointer as child. find the tail and keep attaching
to tail if there is a child...
struct node * makeDLL(struct node *pDLL) {
if (!pDLL) return pDLL;
struct node *pTail = pDLL;
while (pTail-next) pTail = pTail-next;
struct node *pCurr = pDLL;
while (pCurr) {
if (pCurr-child) {
pTail-next = pCurr-child;
pCurr-child-prev = pTail;
while (pTail-next) pTail = pTail-next;
}
pCurr= pCurr-next;
}
return pDLL;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Aug 2, 2012 at 5:45 PM, Navin Kumar algorithm.i...@gmail.comwrote:
@sahil: Please elaborate your question. I didn't understand your question.
what is straight doubly linked list?? How many pointers each node have??
On Thu, Aug 2, 2012 at 4:26 PM, Amit Basak abas...@gmail.com wrote:
Does each node in the list have three pointers?
What do you mean by straight doubly link list?
Thanks,
Amit
On Wed, Aug 1, 2012 at 7:25 PM, sahil gupta sahilgupta...@gmail.comwrote:
There is doubly link list and each node is having another pointer which
is points to another doubly link list or points to null.
You need make it straight doubly link list.
Provide the efficient code.
Sahil Gupta
--
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.
--
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.
Re: [algogeeks] Re: Microsoft online questions : DLL to bst??
how would you do convert sorted doubly linked list to bst using same nodes as in DLL Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Jul 29, 2012 at 10:30 PM, Purani Sekar nagapur...@gmail.com wrote: convert sorted doubly linked list to bst using same nodes as in DLL -- 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.
Re: [algogeeks] Programming Problem
@piyus khanna--- while forming a BST with aaab and removing duplicates if a charcter occur once .. so for aaab first make a node for 'a'. and ignore next two a's as they are already on the BST. next is 'b'. make 'b' as root and 'a' on the right side.. and use inorder parsing to get 'ba' as the unique beautiful string. On Fri, Jul 20, 2012 at 12:22 PM, piyush khanna piyush_khanna2...@yahoo.com wrote: @ashish jain :then what for aaab.. -- *From:* ashish jain ashishjainco...@gmail.com *To:* algogeeks@googlegroups.com *Sent:* Thursday, July 19, 2012 9:48 PM *Subject:* Re: [algogeeks] Programming Problem if from the string s.. a binary search tree (with higher value alphabets on the left side of the root and lower value alphabets on the right side of root) is formed removing the repeated characters during the formation of he BST and then applying inorder technique to get the string s2. String S2 will give the most beautifull unique string producible from s. ^^ Correct me if wrong!! On Thu, Jul 19, 2012 at 11:00 AM, gobind hemb gobind.h...@gmail.comwrote: String s is called *unique* if all the characters of s are different. String s2 is *producible* from string s1, if we can remove some characters of s1 to obtain s2. String s1 is *more beautiful* than string s2 if length of s1 is more than length of s2 or they have equal length and s1 is lexicographically greater than s2. Given a string s you have to find the *most beautiful unique* string that is producible from s. *Input:* First line of input comes a string s having no more than 1,000,000(10^6) characters. all the characters of s are lowercase english letters. *Output:* Print the most beautiful unique string that is producable from s *Sample Input:* babab *Sample Output:* ba *Explanation* In the above test case all unique strings that are producible from s are ab and ba and ba is more beautiful than ab. -- 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. -- 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.
Re: [algogeeks] Programming Problem
if from the string s.. a binary search tree (with higher value alphabets on the left side of the root and lower value alphabets on the right side of root) is formed removing the repeated characters during the formation of he BST and then applying inorder technique to get the string s2. String S2 will give the most beautifull unique string producible from s. ^^ Correct me if wrong!! On Thu, Jul 19, 2012 at 11:00 AM, gobind hemb gobind.h...@gmail.com wrote: String s is called *unique* if all the characters of s are different. String s2 is *producible* from string s1, if we can remove some characters of s1 to obtain s2. String s1 is *more beautiful* than string s2 if length of s1 is more than length of s2 or they have equal length and s1 is lexicographically greater than s2. Given a string s you have to find the *most beautiful unique* string that is producible from s. *Input:* First line of input comes a string s having no more than 1,000,000(10^6) characters. all the characters of s are lowercase english letters. *Output:* Print the most beautiful unique string that is producable from s *Sample Input:* babab *Sample Output:* ba *Explanation* In the above test case all unique strings that are producible from s are ab and ba and ba is more beautiful than ab. -- 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.
Re: [algogeeks]
@Vindhya
every time least is getting 101-'e' as the value. and not llo
as the statement
least = (*ptrleast ) ?(*ptr) :(least);
is equivalent to
if(*ptrleast)
least=*ptr;
so firstly it compares 127 with 'e' and least ='e'
in next iteration , it compares l and e, so agn least = 'e'
in next iteration , it compares l and e, so agn least = 'e'
in next iteration , it compares o and e, so agn least = 'e'
in next iteration , it compares null and e, so least = 0
i hope this will clarify your doubts
On Sun, Jul 15, 2012 at 11:57 PM, vindhya chhabra
vindhyachha...@gmail.comwrote:
please someone explain
On Sun, Jul 15, 2012 at 3:54 PM, vindhya chhabra vindhyachha...@gmail.com
wrote:
#include stdio.h
main()
{
char * str = hello;
char * ptr = str;
char least = 127;
while (*ptr++)
least = (*ptrleast ) ?(*ptr) :(least);
printf(%d,least);
getch();
}
in this ques i got o/p is 0(no doubt) but i have a doubt in why every
time least is getting 101-'e' as the value. why are ascii values of llo not
assigned in least. please someone explain.
--
Vindhya Chhabra
--
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.
--
Vindhya Chhabra
--
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.
Re: [algogeeks] C o/p
I think it should output: 9 9 On Sun, Jul 8, 2012 at 11:42 PM, md shaukat ali ali.mdshau...@gmail.comwrote: but i am confused in this problem... int a=10; int b; b=--a--; printf(%d %d,a,b);..what will output? On Sun, Jul 8, 2012 at 11:39 PM, md shaukat ali ali.mdshau...@gmail.comwrote: agree with adarsh On Sun, Jul 8, 2012 at 10:39 PM, adarsh kumar algog...@gmail.com wrote: Sorry, its 6/6 and not 6/5, regds. On Sun, Jul 8, 2012 at 10:39 PM, adarsh kumar algog...@gmail.comwrote: Firstly, this is ambiguous and expressions with multiple increment/decrement operators will get executed according to the compiler. Even if you consider the normal way, as we(humans) percieve it, it will be evaluated as (++i)/(i++), which is 6/5, which is 1. Simple! On Sun, Jul 8, 2012 at 10:23 PM, rahul sharma rahul23111...@gmail.comwrote: int i=5; i=++i/i++; print i; i=1 how? -- 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. -- 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.
Re: [algogeeks] Finding intersection of 2 linked lists
struct node* intersection( struct node *pL1, struct node* pL2)
{
if ((!pL1) || (!pl2)) return NULL;
struct node * pL3 = NULL;
struct node* pL3Tail = NULL;
while(pL1)(pL2) {
if (pL1-data pL2-data) pL1=pL1-next;
else if (pL1-data pL2-data) pL2=pL2-next;
else {
struct node *pNew = (struct node*)malloc(sizeof(struct node));
if !pNew return NULL; //scary
pNew-data = pL1-data; pNew-next = NULL;
if ( !pL3) pL3= pNew;
else pL3Tail-next = pNew;
pL3Tail = pNew;
}
return pL3;
}
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 10:41 PM, Abhi abhi120...@gmail.com wrote:
Any efficient algorithm to find intersection of two linked lists.Example:
Linked List 1) 1 - 2 - 3 - 4 - 5 - 6
Linked List 2) 3 - 4 - 5
Intersection 4 - 5 - 6
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/-8_lnGA-ZhgJ.
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.
Re: [algogeeks] Amazon Interview Question
1. inverted hasp map
2. not clear
3. VLR, how do you identify end of L and start of R, question incomplete
4. One problem: consider
...
a b...
c d...
...
if ab is a prefix, can aba be another prefix, i would assume so. But if
that is true, i am not sure if this program will come to an end.
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.com wrote:
Find the next higher number in set of permutations of a given number
--
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.
Re: [algogeeks] Amazon Interview Question
Q5 is sorting problem
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote:
1. inverted hasp map
2. not clear
3. VLR, how do you identify end of L and start of R, question incomplete
4. One problem: consider
...
a b...
c d...
...
if ab is a prefix, can aba be another prefix, i would assume so. But if
that is true, i am not sure if this program will come to an end.
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.com wrote:
Find the next higher number in set of permutations of a given number
--
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.
Re: [algogeeks] Amazon Interview Question
Q4
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
if (visited[i][j]) continue;
visited[i][j] = true;
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote:
1. inverted hasp map
2. not clear
3. VLR, how do you identify end of L and start of R, question incomplete
4. One problem: consider
...
a b...
c d...
...
if ab is a prefix, can aba be another prefix, i would assume so. But if
that is true, i am not sure if this program will come to an end.
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s); prefix[k]=s; continue;}
else if isPrefix(s) prefix[prefixCount++] = s;
else removePrefix(prefix[k], prefixCount);
prefix[prefixCount++] = String(a[i][j];
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.com wrote:
Find the next higher number in set of permutations of a given number
--
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.
Re: [algogeeks] serialize a binary tree
my understanding is to either write the level order traversal noting parent, child relation or write the adjacency list into a file where we store the edges Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 3:58 PM, adarsh kumar algog...@gmail.com wrote: Serialisation meaning? Numbering the nodes. Any specific order, or as in level order?? On 7/4/12, Ashish Goel ashg...@gmail.com wrote: a] How would you serialize a binary tree in a file(improve it) b] serialization that you have chosen, write a code to reconstruct the tree Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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. -- 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] IV Question : Design Tatkal Seva (dev Question)
Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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] serialize a binary tree
a] How would you serialize a binary tree in a file(improve it) b] serialization that you have chosen, write a code to reconstruct the tree Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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] balanced tree
WAP to find if a tree is balanced/fully balanced? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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.
Re: [algogeeks] Please help in understanding this question. I have no answers just this question.
count island problem On Jul 1, 2012, at 11:06 AM, Vikas wrote: Given matrix(screen black n white)..where 1 represents black dot and 0=white. there can b many images/objects in it..return list of coordinates for each obkect..(Hint do BFS) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/3F5k2u0wwWwJ. 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.
Re: [algogeeks] Microsoft interview qs
trie or ternary tree and build stack for the string being entered, keep
distributed hashmap for head/tail queries like cricket, weather, finance
etc various domains etc..
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sat, Jun 30, 2012 at 12:05 PM, shady sinv...@gmail.com wrote:
i am not sure if it is possible to change the length of an already
declared array, so i think one might wanna use pointers instead. Allocate
memory dynamically.
On Thu, Jun 28, 2012 at 2:36 PM, deepikaanand swinyanand...@gmail.comwrote:
//Taken from careercup.com
Design the autocomplete feature (ex:Google Suggest)
I assumed {abcde,abcegh,abcpqr,abcxyz,xyz ,abcmno} URLs
and stored them in trie...Such if the user enters abc ...the o/p will
be
abc is a prefix in 5 number of cases
d e
e g h
m n o
p q r
x y z
Now say if I add more strings of the form abcdpqr,abcdprst..How can
I modify this code such that now thw o/p is
d e
e g h
m n o
p q r
x y z
d p q r
d p r s t
code in c :-
http://ideone.com/rBvQb
--
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.
--
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] MS Question :implement read write lock class
Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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] MS Question: Add two large numbers where the numbers are stored in an array format
Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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.
Re: [algogeeks] Re: Frequently one of the Top Question Asked in Amazon
This is zigzag problem where in addition to print, one needs to append the printed data to the resulting DLL at the tail. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Feb 1, 2011 at 6:12 PM, bittu shashank7andr...@gmail.com wrote: append(result,head); -- 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.
Re: [algogeeks] MS Question: Add two large numbers where the numbers are stored in an array format
the base is not given, so 10 can't be assumed
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jun 26, 2012 at 4:38 PM, amrit harry dabbcomput...@gmail.comwrote:
make size of both array by adding '0' in front of smaller array
then
int carry=0;
for(i=array.size();i=0;i--)
{
sum[i]=carry+arrayA[i]+arrayB[i];
carry=sum[i]/10;
sum[i]=sum[i]%10;
}
then reverse and print sum
On Tue, Jun 26, 2012 at 3:40 PM, Ashish Goel ashg...@gmail.com wrote:
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
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 Regards
Amritpal singh
--
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.
Re: [algogeeks] Re: Question asked in Amazon online test
@all
yaa.. For getting number of swaps.. we have to calculate total number of
zeroes on the right for each '1' and on adding them
we will get the number of swaps. and in O(n) time.
On Sat, Jun 23, 2012 at 1:16 PM, Guruprasad Sridharan
sridharan.mi...@gmail.com wrote:
It will work because we need to swap only adjacent elements. So we do a
sweep from left to right finding the number of ones encountered to the left
of a zero when we find a zero. We keep adding the number as we sweep the
entire length.
On Sat, Jun 23, 2012 at 1:14 PM, deepikaanand swinyanand...@gmail.comwrote:
@saurabh..wat array r u getting finallyis it all 1's or in sorted
order for the input
int a[8]={1,1,1,0,1,0,1,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.
--
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.
Re: [algogeeks] Re: Directi question-centre of the tree
farthest from 2: Find a vertex v1 | the farthest form r. 3: Find a vertex v2 | the farthest form v1. won't v2 be farthest from r? or we are talking about alternate pats also Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jun 20, 2012 at 6:25 PM, adarsh kumar algog...@gmail.com wrote: As you traverse along and find the diameter of the tree, keep track of the number of nodes thereby traversed. Let that be equal to n. Now, centre is the node corresponding to floor((n+1)/2). On Wed, Jun 20, 2012 at 5:19 PM, Nishant Pandey nishant.bits.me...@gmail.com wrote: I am asking again .. can any one please suggest better method for getting the median on the longest path of the tree .. efficient method . On Tue, Jun 19, 2012 at 5:08 PM, Nishant Pandey nishant.bits.me...@gmail.com wrote: for getting diameter we can simply add the max height of left subtree and max height of the right sub tree . the main issue is how efficiently we find median on that longest path to get the center of the tree . can any bdy sugest optimized algo for that ? On Mon, Jun 18, 2012 at 6:08 PM, rajesh pandey rajesh.pandey.i...@gmail.com wrote: I found it in some paper ;) Diameter and center De nition 4. The diameter of tree is the length of the longest path. De nition 5. A center is a vertex v such that the longest path from v to a leaf is minimal over all vertices in the tree.Tree center(s) can be found using simple algorithm. Algorithm 1. (Centers of tree) 1: Choose a random root r. 2: Find a vertex v1 | the farthest form r. 3: Find a vertex v2 | the farthest form v1. 4: Diameter is a length of path from v1 to v2. 5: Center is a median element(s) of path from v1 to v2. This is O(n) algorithm. It is clear that we can't determine tree isomorphism faster than O(n). So, if we nd a O(f(n)) algorithm for rooted trees isomorphism we can also obtain O(f(n)) algorithm for ordinary trees. On Saturday, June 16, 2012 12:04:32 PM UTC+5:30, achala sharma wrote: I think this algorithm is used for calculating poset in graph. On Sat, Jun 16, 2012 at 3:04 AM, Hemesh Singh hemesh.mn...@gmail.comwrote: + 1 for DK's solution. Is that a standard algorithm coz I feel like I have heard it somewhere ?? On Mon, Aug 8, 2011 at 1:37 AM, DK divyekap...@gmail.com wrote: @KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3). Could you please state how you can use the traversals directly to get the center? (And prove your correctness too?) The solution given by Wladimir ( expanded upon by me) is O(N) and uses (somewhat) the inverse of a BFS as a traversal. -- DK http://twitter.com/divyekapoor http://gplus.to/divyekapoor http://www.divye.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/**msg/algogeeks/-/HnMOZtOrkqwJhttps://groups.google.com/d/msg/algogeeks/-/HnMOZtOrkqwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@ **googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- Hemesh singh -- 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+unsubscribe@* *googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/BWplK7bCatMJ. 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. -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.comgvib...@google.com | +91-9911258345 -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.comgvib...@google.com | +91-9911258345 -- 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
Re: [algogeeks] Microsoft question
is the modification of the given array allowed? if yes use quick select, otherwise build tree where each node keeps count of its left subtree Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Jun 17, 2012 at 8:13 AM, Prem Nagarajan prem.cmna...@gmail.comwrote: Give an array of unsorted elements, find the kth smallest element in the array. The expected time complexity is O(n) and no extra memory space should be used. Quickselect algorithm can be used to obtain the solution. Can anyone explain how quickselect works? -- 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] print spiral
given a matrix m*n print elements in spiral
eg
1 2
3 4
5 6 = 1,2,4,6,5,3
1
2
3 =1,2,3
i wrote following code but for the case 2 printing 1,2,3,2
I wish to avoid keeping a counter of how many elements have been print so
far...
void spiral(int a[], int m, int n) {
while ( (rs(m+1)/2) (cs (n+1)/2)) {
int r=rs;
int c=cs;
for (int j=c;jn-c-1;j++) printf(%d ,a[r][j]);
for (int i=r;im-r-1;i++) printf(%d ,a[i][n-c-1]);
for (int j=n-c-1;jc;j--) printf(%d ,a[m-r-1][j]);
for (int i=m-r-1;ir;i--) printf(%d ,a[i][c]);;
rs++;cs++;
}
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
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] water trap
question @ http://www.leetcode.com/groups/twitter-interview/forum/topic/rain-water-trap-2d-version/ can someone help please Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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.
Re: [algogeeks] print spiral
yes, using count i solved this, but IMHO, this should be done without this
count somehow..
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Fri, Jun 15, 2012 at 3:14 PM, utsav sharma utsav.sharm...@gmail.comwrote:
check no. of elements printed in all inner for loop also
for (int j=c;jn-c-1 cntm*n;j++) {printf(%d ,a[r][j]); cnt++;}
for (int i=r;im-r-1 cntm*n;i++) {printf(%d ,a[i][n-c-1]); cnt++}
for (int j=n-c-1 cntm*n;jc;j--) {printf(%d ,a[m-r-1][j]); cnt++}
for (int i=m-r-1 cntm*n;ir;i--) {printf(%d ,a[i][c]); cnt++}
On Fri, Jun 15, 2012 at 2:10 PM, Guneesh Paul Singh
gunees...@gmail.comwrote:
void spiral(int a[][],int m,int n)
{
int c=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.
--
Utsav Sharma,
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.
--
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.
Re: [algogeeks] Re: Book Feedback needed for book from Narasimha Karumanchi
bought this book and i am quite impressed with the quantity and quality of code. Recommend this with programming pearls, prog interview exposed, cracking the coding interview. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, Jun 16, 2012 at 2:01 AM, Hemesh Singh hemesh.mn...@gmail.comwrote: @Saurabh : That's http://www.squifer.com/ http://www.squifer.com/document/e6e6192d75/Data-Structures-And-Algorithms-Made-Easy-%28for-Interviews%29-Programming-Interview-Questions/ Some chapters of the book are available here. On Thu, Jun 14, 2012 at 11:46 PM, saurabh singh saurab...@gmail.comwrote: Kindly find some other group for requesting e-books- www.squiffer.com This is a good reference for ebooks.Any more requests for uploading ebooks may result in a ban from the group. Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Fri, Jun 8, 2012 at 7:05 PM, Decipher ankurseth...@gmail.com wrote: Does anybody has its ebook ? Please upload it -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/AETPnqJps7AJ. 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. -- Hemesh singh -- 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] MS Question: Reverse stack using push, pop without any auxiliary data structure
Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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.
Re: [algogeeks] MS Question: Reverse stack using push, pop without any auxiliary data structure
Navin: copy pastes not encouraged till the logic is also clarified ;)
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Jun 14, 2012 at 7:25 PM, Sourabh Singh singhsourab...@gmail.comwrote:
@ Navin Kumar
Nice . Solution.
But
your function also make a stack only. so you are using a stack[internal]
here.
but may be this one is allowed:-)
On Thu, Jun 14, 2012 at 5:23 AM, Navin Kumar algorithm.i...@gmail.comwrote:
void Reverse(struct Stack *S) {
int data;
if(IsEmptyStack(S)) return;
data=pop(s);
ReverseStack(S);
InsertAtBottom(S, data);
}
void InsertAtBottom(struct stack *S, int data)
{
int temp;
if(!IsEmptyStack(S)){
push(S,data);
return;
}
temp=pop(S);
InsertAtBottom(S,data);
push(S, temp);
}
On Thu, Jun 14, 2012 at 2:44 PM, rahul patil
rahul.deshmukhpa...@gmail.com wrote:
to store items in stack you will need some DS. Do they mean you cant use
any auxillary DS than stack ?
On Thu, Jun 14, 2012 at 2:24 PM, Ashish Goel ashg...@gmail.com wrote:
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
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,
Rahul Patil
--
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.
--
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.
Re: [algogeeks] Microsoft Interview Question
int i=0;
int j=n-1;
while (ij) {
while (ij) (a[i]=0) i++;
while (ij) (a[j0) j--;
if (ij) swap(a[i],a[j]);
else break;
i++; j--;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jun 13, 2012 at 9:49 PM, Krishna Kishore
kknarenkris...@gmail.comwrote:
Given a array of integers both positive and negative and you need to shift
positive numbers to one side
and negative numbers to other side with the order intact.
ex. {-1,5,3,-8,4,-6,9} to {-1,-8,-6,5,3,4,9}. This should be done in O(n).
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/PebCCcpUXpIJ.
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.
Re: [algogeeks] MS Q: how to test a driverless car?
Things like sensor data coming from CAN/MoST from the car is collected and analysed in real time to avoid collisions, off-lane movement, distance maintenance, auto parking(including parallel), slippage on road/snow, GPS integration for perfect location and location specific data (like traffic,school/hospital/potholes etc), capability to act on instructions from telematics agents for SoS(accidents, profile based paths/alterations,speed control as per laws), action on maintenance reminders, fuel auto-filling/auto-charging should drive the testing, . Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Jun 7, 2012 at 1:07 PM, Umer Farooq the.um...@gmail.com wrote: What are the specs of the car. Can you please give the answer to the following clarifying questions: - How much distance is it suppose to travel without the driver? - Is it suppose to run on smooth roads only or can it also run on roads with jumps on it? On what type of road is the car most suitable? - Is it suppose to slow down at speed brakers? - Is it suppose to run on a two-way street as well or can it run on one way roads only? - Is it suppose to auto-park the car, or do we need to have a driver to park the car? On Wed, Jun 6, 2012 at 8:34 PM, Ashish Goel ashg...@gmail.com wrote: Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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. -- Umer -- 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.
Re: [algogeeks] Re: MS question : string compression
#include stdafx.h
#include iostream
using namespace std;
const int len = 20;
const int maxCount = 127;
int rle(char* pStr, int length, char* pNew) {
if (!pStr) return -1;
if (length 3) return -1;
int i = 0;
int k = 0;
char p1 = pStr[i++];
char p2 = pStr[i++];
char p3 = pStr[i++];
int pos=0;
int cCount = 0;
bool verbatim = false;
while ((p3) (ilength)) {
if (p1==p2) {
if (p2==p3) {
if (i == k+3) //no vRun
verbatim = false;//no vRun befor this cRun
if (verbatim)
{
int vEnd = (i-3)-k;;
pNew[pos++] = vEnd;
for (int t=k;tvEnd;t++) {
pNew[pos++]=pStr[t];
}
}
cCount++;
p1 = p2;
p2 = p3;/*not required*/
p3 = pStr[i++];
continue;
}
else { //run end or no run at all
if (cCount 0) { //a run
pNew[pos++] = -cCount; ///
pNew[pos++] = p2;
p1 = p3;
k = i-1; //p3's position
p2 = pStr[i++];
if (!p2) break;
p3 = pStr[i++];
cCount = 0;
}
else { /*aab */
verbatim = true;
p1 = p2;
p2 = p3;
p3 =pStr[i++];
}
}
}
else { //no run
verbatim = true;
p1 = p2;
p2 = p3;
p3 =pStr[i++];
}
}
//possible run or no run here
if (cCount0) {
pNew[pos++] = -cCount;
pNew[pos++] = p2;
} else {
if (klength) {
pNew[pos++] = length-k-1;
for (int t=k;tlength;t++) {
pNew[pos++]=pStr[t];
}
}
}
pNew[pos]='\0';
return 1;
}
void rleDecode(char *pEnc, char *pDec, char *pOrig)
{
int i = 0;
int pos =0;
int count ;
char character ;
do {
count = pEnc[i++];
if (count 0) {
count = 2-count;
character = pEnc[i++];
for (int j=0;jcount;j++)
pDec[pos++] = character;
}
else {
//pNew[pos++]=character;
for (int j=0;jcount;j++) {
pDec[pos++]=pEnc[i++];
}
}
}while (pEnc[i]);
pDec[pos]='\0';
for(int i=0;ilen;i++)
if (pOrig[i]!=pDec[i]) cout JERK, do it again!! (: endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
char *pStr = (char *)malloc(sizeof(char)*len);
pStr = abccdddijkk; //TRY more examples
char *pNew = (char *)malloc(sizeof(char)*len);
char *pDec = (char *)malloc(sizeof(char)*len);
//rleSimple(pStr,pNew);
rle(pStr,len,pNew);
rleDecode(pNew, pDec, pStr);
return 0;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Fri, Jun 8, 2012 at 9:04 AM, Ashish Goel ashg...@gmail.com wrote:
The idea here is that there will be parts of the stream which actually
should not be compressed. For example abcdef as well as aa do not need any
compression. We need to compress only if 3 characters match because for
compressing two chars we will take up 2 chars so no compression benefit (:
So we need to keep a pos as a reference to say that here is the position
in the string i am processing now and do the compress(either verbatim or
real compress) when 3 same chars are found
eg
abcfdgffg: pos is 0 and at index 8 we get to know that there is a run,
so we should say 8-3+1=6 need to go verbatim so we write 6abcfdg and update
pos to index 6, and count to 1. Since now run flag is on, we continue till
we find a triplet mismatch(f==f but f!=g) which happens at g (index
12)implying an end to a run, therefore now count is 4, we would write 4f
implying 2+4 times of next char should be expanded. now again pos will be
set to 12, count to 0 and three same char check should re-begin. This will
for sure have 2 while loops and a bit comex, and i donot think this is what
the interviewer should expect one to code. Kindly note that if run is more
than max length, we need to tweak the writing part too.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Jun 7, 2012 at 7:05 PM, Navin Gupta navin.nit...@gmail.comwrote:
If abcdef is changed to a1b1c1d1e1f1,
then we need to allocate memory dynamically.
Because length is increased,I think this has no practical
implementation.As abcdef serves the same purpose.
On Sunday, 3 June 2012 09:36:25 UTC+5:30, utsav sharma wrote:
@ashish:-algo given in link wiil fail for abcdef
@navin:- output of abcdef should be 1a1b1c1d1e1f
On Sun, May 27, 2012 at 3:24 PM, Ashish Goel ashg...@gmail.com wrote:
Will fail for the sing having say 257characters all same
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sat, May 26, 2012 at 12:26 PM, Navin Gupta
navin.nit...@gmail.comwrote:
This is called Run-Length-Encoding (RLE) of a string.
Its purpose is to save space.So in case of abcdef,I think the output
needed is abcdef (1 is implicit).
The added benefit is it makes the solution in-place.
Approach:- (In-place and Linear Time)
Start from the left of string and PREVIOUS_CHAR = str[0]
move forward till u match the CURRENT_CHAR with PREVIOUS_CHAR and keep
count of PREVIOUS_CHAR
At any point if (PREVIOUS_CHAR!=CURRENT_CHAR)
put the count of prev_char next to the start position of the
previous character.
Below is the working code :-
void torle(char *str)
{ int i=0,j=0,k=0,cnt=1;
char cur_char=str[0],num[100];
while(str[j+1])
{
cnt=1;
while(str[j+1]==cur_char str[j]!='\0
[algogeeks] Book Feedback needed for book from Narasimha Karumanchi
Hi, I came across Data Structures and Algorithms Made Easy: Data Structure and Algorithmic Puzzles Request for feedback if it is worth purchase. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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.
Re: [algogeeks] first Repeating character in a string
This is MS Q and hasing will give the right answer. walk over the string, if it is present in hashTable, it is first repeated character. This is single pass. However, if you do another pass, your answer would be a which is first char that is repeated whereas b is first character to occur first again in the string. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Fri, Jun 8, 2012 at 2:15 PM, himanshu kansal himanshukansal...@gmail.com wrote: how can we find 1st repeating character in string??? e.g. if the string is abba it should return 'b' and not 'a'. note: hashing will give the answer as 'a' -- 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.
Re: [algogeeks] Re: MS question : string compression
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Fri, Jun 8, 2012 at 12:54 PM, Ashish Goel ashg...@gmail.com wrote:
#include stdafx.h
#include iostream
using namespace std;
const int len = 20;
const int maxCount = 127;
int rle(char* pStr, int length, char* pNew) {
if (!pStr) return -1;
if (length 3) return -1;
int i = 0;
int k = 0;
char p1 = pStr[i++];
char p2 = pStr[i++];
char p3 = pStr[i++];
int pos=0;
int cCount = 0;
bool verbatim = false;
while ((p3) (ilength)) {
if (p1==p2) {
if (p2==p3) {
if (i == k+3) //no vRun
verbatim = false;//no vRun befor this cRun
if (verbatim)
{
int vEnd = (i-3)-k;;
pNew[pos++] = vEnd;
for (int t=k;tvEnd;t++) {
pNew[pos++]=pStr[t];
}
}
cCount++;
if (cCount == maxCount) {
pNew[pos++] = -cCount; ///
pNew[pos++] = p3;
p1 = pStr[i++];
if (!p1) break;
k = 0;
p2 = pStr[i++];
if (!p2) break;
p3 = pStr[i++];
cCount = 0;
continue;
} else {
/*p1 = p2;
p2 = p3; //not required*/
p3 = pStr[i++];
}
}
else { //run end or no run at all
if (cCount 0) { //a run
pNew[pos++] = -cCount; ///
pNew[pos++] = p2;
p1 = p3;
k = i-1; //p3's position
p2 = pStr[i++];
if (!p2) break;
p3 = pStr[i++];
cCount = 0;
}
else { /*aab */
verbatim = true;
p1 = p2;
p2 = p3;
p3 =pStr[i++];
}
}
}
else { //no run
verbatim = true;
p1 = p2;
p2 = p3;
p3 =pStr[i++];
}
}
//possible run or no run here
if (cCount0) {
pNew[pos++] = -cCount;
pNew[pos++] = p2;
} else {
if (klength) {
pNew[pos++] = length-k-1;
for (int t=k;tlength;t++) {
pNew[pos++]=pStr[t];
}
}
}
pNew[pos]='\0';
return 1;
}
void rleDecode(char *pEnc, char *pDec, char *pOrig)
{
int i = 0;
int pos =0;
int count ;
char character ;
do {
count = pEnc[i++];
if (count 0) {
count = 2-count;
character = pEnc[i++];
for (int j=0;jcount;j++)
pDec[pos++] = character;
}
else {
//pNew[pos++]=character;
for (int j=0;jcount;j++) {
pDec[pos++]=pEnc[i++];
}
}
}while (pEnc[i]);
pDec[pos]='\0';
for(int i=0;ilen;i++)
if (pOrig[i]!=pDec[i]) cout JERK, do it again!! (: endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
char *pStr = (char *)malloc(sizeof(char)*len);
pStr = abccdddijkk; //TRY more examples
char *pNew = (char *)malloc(sizeof(char)*len);
char *pDec = (char *)malloc(sizeof(char)*len);
//rleSimple(pStr,pNew);
rle(pStr,len,pNew);
rleDecode(pNew, pDec, pStr);
return 0;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Fri, Jun 8, 2012 at 9:04 AM, Ashish Goel ashg...@gmail.com wrote:
The idea here is that there will be parts of the stream which actually
should not be compressed. For example abcdef as well as aa do not need any
compression. We need to compress only if 3 characters match because for
compressing two chars we will take up 2 chars so no compression benefit (:
So we need to keep a pos as a reference to say that here is the position
in the string i am processing now and do the compress(either verbatim or
real compress) when 3 same chars are found
eg
abcfdgffg: pos is 0 and at index 8 we get to know that there is a
run, so we should say 8-3+1=6 need to go verbatim so we write 6abcfdg and
update pos to index 6, and count to 1. Since now run flag is on, we
continue till we find a triplet mismatch(f==f but f!=g) which happens at g
(index 12)implying an end to a run, therefore now count is 4, we would
write 4f implying 2+4 times of next char should be expanded. now again pos
will be set to 12, count to 0 and three same char check should re-begin.
This will for sure have 2 while loops and a bit comex, and i donot think
this is what the interviewer should expect one to code. Kindly note that if
run is more than max length, we need to tweak the writing part too.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Jun 7, 2012 at 7:05 PM, Navin Gupta navin.nit...@gmail.comwrote:
If abcdef is changed to a1b1c1d1e1f1,
then we need to allocate memory dynamically.
Because length is increased,I think this has no practical
implementation.As abcdef serves the same purpose.
On Sunday, 3 June 2012 09:36:25 UTC+5:30, utsav sharma wrote:
@ashish:-algo given in link wiil fail for abcdef
@navin:- output of abcdef should be 1a1b1c1d1e1f
On Sun, May 27, 2012 at 3:24 PM, Ashish Goel ashg...@gmail.com wrote:
Will fail for the sing having say 257characters all same
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sat, May 26, 2012 at 12:26 PM, Navin Gupta
navin.nit...@gmail.comwrote:
This is called Run-Length-Encoding (RLE) of a string.
Its purpose is to save space.So in case of abcdef,I think the output
needed is abcdef (1 is implicit).
The added benefit is it makes the solution in-place.
Approach:- (In-place and Linear
Re: [algogeeks] first Repeating character in a string
no hashtable needed , a bitmap is sufficient
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Fri, Jun 8, 2012 at 4:04 PM, saurabh singh saurab...@gmail.com wrote:
The key doesn't lies in the way it will be solved.It is how efficiently
you implement the hash table.do we really need an integer array ( 4*256
bytes) just to record the first occurrence of a character?
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Fri, Jun 8, 2012 at 2:36 PM, Nishant Pandey
nishant.bits.me...@gmail.com wrote:
you may use look up table for each character like this :
int table[255]={0};
for(int i=0;str[i];i++)
{
if( table[str[i]] )
return true;
else
{
table[str[i]]=1;
}
}
return false;
On Fri, Jun 8, 2012 at 2:26 PM, Anika Jain anika.jai...@gmail.comwrote:
you will have to note time for of occurence of a character for all chars
On Fri, Jun 8, 2012 at 2:15 PM, himanshu kansal
himanshukansal...@gmail.com wrote:
how can we find 1st repeating character in string???
e.g. if the string is abba it should return 'b' and not 'a'.
note: hashing will give the answer as 'a'
--
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
Anika Jain
--
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.
--
Cheers,
Nishant Pandey |Specialist Tools Development |
npan...@google.comgvib...@google.com |
+91-9911258345
--
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.
--
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.
Re: [algogeeks] Finding largest zigzag subsequence
O(n) is straight forward
bool increase = true;
int j = 0;
result[j++]=a[0];
for (int i=1;in;i++)
{
if ((increase)
{
if (result[j-1]a[i]))
{
result[j++] = a[i];
increase = false;
}
}
else {
if (result[j-1] a[i]))
{
result[j++] = a[i];
increase = true;
}
}
}
What i was thinking is to find the number of peaks and valleys through
binary search thereby using log(n) solution not able to conceptualize it
this way (:.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Fri, Jun 8, 2012 at 3:47 PM, Ratan success.rata...@gmail.com wrote:
Given a list of integers n, we have to find the length of largest
zigazg subsequence in the list i.e,zigzag subsequence is defined
as if the first number is increasing then the 2nd one should be
decreasing or vice versa..
for eg : if list[n]={1,10,5,9,8,12,20} then,
largest zigzag subsequence will be : {1,10,5,9,8,12} or
{1,10,5,9,8,20} and length will be=6;
--
--
--
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.
Re: [algogeeks] If any one have algorithms for interviews by adnan aziz ebook... Please mail ...
please send me the download link @hi.ashish...@gmail.com. ..Thanks On Thu, Jun 7, 2012 at 3:28 PM, sengar.mahi sengar.m...@gmail.com wrote: http://users.ece.utexas.edu/~adnan/afi-samples.pdf is dis wat u al r lukin 4?? On Thu, Jun 7, 2012 at 3:01 PM, Abhishek Sharma abhi120...@gmail.comwrote: yes,it is helpful,but read it only if u have fully understood Introduction to algorithms or if u have strong foundation of algorithms/data structures On Thu, Jun 7, 2012 at 12:37 PM, BUBUN SHEKHAR dce.stu...@gmail.comwrote: Guys is this book useful for cracking interviews?? On Mon, Jun 4, 2012 at 1:31 AM, Dhaval Moliya moliyadha...@gmail.comwrote: If any one have algorithms for interviews by adnan aziz ebook... Please mail ... Thanks -- 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. -- Abhishek Sharma Under-Graduate Student, PEC University of Technology -- 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. -- Ashish Kumar Bharat Electronics Ltd Ghaziabad +91 8527110885 -- 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.
Re: [algogeeks] Re: MS question : string compression
The idea here is that there will be parts of the stream which actually
should not be compressed. For example abcdef as well as aa do not need any
compression. We need to compress only if 3 characters match because for
compressing two chars we will take up 2 chars so no compression benefit (:
So we need to keep a pos as a reference to say that here is the position in
the string i am processing now and do the compress(either verbatim or real
compress) when 3 same chars are found
eg
abcfdgffg: pos is 0 and at index 8 we get to know that there is a run,
so we should say 8-3+1=6 need to go verbatim so we write 6abcfdg and update
pos to index 6, and count to 1. Since now run flag is on, we continue till
we find a triplet mismatch(f==f but f!=g) which happens at g (index
12)implying an end to a run, therefore now count is 4, we would write 4f
implying 2+4 times of next char should be expanded. now again pos will be
set to 12, count to 0 and three same char check should re-begin. This will
for sure have 2 while loops and a bit comex, and i donot think this is what
the interviewer should expect one to code. Kindly note that if run is more
than max length, we need to tweak the writing part too.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Jun 7, 2012 at 7:05 PM, Navin Gupta navin.nit...@gmail.com wrote:
If abcdef is changed to a1b1c1d1e1f1,
then we need to allocate memory dynamically.
Because length is increased,I think this has no practical
implementation.As abcdef serves the same purpose.
On Sunday, 3 June 2012 09:36:25 UTC+5:30, utsav sharma wrote:
@ashish:-algo given in link wiil fail for abcdef
@navin:- output of abcdef should be 1a1b1c1d1e1f
On Sun, May 27, 2012 at 3:24 PM, Ashish Goel ashg...@gmail.com wrote:
Will fail for the sing having say 257characters all same
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sat, May 26, 2012 at 12:26 PM, Navin Gupta navin.nit...@gmail.comwrote:
This is called Run-Length-Encoding (RLE) of a string.
Its purpose is to save space.So in case of abcdef,I think the output
needed is abcdef (1 is implicit).
The added benefit is it makes the solution in-place.
Approach:- (In-place and Linear Time)
Start from the left of string and PREVIOUS_CHAR = str[0]
move forward till u match the CURRENT_CHAR with PREVIOUS_CHAR and keep
count of PREVIOUS_CHAR
At any point if (PREVIOUS_CHAR!=CURRENT_CHAR)
put the count of prev_char next to the start position of the
previous character.
Below is the working code :-
void torle(char *str)
{ int i=0,j=0,k=0,cnt=1;
char cur_char=str[0],num[100];
while(str[j+1])
{
cnt=1;
while(str[j+1]==cur_char str[j]!='\0'){
j++;
cnt++;
}
str[i++]=cur_char;
if( cnt9 ){
itoa(cnt,num);
k=0;
while(num[k]) str[i++]=num[k++];
}
else if( cnt1 cnt10 )
str[i++]= cnt+'0';
j++;
if(str[j]) cur_char=str[j];
}
if(i!=0){
if(cnt==1)
str[i++]=cur_char;
str[i]='\0';
}
}
On Saturday, 26 May 2012 04:32:35 UTC+5:30, utsav sharma wrote:
Implement a method to perform basic string compression using the
counts of repeated characters.(inplace)
eg:- input: aaabcdef
output:3a5b1c1d1e1f.
what should be my approach to this problem
if i calculate the size of array required to store the output string
and start from the last of the array then i wldn't get the right
answer of above input case.
and if start from front then i wldn't get the right answer of this
input case
eg:- input: abcdef
output: 1a1b1c1d1e1f
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To view this discussion on the web visit https://groups.google.com/d/**
msg/algogeeks/-/4LxWHEUJuK8Jhttps://groups.google.com/d/msg/algogeeks/-/4LxWHEUJuK8J
.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to algogeeks+unsubscribe@**
googlegroups.com algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at http://groups.google.com/**
group/algogeeks?hl=en 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+unsubscribe@**
googlegroups.com algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at http://groups.google.com/**
group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
Re: [algogeeks] Re: amazon interview questions
Hassan geke should not be a valid string. The question states which have the same substring following it so here e follows e. There is no precondition that it has to follow immediate. Utsav: can you clarify? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 11:32 PM, Hassan Monfared hmonfa...@gmail.comwrote: yes It's valid, cuz it doesn't have any repeated substring next together On Tue, Jun 5, 2012 at 7:08 PM, Lomash Goyal lomesh.go...@gmail.comwrote: is geke is a invalid strng? On Tue, Jun 5, 2012 at 12:17 PM, Hassan Monfared hmonfa...@gmail.comwrote: Ashish: the algorithm passes over string and check if there is any substring with len=1 is repeated or not. if not, tries for substring with len 2,... and so on. max length of substring which can be repeated can be at most N/2. Regards, On Tue, Jun 5, 2012 at 10:48 AM, Ashish Goel ashg...@gmail.com wrote: The problem suggests that a character can't be more than once present and thereby it can be done by just having s bitmap and if a char repeats, any longer repeating substring will have those char repeated atleast twice, hence O(n) solution. Also, Hasaan: how is your algo O(n2) for for-while-for chain? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 11:42 AM, Ashish Goel ashg...@gmail.com wrote: Hassan, can you explain your algo? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared hmonfa...@gmail.comwrote: for -- 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. -- Regards Lomash Goyal * * -- 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. -- 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.
Re: [algogeeks] Re: interview HARD problem
Gene, you are right, the rectangle is valid if rotated by 90 degrees too. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 7:45 PM, Gene gene.ress...@gmail.com wrote: Does this sufficae? Suppose you were using a dictionary from the frapplewonk language, which has only 5 words: tab oma to am ba Then the biggest rectangle is clearly tab oma On Jun 4, 10:39 pm, Ashish Goel ashg...@gmail.com wrote: preparing a sample itself is a great problem here, that is why i called it hard all words in the rectangle horizontally as well as vertically needs to be valid dictionary words Ashish Hassan say this rectangle AH,SA,HS,IS,SA,HN should also be valid dictonary words, indeed they are not.. definitely we will need a multimap to have words of same length forming a bucket..not able to think beyond this Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Jun 4, 2012 at 6:38 PM, Hassan Monfared hmonfa...@gmail.com wrote: Give a sample please On Mon, Jun 4, 2012 at 5:34 PM, Ashish Goel ashg...@gmail.com wrote: Given a dictionary of millions of words, give an algorithm to find the largest possible rectangle of letter that every row forms a word(reading left to right) and every column forms a word(reading from top to bottom). Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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. -- 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] 2 Dim array as parameter
Hi, traditional C style of passing 2D array to a C func is for example, void func(char **pArr, int m, int n). Like we validate a pointer before accessing it if it is valid, how do we verify that the array provided indeed has got memory allocated to it before accessing it Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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] MS Question : find word in 2D array
WAP to find a word in a 2D array. The word can be formed on row/col/diagnal/reverse diagnal Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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] MS Q: how to test a driverless car?
Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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.
Re: [algogeeks] Re: amazon interview questions
Thanks, my approach prepare a multimap of charcters and their positions by walking over the string. ashishis if is give string the multimap will have a-0 s-1,4,7 h-2,5 i-3,6 now for every character while walkingover the given string again, check from its multimap, if it is repeated, if not continue to next char. but if it is for all possible differences w.r.t this position, find the repeated string eg for s the values are 4-1=3 and 7-1=6 so if the string repeats than the next 3-1 or 6-1 chars should also have the diff exactly the same the next tow chars are h and i for h current pos is 2 and the diff is 5-2=3 which is good for i current pos is 3 and the diff is 6-3=3, hence shi is indeed a repeating string immediately and hence it is not a valid string. Had it not matched, we would have started for string of length 6 starting at a[7]. hope this helps. But this is not O(n) algo. O(n2) actually in worst case. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jun 6, 2012 at 12:52 PM, atul anand atul.87fri...@gmail.com wrote: nope geke is valid string.. here is the link from where question was taken http://geeksforgeeks.org/forum/topic/amazon-interview-question-password-checker On Wed, Jun 6, 2012 at 11:44 AM, Ashish Goel ashg...@gmail.com wrote: Hassan geke should not be a valid string. The question states which have the same substring following it so here e follows e. There is no precondition that it has to follow immediate. Utsav: can you clarify? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 11:32 PM, Hassan Monfared hmonfa...@gmail.comwrote: yes It's valid, cuz it doesn't have any repeated substring next together On Tue, Jun 5, 2012 at 7:08 PM, Lomash Goyal lomesh.go...@gmail.comwrote: is geke is a invalid strng? On Tue, Jun 5, 2012 at 12:17 PM, Hassan Monfared hmonfa...@gmail.comwrote: Ashish: the algorithm passes over string and check if there is any substring with len=1 is repeated or not. if not, tries for substring with len 2,... and so on. max length of substring which can be repeated can be at most N/2. Regards, On Tue, Jun 5, 2012 at 10:48 AM, Ashish Goel ashg...@gmail.comwrote: The problem suggests that a character can't be more than once present and thereby it can be done by just having s bitmap and if a char repeats, any longer repeating substring will have those char repeated atleast twice, hence O(n) solution. Also, Hasaan: how is your algo O(n2) for for-while-for chain? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 11:42 AM, Ashish Goel ashg...@gmail.comwrote: Hassan, can you explain your algo? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared hmonfa...@gmail.com wrote: for -- 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. -- Regards Lomash Goyal * * -- 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. -- 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
Re: [algogeeks] Re: amazon interview questions
*tree substrings*
tree--|---mississippim .. mississippi
|
|---i--|---ssi--|---ssippi i .. ississippi
| | |
| | |---ppi issip,issipp,issippi
| |
| |---ppiip, ipp, ippi
|
|---s--|---si--|---ssippis .. ssissippi
| ||
| ||---ppi ssip, ssipp, ssippi
| |
| |---i--|---ssippi si .. sissippi
| |
| |---ppisip, sipp, sippi
|
|---p--|---pi p, pp, ppi
|
|---i p, pi
*--- Suffix Tree for mississippi ---*
in this example, any bifurcation implies that the substring is repeated(eg
i, s, ss, si, p, issi) and looks like this problem can be done while
forming the suffix trie
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jun 5, 2012 at 12:28 AM, Abhishek Sharma abhi120...@gmail.comwrote:
I think it can be done by modifying the h-array and by making some changes
in KMP-algorithm
On Mon, Jun 4, 2012 at 9:35 AM, Jeevitesh jeeviteshshekha...@gmail.comwrote:
i have not implemented it but i can you an idea how to approach it.
Go to Each suffix in suffix or suffix array(I would prefer suffix array
as it is easier) traverse the each suffix till you encounter the first
letter of the suffix you are traversing and check to see this suppose i is
the index you found out the starting letter then check
s.substring(0,i)==s.substring(i,2i).
I hope you get the idea.
On Mon, Jun 4, 2012 at 9:14 AM, utsav sharma utsav.sharm...@gmail.comwrote:
@jeevitesh :- yes i am also thinking of suffix tree,
but i am facing problem in implementing it. did you implement it ??
On Mon, Jun 4, 2012 at 9:11 AM, utsav sharma
utsav.sharm...@gmail.comwrote:
@hassan :- it will not work for many strings as you are checking from
the mid of strings. try out ababcdef,aabc.
@atul :- it should be done in O(n).
On Sun, Jun 3, 2012 at 11:54 PM, Hassan Monfared
hmonfa...@gmail.comwrote:
yes it's not valid
On Sun, Jun 3, 2012 at 5:36 PM, anugrah anugrah.agra...@gmail.comwrote:
So any string with two same characters is not valid??
for example :
GEEK has E followed by E.
So GEEK is also invalid?
On Jun 3, 1:49 pm, Hassan Monfared hmonfa...@gmail.com wrote:
bool IsValid(string s)
{
for(int len=0;lens.len/2;len++)
{
int start1=0,start2=len+1;
while(start2s.size())
{
for(int i=0;ilen start2+is.size()
s[start1+i]=s[start2+i];i++);
if(i==len)
return false; //not valid
start1++;
start2++;
}
}
return true; // valid
}
On Sun, Jun 3, 2012 at 12:52 PM, atul anand
atul.87fri...@gmail.com wrote:
can be done with O(n^2) time complexity..
can it be done with O(n) complexity ???
On 6/3/12, utsav sharma utsav.sharm...@gmail.com wrote:
given a string tell wether it is valid or not.
string is valid if there is no substring which have the same
substring
following it.
these strings are not valid:- stringstring,geek123123rt,
abcadabcad,strngstingstrngsting
--
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.
--
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.
--
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
Re: [algogeeks] Re: amazon interview questions
Hassan, can you explain your algo? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared hmonfa...@gmail.comwrote: for -- 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.
Re: [algogeeks] Re: amazon interview questions
The problem suggests that a character can't be more than once present and thereby it can be done by just having s bitmap and if a char repeats, any longer repeating substring will have those char repeated atleast twice, hence O(n) solution. Also, Hasaan: how is your algo O(n2) for for-while-for chain? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 11:42 AM, Ashish Goel ashg...@gmail.com wrote: Hassan, can you explain your algo? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared hmonfa...@gmail.comwrote: for -- 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.
Re: [algogeeks] Re: interview HARD problem
yes, but this rectangle clause is troubling me... Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 3:18 PM, rafi rafiwie...@gmail.com wrote: you mean like scramble ? On Jun 5, 5:39 am, Ashish Goel ashg...@gmail.com wrote: preparing a sample itself is a great problem here, that is why i called it hard all words in the rectangle horizontally as well as vertically needs to be valid dictionary words Ashish Hassan say this rectangle AH,SA,HS,IS,SA,HN should also be valid dictonary words, indeed they are not.. definitely we will need a multimap to have words of same length forming a bucket..not able to think beyond this Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Jun 4, 2012 at 6:38 PM, Hassan Monfared hmonfa...@gmail.com wrote: Give a sample please On Mon, Jun 4, 2012 at 5:34 PM, Ashish Goel ashg...@gmail.com wrote: Given a dictionary of millions of words, give an algorithm to find the largest possible rectangle of letter that every row forms a word(reading left to right) and every column forms a word(reading from top to bottom). Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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. -- 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] interview HARD problem
Given a dictionary of millions of words, give an algorithm to find the largest possible rectangle of letter that every row forms a word(reading left to right) and every column forms a word(reading from top to bottom). Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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.
Re: [algogeeks] interview HARD problem
preparing a sample itself is a great problem here, that is why i called it hard all words in the rectangle horizontally as well as vertically needs to be valid dictionary words Ashish Hassan say this rectangle AH,SA,HS,IS,SA,HN should also be valid dictonary words, indeed they are not.. definitely we will need a multimap to have words of same length forming a bucket..not able to think beyond this Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Jun 4, 2012 at 6:38 PM, Hassan Monfared hmonfa...@gmail.com wrote: Give a sample please On Mon, Jun 4, 2012 at 5:34 PM, Ashish Goel ashg...@gmail.com wrote: Given a dictionary of millions of words, give an algorithm to find the largest possible rectangle of letter that every row forms a word(reading left to right) and every column forms a word(reading from top to bottom). Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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. -- 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.
RE: [algogeeks] MS Question: WAP to find files in a
directory/subdirectories MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit The question is to implement without use of any library Sent from my Windows Phone From: atul anand Sent: 03-06-2012 11:19 To: algogeeks@googlegroups.com Subject: Re: [algogeeks] MS Question: WAP to find files in a directory/subdirectories i wrote this program in college labbut used shell script to simulate ls -r functionality. now to do in c or java .. we only need to knw about the libraries to use. On 6/3/12, Ashish Goel ashg...@gmail.com wrote: ls-r implementation needed... Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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. -- 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] MS Question: WAP to find files in a directory/subdirectories
ls-r implementation needed... Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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.
Re: [algogeeks] Amazon : exponentiation(x,n)
the return type is int, hence when xpowern becomes bigger than INT_MAX, it
should throw an exception.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 31, 2012 at 11:59 AM, Amol Sharma amolsharm...@gmail.comwrote:
i didn't got your problem where is the overflow.. ??
btw i will do the same like this :
int pow(int b, int e)
{
int result = (e 1) ? b:1;
while( e 1 )
{
b = ((long long int)b * b);
e = 1;
if( e 1 )
result = ((long long int)result * b);
}
return result;
}
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Thu, May 31, 2012 at 9:54 AM, Ashish Goel ashg...@gmail.com wrote:
This algo is log(n) algo for finding power. However, this also has a
problem of overflow. How do we control this.
int power(int x, int n) {
int expo =1;
int even=x;
while (n0)
{
while (n 0x1==0) {
n=1; /*divide by 2*/
even*=even;
}
expo = expo*even;
n=1; /*n will be odd here always*/
}
return expo;
}
this is utilizing the fact that n is a binary number and can be written
as x*xE when odd or xE otherwise.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
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.
--
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] MS Question: Delete a node in single linked list if it is less than any of the successor nodes
the LL is unsorted, is there any better solution that this?
struct node* deleteNodes(struct node *pHead, struct node *pPrev)
{
struct node *pLL = *pHead;
if (!pLL) return NULL;
struct node *pCurr = pLL;
struct node *pRest = deleteNodes(pCurr-next, pCurr);
if (!pRest) return pCurr;
if (pCurr-data pRest-data)
{
if (pPrev) { pPrev-next = pRest; };
free(pCurr);
}
else
{
pCurr-next = pRest;
}
return pCurr;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
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.
Re: [algogeeks] MS Question: Delete a node in single linked list if it is less than any of the successor nodes
yes
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 31, 2012 at 2:34 PM, atul anand atul.87fri...@gmail.com wrote:
@Ashish : please clarify this ques...
delete a node in SLL if it is less than *any* of the succesor node ..
1 2 8 10 3 4 7 12
delete 1,2,8,10,3,4,7
ouput will be single node i.e 12
dats what question asks?
On Thu, May 31, 2012 at 2:16 PM, Ashish Goel ashg...@gmail.com wrote:
the LL is unsorted, is there any better solution that this?
struct node* deleteNodes(struct node *pHead, struct node *pPrev)
{
struct node *pLL = *pHead;
if (!pLL) return NULL;
struct node *pCurr = pLL;
struct node *pRest = deleteNodes(pCurr-next, pCurr);
if (!pRest) return pCurr;
if (pCurr-data pRest-data)
{
if (pPrev) { pPrev-next = pRest; };
free(pCurr);
}
else
{
pCurr-next = pRest;
}
return pCurr;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
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.
--
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.
Re: [algogeeks] MS Question: Delete a node in single linked list if it is less than any of the successor nodes
that is what i have done by using recursion=stack.
my code has problem, after free(pCurr);, i should have return pRest;
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 31, 2012 at 4:37 PM, atul anand atul.87fri...@gmail.com wrote:
then i guess ...it can be done using stack..with O(n) complexity..
it is similar to finding next greater element
http://www.geeksforgeeks.org/archives/8405
element in the stack at the end of the algo...are the element which will
remain in the linked list . if stack is not empty then keep poping elements
and create a SLL.
On Thu, May 31, 2012 at 4:29 PM, Ashish Goel ashg...@gmail.com wrote:
yes
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 31, 2012 at 2:34 PM, atul anand atul.87fri...@gmail.comwrote:
@Ashish : please clarify this ques...
delete a node in SLL if it is less than *any* of the succesor node ..
1 2 8 10 3 4 7 12
delete 1,2,8,10,3,4,7
ouput will be single node i.e 12
dats what question asks?
On Thu, May 31, 2012 at 2:16 PM, Ashish Goel ashg...@gmail.com wrote:
the LL is unsorted, is there any better solution that this?
struct node* deleteNodes(struct node *pHead, struct node *pPrev)
{
struct node *pLL = *pHead;
if (!pLL) return NULL;
struct node *pCurr = pLL;
struct node *pRest = deleteNodes(pCurr-next, pCurr);
if (!pRest) return pCurr;
if (pCurr-data pRest-data)
{
if (pPrev) { pPrev-next = pRest; };
free(pCurr);
}
else
{
pCurr-next = pRest;
}
return pCurr;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
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.
--
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.
--
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] Amazon : exponentiation(x,n)
This algo is log(n) algo for finding power. However, this also has a
problem of overflow. How do we control this.
int power(int x, int n) {
int expo =1;
int even=x;
while (n0)
{
while (n 0x1==0) {
n=1; /*divide by 2*/
even*=even;
}
expo = expo*even;
n=1; /*n will be odd here always*/
}
return expo;
}
this is utilizing the fact that n is a binary number and can be written as
x*xE when odd or xE otherwise.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
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.
Re: [algogeeks] Re: Tree/Graph implementation
Gene: why do you say that adjacency list is not a good solution for sparse
matrix? what other alternates are you looking at?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, May 29, 2012 at 9:09 PM, Gene gene.ress...@gmail.com wrote:
I'm interested to see problems where tree implementation causes a
performance problem. Example?
Choice of graph data structures is very problem-dependent. An
adjacency matrix will probably be fastest and simplest for dense
graphs. For sparse ones there are many, many answers.
An efficient way to do n-ary trees (which are usually sparse graphs)
in C:
typedef struct node_s {
// Use a fixed size array of NODE* if you know
// the maximum number of children in advance.
// Here we assume this isn't true.
struct node_s **children;
int n_children;
...
} NODE;
NODE *make_node(int max_children)
{
// Allocate nodes in a single array if you know the max
// number in advance. Here we assume this isn't true.
NODE *node = safe_malloc(sizeof *node);
node-children = safe_malloc(max_children * sizeof *node-children);
node-n_children = 0;
return node;
}
void add_child(NODE *parent, NODE *child)
{
parent-children[parent-n_children++] = child;
}
void walk
On May 29, 6:17 am, prakash y yprakash@gmail.com wrote:
How to implement complex data structures like trees (with unknown no.of
subtrees) and graphs efficiently in C/Java?
I have implemented binary trees in Java as it always contains two nodes.
But I don't know about graphs.
I am not able to solve these problems in coding contests because of this.
Can anyone please suggest me?
Thanks in advance.
~Prakash.
--
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] problem with increment operator
#includestdio.h
int main()
{
int a=4;
printf(%d\n,++a + ++a + a++);
return 0;
}
according to me output should be 17, but it is coming out to be 18.
plz explain it??
--
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.
Re: [algogeeks] classic problem to tree to circular doubly linked list
//can be improved by having a function to join 2 DLLs
struct node *tree2DLL(struct node * pRoot)
{
if (!pRoot) return NULL;
struct node *pleftDLL = tree2DLL(pRoot-left);
struct node *pRightDLL = tree2DLL(pRoot-right);
//now join left with root
pLeftDLL-left-right = pRoot;
pRoot-left = pleftDLL-left;
pRoot-right= pLeftDLL;
pLeftDLL-left = pRoot;
//now join pLeftDLL and pRightDLL;
struct node* pTemp = pRightDLL-left;
pLeftDLL-left-right = pRightDLL;
pRightDLL-left = pLeftDLL-left;
pTemp-right = pLeftDLL;
pLeftDLL-left = pTemp;
return pLeftDLL;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 24, 2012 at 11:20 PM, rahul r. srivastava
rahul.ranjan...@gmail.com wrote:
hey people
can anyone explain the logic and solution(in simple words) behind the
classical problem of converting binary tree to circular doubly linked list
in inorder fashion.
stanford language seems to be way above my head
http://cslibrary.stanford.edu/109/TreeListRecursion.html
thnx...
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/IyQsfiqEmdUJ.
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.
Re: [algogeeks] Re: MS question : string compression
Will fail for the sing having say 257characters all same
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sat, May 26, 2012 at 12:26 PM, Navin Gupta navin.nit...@gmail.comwrote:
This is called Run-Length-Encoding (RLE) of a string.
Its purpose is to save space.So in case of abcdef,I think the output
needed is abcdef (1 is implicit).
The added benefit is it makes the solution in-place.
Approach:- (In-place and Linear Time)
Start from the left of string and PREVIOUS_CHAR = str[0]
move forward till u match the CURRENT_CHAR with PREVIOUS_CHAR and keep
count of PREVIOUS_CHAR
At any point if (PREVIOUS_CHAR!=CURRENT_CHAR)
put the count of prev_char next to the start position of the previous
character.
Below is the working code :-
void torle(char *str)
{ int i=0,j=0,k=0,cnt=1;
char cur_char=str[0],num[100];
while(str[j+1])
{
cnt=1;
while(str[j+1]==cur_char str[j]!='\0'){
j++;
cnt++;
}
str[i++]=cur_char;
if( cnt9 ){
itoa(cnt,num);
k=0;
while(num[k]) str[i++]=num[k++];
}
else if( cnt1 cnt10 )
str[i++]= cnt+'0';
j++;
if(str[j]) cur_char=str[j];
}
if(i!=0){
if(cnt==1)
str[i++]=cur_char;
str[i]='\0';
}
}
On Saturday, 26 May 2012 04:32:35 UTC+5:30, utsav sharma wrote:
Implement a method to perform basic string compression using the counts
of repeated characters.(inplace)
eg:- input: aaabcdef
output:3a5b1c1d1e1f.
what should be my approach to this problem
if i calculate the size of array required to store the output string
and start from the last of the array then i wldn't get the right answer
of above input case.
and if start from front then i wldn't get the right answer of this input
case
eg:- input: abcdef
output: 1a1b1c1d1e1f
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/4LxWHEUJuK8J.
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.
Re: [algogeeks] Re: MS question : string compression
http://michael.dipperstein.com/rle/index.html
and basic one is
http://www.fileformat.info/mirror/egff/ch09_03.htm
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sat, May 26, 2012 at 1:10 PM, Hassan Monfared hmonfa...@gmail.comwrote:
1- try abb
On Sat, May 26, 2012 at 12:07 PM, Anchal Gupta anchal92gu...@gmail.comwrote:
yeah i forgot inplace so to do that we simply add count and ch in str
input array instead of op.
btw whats wrong with count it give me right answer.
On May 26, 12:08 pm, Hassan Monfared hmonfa...@gmail.com wrote:
u forgot to do inplace and you have wrong conversion of count
On Sat, May 26, 2012 at 11:31 AM, Anchal Gupta anchal92gu...@gmail.com
wrote:
hey, here is the function that do the compression and store the output
in an array op.
void str_comp(char *str)
{
int count=0,j=0,i;
char ch,op[100];
for(i=0;istrlen(str);)
{
ch = str[i];
while(str[i] == ch)
{ count++;
i++;
}
op[j] = count+48;
op[++j] = ch;
j++;
count=0;
}
coutinput : ;
for(i=0;istrlen(str);i++)
coutstr[i];
cout\n\noutput : ;
for(i=0;ij;i++)
coutop[i];
}
Best Regards
Anchal Gupta
USIT(GGSIPU), Delhi
+91-9015897983
--
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.
--
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] Amazon Q: Implement an algorithm to do wild card string matching
Implement an algorithm to do wild card string matching Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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] Amazon Q : Design a logWritter for server kind of application
Design a logWritter for server kind of application Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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] # of paths betweek two nodes in a DAG
My bad, i am not able to conceptualize this known problem, can anyone help Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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.
Re: [algogeeks] Amazon interview question
What is the purpose of these numbers, if the idea is to manage a free pool, then probably 10-ary-tree is the solution. May be Tiger Tree Hash a better answer where it is tree to say level 7 and then for rest three digits it become hash table. This way, the chunks can be kept on different machines too. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, May 24, 2012 at 4:51 PM, Aman Raj amanka...@gmail.com wrote: array of bits? if the current integer is present set the bit if else make it zero, searching, insertion and deletion all in O(1) time. On Thu, May 24, 2012 at 4:15 PM, rishabh shukla rockrishabh.mn...@gmail.com wrote: Suggest a data structure for storing million trillion numbers efficiently in very less space. Means space complexity should be as less as possible -- Rishabh Shukla B.Tech Final Year MNNIT 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. -- 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.
Re: [algogeeks] Amazon interview question
refer http://www.cs.bell-labs.com/cm/cs/pearls/sol01.html Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, May 24, 2012 at 6:00 PM, Ashish Goel ashg...@gmail.com wrote: What is the purpose of these numbers, if the idea is to manage a free pool, then probably 10-ary-tree is the solution. May be Tiger Tree Hash a better answer where it is tree to say level 7 and then for rest three digits it become hash table. This way, the chunks can be kept on different machines too. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, May 24, 2012 at 4:51 PM, Aman Raj amanka...@gmail.com wrote: array of bits? if the current integer is present set the bit if else make it zero, searching, insertion and deletion all in O(1) time. On Thu, May 24, 2012 at 4:15 PM, rishabh shukla rockrishabh.mn...@gmail.com wrote: Suggest a data structure for storing million trillion numbers efficiently in very less space. Means space complexity should be as less as possible -- Rishabh Shukla B.Tech Final Year MNNIT 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. -- 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.
Re: [algogeeks] MS Q
// countIslands.cpp : Defines the entry point for the console application.
//
#include stdafx.h
const int rows = 5;
const int cols = 6;
bool visited[rows][cols] = {0};
int arr[rows][cols] =
{
0,0,0,0,1,1,
0,1,0,0,0,1,
1,1,0,0,0,0,
1,0,0,0,1,1,
0,0,1,0,1,0};
void initialize()
{
for (int i=0; irows;i++) {
for (int j=0; jcols;j++) {
if (arr[i][j] != 1) visited[i][j]=1;
}
}
}
void coverNeighbours( int x, int y)
{
int neighbours[8][2] = {{x-1,y}, {x-1,y+1},{x,y+1},{x+1,y+1},
{x+1,y},{x+1,y-1},{x,y-1},{x-1,y-1}};
for (int i=0;i8;i++)
if ((neighbours[i][0] =0) (neighbours[i][0] rows)
(neighbours[i][1] =0) (neighbours[i][1] cols)
(arr[neighbours[i][0]][neighbours[i][1]] == 1)
(visited[neighbours[i][0]][neighbours[i][1]] == false))
{
visited[neighbours[i][0]][neighbours[i][1]] = true;
coverNeighbours(neighbours[i][0], neighbours[i][1]);
}
}
int countIslands()
{
int result = 0;
if ((rows 0) || (cols 0)) return 0;
if ((rows == 0) (cols == 0)) return arr[0][0];
initialize();
for (int i=0;irows;i++)
{
for (int j=0;jcols;j++) {
if ((arr[i][j] == 1) (visited[i][j] !=1))
{
result++;
visited[i][j] = true;
//don't increase result for the neighbours
coverNeighbours(i,j);
}
}
}
return result;
}
int _tmain(int argc, _TCHAR* argv[])
{
int result=countIslands();
return 0;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jan 10, 2012 at 1:17 PM, Ashish Goel ashg...@gmail.com wrote:
http://www.janaganamana.net/onedefault.aspx?bid=276
did not get it
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jan 10, 2012 at 1:15 PM, Ashish Goel ashg...@gmail.com wrote:
this is a single island, sorry for that
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jan 10, 2012 at 9:24 AM, atul anand atul.87fri...@gmail.comwrote:
@Ashish Goel : didnt get it :(
1 1 0 0
1 1 0 0
0 0 1 1
1-1-1 diagonal is one island ...where is another??
1 1 0 0
1 1 0 0
0 0 1 1
these 1 will be considered one island of 2 island.??
On Tue, Jan 10, 2012 at 7:36 AM, Ashish Goel ashg...@gmail.com wrote:
row, col, diag all
1-1-1 is a single island :)
1 1 0 0
1 1 0 0
0 0 1 1
this has only 2 islands
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jan 10, 2012 at 7:29 AM, Ankur Garg ankurga...@gmail.comwrote:
Can you give an example
Say matrix is
1 1 0 0
1 1 0 0
0 0 1 1
Has it got 3 islands i.e 1-1 be in same row or they can be column wise
also i.e. 5
On Tue, Jan 10, 2012 at 7:09 AM, Ashish Goel ashg...@gmail.comwrote:
there is a matrix of 1 and 0
1 is a island and 0 is water
1-1 together makes one island
calculate total no of islands
Best Regards
Ashish Goel
Think positive and find fuel in failure
--
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.
--
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.
--
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] Google Q : all anagrams next to each other
Write a method to sort an array of strings so that all the anagrams are next to each other. What i could think of is preparing a multi linked list( multimap) whereby the key for each string is the sorted representation of the string(eg if string is gac, its sorted representation is acg). Walk of all lists of this multimap to give all anagrams. Is there any other better solution for this problem? Can this be done *inplace*? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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] Google Q: longest word made of subwords within the list
write a program to find the longest word made of other words. For instance, If my file has the following words (sorted): test tester testertest testing testingtester The longest word should be testingtester. Trie is the solution, what is the best Order possible? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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.
Re: [algogeeks] Re: Amazon Question
For this the cousins of 1 should be 9 8 12 13 14 15 how then can it be a 2 pass algorithm... we should also consider great grandparent as in this case ... Correct me if I m wrong!! the first cousins are 9,8 not 12,13...otherwise the question becomes really simple :) Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, May 21, 2012 at 12:54 PM, sivaviknesh sivavikne...@gmail.comwrote: For this the cousins of 1 should be 9 8 12 13 14 15 how then can it be a 2 pass algorithm... we should also consider great grandparent as in this case ... Correct me if I m wrong!! -- 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.
Re: [algogeeks] Re: Amazon Question
bool firstCousins(struct node * pRoot, struct node *pThis, (struct node*)[]
path, int pos, vectorint firstCousins)
{
if ((!pThis) || (!pRoot)) return false;
if (pRoot-data!=pThis-data) {
path[pos] = pRoot;
if (!findCousins(pRoot-left, pThis, path, pos+1, firstCousins))
return findCousins(pRoot-left, pThis, path, pos+1, firstCousins);
}
if (pos2) return false; //this node is at level 0 or level 1
struct node* pGP = path[pos-2];
struct node *pParent = path[pos-1];
struct node *pUncle = NULL;
if (pParent == pGP-left)
{
pUncle = pGP-right;
}else pUncle = pGP-left;
if (pUncle-left) firstCousins.add(pUncle-left-data);
if (pUncle-right) firstCousins.add(pUncle-right-data);
return true;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, May 21, 2012 at 5:41 PM, Ashish Goel ashg...@gmail.com wrote:
For this the cousins of 1 should be 9 8 12 13 14 15 how
then can it be a 2 pass algorithm... we should also consider great
grandparent as in this case ... Correct me if I m wrong!!
the first cousins are 9,8 not 12,13...otherwise the question becomes
really simple :)
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, May 21, 2012 at 12:54 PM, sivaviknesh sivavikne...@gmail.comwrote:
For this the cousins of 1 should be 9 8 12 13 14 15 how
then can it be a 2 pass algorithm... we should also consider great
grandparent as in this case ... Correct me if I m wrong!!
--
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.
Re: [algogeeks] Re: Microsoft interview question
Dave,
Cant we have a hash table with the item as key and its count as value (walk
over array A and build HT).
For permutation check, walk over second array and start reducing the count
and remove when count becomes zero for that particular key. If some char
not there in HT, return false, else return true.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, May 21, 2012 at 6:14 PM, Dave dave_and_da...@juno.com wrote:
@Piyush: Did you even try this on any examples? If not, try a = {0,1,2,3}
and b = {0,2,2,2}.
Dave
On Sunday, May 20, 2012 1:39:25 AM UTC-5, Kalyan wrote:
Piyush. I think we can use your logic. But You should check the product
also.
Have 4 variables, sum_a,sum_b , prod_a, prod_b
Calculate Sum and product of array 'a' and store it in sum_a,prod_a
Calculate Sum and product of array 'b' and store it in sum_b,prod_b
if sum_a=sum_b prod_a==prod_b then these 2 arrays are permutations
of each other.
Space = O(1)
Time=O(n)
I think this should work. Please correct me if you find mistakes.
On 5/20/12, anuj agarwal coolbuddy...@gmail.com wrote:
U are checking if the sum is same or not.. which can be same even if
the
elements are different.
On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal
piyushkhandelwal...@gmail.com wrote:
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0; in;i++)
{ diff= diff+a[i]-b[i];
}
if diff == 0
print: permutation
else
print: not permutation
On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote:
@Harshit: These are a few unanswered questions that came to mind when
I
read your solution attempt: What do you do with negative elements?
What
is
the -12th prime number? How do you deal with overflow in the cases
where
you have a lot of large prime numbers and the product exceeds your
native
data types?
Dave
On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote:
given 2 unsorted integer arrays a and b of equal size. Determine if
b is
a permutation of a. Can this be done in O(n) time and O(1) space ?
please help me with my solution
suppose a -- 3 5 4
b -- 4 3 5
now we replace a[i] with a[i]..th prime number and b with b[i] ..
th
prime number
now array a becomes 5 11 7
array b becomes 7 5 11
now we take product of elements of array a and do the same with
array b
elements
if product is equal then b is a permutation of a
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/**msg/algogeeks/-/WEW0M5VUUVEJhttps://groups.google.com/d/msg/algogeeks/-/WEW0M5VUUVEJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/**group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en.
--
*Piyush Khandelwal***
Mobile No: 91-8447229204
91-9808479765
--
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+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/**group/algogeeks?hl=enhttp://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+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/**group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en.
--
*
*
*Kalyanasundaram N*
*BE 2nd year, CSE*
*College of Engineering Guindy,*
*Chennai-600025*
*
*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/i-WLn7rdzDYJ.
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
Re: [algogeeks] Re: Microsoft interview question
constant space vs no additional space and then O(n) time complexity not
possible..
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, May 21, 2012 at 8:01 PM, Dave dave_and_da...@juno.com wrote:
@Ashish: Using a hash table violates the O(1) space requirement given in
the original problem.
Dave
On Monday, May 21, 2012 8:53:44 AM UTC-5, ashgoel wrote:
Dave,
Cant we have a hash table with the item as key and its count as value
(walk over array A and build HT).
For permutation check, walk over second array and start reducing the
count and remove when count becomes zero for that particular key. If some
char not there in HT, return false, else return true.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, May 21, 2012 at 6:14 PM, Dave dave_and_da...@juno.com wrote:
@Piyush: Did you even try this on any examples? If not, try a =
{0,1,2,3} and b = {0,2,2,2}.
Dave
On Sunday, May 20, 2012 1:39:25 AM UTC-5, Kalyan wrote:
Piyush. I think we can use your logic. But You should check the product
also.
Have 4 variables, sum_a,sum_b , prod_a, prod_b
Calculate Sum and product of array 'a' and store it in sum_a,prod_a
Calculate Sum and product of array 'b' and store it in sum_b,prod_b
if sum_a=sum_b prod_a==prod_b then these 2 arrays are permutations
of each other.
Space = O(1)
Time=O(n)
I think this should work. Please correct me if you find mistakes.
On 5/20/12, anuj agarwal coolbuddy...@gmail.com wrote:
U are checking if the sum is same or not.. which can be same even if
the
elements are different.
On Sun, May 20, 2012 at 11:54 AM, Piyush Khandelwal
piyushkhandelwal...@gmail.com wrote:
Hiii!! I have some idea about the solution. Please notify me if i am
wrong
a= [ 4,3,5 ] and b= [ 3,5,4 ]
diff=0;
for (i=0; in;i++)
{ diff= diff+a[i]-b[i];
}
if diff == 0
print: permutation
else
print: not permutation
On 20 May 2012 07:2 0, Dave dave_and_da...@juno.com wrote:
@Harshit: These are a few unanswered questions that came to mind
when I
read your solution attempt: What do you do with negative elements?
What
is
the -12th prime number? How do you deal with overflow in the cases
where
you have a lot of large prime numbers and the product exceeds your
native
data types?
Dave
On Saturday, May 19, 2012 2:29:52 PM UTC-5, harshit pahuja wrote:
given 2 unsorted integer arrays a and b of equal size. Determine
if b is
a permutation of a. Can this be done in O(n) time and O(1) space ?
please help me with my solution
suppose a -- 3 5 4
b -- 4 3 5
now we replace a[i] with a[i]..th prime number and b with b[i] ..
th
prime number
now array a becomes 5 11 7
array b becomes 7 5 11
now we take product of elements of array a and do the same with
array b
elements
if product is equal then b is a permutation of a
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/**ms**g/algogeeks/-/WEW0M5VUUVEJhttps://groups.google.com/d/msg/algogeeks/-/WEW0M5VUUVEJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscribe@**googlegr**oups.comalgogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/**group**/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en.
--
*Piyush Khandelwal***
Mobile No: 91-8447229204
91-9808479765
--
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+unsubscribe@**googlegr**oups.comalgogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/**group**/algogeeks?hl=enhttp://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+unsubscribe@**googlegr**oups.comalgogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/**group**/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en.
--
*
*
*Kalyanasundaram N*
*BE 2nd year, CSE*
*College of Engineering Guindy,*
*Chennai-600025*
*
*
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To view this discussion on the web visit https://groups.google.com/d/**
msg/algogeeks/-/i-WLn7rdzDYJhttps
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
i could not understand the Order Analysis of the solution ..is it k*(lg
n)(lg m) or k*lg(mn)
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sun, May 20, 2012 at 11:15 PM, Anika Jain anika.jai...@gmail.com wrote:
@ashish: ya m sorry.. i didnt read the quest properly, it was for any
given number..
On Fri, May 18, 2012 at 11:37 AM, Ashish Goel ashg...@gmail.com wrote:
Anika, what you are talking about is finding a specific element, not the
kth largest or smallest element, can you give a walk through with an
example in case i have understood you incorrectly
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 17, 2012 at 3:33 PM, Anika Jain anika.jai...@gmail.comwrote:
there's a solution of O(log n) where 2D matrix has n rows and n columns.
Apply binary search for the search on the diagonal. when you are left with
just one element after the search apply binary search within that elements
row and its column. you will get the element. O(log n+log n+log n). so
O(log n).
On Wed, May 16, 2012 at 6:36 PM, Prem Krishna Chettri
hprem...@gmail.com wrote:
Well I hv got Something running in my mind buy ofcse need some cornor
case tuning.
If we take sqrt() of the number (say K) than we can avoid looking
into sqrt(k)-1 and sqrt(k)+1 rows and column entirely, which literally
means that the final solution is possible in constant time (the time
independent of k or matrix values), which ofcourse can go upto O(n) in
worst case where N is the Matrix of N Rows and 1 Column as we cannot use
the intelligence of sqrt function to corner the value.
Its seems okei logically to remove those rows and columns as we are
certain that they are sorted in both ways and avoid unnecessary time
looking for the place where it won't belong.
Now the issue is so clear that we can say (sqrt(k)-1)*(sqrt(k)-1)k and
now keep on adding the value to sqrt(k)+1 till U reach k and get corner
that element.
I guess it works..
On Wed, May 16, 2012 at 1:17 PM, Ashish Goel ashg...@gmail.com wrote:
Vikas, can you suggest the logic of this also? I am a bit unclear on
how the 2D arr is being used as a heap and how recursion is used to solve
this
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Oct 13, 2011 at 11:37 PM, vikas
vikas.rastogi2...@gmail.comwrote:
@Sunny, good catch, k X k approach wont work
lets try to use matrix itself as heap
heapify(int cr, int cc, int Nr, int Nc){
mr = cr; mc = cc;
if(cr+1 Nr)
mr = cr+1 mc = cc;
if(cc + 1 Nc min A[cc+1][cr])
mr = cr; mc = cc+1;
if(A[cr][cc] A[mr][mc]){
swap(A[cr][cc] ,A[mr][mc]);
heapify(mr, mc, Nr, Nc);
}
extract_min(){
swap(A[0][0], A[hr][hc]);
if(hc 0) hc--;
else if(hr 0){
hr --;
hc = N;
}
if(hr | hc)
heapify(0, 0, hr, hc);
}
}
On Oct 13, 12:18 pm, sunny agrawal sunny816.i...@gmail.com wrote:
Nopes
Still it does not ensure that duplicates will not be there in the
priority
queue
what i mean is you cannot write directly
do k times{
data = pop()
// let i,j are row and col of data
push(i+1,j);
push(i,j+1);
}
you need to add the following checks
if((i+1,j) is not in the heap) push(i+1,j)
if((i,j+1) is not in the heap) push(i,j+1)
because heap does not automatically check for duplicates
and to check for duplicates we need an extra data structure other
than heap,
which stores that which (i+1,j) are already there in the heap map
can also
be used so overall complexity will go O(k* lg^2K)
On Thu, Oct 13, 2011 at 12:26 PM, anshu mishra
anshumishra6...@gmail.comwrote:
struct data
{
int row, col,
int val;
};
priority_queuedata heap;
now fine?
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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
Re: [algogeeks] Print longest string duplicated M times
soln pls
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sun, May 20, 2012 at 5:49 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote:
I can give you a dynamic programming approach in O(n^2) and O(n) space .
On Tue, May 15, 2012 at 12:22 PM, Ashish Goel ashg...@gmail.com wrote:
I am unclear about the answer provided by Programming Pearls on the
question. What this does is to find longest string whose beginning is
separated by exactly M chars.
The original question is to find the longest string duplicated M times. Any
ideas on the approach for this? I could think of having a suffix tree with
each node keeping a count to keep track of while insertion how many times
this node was passed while going down
#include stdlib.h
#include string.h
#include stdio.h
int pstrcmp(char **p, char **q)
{ return strcmp(*p, *q); }
int comlen(char *p, char *q)
{int i = 0;
while (*p (*p++ == *q++))
i++;
return i;
}
#define M 1
#define MAXN 500
char c[MAXN], *a[MAXN];
int main()
{ int i, ch, n = 0, maxi, maxlen = -1;
while ((ch = getchar()) != EOF) {
a[n] = c[n];
c[n++] = ch;
}
c[n] = 0;
qsort(a, n, sizeof(char *), pstrcmp);
for (i = 0; i n-M; i++)
if (comlen(a[i], a[i+M]) maxlen) {
maxlen = comlen(a[i], a[i+M]);
maxi = i;
}
printf(%.*s\n, maxlen, a[maxi]);
return 0;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
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,
Jalaj Jaiswal
Software Developer,
Adobe Systems
+91-9019947895
*
*
FACEBOOK http://www.facebook.com/jalaj.jaiswal89
LINKEDINhttp://www.linkedin.com/profile/view?id=34803280trk=tab_pro
--
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.
