[algogeeks] Re: Given sequence A_k, k=[1,n] find min{A_k} k=[i,j] in O(logn) time with O(n) memory
On Wednesday, July 23, 2014 8:41:33 AM UTC-4, bujji wrote: Suppose that we are given a sequence of n values x1, x2, ..., xn and seek to quickly answer repeated queries of the form: given i and j, find the smallest value in xi, . . . , xj . Design a data structure that uses O(n) space and answers queries in O(log n) time. For partial credit, your data structure can use O(n log n) space and have O(log n) query time. You can use a segment tree representing the range 1..n. Each tree node stores the sequence index of the minimum element in the represented segment. Querying this structure for a range i..j is just finding all the nodes that represent included subranges and taking the min. How many can that be? It is easy to show that a recursive search from the root will have to look at most two nodes per tree level. Therefore the query is O(2 log n) = O(log n). The tree is best represented in a simple array, since it is nearly complete like an array-based heap. This array will elements 2n-1 elements if n is a power of 2 or at most another factor of 2 if n is arbitrary, so space is clearly O(n). -- 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] Re: override struct definition in c ????
No.
In C++ you can't either. You can declare a new class that _extends_ a
previous one, but you can't change a declaration once it's complete.
On Jun 8, 11:38 am, HARSHIT PAHUJA hpahuja.mn...@gmail.com wrote:
is it possible to override struct definition in c
in header.h header file i have
eg
typedef struct a
{
int ab ;
}
nw in .c file i have included header.h
typedef struct a
{
char c ;
int b;
}
and giving following def i m getting an error ...
*'struct type redefinition'*
So anyways in c anyways to override this error , like in c++ or c# we use
virtual keyword
--
HARSHIT PAHUJA
M.N.N.I.T.
ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: interview HARD problem
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.
[algogeeks] Re: MS: searching problem......help me out...
Finding a given element in an unsorted list in less than O(n) time (with a normal RAM model of computation) is easy to prove impossible. On Jun 3, 11:01 am, abhinav gupta abhinav@gmail.com wrote: We have given a list 14 6 7 15 8 9 we have to find 15 in (log n ) times. -- *Thanks and Regards,* Abhinav Kumar Gupta **abhinav@gmail.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.
[algogeeks] Re: Allocating memory of size 0
This is exactly right. If it happens to work it's probaby because a
pointer to the current top of heap was returned by malloc(), and just
by luck writing to it did not mess anything up. For fun, try this:
main()
{
int *p=malloc(0);
int *q = malloc(sizeof(int));
*p=2566;
*q = 42;
printf(%d\n,*p);
getchar();
}
On Jun 2, 1:16 pm, Karthikeyan V.B kartmu...@gmail.com wrote:
It does not return a valid address.
The result of malloc(0) is implementation defined and therefore unreliable.
Some compiler implementations will cause it to return a NULL pointer,
others may return some other value (but it still can't/shouldn't be used to
access memory).
The memory cannot be used, (however it may require free()ing).
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Tree/Graph implementation
You can look at adjacency lists as a way of compressing the rows of the adjacency matrix. So you can choose instead to compress the columns into lists. This is a reverse adjacency list. You can also compress both dimensions by storing row,col - value mappings in a map (hash table, tree, etc.) There are other variations on adjacency lists. The outer list can be a linked list (single or double), array, or map from node id to list of adjacent nodes. Same for the inner list, but add the possiblity of maps where the key is the label on the edge. Several graph data structures are used for computational geometry: winged edge, half-edge, quad-edge, and vertex lists, for example. These support certain query and edit operations in constant time regardless of vertex degree. The best choice depends on the operations that must be performed and their relative frequency. In this choice you are often trading constant factors of memory usage for speed. On May 31, 2:06 pm, Mad Coder imamadco...@gmail.com wrote: @Gene: Can you tell some other ways of graph representation in case of sparse matrix as till now I consider adjacency list as the best method for the same. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Linked list using void pointer
You didn't say C or C++. It makes a difference. A void pointer is
just a pointer that can point to any kind of data. You convert it to
a specific type by using casts. So just implement an exogenous list
the same way you would if data had some type Foo. The replace all
the Foo pointers with void*. In C++ you can wrap the implementation
in a template so the list methods automatically do the casting.
In case you aren't familiar with the term, an exogenous list is just
one where list nodes _point to_ data rather than containing data. For
example, this list node is exogenous:
typedef struct node_s {
struct node_s *next;
FOO *ptr_to_data; // replace with void* to make this useful for any
data type.
} NODE;
This one is endogenous:
typedef struct node_s {
struct node_s *next;
FOO data;
} NODE;
On May 31, 12:19 am, mahendra sengar sengar.m...@gmail.com wrote:
how to implement generioc linked list..using void pointer...i havent
used void pointer much so, m not able to use it properly in linked
list..please help asap !!!
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: The following problem is a variation of Tower of hanoi problem...Plz suggest on how to approach the following problem...
Since the number of moves must be optimal, this seems to be a search problem. A-Star is the right search algorithm. This is an algorithm that's somewhere between depth first and breadth first. It expands the tree according to a heuristic that you choose, which can shrink the run time enormously. The Wikipedia page on this is not bad http://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode On May 30, 2:41 pm, g4ur4v gauravyadav1...@gmail.com wrote: There are K pegs. Each peg can hold discs in decreasing order of radius when looked from bottom to top of the peg. There are N discs which have radius 1 to N; Given the initial configuration of the pegs and the final configuration of the pegs, output the moves required to transform from the initial to final configuration. You are required to do the transformations in minimal number of moves. A move consists of picking the topmost disc of any one of the pegs and placing it on top of anyother peg. At anypoint of time, the decreasing radius property of all the pegs must be maintained. Constraints: 1= N=8 3= K=5 Input Format: N K 2nd line contains N integers. Each integer in the second line is in the range 1 to K where the i-th integer denotes the peg to which disc of radius i is present in the initial configuration. 3rd line denotes the final configuration in a format similar to the initial configuration. Output Format: The first line contains M - The minimal number of moves required to complete the transformation. The following M lines describe a move, by a peg number to pick from and a peg number to place on. If there are more than one solutions, it's sufficient to output any one of them. You can assume, there is always a solution with less than 7 moves and the initial confirguration will not be same as the final one. Sample Input #00: 2 3 1 1 2 2 Sample Output #00: 3 1 3 1 2 3 2 Sample Input #01: 6 4 4 2 4 3 1 1 1 1 1 1 1 1 Sample Output #01: 5 3 1 4 3 4 1 2 1 3 1 (question taken from facebook hiring sample test .) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Tree/Graph implementation
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.
[algogeeks] Re: classic problem to tree to circular doubly linked list
The recursion invariant is that calling
convert(root, list)
will return a list that is the tree root converted to a singly linked
list connected by 'left' pointers, with list appended at the end.
So if the tree is empty, the corresonding list is empty, so appending
argument 'list' on the end means just returning the argument.
if (root == NULL) return list;
Otherwise the tree is not empty. So we first convert the right
subtree with 'list' appended at its end and attach it to the root's
left pointer, which is now the next pointer.
root-left = convert(root-right, list);
But this overwrites root-left, and we still need the old value, so
insert:
NODE *left_subtree = root-left;
This is the root of the left subtree.
Now convert the left subtree to a list with the list having 'root' as
its first node appended at the end.
return convert(left_subtree, root);
Sorry in my original post I had a typo.
On May 27, 9:54 am, atul anand atul.87fri...@gmail.com wrote:
@Gene :
NODE *convert(NODE *root, NODE *list)
{
if (root == NULL) return list;
NODE *left_subtree = root-left;
root-left = convert(root-right, list);
return convert(left_subtree, root);
}
what *tree(left_subtree, root)* function doing here??
On Sun, May 27, 2012 at 7:12 PM, Gene gene.ress...@gmail.com wrote:
Another approach is to form a singly linked, NULL-terminated list
(connected e.g. by 'left' pointers). This is a harder problem, and
it
might be required if you have a purpose for the other (right)
pointer. If you need a doubly linked list it's easy to walk down the
singly linked one, creating 'previous' pointers as you go.
The converter accepts both a tree and list that's already in the
correct order, which should be appended at the end of the converted
tree. The result of the append operation should be returned.
NODE *convert(NODE *root, NODE *list)
{
if (root == NULL) return list;
NODE *left_subtree = root-left;
root-left = convert(root-right, list);
return tree(left_subtree, root);
}
I like this solution because it's so simple. Initiate it with
convert(tree, NULL);
If you really need the double links:
void adjust(NODE *head)
{
NODE *p, *q;
for (q = NULL, p = head; p; q = p, p = p-next)
p-right = q;
head-right = q;
q-right = head;
}
On May 26, 3:07 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
Both the explanations above are wrong . It is true that BST can be
converted to a Doubly linked list by doing inorder traversal.
But the approach mentioned in the stanford link follows a postorder
Approach , it is better because it avoids useage of a static/global
variable which is required in inorder Approach.
recursively changing the small and large sub-trees into lists, and then
append those lists together with the parent node to make larger lists -
quoted from the stanford page. (parent is visited after the subtrees)
Explanation of the postorder Approach :-
refer to the drawing in the page.
FIrst of all it makes the node named 1 as a an independent node after
that
as in postorder it makes node 3 as an independent node . Independent here
means
root-left=root-right=NULL.
After that it comes to node 2 . ( Note that it is happening in postorder
fashion) .
then it makes node 2 as independent and append it with the list returned
from left side(which is independent node 1) and list returned from right
side *(which is independent node 3) and make the left side returned node
as
head and follows the process recursively . The order is similar to
inorder
apptoach which is O(n).
*IF you want to know the inorder approach as well, Here it is :-*
void BSTTODLL( node *root){
static int count = 0 ;
static node * temp = NULL:
if(root != NULL){
BSTTODLL(root-left);
if(count == 0) {
temp = root;
count++;
}
temp-right= root;
root-left = temp;
temp = root;
BSTTODLL(root-right);
}
}
// explanation is trivial , its just keeping a temp pointer to previous
node and adjusting pointers in inorder fashion keeping the list sorted.
Hope it Helps !
On Thu, May 24, 2012 at 11:46 PM, sanjay pandey
sanjaypandey...@gmail.comwrote:
the main code is dis function only:i will explain dis
static Node treeToList(Node root) {
Node aList, bList;
if (root==NULL) return(NULL);*
/* the below next two lines are just lyk inorder traversal...u mst
hv done dis*/*
aList = treeToList(root-small);
bList = treeToList(root-large);
*/* this is for breaking the links of its left n right child nodes
n pointing to itself*/*
root-small = root;
root-large = root;
* /* Appending leftchild parent n rightchild together in
doublylinked list form */*
aList = append(aList, root
[algogeeks] Re: Amazon Q : Design a logWritter for server kind of application
This is a pretty nice question because it requires you to show knowledge in many different areas. In business settings, logs can make the difference between success and failure, not to mention complying with law. Here are some dimensions of the design space: * Convenience of the programmer's interface. * Flexibility in controlling how much and what kind of information is written. * Synchronization and sequencing of input coming from many processes and threads, including from different hosts on a network. * Searchability. * Compliance with existing format standards so that third party tools can be used. * Efficiency, including when logging is turned off. * Compression of log information (storage efficiency). * Spare, backup, and archiving schemes. On May 26, 4:49 am, Ashish Goel ashg...@gmail.com wrote: 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] Re: whats a CALL BACK in C?
A callback is a function, say B, that you provide to some other function F in order to control F's behavior. The intuition is that F is defined with a hole in its specification that it fills up by calling back to the B you furnished. A simple example of a callback is the comparison function argument of qsort() . For a more interesting example, look up the API for zlib, which is nicely designed with several callbacks. The raw Win32 API also uses callbacks for various purposes. In the C language, callback is through a simple function pointer to B because that's all you have. In higher level languages, the function can carry data in a closure. With a Java-like object model, a listener object can be provided with both data and one or more methods. The normal way to approximate this higher level language behavior is by defining the C API with a void* parameter to F that it in turn passes back to B. So when you call F, you can also provide data for B to use when F calls it later. The zlib API uses this technique. On May 28, 4:22 pm, rahul r. srivastava rahul.ranjan...@gmail.com wrote: whats a CALL BACK in 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.
[algogeeks] Re: classic problem to tree to circular doubly linked list
Another approach is to form a singly linked, NULL-terminated list
(connected e.g. by 'left' pointers). This is a harder problem, and
it
might be required if you have a purpose for the other (right)
pointer. If you need a doubly linked list it's easy to walk down the
singly linked one, creating 'previous' pointers as you go.
The converter accepts both a tree and list that's already in the
correct order, which should be appended at the end of the converted
tree. The result of the append operation should be returned.
NODE *convert(NODE *root, NODE *list)
{
if (root == NULL) return list;
NODE *left_subtree = root-left;
root-left = convert(root-right, list);
return tree(left_subtree, root);
}
I like this solution because it's so simple. Initiate it with
convert(tree, NULL);
If you really need the double links:
void adjust(NODE *head)
{
NODE *p, *q;
for (q = NULL, p = head; p; q = p, p = p-next)
p-right = q;
head-right = q;
q-right = head;
}
On May 26, 3:07 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
Both the explanations above are wrong . It is true that BST can be
converted to a Doubly linked list by doing inorder traversal.
But the approach mentioned in the stanford link follows a postorder
Approach , it is better because it avoids useage of a static/global
variable which is required in inorder Approach.
recursively changing the small and large sub-trees into lists, and then
append those lists together with the parent node to make larger lists -
quoted from the stanford page. (parent is visited after the subtrees)
Explanation of the postorder Approach :-
refer to the drawing in the page.
FIrst of all it makes the node named 1 as a an independent node after that
as in postorder it makes node 3 as an independent node . Independent here
means
root-left=root-right=NULL.
After that it comes to node 2 . ( Note that it is happening in postorder
fashion) .
then it makes node 2 as independent and append it with the list returned
from left side(which is independent node 1) and list returned from right
side *(which is independent node 3) and make the left side returned node as
head and follows the process recursively . The order is similar to inorder
apptoach which is O(n).
*IF you want to know the inorder approach as well, Here it is :-*
void BSTTODLL( node *root){
static int count = 0 ;
static node * temp = NULL:
if(root != NULL){
BSTTODLL(root-left);
if(count == 0) {
temp = root;
count++;
}
temp-right= root;
root-left = temp;
temp = root;
BSTTODLL(root-right);
}
}
// explanation is trivial , its just keeping a temp pointer to previous
node and adjusting pointers in inorder fashion keeping the list sorted.
Hope it Helps !
On Thu, May 24, 2012 at 11:46 PM, sanjay pandey
sanjaypandey...@gmail.comwrote:
the main code is dis function only:i will explain dis
static Node treeToList(Node root) {
Node aList, bList;
if (root==NULL) return(NULL);*
/* the below next two lines are just lyk inorder traversal...u mst hv
done dis*/*
aList = treeToList(root-small);
bList = treeToList(root-large);
*/* this is for breaking the links of its left n right child nodes n
pointing to itself*/*
root-small = root;
root-large = root;
* /* Appending leftchild parent n rightchild together in doublylinked
list form */*
aList = append(aList, root);
aList = append(aList, bList);
return(aList);
}
--
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.
[algogeeks] Re: Google Q : all anagrams next to each other
This will work in fine, but multiplying primes requires arbitrary
precision arithmetic for keys of any significant length.
You don't need to compute a hash at all. Just maintain two buffers
long enough to hold the longest word and an O(n) sort like counting
sort. If you are using Latin (8-bit) characters, you don't even need
to complete the counting sort. Just do the counting into arrays of
256 ints. You'll end up with character histograms. It's easy to
compare these rather than sorted strings. They require O(2 log C) =
O(log C) storage and comparing them needs O(log C) int comparisons,
where C is the number of characters in the alphabet. Since C is a
constant, this would normally be considered O(1) time and space.
On May 26, 2:52 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
If you sort every word , then you will lose the original word as Ankita
pointed out and if you keep a hashmap to track that it will not be inplace
.,
Is there any problem in the solution I gave Above , please point it out .
On Fri, May 25, 2012 at 1:14 AM, Anika Jain anika.jai...@gmail.com wrote:
I have a doubt. If u r doing inplace sorting of a word during checks for a
word, wouldnt that change that word there itself? then how will the
original anagram get restored to arrange in the output in sorted manner?
On Thu, May 24, 2012 at 5:54 PM, Jitender Kumar
jitender...@gmail.comwrote:
The complexity will be (N^2)W because the sorting can be done linear time
O(W) for strings.
On Thu, May 24, 2012 at 3:44 PM, WgpShashank bshashank7andr...@gmail.com
wrote:
Yeah , its the in-place approach strikes in mind at first look , just
slightly clearing the complexity to O(N^2* Wlog(W)) , N is number of
words in array W is length of longest word in array , let me know i
missed something ?
original eat I ate att I the eel eth het
after sorting I I ate att can eat eel eth het the
output should be I I ate eat att can eel eth het the
Shashank Mani Narayan
Computer Science Engineering
Birla Institute of Technology,Mesra
Founder Cracking The Code Lab http://shashank7s.blogspot.com/;
FB Pagehttp://www.facebook.com/pages/LestCode
Google+http://gplus.to/wgpshashank
Twitter https://twitter.com/wgpshashank;
Puzzled Guy @ http://ashutosh7s.blogspot.com;
FB Pagehttp://www.facebook.com/Puzzles.For.Puzzled.Minds
On May 22, 8:18 am, Navin Gupta navin.nit...@gmail.com wrote:
It can be done inplace, then Time Complexity will be O( N^2 x W )
where N
is no. of words and W is word size.
Start from the left and sort the current word.
Keep a pointer PTR to the first index of the element left to process.
Initially it will be 0.As we add words this pointer moves forwards.
Now iterate the whole list of words to find all those words having same
sorted sequence i.e. anagrams
Whenver we get a word which is anagram of the current string, swap it
with
the string pointed by PTR, move PTR forward.
pseudoCode :-
func( vectorstring v)
{
int n=v.size();
for(int i=0;in;i++)
{
string currentWord = v[i];
sort(currentWord);
for(int j=i+1;jn;j++)
{
if ( sort(v[j]) == currentWord ) // anagrams found,
{
swap( v[i] , v[j] ); //move this string
to
the position next to pos of currentWord
i++; //and move the
index
of currentWord forward
}
}
}
--
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.
--
With regards,
Jitender Kumar
3rd year (Computer Engineering)
NIT Kurukshetra
Kurukshetra- 136119
Mobile +91-8529035751
--
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.
--
Regards,
Jalaj Jaiswal
Software Developer,
Adobe Systems
+91-9019947895
*
*
FACEBOOK http://www.facebook.com/jalaj.jaiswal89
[algogeeks] Re: Interview Question based on histogram
The problem is not so clear, so you must make some assumptions to gat an answer. Since we have water, we have to envision the histogram in 3d. Then assume that the distance between histogram bars is 1 and bar i has height H[i], 0=iN, zero width and unit depth, and the base plane is at zero. Water is held in the pockets between bars. Then the pocket between H[i] and H[i+1] holds min(H[i],H[i+1]). To get the total, just sum these for 0 = i N-1 . On May 17, 1:57 am, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Imagine that you have an histogram stored in an array. Now imagine that you can pour water on top of your histogram. Describe an algorithm that computes the amount of water that remains trapped among the columns of the graph. Clearly on the edges the water would fall off. Use the language or the pseudocode you prefer. -- Thanks Regards Nikhil Agarwal B.Tech. in Computer Science Engineering National Institute Of Technology, Durgapur,Indiahttp://tech-nikk.blogspot.comhttp://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: storing URL's
This question has no answer. Every good student of computer science will know that you choose a data structure based on the _operations_ that must be performed on it: insert, lookup and what flavors of lookup, delete, etc.. So if an interviewer uses this question, he or she is probably trying to get you discuss this. So the right _response_ (not an answer) is What will you be _doing_ with these URLs? An example: Suppose you take Varun's approach and build a tree. Then it turns out the operation is Count the URLs for .png files. Well, the tree is no help here. You have to search the whole thing. On May 15, 11:50 am, atul anand atul.87fri...@gmail.com wrote: Given a file which contain millions of URL's. which data structure would you use for storing these URL's . data structure used should store and fetch data in efficient manner. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: finding anagrams in a list of words
Ah but this isn't a key because ac would have the same ascii sum as bb. On May 14, 1:11 pm, payal gupta gpt.pa...@gmail.com wrote: @atul instead of sorting the string individually which would require tc- O(nlogn) shouldnot it be a better idea to use the sum of the ascii values of the individual alphabets as the key which would require tc-O(n) ??? On Sun, May 13, 2012 at 7:07 PM, GAURAV CHAWLA togauravcha...@gmail.comwrote: @deepikaanand: 1 is not a prime no. and also ignore 2 as chosen prime no,. On Sun, May 13, 2012 at 6:31 PM, deepikaanand swinyanand...@gmail.comwrote: @gaurav the approach suggested as : to have an array of 25 prime nos..How is it supposed to work ; cz(this is wat i have understood) if a :0 ,b:1,c:3,d:5,e:7 then be = b + e = 1+7 =8 and dc = d + c =5 +3 = 8.. -- 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, GAURAV CHAWLA +919992635751 +919654127192 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: finding anagrams in a list of words
Yes exactly. And now I hope to convince you that it's good to learn a
few languages so you can use the best one for the problem at hand. In
Perl for example, your proposed algorithm looks like this:
while () {
chomp;
push @{ $map{join('', sort split('', $_))} }, $_;
}
while ( (undef, $val) = each %map ) {
print join(' ', @$val).\n if @$val 1;
}
On my litltle laptop this writes to a file all the anagrams in a
dictionary of about 250,000 words in 4 seconds.
My favorite is:
anatomicopathologic pathologicoanatomic
And there are three 9-fold anagrams:
angor argon goran grano groan nagor orang organ rogan
ester estre reest reset steer stere stree terse tsere
caret carte cater crate creat creta react recta trace
Cheers.
On May 12, 4:43 am, Jeevitesh jeeviteshshekha...@gmail.com wrote:
Yup i agree with Atul's solution.
Just explaining the same thing a little better.
Have a HashMap with the following structure:-
HashMapString, ArrayListString;
now scan through the List of words Sort the word and check whether it is
already there on the hashmap if it is just add this word to the list for
this corresponding word else just add this sorted form of this word to the
HashMap .
So if you give me any word i will sort it check it in hashmap and get the
list of all its corresponding anagrams.
On Sat, May 12, 2012 at 1:57 PM, atul anand atul.87fri...@gmail.com wrote:
given the list of words... what you can do is the following :-
now take first word from the list..
sort this word in alphabetical order...for eg str=bcda --- sort , we get
str=abcd
now considering this sorted word as a key(abcd) , insert original word
(bcda as value) into the hash table ( hash table with chaining )
similarly do it for other words.
now given a word , you just need to sort this given word and use it as a
key to fetch all anagram.
On Fri, May 11, 2012 at 5:24 PM, mayur mayursa...@gmail.com wrote:
Hi all,
I am stuck with a question for a long time...can someone provide the best
algorithm for this..
Question).. find all the anagrams in a list of words. The algorithm
should be efficient as the list can be very large.
--
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/-/c4cSIMcBYLEJ.
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.
--
*Thanks,
Jeevitesh Shekhar 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.
[algogeeks] Re: how to code a deterministic or Non-Deterministic finite state automata model?
The scanner part of any program that processes a language is probably
a DFA.
There are three main methods to code DFAs. Two use an explicit
variable to represent state in this fashion:
int state = INITIAL_STATE;
while (!is_accepting_state(state)) {
char ch = get_next_char();
state = transition(ch, state);
if (state == ERROR_STATE) {
take_error_action();
break;
}
}
Now this is pseudocode. The question is how to implement
transition(char ch, int state);
Simplest way is with tables
int transition[256][N_STATES];
boolean is_accepting[N_STATES];
The is_accepting[] array is normally fine. But the 2d array
transition gets big quickly, especially if the number of possible
input characters is high. So there are various table compression
schemes. Run length encoding of table rows is a common method.
The other way to encode is nested switch statements.
Finally - and you see this less often but it often results in the
fastest DFAs:
You use goto and use labels to represent state implicitly. For
example, here is a simple DFA that recognizes floating point numbers.
There are 4 possible input characters: '-', D, '.', '*' where D
stands for a digit and * stands for any char that is not -,D, or .
State 0 is the initial state:
current'-' D '.'*
0 1 2 3 err
1 err2 3 err
2 err2 3 accept
3 err4 err accept
4 err4 err accept
Code this with goto logic as follows:
state0:
switch (get_next_char()) {
case '-': goto state1;
case '0'...'9': goto state2;
case '.': goto state3;
default: goto err;
}
state1:
switch (get_next_char()) {
}
state2:
switch (get_next_char()) {
}
state3:
switch (get_next_char()) {
}
state4:
switch (get_next_char()) {
}
accept:
// accept action goes here
return;
err:
// error action goes here
return;
Of course there are many variations on these 3, but the principles
stay the same.
On Apr 6, 1:39 pm, Doom duman...@gmail.com wrote:
Any pointers to a code using NFA / DFA computation model?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Permutations of a string
You just need to make sure that the same character is never swapped to
the same position twice. Here is one way to do it.
#include stdio.h
#include string.h
void swap(char *s, int i, int j)
{
char t = s[i];
s[i] = s[j];
s[j] = t;
}
void permute(char *s, int n)
{
if (s[n]) {
int i;
unsigned char done[256] = { 0 };
for (i = n; s[i]; i++) {
if (!done[s[i]]) {
swap(s, n, i);
permute(s, n + 1);
swap(s, n, i);
done[s[i]] = 1;
}
}
}
else printf(%s\n, s);
}
int main(int argc, char *argv[])
{
char buf[10 * 1024];
if (argc 1) {
strcpy(buf, argv[1]);
permute(buf, 0);
}
return 0;
}
On May 7, 6:23 am, Sairam ravu...@gmail.com wrote:
Thanks for ur clean Code!! But you haven't considered the case of repeating
characters in a string
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Sorting in O(n)
Ah, but you can pick the radix to be n. Then at most 3 passes will always sort the array. O(3n) = O(n), so you are done. This topic has come up before. There is code at http://groups.google.com/group/algogeeks/msg/90ce2df194aba2d2 . It is true this code assumes math including mod takes constant time, but that's normal for RAM computation models used for most algorithms. Gene On May 5, 4:32 am, saurabh singh saurab...@gmail.com wrote: After giving some thought,I think even radix sort may not be sufficient. Complexity of radix sort is O(k*n) where k is the number of buckets required to sort the given range. The number of buckets is proportional to the number of bits required to represent the *maximum number in the given range.*For our case the maximum number is O(n^2).Hence *the number of buckets required would be proportional to log(n^2) in the worst case.* Hence the worst case complexity for the given constraints using radix sort would be *O(n*(log n^2)) = O(n*logn).* This is no better than comparision sort.A slight optimization that we can make is to use a higher base which would reduce the number of buckets required but would add the cost of converting each number into the higher base. Somehow I am getting convinced worst case O(n) algorithm may not be possible.Working on the mathematical proof. Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sat, May 5, 2012 at 8:37 AM, saurabh singh saurab...@gmail.com wrote: @cegprakash They are n numbers lying in the range 1 to n^2.Not necessarily sorted. eg 3 4 1 2 5 8 (6 numbers satisfying the conditions given in the problem) Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sat, May 5, 2012 at 5:17 AM, Prakash D cegprak...@gmail.com wrote: The range 1 to n^2 is already sorted On Sat, May 5, 2012 at 12:17 AM, Algobiz deepak.arulkan...@gmail.com wrote: How to sort n numbers in the range of 1 to n^2 in O(n).. Any ideas? -- 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/-/PGgMdaIbGIsJ. 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] Re: String comparison
You can't solve a problem like this with only examples of . A
complete definition is necessary. For example, what do you do with
a1 ? 2b
Report mismatch?
What do you do with
1 abc ? 2 2
Do you report or mismatch?
Here is one of infinitely many complete definitions consistent with
your examples:
1. Split each string into lists of maximal tokens consisting of all
decimal digits or all letters. White space separates tokens but is
otherwise ignored. Anything other than digits, letters, and
whitespace is counted as end of string.
2. Call these lists A and B. Compare them pairwise. If Ai and Bi are
both strings of letters, compare them lexically using UTF-8 order. If
Ai and Bi are all digits, compare them numerically. Continue until
you find an inequality between a pair and report this immediately,
ignoring the rest of the string. If you find a pair with types
(letters or digits) that don't match, or if one token list is shorter
than the other, report nothing. Otherwise if you run out of pairs,
report equal.
Here is code that is probably pretty close to this definition. Tasks
like this are easier if you split them up into a token scanning step
and a processing step. I've done that here.
#include stdio.h
#include ctype.h
// Scanner return values.
#define END 0
#define DIGITS 1
#define ALPHA 2
// Find the start and end of the first token in s
// beginning at *start, ignoring initial white space.
int scan(char *s, int *start, int *end)
{
int i = *start;
while (isspace(s[i])) ++i;
if (isdigit(s[i])) {
*start = i;
do ++i; while (isdigit(s[i]));
*end = i;
return DIGITS;
}
if (isalpha(s[i])) {
*start = i;
do ++i; while (isalpha(s[i]));
*end = i;
return ALPHA;
}
return END;
}
// Return the non-negative value of the string
// starting at start and ending at the char before end.
int int_value(char *start, char *end)
{
int x = 0;
char *p = start;
while (p != end)
x = 10 * x + (*p++ - '0');
return x;
}
// Possible comparison values.
#define LT -1
#define EQ 0
#define GT 1
#define NOTHING 2
// Compare the strings starting at xp and ending
// one char before x_end where x is a or b.
int string_compare(char *ap, char *a_end,
char *bp, char *b_end)
{
while (ap a_end bp b_end) {
int diff = *ap - *bp;
if (diff != 0) return diff;
++ap; ++bp;
}
if (ap a_end) return GT;
if (bp b_end) return LT;
return EQ;
}
// Compare tokens in strings a and b.
int compare(char *a, char *b)
{
int a_start, a_end, b_start, b_end;
a_start = b_start = 0;
while (1) {
int a_scan = scan(a, a_start, a_end);
int b_scan = scan(b, b_start, b_end);
if (a_scan != b_scan) return NOTHING;
if (a_scan == END) return EQ;
if (a_scan == DIGITS) {
int a_val = int_value(a + a_start, a + a_end);
int b_val = int_value(b + b_start, b + b_end);
if (a_val b_val) return LT;
if (a_val b_val) return GT;
}
else if (a_scan == ALPHA) {
int cmp = string_compare(a + a_start, a + a_end,
b + b_start, b + b_end);
if (cmp 0) return LT;
if (cmp 0) return GT;
}
a_start = a_end;
b_start = b_end;
}
}
int main(void)
{
char *s[] = {
a5, a11,
6xxx, 007asdf,
00042Q, 42s,
6 8, 006 9,
};
int i;
for (i = 0; i sizeof s / sizeof s[0]; i += 2) {
int cmp = compare(s[i], s[i + 1]);
printf(%s %c %s\n, s[i], =?[cmp + 1], s[i + 1]);
}
return 0;
}
On Apr 17, 11:46 pm, abhishek zeal.gosw...@gmail.com wrote:
Hi,
I need to compare string into following way. Can anyone provide me some
insight or algorithm in c++.
For example:
a5 a11 - because 5 is less than 11
6xxx 007asdf - because 6 7
00042Q 42s - because Q s alphabetically
6 8 006 9 - because 8 9
Thx in advance
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: String comparison
You can't solve a problem like this with only examples of . A
complete definition is necessary. For example, what do you do with
a1 ? 2b
Report mismatch?
What do you do with
1 abc ? 2 2
Do you report or mismatch?
Here is one of infinitely many complete definitions consistent with
your examples:
1. Split each string into lists of maximal tokens consisting of all
decimal digits or all letters. White space separates tokens but is
otherwise ignored. Anything other than digits, letters, and
whitespace is counted as end of string.
2. Call these lists A and B. Compare them pairwise. If Ai and Bi
are
both strings of letters, compare them lexically using UTF-8 order.
If
Ai and Bi are all digits, compare them numerically. Continue until
you find an inequality between a pair and report this immediately,
ignoring the rest of the string. If you find a pair with types
(letters or digits) that don't match, or if one token list is shorter
than the other, report nothing. Otherwise if you run out of pairs,
report equal.
Here is code that is probably pretty close to this definition. Tasks
like this are easier if you split them up into a token scanning step
and a processing step. I've done that here.
#include stdio.h
#include ctype.h
// Scanner return values.
#define END 0
#define DIGITS 1
#define ALPHA 2
// Find the start and end of the first token
// beginning at *start, ignoring initial white space.
int scan(char **start, char **end)
{
char *p = *start;
while (isspace(*p)) ++p;
if (isdigit(*p)) {
*start = p;
do ++p; while (isdigit(*p));
*end = p;
return DIGITS;
}
if (isalpha(*p)) {
*start = p;
do ++p; while (isalpha(*p));
*end = p;
return ALPHA;
}
return END;
}
// Return the non-negative value of the string
// starting at p and ending at the char before end.
int int_value(char *p, char *end)
{
int x = 0;
while (p != end)
x = 10 * x + (*p++ - '0');
return x;
}
// Possible comparison values.
#define LT -1
#define EQ 0
#define GT 1
#define NOTHING 2
// Compare the strings starting at xp and ending
// one char before x_end where x is a or b.
int string_compare(char *ap, char *a_end,
char *bp, char *b_end)
{
while (ap a_end bp b_end) {
int diff = *ap++ - *bp++;
if (diff 0) return LT;
if (diff 0) return GT;
}
if (bp b_end) return LT;
if (ap a_end) return GT;
return EQ;
}
// Compare tokens in strings a and b.
int compare(char *a, char *b)
{
char *a_end, *b_end;
while (1) {
int a_scan = scan(a, a_end);
int b_scan = scan(b, b_end);
if (a_scan != b_scan) return NOTHING;
if (a_scan == END) return EQ;
if (a_scan == DIGITS) {
int a_val = int_value(a, a_end);
int b_val = int_value(b, b_end);
if (a_val b_val) return LT;
if (a_val b_val) return GT;
}
else if (a_scan == ALPHA) {
int cmp = string_compare(a, a_end, b, b_end);
if (cmp != EQ) return cmp;
}
a = a_end;
b = b_end;
}
}
int main(void)
{
char *s[] = {
a5, a11,
6xxx, 007asdf,
00042Q, 42s,
6 8, 006 9,
};
int i;
for (i = 0; i sizeof s / sizeof s[0]; i += 2) {
int cmp = compare(s[i], s[i + 1]);
printf(%s %c %s\n, s[i], =?[cmp + 1], s[i + 1]);
}
return 0;
}
On Apr 17, 11:46 pm, abhishek zeal.gosw...@gmail.com wrote:
Hi,
I need to compare string into following way. Can anyone provide me some
insight or algorithm in c++.
For example:
a5 a11 - because 5 is less than 11
6xxx 007asdf - because 6 7
00042Q 42s - because Q s alphabetically
6 8 006 9 - because 8 9
Thx in advance
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find border of a binary tree.
Good question. The problem is not well-defined. It's possible that 75 should be omitted because there are deeper subtrees to the left and right. But we'll never know for sure because examples don't make a good definition. On Apr 8, 2:29 pm, atul anand atul.87fri...@gmail.com wrote: i guess in the given link 1st example should inculde 75 ?? correect me if i am wrong. On Fri, Apr 6, 2012 at 10:53 PM, Doom duman...@gmail.com wrote: Here is the reference: http://stackoverflow.com/questions/3753928/finding-border-of-a-binary... None of the proposed solutions is effective enough. Any ideas? -- 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/-/xjchdh2I_7MJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Interview question
This problem isn't carefully defined. If you have 3,4,2 then 2 is the first value smaller and of higher index than both 3 and 4. So which to swap with? On Mar 24, 10:01 am, Navin Kumar navin.nit...@gmail.com wrote: Given an array of integers, for each index i, you have to swap the value at i with the first value smaller than A[ i ] that comes after index i. An efficient solution expected. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: MySql Connector/C
My friend, all you have to do is read the manual. http://dev.mysql.com/doc/refman/5.6/en/c.html On Mar 22, 1:14 pm, Gobind Kumar Hembram gobind@gmail.com wrote: Hi Do any one know how to configure MySQL Connector ; so as to connect to MySql using C.If any one have any idea ; please share. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Check if one tree is sub tree of other
I'll point out that if you are building a system where this problem actually occurs (as in generating DAGs in a compiler expression optimizer), you can nearly always engineer the problem down to O(log(| T|)) if T is balanced and O(|T|) in the worst case. Trees need parent pointers, and also a map must be maintained HashMapTripleNode, Node, Data, Node nodeMap; where the key holds the children and data value of the corresponding node that has already been generated. The system never constructs a new node without first checking this global map to see if a node with the right pair of children and data has already been generated. If so, the existing node is used. Otherwise a new one is created and added to the map. Now within this system, checking tree equality is the same as checking root pointer equality. (Proof is by induction over the height of trees!) So two trees can be compared in one machine instruction. For the subtree test, just follow parent pointers from S to its root checking each node to see if it's the root of T. On Mar 20, 8:24 am, Dheeraj Sharma dheerajsharma1...@gmail.com wrote: How to check if one binary tree is a sub tree of other? Any Solution other then bruteforce? Prototype bool check(node *t1,node *subtree) -- Sent from my mobile device *Dheeraj Sharma* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Run Length Decoding... inplace
I don't think you're seeing the requirement completely. The problem
promises only that the output buffer will be big enough to hold the
output. You have made it huge. I tried your code on an input of
a1b1c6
with the required output space of 8 characters (plus 1 for the C null
character), and it printed
cc
and stopped.
Last night I realized there is another approach that will work in all
cases, so I deleted my post. I guess it wasn't deleted on the server
in your part of the world.
You all can certainly work it out. You can't just copy the input to a
predetermined place in the buffer before processing it. It needs to be
placed carefully, and it needs to be processed from both ends to a
certain point in the middle.
On Mar 20, 7:32 am, atul anand atul.87fri...@gmail.com wrote:
using Gene logic , but we need to take care of number with more than 1
digits , so updated gene's code is as follows :-
#includestdio.h
#define MAX 1000
int copy(char *str,int len)
{
int max_len=MAX-1,i;
for(i=len-1;i=0;i--)
{
str[max_len]=str[i];
max_len--;
}
return max_len+1;
}
void runLength(char *str)
{
unsigned int j,k=1,loop=0,res_len=0;
int i,n_start;
char c;
/*copying input to the end of the buffer*/
n_start=copy(str,strlen(str));
for(i=MAX-1;i=n_start;i--)
{
if(str[i]='0' str[i]='9')
{
continue;
}
else
{
sscanf(str[i],%c%d,c,loop);
for(j=0;jloop;j++)
{
str[res_len]=c;
res_len++;
}
}
}
str[res_len]='\0';
printf(\nDecoded Msg = %s\n,str);
}
int main()
{
char str[MAX];
memset(str,0,MAX);
printf(\nEnter String = );
scanf(%s,str);
runLength(str);
return 1;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Google written test
Thanks.
I noticed this too. If the n'th 1/0 digit is supposed to correspond
with the n'th fibonacci number, then my original code would have been
right. But the example isn't done this way.
I fixed the code to match the example the evening of the 18th
(Eastern time), but I guess the change is not showing on your server
yet.
On Mar 19, 3:16 am, atul anand atul.87fri...@gmail.com wrote:
@Gene : your code will work fine by changing the argument passed from
main(), you just need to call rite f(n, 1, 1); from main instead of f(n,
1, 0);
On Mon, Mar 19, 2012 at 10:10 AM, atul anand atul.87fri...@gmail.comwrote:
@all : i guess question is on Fibonacci coding.
here you can find the algo :-
http://en.wikipedia.org/wiki/Fibonacci_coding
On Sun, Mar 18, 2012 at 2:58 AM, Atul Singh atulsingh7...@gmail.comwrote:
@Ravi... there should be only one answer as for fibonacci representation
of a number we have to include the part of the fibonacci number just less
than the number then remaining part of the sum is filled by fibonacci
numbers starting from 1
suppose we have to convert 6 into fibonacci representation
then 6 has two sum sets as {1,2,3} or {1,5}
then the fibonacci number just less than 6 is 5 so bit representing 5 is
set then for completing the sum to 6 bit 1 is also set.
so *fibonacci representation of 6 is 1001 .* not 0111
ATul Singh | Final Year | Computer Science Engineering | NIT
Jalandhar | 9530739855 |
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Run Length Decoding... inplace
It's not hard if all the run lengths are at least 2.
void decode(char *buf, int in_size, int buf_size)
{
int i, j, rl, p;
char t;
// Reverse the input.
for (i = 0, j = in_size - 1; i j; i++, j--) {
t = buf[i]; buf[i] = buf[j]; buf[j] = t;
}
// Copy to end of buffer (carefully)
for (i = in_size - 1, j = buf_size - 1; i = 0; i--, j--)
buf[j] = buf[i];
// Execute commands.
++j; // j now points to first command
for (i = p = 0; i in_size; i += 2, j += 2) {
sscanf(buf[j], %d%c, rl, t) != 2);
while (rl-- 0) buf[p++] = t;
}
}
If they can be rl 1, I don't think it can be done without a trick like
setting the high bit of the character instead of storing the run
length of 1 or adding the run lengths to the char values so both are
stored in one location.
On Mar 19, 1:08 pm, ATul SIngh atulsingh7...@gmail.com wrote:
This was a MS question asked recently on Run length Decoding. I was
given
Input- a3b5c3d2
And the output should be ddcccbaaa
Assuming that the memory given is sufficient to accomodate the whole
string.
And this conversion should be inplace. ie the output string should not
use another array.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Math Question
I'm sorry there's an algebra error below, but fortunately the proof
still works. It should be
From this, algebra provides
10^e - 1 == 0 (mod 9Y) and
10^e == 1 (mod 9Y).
But 9Y and 10^e are still coprime, so we're good.
Here is code that seems to be working fine.
#include stdio.h
int main(int argc, char *argv[])
{
int x, x9, m, p, a, b;
if (argc 1 sscanf(argv[1], %d, x) == 1) {
a = b = 0;
while (x % 2 == 0) {
a++;
x /= 2;
}
while (x % 5 == 0) {
b++;
x /= 5;
}
x9 = 9 * x;
m = 10 % x9;
p = 1;
while (m != 1) {
m = (10 * m) % x9;
p++;
}
printf(divides %d 1's followed by %d 0's\n,
p, a b ? a : b);
}
return 0;
}
For example:
$ ./a.out 45
divides 9 1's followed by 1 0's
$ ./a.out 192
divides 3 1's followed by 6 0's
./a.out 947838840
divides 299910 1's followed by 3 0's
On Mar 16, 4:27 pm, Gene gene.ress...@gmail.com wrote:
Dave, this is very beautiful. Here is a less elegant proof, though it leads
to an efficient algorithm.
In a different problem some time ago, there was a statement that every
number with a 3 in the units position has a multiple that consists of
all 1s. The proof needs a little number theory. Any number Z that is
all 1's can be written as (10^e - 1) / 9 for some integer e. So if Y
is the number we are given (ending in 3), we must find e such that
(10^e - 1) / 9 == 0 (mod Y). From this, algebra provides 10^e - 1 ==
0 (mod Y) and 10^e == 1 (mod Y). Note 10^e and Y are coprime. The
prime factors of the former are all 5 and 2, and since Y ends in 3, it
can have neither of these. Then by Euler's Theorem, e must exist (and
in fact Euler's Totient Function gives its value)! So we are done.
Corollary: a number with 1, 7, or, 9 in the units position also has a
multiple that's all 1s. Proof: Multiply by 3, 9, or 7 respectively to
get a number with 3 in the units position, then use the result above.
The rest:
Let X be the (arbitrary) number we are given. Divide out all its
factors of 2 and 5 to obtain Y.
Claim: Y has 1, 3, 7, or 9 in the units position. Proof: If it ended
with any other digit, it would be divisible by 2 or 5!
Therefore we can find a number Z consisting of all 1's that is a
multiple of Y. Suppose we factored out (2^a)(5^b) above. Then Z
(10^max(a, b)) is a number consisting of all 1's and 0's that is a
multiple of X as desired!
It's not hard to implement in this in time linear to the number of
digits of the multiple (assuming a real RAM model of computation).
Please let me know if you see any problems with this argument.
On Mar 7, 4:32 pm, Don dondod...@gmail.com wrote:
Theorem: In any set of (n+1) distinct integers there exists two whose
difference is divisible by n.
Proof: Each of these integers leaves a remainder between 0 and n-1
inclusive upon division by n. Since there are n possible remainders
and (n+1) integers that means there exist two which have the same
remainder by the PigeonHole Principle. So their difference is
divisible by n.
Theorem: Given any positive integer n there exists a positive number
consisting of only 1's and 0's which is divisible by n.
Proof: Construct the sequence of (n+1) integers:
1,11,111,,111...1
By the first theorem two of these numbers have a difference divisible
by n. That difference will be a number consisting of only 1's and
0's.
On Mar 7, 1:17 pm, karthikeya s karthikeya.a...@gmail.com wrote:
A math problem: Prove that for all positive integer n, there exist at
least
one positive integer whose digits are only 1s and 0s and is divisible
by n.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Google written test
It looks from the example like you pick the largest (as if the digits
were a binary number). Here's what I get:
#include stdio.h
unsigned f(unsigned n, unsigned fi, unsigned fim1)
{
if (fi n) return n;
unsigned r = f(n, fi + fim1, fi);
if (r = fi) {
putchar('1');
return r - fi;
}
putchar('0');
return r;
}
int main(int argc, char *argv[])
{
unsigned n;
if (argc 1 sscanf(argv[1], %u, n) == 1) {
f(n, 1, 0);
putchar('\n');
}
return 0;
}
On Mar 17, 2:08 pm, Ravi Ranjan ravi.cool2...@gmail.com wrote:
@ if for a given number more than 1 answer exist then whats the answer???
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Google written test
It looks from the example like you pick the largest (as if the digits
were a binary number). Here's what I get:
#include stdio.h
unsigned f(unsigned n, unsigned fi, unsigned fim1)
{
if (fi n) return n;
unsigned r = f(n, fi + fim1, fi);
if (r = fi) {
putchar('1');
return r - fi;
}
putchar('0');
return r;
}
int main(int argc, char *argv[])
{
unsigned n;
if (argc 1 sscanf(argv[1], %u, n) == 1) {
f(n, 1, 1);
putchar('\n');
}
return 0;
}
On Mar 17, 2:08 pm, Ravi Ranjan ravi.cool2...@gmail.com wrote:
@ if for a given number more than 1 answer exist then whats the answer???
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: select k numbers
When the n'th number (nk) is received, apply the following algorithm: 1. Generate random real r uniformly distributed in [0..1]. 2. If r k/n, throw away the new number, 3. else generate random integer i in [1..k] and replace the number in the i'th storage location with the new one. This is working properly if after completion each number in storage is there with probability k/n. Certainly this is true of the new number. The rest of the numbers must have been in storage with probability k/(n-1) before our algorithm ran. In order to remain in storage, they had not to be replaced. The probability of replacement was k/n * 1/k = 1/n. So they remained through this execution of the algorithm with probability 1-1/n = (n-1)/n. This execution was independent of previous ones, so the overall probability of remaining in storage through all executions was k/(n-1) * (n-1)/n = k/n as desired. On Mar 17, 2:23 pm, karthikeya s karthikeya.a...@gmail.com wrote: You are given a dynamic stream of numbers and numbers are coming one by one. At a time you can store at max k numbers(coz you have only that much memory available). Task is that we have to select the random subset of size k from the numbers we have got so far with equal probability. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Math Question
This is very beautiful. Here is a less elegant proof, though it leads to an efficient algorithm. In a different problem some time ago, there was a statement that every number with a 3 in the units position has a multiple that consists of all 1s. The proof needs a little number theory. Any number Z that is all 1's can be written as (10^e - 1) / 9 for some integer e. So if Y is the number we are given (ending in 3), we must find e such that (10^e - 1) / 9 == 0 (mod Y). From this, algebra provides 10^e - 1 == 0 (mod Y) and 10^e == 1 (mod Y). Note 10^e and Y are coprime. The prime factors of the former are all 5 and 2, and since Y ends in 3, it can have neither of these. Then by Euler's Theorem, e must exist (and in fact Euler's Totient Function gives its value)! So we are done. Corollary: a number with 1, 7, or, 9 in the units position also has a multiple that's all 1s. Proof: Multiply by 3, 9, or 7 respectively to get a number with 3 in the units position, then use the result above. The rest: Let X be the (arbitrary) number we are given. Divide out all its factors of 2 and 5 to obtain Y. Claim: Y has 1, 3, 7, or 9 in the units position. Proof: If it ended with any other digit, it would be divisible by 2 or 5! Therefore we can find a number Z consisting of all 1's that is a multiple of Y. Suppose we factored out (2^a)(5^b) above. Then Z (10^max(a, b)) is a number consisting of all 1's and 0's that is a multiple of X as desired! It's not hard to implement in this in time linear to the number of digits of the multiple (assuming a real RAM model of computation). Please let me know if you see any problems with this argument. On Mar 7, 4:32 pm, Don dondod...@gmail.com wrote: Theorem: In any set of (n+1) distinct integers there exists two whose difference is divisible by n. Proof: Each of these integers leaves a remainder between 0 and n-1 inclusive upon division by n. Since there are n possible remainders and (n+1) integers that means there exist two which have the same remainder by the PigeonHole Principle. So their difference is divisible by n. Theorem: Given any positive integer n there exists a positive number consisting of only 1's and 0's which is divisible by n. Proof: Construct the sequence of (n+1) integers: 1,11,111,,111...1 By the first theorem two of these numbers have a difference divisible by n. That difference will be a number consisting of only 1's and 0's. On Mar 7, 1:17 pm, karthikeya s karthikeya.a...@gmail.com wrote: A math problem: Prove that for all positive integer n, there exist at least one positive integer whose digits are only 1s and 0s and is divisible by n. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Math Question
I'm sorry there's an algebra error here, but fortunately the proof
still works. It should be
From this, algebra provides
10^e - 1 == 0 (mod 9Y) and
10^e == 1 (mod 9Y).
But 9Y and 10^e are still coprime, so we're good.
Here is code that seems to be working fine.
#include stdio.h
int main(int argc, char *argv[])
{
int x, x9, m, p, a, b;
if (argc 1 sscanf(argv[1], %d, x) == 1) {
a = b = 0;
while (x % 2 == 0) {
a++;
x /= 2;
}
while (x % 5 == 0) {
b++;
x /= 5;
}
x9 = 9 * x;
m = 10 % x9;
p = 1;
while (m != 1) {
m = (10 * m) % x9;
p++;
}
printf(divides %d 1's followed by %d 0's\n,
p, a b ? a : b);
}
return 0;
}
For example:
$ ./a.out 45
divides 9 1's followed by 1 0's
$ ./a.out 192
divides 3 1's followed by 6 0's
./a.out 947838840
divides 299910 1's followed by 3 0's
On Mar 16, 4:27 pm, Gene gene.ress...@gmail.com wrote:
This is very beautiful. Here is a less elegant proof, though it leads
to an efficient algorithm.
In a different problem some time ago, there was a statement that every
number with a 3 in the units position has a multiple that consists of
all 1s. The proof needs a little number theory. Any number Z that is
all 1's can be written as (10^e - 1) / 9 for some integer e. So if Y
is the number we are given (ending in 3), we must find e such that
(10^e - 1) / 9 == 0 (mod Y). From this, algebra provides 10^e - 1 ==
0 (mod Y) and 10^e == 1 (mod Y). Note 10^e and Y are coprime. The
prime factors of the former are all 5 and 2, and since Y ends in 3, it
can have neither of these. Then by Euler's Theorem, e must exist (and
in fact Euler's Totient Function gives its value)! So we are done.
Corollary: a number with 1, 7, or, 9 in the units position also has a
multiple that's all 1s. Proof: Multiply by 3, 9, or 7 respectively to
get a number with 3 in the units position, then use the result above.
The rest:
Let X be the (arbitrary) number we are given. Divide out all its
factors of 2 and 5 to obtain Y.
Claim: Y has 1, 3, 7, or 9 in the units position. Proof: If it ended
with any other digit, it would be divisible by 2 or 5!
Therefore we can find a number Z consisting of all 1's that is a
multiple of Y. Suppose we factored out (2^a)(5^b) above. Then Z
(10^max(a, b)) is a number consisting of all 1's and 0's that is a
multiple of X as desired!
It's not hard to implement in this in time linear to the number of
digits of the multiple (assuming a real RAM model of computation).
Please let me know if you see any problems with this argument.
On Mar 7, 4:32 pm, Don dondod...@gmail.com wrote:
Theorem: In any set of (n+1) distinct integers there exists two whose
difference is divisible by n.
Proof: Each of these integers leaves a remainder between 0 and n-1
inclusive upon division by n. Since there are n possible remainders
and (n+1) integers that means there exist two which have the same
remainder by the PigeonHole Principle. So their difference is
divisible by n.
Theorem: Given any positive integer n there exists a positive number
consisting of only 1's and 0's which is divisible by n.
Proof: Construct the sequence of (n+1) integers:
1,11,111,,111...1
By the first theorem two of these numbers have a difference divisible
by n. That difference will be a number consisting of only 1's and
0's.
On Mar 7, 1:17 pm, karthikeya s karthikeya.a...@gmail.com wrote:
A math problem: Prove that for all positive integer n, there exist at
least
one positive integer whose digits are only 1s and 0s and is divisible by
n.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Novell - Interview (Round-3 Coding)
In case you want to play with this, here is a little program
that computes suffix trees with a simple brute force algorithm
and prints their sizes. It looks like the actual growth is
O(m^2). So my quick analysis was too conservative:
m=1 chars=0
m=3 chars=3
m=6 chars=11
m=10 chars=29
m=15 chars=67
m=21 chars=137
m=28 chars=254
m=36 chars=436
m=45 chars=704
m=55 chars=1082
m=66 chars=1597
m=78 chars=2279
m=91 chars=3161
m=105 chars=4279
m=120 chars=5672
m=136 chars=7382
m=153 chars=9454
m=171 chars=11936
m=190 chars=14879
m=210 chars=18337
m=231 chars=22367
m=253 chars=27029
m=276 chars=32386
m=300 chars=38504
m=325 chars=45452
m=351 chars=53302
m=378 chars=62129
m=406 chars=72011
m=435 chars=83029
m=465 chars=95267
m=496 chars=108812
m=528 chars=123754
m=561 chars=140186
m=595 chars=158204
m=630 chars=177907
m=666 chars=199397
m=703 chars=222779
m=741 chars=248161
m=780 chars=275654
m=820 chars=305372
m=861 chars=337432
m=903 chars=371954
m=946 chars=409061
m=990 chars=448879
m=1035 chars=491537
public class SuffixTreeProblem {
// We store strings implicitly. If there is an a child,
// there is an a edge out of the node. If dollar is
// true then this node marks the end of a suffix.
static class Node {
Node a = null, b = null;
boolean dollar = false;
}
// Produce a string that requires a big suffix tree.
byte [] genString(int n) {
byte [] s = new byte [1 + n + n * (n + 1) / 2];
int i = 0;
for (int in = n; in 0; in--) {
s[i++] = 'b';
for (int j = 0; j in; j++) {
s[i++] = 'a';
}
}
s[i] = '$';
return s;
}
// Brute force: Build the tree counting characters used.
int suffixTreeChars(byte [] s) {
Node tree = new Node();
int n = 0;
for (int iStart = s.length - 1; iStart = 0; --iStart) {
Node p = tree;
for (int i = iStart; ; ++i) {
if (s[i] == '$') {
p.dollar = true;
break;
}
else if (s[i] == 'a') {
if (p.a == null) {
p.a = new Node();
++n;
}
p = p.a;
}
else {
if (p.b == null) {
p.b = new Node();
++n;
}
p = p.b;
}
}
}
return n;
}
void test() {
for (int n = 0; n 50; ++n) {
byte [] s = genString(n);
int m = s.length;
System.out.println(m= + m + chars= +
suffixTreeChars(s));
}
}
public static void main(String [] argv) {
new SuffixTreeProblem().test();
}
}
On Mar 14, 1:06 am, Gene gene.ress...@gmail.com wrote:
Let's try
{ reverse( $ a b a a b a a a b ... a^n b ) | n = 0,1,2,... } .
Note that m = n(n+1)/2 + n = O(n^2)
Think about adding suffixes to the tree from shortest to longest.
So suppose you are now adding something of the form
reverse( $ X a^L Y )
where L is the length of the longest run of a's and X and Y are what
comes before and after. Well we know the length of Y is at most L
and the length of X must be L(L-1)/2+(L-1) = L(L+1)/2 - 1 . What's
already in the tree will match no more than 2L characters before a new
branch occurs. The new branch will therefore have at least
L(L+1)/2 - 1 - 2L characters. This is O(L^2).
You should do the math more rigorously, but roughly you will be
getting for the total of all branches added,
sum_{L=0,1,..n} O(L^2) = O(n^3) = O(m ^ 1.5)
with one character per branch. This is super-linear.
On Mar 13, 12:47 am, reynald reni reni.reyn...@gmail.com wrote:
Construct an infinite family of strings over a fixed alphabet, where
the total length of the edge-labels on their suffix tree grows faster
than O(m), where 'm' is the length of the string. [That is, show that
linear time suffix tree algorithm would be impossible if edge-labels
were written explicitly on the edges.]
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Microsoft Interview Question
This problem is close to copying a graph. For that as you said, just
do DFS or BFS and maintain a map from original nodes to copies. Use
the copy to set pointers whenever it exists. When it doesn't exist,
make a new node and add it to the map.
You can implement the map in various ways. A hash table works fine.
If you can add a pointer to each original vertex node, you can store
the mapping right there. If nodes are numbered consecutively, you can
use these as indices into a table. Etc. Etc. Lots of schemes are
possible. No matter how you do it, the algorithm is the same:
Node copy(Node x)
{
if (x == null) return null;
if (Map(x) != null) return Map(x);
xCopy = new Node();
Set Map(x) = xCopy;
xCopy.next = copy(x.next);
xCopy.other = copy(x.other);
return xCopy;
}
But general graph copy is overkill here. The searching requires O(L)
space for a list of length L. So for this special problem, just
traverse the list once to find and copy all the nodes and then a
second time to set the other pointers:
Node Copy(Node x)
{
// Using a dummy head node makes copying simple.
Node dummyHead = new Node();
Node q = dummyHead;
// Make the copied list and fill in the Map.
for (Node p = x; p != null; p = p.next, q = q.next) {
Node pCopy = new Node();
q.next = pCopy;
Set Map(p) = pCopy;
}
// Set all the other pointers.
for (Node p = x; p != null; p = p.next)
Map(p).other = Map(p.other);
return dummyHead.next;
}
The final question is whether you can implement the Map in a tricky
way. After the list is constructed, you have the L other pointers
doing nothing, so how can they be exploited?
I'll let you think about that...
On Mar 13, 2:01 am, Umer Farooq the.um...@gmail.com wrote:
Yes that is exactly what they wanted. I proposed BFS for this solution.
Anyway, there was another problem that I was able to solve; but the
interviewer brought up a much more efficient approach.
The problem was:
- Given a linked a linked list with one pointer pointing to next,
another pointer pointing to any random pointer in the list. The random
pointer can be before or after the current pointer or it can even be at the
same node. Write a piece of code that can produce an exact copy of the
linked list.
On Tue, Mar 13, 2012 at 10:57 AM, Umer Farooq the.um...@gmail.com wrote:
Yes that is exactly what they wanted. I proposed BFS for this solution.
Anyway, there was another problem that I was able to solve; but the
interviewer brought up a much more efficient approach.
The problem was:
Given a linked l
On Mon, Mar 12, 2012 at 11:31 PM, Gene gene.ress...@gmail.com wrote:
Since there is no mention of weights, you are looking for any spanning
tree. Primm and Kruskal are for _minimum_ spanning tree. They are
overkill for this problem.
You can construct a spanning tree in any graph with DFS. Just record
every edge you find that reaches a vertex that has never been visited
before. This has to find every vertex, and since you are recording
only the first edge used to arrive at each vertex, these edges must
form a tree. This works even if there are cycles. The algorithm is O(|
E|).
Note that in general a graph doesn't have a single root. So you'd
search from all roots. Another way to think about this: introduce
your own dummy root and edges to each vertex where there are no
incident in edges. Of course you don't report the dummy edges.
On Mar 12, 1:09 pm, atul anand atul.87fri...@gmail.com wrote:
i guess they were talking abt spanning tree , so you can use prism or
kruskal algo to do the same.
On Mon, Mar 12, 2012 at 3:05 PM, Umer Farooq the.um...@gmail.com
wrote:
Hello friends,
I recently had an onsite MS interview. One of the questions that they
asked was:
- Given a directed graph, write a program that takes root of the
graph
and returns root of a tree which comprises of all the nodes of the
graph in
the same way as they appeared in the graph (the graph contains no
cycles).
--
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.
--
Umer
--
Umer
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send
[algogeeks] Re: Microsoft Interview Question
Copying a full graph requires a BFS or DFS. But here we have a big
advantage. We know the nodes are linked in a single chain. So we
don't need to search to find all nodes. We can just use .next
pointers.
No matter how we do things, we will need Map(A) that returns the copy
of node A if it already exists.
If you use a separate map like a hash table, then things are very
simple. Traverse the list one time to make copies of all the nodes,
chain them in a list, and create the Map. Then traverse the original
list a second time to set the other pointers: for each node A, set
Map(A).other = Map(A.other).
The Map requires O(L) space for a list of length L.
But it turns out we can store the map in a very tricky way that
requires zero additional space _if_ we are allowed to change the
original list while making the copy. If A' is the copy of A, and we
start with list [ A,B,C,... ], then we transform this in one pass to
[A, A', B, B', C, C', ... ]. In this list, A.next is A'. So we have
created the map without losing any information.
Here's untested code that ought to be at least very close:
class Node {
int val;
Node next, other;
Node() {}
Node(int val, Node next, Node other) {
this.val = val;
this.next = next;
this.other = other;
}
Node(Node org) {
this(org.val, org.next, org.other);
}
/**
* @return a copy of the list including other pointers
*/
Node copy() {
// Make the copies and the map.
for (Node p = this; p != null; p = p.next.next)
p.next = new Node(p);
// Use the map to fix up the other pointers in the
copies.
for (Node p = this.next; p.next != null; p =
p.next.next)
p.other = p.other.next;
// Split into original list and list of copies.
Node dummyHead = new Node();
for (Node p = this, q = dummyHead; p != null; p =
p.next, q =
q.next) {
q.next = p.next;
p.next = p.next.next;
}
return dummyHead.next;
}
}
On Mar 13, 2:01 am, Umer Farooq the.um...@gmail.com wrote:
Yes that is exactly what they wanted. I proposed BFS for this solution.
Anyway, there was another problem that I was able to solve; but the
interviewer brought up a much more efficient approach.
The problem was:
- Given a linked a linked list with one pointer pointing to next,
another pointer pointing to any random pointer in the list. The random
pointer can be before or after the current pointer or it can even be at the
same node. Write a piece of code that can produce an exact copy of the
linked list.
On Tue, Mar 13, 2012 at 10:57 AM, Umer Farooq the.um...@gmail.com wrote:
Yes that is exactly what they wanted. I proposed BFS for this solution.
Anyway, there was another problem that I was able to solve; but the
interviewer brought up a much more efficient approach.
The problem was:
Given a linked l
On Mon, Mar 12, 2012 at 11:31 PM, Gene gene.ress...@gmail.com wrote:
Since there is no mention of weights, you are looking for any spanning
tree. Primm and Kruskal are for _minimum_ spanning tree. They are
overkill for this problem.
You can construct a spanning tree in any graph with DFS. Just record
every edge you find that reaches a vertex that has never been visited
before. This has to find every vertex, and since you are recording
only the first edge used to arrive at each vertex, these edges must
form a tree. This works even if there are cycles. The algorithm is O(|
E|).
Note that in general a graph doesn't have a single root. So you'd
search from all roots. Another way to think about this: introduce
your own dummy root and edges to each vertex where there are no
incident in edges. Of course you don't report the dummy edges.
On Mar 12, 1:09 pm, atul anand atul.87fri...@gmail.com wrote:
i guess they were talking abt spanning tree , so you can use prism or
kruskal algo to do the same.
On Mon, Mar 12, 2012 at 3:05 PM, Umer Farooq the.um...@gmail.com
wrote:
Hello friends,
I recently had an onsite MS interview. One of the questions that they
asked was:
- Given a directed graph, write a program that takes root of the
graph
and returns root of a tree which comprises of all the nodes of the
graph in
the same way as they appeared in the graph (the graph contains no
cycles).
--
Umer
--
You received this message because you are subscribed
[algogeeks] Re: Microsoft Interview Question
Sorry, a small test showed a loop quitting one iteration too soon.
Here is the fix.
import java.util.Random;
public class ListCopy {
class Node {
int val;
Node next, other;
Node() { }
Node(int val, Node next, Node other) {
this.val = val;
this.next = next;
this.other = other;
}
Node(Node org) {
this(org.val, org.next, org.other);
}
Node copy() {
// Make the copies and the map.
for (Node p = this; p != null; p = p.next.next) {
p.next = new Node(p);
}
// Use the map to fix up the other pointers in the copies.
for (Node p = this.next; ; p = p.next.next) {
p.other = p.other.next;
if (p.next == null)
break;
}
// Split into original list and list of copies.
Node d = new Node();
for (Node p = this, q = d; p != null; p = p.next, q =
q.next) {
q.next = p.next;
p.next = p.next.next;
}
return d.next;
}
}
void run() {
Node [] test = new Node [10];
int n = test.length;
int i = n - 1;
test[i] = new Node(n, null, null);
Random gen = new Random(42);
for (--i; i = 0; --i)
test[i] = new Node(i + 1, test[i + 1], null);
for (i = 0; i n; i++)
test[i].other = test[gen.nextInt(n)];
Node copy = test[0].copy();
int count = 0;
for (Node p = test[0], q = copy; p != null; p = p.next, q
=q.next) {
if (p.val != q.val || p.other.val != q.other.val || p == q
|| p.other == q.other)
System.err.println(error: p= + p.val + q= +
q.val);
count++;
}
System.err.println(# nodes: + count);
}
public static void main (String [] args) {
new ListCopy().run();
}
}
On Mar 13, 3:15 pm, Gene gene.ress...@gmail.com wrote:
Copying a full graph requires a BFS or DFS. But here we have a big
advantage. We know the nodes are linked in a single chain. So we
don't need to search to find all nodes. We can just use .next
pointers.
No matter how we do things, we will need Map(A) that returns the copy
of node A if it already exists.
If you use a separate map like a hash table, then things are very
simple. Traverse the list one time to make copies of all the nodes,
chain them in a list, and create the Map. Then traverse the original
list a second time to set the other pointers: for each node A, set
Map(A).other = Map(A.other).
The Map requires O(L) space for a list of length L.
But it turns out we can store the map in a very tricky way that
requires zero additional space _if_ we are allowed to change the
original list while making the copy. If A' is the copy of A, and we
start with list [ A,B,C,... ], then we transform this in one pass to
[A, A', B, B', C, C', ... ]. In this list, A.next is A'. So we have
created the map without losing any information.
Here's untested code that ought to be at least very close:
class Node {
int val;
Node next, other;
Node() {}
Node(int val, Node next, Node other) {
this.val = val;
this.next = next;
this.other = other;
}
Node(Node org) {
this(org.val, org.next, org.other);
}
/**
* @return a copy of the list including other pointers
*/
Node copy() {
// Make the copies and the map.
for (Node p = this; p != null; p = p.next.next)
p.next = new Node(p);
// Use the map to fix up the other pointers in the
copies.
for (Node p = this.next; p.next != null; p =
p.next.next)
p.other = p.other.next;
// Split into original list and list of copies.
Node dummyHead = new Node();
for (Node p = this, q = dummyHead; p != null; p =
p.next, q =
q.next) {
q.next = p.next;
p.next = p.next.next;
}
return dummyHead.next;
}
}
On Mar 13, 2:01 am, Umer Farooq the.um...@gmail.com wrote:
Yes that is exactly what they wanted. I proposed BFS for this solution.
Anyway, there was another problem that I was able to solve; but the
interviewer brought up a much more efficient approach.
The problem was:
- Given a linked a linked list with one pointer pointing to next,
another
[algogeeks] Re: Novell - Interview (Round-3 Coding)
{ reverse( $ a b a a b b a a a b b b ... a^n b^n ) | n = 0,1,2,... }
On Mar 13, 12:47 am, reynald reni reni.reyn...@gmail.com wrote:
Construct an infinite family of strings over a fixed alphabet, where
the total length of the edge-labels on their suffix tree grows faster
than O(m), where 'm' is the length of the string. [That is, show that
linear time suffix tree algorithm would be impossible if edge-labels
were written explicitly on the edges.]
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Novell - Interview (Round-3 Coding)
Let's try
{ reverse( $ a b a a b a a a b ... a^n b ) | n = 0,1,2,... } .
Note that m = n(n+1)/2 + n = O(n^2)
Think about adding suffixes to the tree from shortest to longest.
So suppose you are now adding something of the form
reverse( $ X a^L Y )
where L is the length of the longest run of a's and X and Y are what
comes before and after. Well we know the length of Y is at most L
and the length of X must be L(L-1)/2+(L-1) = L(L+1)/2 - 1 . What's
already in the tree will match no more than 2L characters before a new
branch occurs. The new branch will therefore have at least
L(L+1)/2 - 1 - 2L characters. This is O(L^2).
You should do the math more rigorously, but roughly you will be
getting for the total of all branches added,
sum_{L=0,1,..n} O(L^2) = O(n^3) = O(m ^ 1.5)
with one character per branch. This is super-linear.
On Mar 13, 12:47 am, reynald reni reni.reyn...@gmail.com wrote:
Construct an infinite family of strings over a fixed alphabet, where
the total length of the edge-labels on their suffix tree grows faster
than O(m), where 'm' is the length of the string. [That is, show that
linear time suffix tree algorithm would be impossible if edge-labels
were written explicitly on the edges.]
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Java question
This is nearly what malloc() and similar memory allocators do. If you look at an operating system book or web search you'll get lots of approaches. The overall problem of finding the best allocation is NP hard, so you must use some kind of heuristic. The most common ones are called First fit and Best fit. First fit just keeps a persistent pointer into the list of trucks with free space. When a new requirement comes in, the pointer is advanced (with wrapping at the end of the list) until the first free block (truck with enough space) is found that is bigger than the requirement. In best fit, the smallest free block that is no smaller than the requirement is always selected. In this case you'd normally need a tree or some other efficient search structure. You might think that best fit would get better results than first fit, but this often isn't true. This is because best fit tends to leave many free blocks so small that requirements can't use them. For this reason in some cases people even use _worst_ fit. In this case that would be equal to always selecting the emptiest truck. Since he told you there are many trucks, this may be the best answer. It's a fast strategy. Keeping track of the trucks by emptiness might be done by maintaining K lists of trucks where list i holds trucks with ceiling(100i/K) space remaining. This is a good question because there is no correct answer. The interviewer is probably trying to see how you think and approach difficult problems. If you have the opportunity you should ask lots of questions: how requests are distributed, whether you can move load from one truck to another as a last resort to make free space, etc. On Mar 10, 11:32 am, shruthi sharma shruthi.shar...@gmail.com wrote: Hi, Im new to algorithms, so this might be a simple question for most of you Lets say there are 5 trucks, each of which can take 100kg load. And they are filled to some extent randomly. Let the free quantity be 40kg, 30kg, 20kg, 80kg, 60kg respectively. At any given time only single load comes. Lets say a load of 25kg comes, we have to select the truck where it fits leaving less free space, here 30kg Now the free quantities are 40, 5, 20, 80 and 60. Next if a load of 10kg comes, we have to select the truck with 20kg free space. and go on... Write a java code for selecting a truck for the above situation when the number of trucks is very large. It should be with least time and space complexity with minimum number of iterations in the loop (interviewer said its part of a very large application which takes huge system resources, so this part of the code should be very efficient) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Explain algo behind code
Not at the moment as I'm traveling. Sorry. You could start with
http://en.wikipedia.org/wiki/Modular_arithmetic . The references
might be helpful.
I'll illustrate what Im talking about. Let M=7. Then here is a
table of inverses and checks:
All mod 7 arithmetic
Inverse Check
1 ^ 5 = 11 * 1 = 1
2 ^ 5 = 44 * 2 = 1
3 ^ 5 = 55 * 3 = 1
4 ^ 5 = 22 * 4 = 1
5 ^ 5 = 33 * 5 = 1
6 ^ 5 = 66 * 6 = 1
So if you want to compute say 4 choose 2, it's 4!/(2!2!) = 24 / (2 *
2) = 6 .
The corresponding computation mod 7 is
3 * inv(2) * inv(2) = 3 * 4 * 4 (mod 7) = 5 * 4 (mod 7) = 6
The code is doing this with a modulus of 17 and storing the
first 5000 factorials (mod M) and their inverses in tables to avoid
computing them repeatedly.
On Mar 6, 12:35 am, amrit harry dabbcomput...@gmail.com wrote:
could you refer a number theory book..?
On Tue, Mar 6, 2012 at 7:01 AM, Gene gene.ress...@gmail.com wrote:
It's a fact from number theory that
x * (x^(M-2)) = 1 (mod M)
if M is prime. So x^(M-2) is the multiplicative inverse of x (mod
M). It follows by identities of modulo arithmetic that
n!/(r!(n-r)!) = n! * inv(r!) * inv( (n-r)! ) (mod M)
This is what the code is computing. A basic number theory book will
cover this stuff in the early chapters.
On Mar 5, 5:13 am, amrit harry dabbcomput...@gmail.com wrote:
#include cstdio
#define MOD 17
int powmod(int base, int expo){
if(expo==0)
return 1;
else if(expo1)
return (long long)base*powmod(base, expo-1)%MOD;
else{
int root=powmod(base, expo1);
return (long long)root*root%MOD;
}
}
int inverse(int x){
return powmod(x, MOD-2);
}
void init(){
fact[0]=1;
for(int i=1; i=5000; i++)
fact[i]=(long long)i*fact[i-1]%MOD;
invfact[5000]=inverse(fact[5000]);
for(int i=5000; i0; i--)
invfact[i-1]=(long long)i*invfact[i]%MOD;
}
int nCr(int n, int r){
if(rn || r0)
return 0;
return (long long)((long
long)fact[n]*invfact[r]%MOD)*invfact[n-r]%MOD;
}
int main(){
init();
int N, K;
while(scanf(%d %d, N, K) (N||K)){
print(%d,nCr(N,K));
}
}
This is code for calculating binomial cofficient =
fact(n)/fact(n-r)*fact(r) value of fact(r)*fact(n-r) lead to overflow so in
this code they use a method of calculating inverse of fact. i could not
able to understand how inverse function work please explain.
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.
--
AMRIT
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: optimisation
This is a nice paper. I think that for matrix multiplication it ends up saying pretty much the same as we've been discussing. The OP said serial code. Vector code isn't serial. However it's easy to try vectorization these days. The latest versions of gcc will do a very reasonable job with the right optimization flags. However be aware that if you create a binary with vector code for one machine it can easily fail on a different one. Unlike the basic x86 instruction set, there are several levels and branches of standards. On Mar 6, 1:47 am, Sairam Ravu ravu...@gmail.com wrote: Here is the nice link for writing fast matrix-matrix multiplication.http://spiral.ece.cmu.edu:8080/pub-spiral/abstract.jsp?id=100 Apart from this we can vectorize the code and also we can do unrolling to get very good performance. -- With love and regards, Sairam Ravu I M.Tech(CS) Sri Sathya Sai Institute of Higher Learning To live life, you must think it, measure it, experiment with it, dance it, paint it, draw it, and calculate 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.
[algogeeks] Re:
The dcache uses this to hash directory names. It looks pretty close
to the old Dragon Book rotate-and-xor algorithm.
24 struct qstr {
25 const unsigned char * name;
26 unsigned int len;
27 unsigned int hash;
28 };
29
30 /* Name hashing routines. Initial hash value */
31 #define init_name_hash()0
32
33 /* partial hash update function. Assume roughly 4 bits per
character */
34 static __inline__ unsigned long partial_name_hash(unsigned long c,
unsigned long prevhash)
35 {
36 prevhash = (prevhash 4) | (prevhash
(8*sizeof(unsigned long)-4));
37 return prevhash ^ c;
38 }
39
40 /* Finally: cut down the number of bits to a int value (and try to
avoid losing bits) */
41 static __inline__ unsigned long end_name_hash(unsigned long hash)
42 {
43 if (sizeof(hash) sizeof(unsigned int))
44 hash += hash 4*sizeof(hash);
45 return (unsigned int) hash;
46 }
47
48 /* Compute the hash for a name string. */
49 static __inline__ unsigned int full_name_hash(const unsigned char
* name, unsigned int len)
50 {
51 unsigned long hash = init_name_hash();
52 while (len--)
53 hash = partial_name_hash(*name++, hash);
54 return end_name_hash(hash);
55 }
56
On Mar 3, 8:32 am, aanchal goyal goyal.aanch...@gmail.com wrote:
Gene:
I am talking about file names.
On Sat, Mar 3, 2012 at 1:07 AM, Gene gene.ress...@gmail.com wrote:
It's possible you're not getting any clear answers because the
question is unclear. Linux does many different kinds of name lookup
all over the system. What names are you talking about?
On Mar 1, 3:50 pm, aanchal goyal goyal.aanch...@gmail.com wrote:
anyone knows what hash function is used in the name lookup procedure in
linux?
Procedure lookup(name)
1: h := hash(name)
2: dentryNode := hashtable(h)
3: while dentryNode != NULL do
4: if dentryNode- name != name then
5: dentryNode := dentryNode- next
6: else
7: return dentryNode
8: end if
9: end while
--
Regards,*
Aanchal 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.
--
Regards,*
Aanchal 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.
[algogeeks] Re: Suggest some Data Structure appropriate to the problem
What Don so succinctly said is this: Comparison sort _requires_ O(n log n) comparisons. If you had the data structure you're asking for, you could easily implement a comparison sort: Just insert n items, then then repeat n times: find min and delete that min. With your proposed time bounds, the resulting sort would be O(n). This is how you can immediately tell what you're asking for is impossible. On Mar 5, 5:51 pm, Sehaj Singh Kalra sehaj...@gmail.com wrote: Ok. Got it. I think that without the assumption that you took ( about FIFO implementation i.e. only the recent most element to be added can be deleted or else there would be problem in updating stack 2) the problem can't be done. Thanks for the proposed solution. On Tue, Mar 6, 2012 at 4:13 AM, SAMM somnath.nit...@gmail.com wrote: As I mentioned we have to use hashing using Separate Chaning to find the element in constant time . This is different than than opening addresing which added the element to the next free slot in case of a collision , so we cann't keep track of the element in a constant . In sepate Chaning the elements when collision is found the element will be in the stored in the form of the linked list on the same slot . IN worst case if all the element give collision then the time complexity can be of O(n) . But chossing the proper hash key can give the result in constant time . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: optimisation
You can get an initial guess with math. The rest you'll need to determine by experiment. The math will be Block Dimension = sqrt( L1 / sizeof(FLOAT) / K ) . K could be 2 or 3 depending on the loop order. A reason you can't predict perfectly is that interrupt handlers can add to cache load in unpredictable ways. You might find it interesting to turn off your network and see if you can get further improvement by making blocks a little bigger than you could with the network turned on. On Mar 5, 2:08 pm, Arun Vishwanathan aaron.nar...@gmail.com wrote: @Gene: if all matrices are of N x N , and my size of L1 cache is L1, then If I need a block of A and B to fit in cache would I need it as 2 x (blocksize )^2 x 8 ( bytes per data item-for example) = L1 ?? or would I need it as 3 ( including C block ) x (blocksize)^2 x 8 = L1 ? Am confused. I tried a sample and I think I got somewhat good speedup for block size 32 ( for matrix dimension 512, 1024 etc )for my L1 of size 16 kbytes and L2 256 kbytes...Any comments or inferences? On Wed, Feb 29, 2012 at 9:31 AM, Arun Vishwanathan aaron.nar...@gmail.comwrote: @all: Thanks a lot On Wed, Feb 29, 2012 at 9:02 AM, Gene gene.ress...@gmail.com wrote: For big matrices, using all the caches well is very important. The usual approach is block tiling as you say. You want two blocks to fit nicely in the L1 cache. The most highly optimized schemes will have a hierarchy of tiles where two tiles at the second level will fit in the L2 cache, etc. Additional levels can be based on memory interfaces, interleaving, page size, and even cylinder size on disk (for really huge matrices). The idea is _never_ to generate more cache misses than you need to. A miss causes a factor of 10 to 1 performance multiple on that operation. Multiplying within the innermost blocks should also consider prefetch: you'll get best performance touching locations in contiguous ascending order. The inner loops are for i = 1 to ma for j = 1 to nb for k = 1 to na r[i,j] += a[i,k] * b[k,j] This ignores that r[i,j] needs to be zeroed out somewhere. But with this assumption, the loops can be juxtaposed in any order without changing the result. You should explore the 6 possible orderings for the best one. Of course you also have to zero out the sums in the best possible manner. FWIW, a GPU will normally outperform a general purpose CPU with ease on this problem. Since even cell phones are getting GPUs these days, tweaking single-processor matrix code is a dying art. Cheers. On Feb 27, 6:57 pm, Arun Vishwanathan aaron.nar...@gmail.com wrote: Hi all, We have this challenge to make the fastest executing serial matrix multiplication code. I have tried using matrix transpose( in C for row major ) and loop unrolling.I was able to obtain little speedup. Does anyone have any hints/papers that I could read upon and try to speed up further?I had tried a bit of block tiling but was not successful. Thanks Arun -- 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. -- People often say that motivation doesn't last. Well, neither does bathing - that's why we recommend it daily. -- People often say that motivation doesn't last. Well, neither does bathing - that's why we recommend it daily. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Explain algo behind code
It's a fact from number theory that
x * (x^(M-2)) = 1 (mod M)
if M is prime. So x^(M-2) is the multiplicative inverse of x (mod
M). It follows by identities of modulo arithmetic that
n!/(r!(n-r)!) = n! * inv(r!) * inv( (n-r)! ) (mod M)
This is what the code is computing. A basic number theory book will
cover this stuff in the early chapters.
On Mar 5, 5:13 am, amrit harry dabbcomput...@gmail.com wrote:
#include cstdio
#define MOD 17
int powmod(int base, int expo){
if(expo==0)
return 1;
else if(expo1)
return (long long)base*powmod(base, expo-1)%MOD;
else{
int root=powmod(base, expo1);
return (long long)root*root%MOD;
}
}
int inverse(int x){
return powmod(x, MOD-2);
}
void init(){
fact[0]=1;
for(int i=1; i=5000; i++)
fact[i]=(long long)i*fact[i-1]%MOD;
invfact[5000]=inverse(fact[5000]);
for(int i=5000; i0; i--)
invfact[i-1]=(long long)i*invfact[i]%MOD;
}
int nCr(int n, int r){
if(rn || r0)
return 0;
return (long long)((long
long)fact[n]*invfact[r]%MOD)*invfact[n-r]%MOD;
}
int main(){
init();
int N, K;
while(scanf(%d %d, N, K) (N||K)){
print(%d,nCr(N,K));
}
}
This is code for calculating binomial cofficient = fact(n)/fact(n-r)*fact(r)
value of fact(r)*fact(n-r) lead to overflow so in this code they use a method
of calculating inverse of fact. i could not able to understand how inverse
function work please explain.
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.
[algogeeks] Re: Floyd Warshall
The Wikipedia entry is pretty good: http://en.wikipedia.org/wiki/Floyd–Warshall_algorithm Read the Algorithm section a few times and draw some examples and you'll probably start seeing it. On Mar 3, 7:56 am, saurabh singh saurab...@gmail.com wrote: Its quite trivial. At least until you have invented something that's so useful and used so widely, this is a harsh judgment. If it's easy for you to understand FW today, that's only because the methods of thinking that FW helped create have been successful. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re:
It's possible you're not getting any clear answers because the question is unclear. Linux does many different kinds of name lookup all over the system. What names are you talking about? On Mar 1, 3:50 pm, aanchal goyal goyal.aanch...@gmail.com wrote: anyone knows what hash function is used in the name lookup procedure in linux? Procedure lookup(name) 1: h := hash(name) 2: dentryNode := hashtable(h) 3: while dentryNode != NULL do 4: if dentryNode- name != name then 5: dentryNode := dentryNode- next 6: else 7: return dentryNode 8: end if 9: end while -- Regards,* Aanchal 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.
[algogeeks] Re: Puzzle
My crazy guess is that you need to add 1900 and then these are important years. Maybe years when a team won some sports championship? I'm getting this from the no math or outside knowledge. You need inside knowledge. On Feb 27, 8:24 am, karthikeya s karthikeya.a...@gmail.com wrote: 3, 39, 41, 43, 45, 49, 51, 53, 55, 64, ?, ?, ... (These are successive numbers sharing a common property. No math or outside knowledge is needed.) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: count possible number of binary search trees, given number of nodes
A related interesting problem is counting binary set hierarchies: the number of perfect binary trees you can build over the same set of n=2^k leaves, where there is no distinction between left and right children. In other words, starting with n=2^k elements, put them into disjoint sets of 2 elements. Then group these sets into sets of 2 and continue a total k times until you have a single top-level set. The number of ways you can form such a hierarchy is n! / [ (n/2)! 2^(n/ 2) ] . This problem comes up in broadcast encryption algorithms. On Feb 14, 4:52 pm, Don dondod...@gmail.com wrote: For a binary search tree the solution is called the Catalan Numbers. The formula is (2n)!/(n!(n+1)!) The first few terms are: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, 18367353072152, 69533550916004, 263747951750360, 1002242216651368, 3814986502092304 Don On Jan 29, 3:58 am, Moheed Moheed Ahmad mohe...@gmail.com wrote: I know how to solve it programatically, can anybody pls help me to solve it using combinatorics. -Moheed -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Structural Padding in C
This depends on the compiler and even on the options you give the
compiler. The C nor C++ standards don't say.
So the asker of the question hasn't give you enough information.
If you assume 32-bit x86 gcc with no packing options or pragmas, I
think shorts (which are 2 bytes long) are aligned on 2-byte
boundaries. Longs and ints (both 4 bytes long) are on 4-byte
boundaries. Chars (1 byte) can go anywhere. If you follow these
rules, then the first will be laid out:
Field @ Offset
a @ 0 // next 3 bytes are padding to reach next 4-byte boundard
b @ 4
c @ 8 // next 2 bytes are padding
d @ 12
so the struct will be 16 bytes in size (a long is 4 bytes).
In the second case you'll have
a @ 0 // next 1 byte are padding
b @ 2
c @ 4 // next 3 bytes are padding
d @ 8
so the struct will be 12 bytes in size.
Even if you are using a 64-bit gcc (without the -m32 flag), you'll get
an entirely different answer!
On Feb 29, 11:13 am, Decipher ankurseth...@gmail.com wrote:
I need some help in understanding how padding works ??
Please answer the following questions with proper explanations..
struct mystruct1
{
char a;
int b;
short c;
long d;
};
struct mystruct2
{
char a;
short b;
char c;
long d;
};
What's the sizeof above 2 structures and why ??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: optimisation
For big matrices, using all the caches well is very important. The usual approach is block tiling as you say. You want two blocks to fit nicely in the L1 cache. The most highly optimized schemes will have a hierarchy of tiles where two tiles at the second level will fit in the L2 cache, etc. Additional levels can be based on memory interfaces, interleaving, page size, and even cylinder size on disk (for really huge matrices). The idea is _never_ to generate more cache misses than you need to. A miss causes a factor of 10 to 1 performance multiple on that operation. Multiplying within the innermost blocks should also consider prefetch: you'll get best performance touching locations in contiguous ascending order. The inner loops are for i = 1 to ma for j = 1 to nb for k = 1 to na r[i,j] += a[i,k] * b[k,j] This ignores that r[i,j] needs to be zeroed out somewhere. But with this assumption, the loops can be juxtaposed in any order without changing the result. You should explore the 6 possible orderings for the best one. Of course you also have to zero out the sums in the best possible manner. FWIW, a GPU will normally outperform a general purpose CPU with ease on this problem. Since even cell phones are getting GPUs these days, tweaking single-processor matrix code is a dying art. Cheers. On Feb 27, 6:57 pm, Arun Vishwanathan aaron.nar...@gmail.com wrote: Hi all, We have this challenge to make the fastest executing serial matrix multiplication code. I have tried using matrix transpose( in C for row major ) and loop unrolling.I was able to obtain little speedup. Does anyone have any hints/papers that I could read upon and try to speed up further?I had tried a bit of block tiling but was not successful. Thanks Arun -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Structural Padding in C
Draw a picture!
char goes at 0 because it can go anywhere
short goes at 2 because it must be on a 2-byte boundary; it consumes
bytes 2 and 3
char goes at 4 because this is the next byte after the short; it
consumes byte 4; byte 5 is the next byte free
long goes at 8 because this is the next 4-byte boundary after 5
8 + 4 = 12, so the struct takes 12 bytes
On Feb 29, 12:03 pm, Karunakar Reddy karunakar.r...@gmail.com wrote:
how in the second case it is 12?can u tell the clear expl..
On Wed, Feb 29, 2012 at 8:39 AM, Gene gene.ress...@gmail.com wrote:
This depends on the compiler and even on the options you give the
compiler. The C nor C++ standards don't say.
So the asker of the question hasn't give you enough information.
If you assume 32-bit x86 gcc with no packing options or pragmas, I
think shorts (which are 2 bytes long) are aligned on 2-byte
boundaries. Longs and ints (both 4 bytes long) are on 4-byte
boundaries. Chars (1 byte) can go anywhere. If you follow these
rules, then the first will be laid out:
Field @ Offset
a @ 0 // next 3 bytes are padding to reach next 4-byte boundard
b @ 4
c @ 8 // next 2 bytes are padding
d @ 12
so the struct will be 16 bytes in size (a long is 4 bytes).
In the second case you'll have
a @ 0 // next 1 byte are padding
b @ 2
c @ 4 // next 3 bytes are padding
d @ 8
so the struct will be 12 bytes in size.
Even if you are using a 64-bit gcc (without the -m32 flag), you'll get
an entirely different answer!
On Feb 29, 11:13 am, Decipher ankurseth...@gmail.com wrote:
I need some help in understanding how padding works ??
Please answer the following questions with proper explanations..
struct mystruct1
{
char a;
int b;
short c;
long d;
};
struct mystruct2
{
char a;
short b;
char c;
long d;
};
What's the sizeof above 2 structures and why ??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Longest Path in A Graph
This not a bad thought experiment, but sorry this isn't true. First, there is a problem of cycles. If a graph is undirected, you can pick any edge and go back and forth an arbitrary number of times along that edge to make any path as long as you want. So if there exists _any_ path there is no longest path because if you claimed you had one I'd just take it and add length 2 by picking any edge and traversing it two extra times, so your claim is false. On the other hand (obviously) if there exists no path at all, then there also exists no longest path. So you have to restrict the problem. If you say longest _simple_ path, which is a path that includes no vertices more than once (hence it's acyclic), you can build a tricky graph that has a path of length greater than K for some K if and only if a given SAT instance is satisfiable. Therefore the problem is NP hard. Or you can use Hamiltonian Path as explained in http://www.tcs.hut.fi/Studies/T-79.240/2001/solutions_5.ps I think the error in your reasoning is that you are searching for the longest simple path that exists starting at a given source. Rather you want the longest simple path that exists between given source _and destination_ . For this BFS is not so helpful. On Feb 29, 9:03 pm, Mad Coder imamadco...@gmail.com wrote: We can find the longest path in a graph by applying 2 bfs. 1st BFS is from our start node. The node which appear in last will be the one farthest from the start node.Let this node be end1. Now again apply bfs from end1 and the last node which appears will be the another end. Here I have made assumptions that graph is undirected and by this algorithm i can tell the length of longest path, but to find actual path I am still thinking. Correct me if i am 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.
[algogeeks] Re: google question
Well the OP is not clear. You could be right. I solved this problem
once before, and there the glasses were arranged in a pyramid like
they do at weddings in my country (this will only look right if you
set the fixed-width font in Groups:
U
U U
U U U
U U U U
U U U U U
---
You pour in the wine at the top and each glass trickles down to the 2
below it. So in this version I assumed the OP meant the children were
the ones below and to the right. I could be wrong.
On Feb 28, 8:46 am, Ashish Goel ashg...@gmail.com wrote:
0.5 ( G(h - 1, i - 1) + G(h - 1, i) ) should be 0.5 ( G(h - 1, i - 1) + G(h
- 1, i+1) )
i am not clear why the parents of a cup in upper row are consecutive?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Feb 28, 2012 at 10:43 AM, Gene gene.ress...@gmail.com wrote:
G is just a helper function. You can in line this function and
eliminate it.
When you do this, you'll end up with
F(h, i) = 0.5 * (l + r)
where l = F(h-1,i-1) - C if 0 = i-1 = h-1 and F(h-1,i-1) C else
0
and r = F(h-1,i) - C if 0 = i = h-1 and F(h-1,i) C else 0
Here l is the left parent's outflow and r is the right parent's.
So you are always computing the h'th row in terms of the (h-1)'th.
For many DPs this means you'll need 2 row buffers. In this one you
only need 1 element back in the current row. You can save this element
in a single variable and get by with one buffer. I.e. note l for a
given value of i is always the previous value of r. And for i=0, l is
always 0 because there is no left parent.
So you end up with
f[0] = L; // fill in the first row
for (ih = 1; ih = h; ih++) { // loop thru rest of rows
double l = 0; // left parent outflow at ii=0 is always 0.
for (ii = 0; ii = ih; ii++) { // loop thru columns
// new right parent outflow
double r = (ii ih f[ii] C) ? f[ii] - C : 0;
f[ii] = 0.5 * (l + r);
l = r; // right parent is left of next row entry
}
}
return (0 = i i = h) ? f[i] : 0;
This is doing the same as Dave's code for all practical purposes. It's
untested but ought to work.
On Feb 27, 10:05 pm, Ashish Goel ashg...@gmail.com wrote:
Gene, your DP is what i was thinking of but in code i could not coreleate
G(h - 1, i - 1) + G(h - 1, i) part (:
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Feb 28, 2012 at 7:50 AM, Gene gene.ress...@gmail.com wrote:
G(h - 1, i - 1) + G(h - 1, i)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: google question
Dave's code is good. Here is a more abstract way of thinking about
it. Maybe helpful?
Number the rows starting at the top with h=0, and the left i=0. Then
the parents of cup(h,i) are always cup(h-1,i-1) and cup(h-1,i). When
h0, i0 or i h, the parent does not exist.
Let F(h, i) be the amount that has flowed in to cup(h,i) after L went
in at the top and let G(h, i) be the amount that has flowed out.
So note that what flowed out is either what flowed in minus C or else
nothing if less than C has flowed in. It's also zero if cup(h,i)
doesn't exist:
G(h,i) = { F(h, i) - C if 0 = i = h and F(h, i) C
{ 0 otherwise
Now note that what flows in is equal to half of what flowed out of
each parent unless we have the top cup, which means L flowed in!
F(h, i) = { L if h = i = 0
{ 0.5 ( G(h - 1, i - 1) + G(h - 1, i) ) otherwise
The answer we want is given by F. Dave's code is a nice
implementation of this DP.
On Feb 27, 5:23 pm, Dave dave_and_da...@juno.com wrote:
@Ashish: I didn't make any assumption that nothing comes from the
left. Does my code give the wrong answer?
Dave
On Feb 27, 10:36 am, Ashish Goel ashg...@gmail.com wrote:
Dave, why the assumption that nothing is coming from left side.
Every cup gets something from cup left above and right above itself when
they have something extra?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, Feb 27, 2012 at 8:17 PM, Dave dave_and_da...@juno.com wrote:
// nothing coming in from the
left
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: google question
G is just a helper function. You can in line this function and
eliminate it.
When you do this, you'll end up with
F(h, i) = 0.5 * (l + r)
where l = F(h-1,i-1) - C if 0 = i-1 = h-1 and F(h-1,i-1) C else
0
and r = F(h-1,i) - C if 0 = i = h-1 and F(h-1,i) C else 0
Here l is the left parent's outflow and r is the right parent's.
So you are always computing the h'th row in terms of the (h-1)'th.
For many DPs this means you'll need 2 row buffers. In this one you
only need 1 element back in the current row. You can save this element
in a single variable and get by with one buffer. I.e. note l for a
given value of i is always the previous value of r. And for i=0, l is
always 0 because there is no left parent.
So you end up with
f[0] = L; // fill in the first row
for (ih = 1; ih = h; ih++) { // loop thru rest of rows
double l = 0; // left parent outflow at ii=0 is always 0.
for (ii = 0; ii = ih; ii++) { // loop thru columns
// new right parent outflow
double r = (ii ih f[ii] C) ? f[ii] - C : 0;
f[ii] = 0.5 * (l + r);
l = r; // right parent is left of next row entry
}
}
return (0 = i i = h) ? f[i] : 0;
This is doing the same as Dave's code for all practical purposes. It's
untested but ought to work.
On Feb 27, 10:05 pm, Ashish Goel ashg...@gmail.com wrote:
Gene, your DP is what i was thinking of but in code i could not coreleate
G(h - 1, i - 1) + G(h - 1, i) part (:
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Feb 28, 2012 at 7:50 AM, Gene gene.ress...@gmail.com wrote:
G(h - 1, i - 1) + G(h - 1, i)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Constructing Binary Tree from a sorted Doubly Linked List
One way to think about it: Given an input list with n items, consume
the first ceiling((n-1)/2)=floor(n/2) items building the left
subtree. Then consume the next item to use for the new tree root.
Then consume the rest of the elements, which number n - floor(n/2) - 1
to build the right subtree.
If n = 0, you have the base case, which is to return the empty tree.
As code:
// Convert the sorted list of n elements with head pointer (*head) to
a bst and return the root.
NODE *sorted_list_to_bst(NODE **head, int n)
{
if (n == 0) return NULL;
NODE *left_subtree = sorted_list_to_bst(head, n / 2);
NODE *root = *head; // head is now the root
*head = (*head)-next; // consume head
NODE *right_subtree = sorted_list_to_bst(head, n - n/2 - 1)
root-prev = left_subtree; // using prev/next for left/right child
root-next = right_subtree;
return root;
}
NODE *convert(NODE *head)
{
int n = 0;
for (NODE *p = head; p; p = p-next) n++;
return sorted_list_to_bst(head, n);
}
This turns out to be an O(n) algorithm.
On Feb 25, 5:24 pm, Supraja Jayakumar suprajasank...@gmail.com
wrote:
Hi All
A sorted doubly linked list is given. We are asked to construct a balanced
binary tree.
I have designed an n^2 solution. Kindly comment on it and also suggest
possible improvements and definitely let me know if something is wrong.
Btree* ConstructTreeFromDLList(DLList *dll) {
// Assuming there is a head and tail
DLLNode *head = dll-head;
DLLNode *tail = dll-tail;
Btree *root = BuildTree(DLList *dll, head, tail);
return root;
}
Btree * BuildTree(DLList *dll, DLLNode * head, DLLNode *tail) {
// Find mid node using two pointers from head and tail.
// Boundary cases - no head ? no tail ? - handle here.
Node *this = head;
Node *that = tail;
int mid = 0;
while(this != that || this-prev != that || that-next != this) { //
Until they have not crossed
this=this-next;
that=that-prev;
mid++;}
printf(“Mid Node Index=%d \n”, mid);
BTree *root = this = that;
root-left = BuildTree(head, that-prev);
root-right = BuildTree(this-next, tail);
return root;
}
Thank You
Supraja J
--
U
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Longest Path in A Graph
Nice. The code is very clean.
It's worth noting in case anyone is intending to implement this that
it's easy find graphs where exhaustive DFS runs in exponential time.
One that's easy to envision is a chain of diamonds
S8o8o8o ... o8D where S is the source and D the destination
with all edges directed left-to-right so that it is acyclic. For N
diamonds, there are 2^N paths to check. So you would have to know a
lot about the structure and/or size of the graph before you could put
this algorithm in a real program.
Since this problem is NP-hard, there's near zero hope of doing better
than exhaustive DFS on general graphs.
On the other hand, if the graph is directed and acyclic, there is a
simple linear time algorithm as was noted by one of the posters.
On Feb 24, 11:08 pm, Don dondod...@gmail.com wrote:
It was pointed out to me by Dave, a very sharp frequent contributor to
this group, that a different definition of a cycle will produce
different results in some cases. If a cycle is defined as following
the same edge in the same direction more than once, rejecting cycles
of that type will often produce longer paths.
To use this rule, replace the else portion of my code with
{
// Try all valid adjacent nodes
for(j = 0; j n; ++j)
if (edges[from][j])
{
edges[from][j] = false;
longestPath(j,to,depth+1);
edges[from][j] = true;
}
}
Don
On Feb 24, 9:42 am, Don dondod...@gmail.com wrote:
// Assuming that the graph with n nodes is specified by an adjacency
matrix edges[n][n]
// where edges[i][j] is true if an edge exists from i to j
// Implements depth-first search with restriction that each
// node may only be visited once.
int longestPath(int from, int to, int depth=0)
{
// Length of longest path encountered
static int max;
// Start new search
if (depth == 0) max = 0;
// Save path followed
path[depth] = from;
// Detect arrival at destination
if (from == to)
{
if (depth max) // Is this the longest path so far?
{
savePath(); // Copy the current path
max = depth;
}
}
else
{
// Avoid cycles
visited[from] = true;
// Try all valid adjacent nodes
for(j = 0; j n; ++j)
if (edges[from][j] !visited[j])
longestPath(j,to,depth+1);
// This node is available to visit again
visited[from] = false;
}
// Return length of longest path found
return max;
}
On Feb 22, 6:05 am, krishna kishore kknarenkris...@gmail.com wrote:
Hi Gentle Men, Can any Please let me know How to Find a LONGEST PATH in a
Graph ( directed or Undirected but unweighted ).
INPUT: we have to give the Source vertex and Destination Vertex.
OUTPUT: it should include the LENGTH OF PATH and PATH as well.
Remember the graph should not be weighted.
Any suggestions are accepted for sure.
And Thanks in Advance.
--
*Vignesh*- Hide quoted text -
- Show quoted text -- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: merge two sorted list
Ah, this reminds me of a beautiful thing that a fine gentleman CB
Falconer posted once in comp.programmer. It was so elegant that my
normally bad memory still remembers it after some years.
You can simplify the merge by using a dummy node for the head of the
merged list rather than just a pointer. There was a question about
sentinels in another thread. This is similar.
struct node* SortedMerge(struct node* a, struct node* b)
{
struct node head[1], *tail;
// Since head is a dummy, head-next will be the real list head.
head-next = NULL;
tail = head;
// Merge lists
while(a b)
{
if (a-data b-data)
{
tail-next = a;
tail = a;
a = a-next;
}
else
{
tail-next = b;
tail = b;
b = b-next;
}
}
// Attach remaining list
tail-next = a ? a : b;
return head-next;
}
On Feb 23, 3:49 pm, Don dondod...@gmail.com wrote:
// Iterative merge
struct node* SortedMerge(struct node* a, struct node* b)
{
struct node* head, tail;
// Select first node
if (a-data b-data)
{
head = tail = a;
a = a-next;
}
else
{
head = tail = b;
b = b-next;
}
// Merge lists
while(a b)
{
if (a-data b-data)
{
tail-next = a;
a = a-next;
}
else
{
tail-next = b;
b = b-next;
}
}
// Attach remaining list
tail-next = a ? a : b;
return head;
}
On Feb 23, 3:41 am, rahul sharma rahul23111...@gmail.com wrote:
struct node* SortedMerge(struct node* a, struct node* b)
{
struct node* result = NULL;
/* Base cases */
if (a == NULL)
return(b);
else if (b==NULL)
return(a);
/* Pick either a or b, and recur */
if (a-data = b-data)
{
result = a;
result-next = SortedMerge(a-next, b);
}
else
{
result = b;
result-next = SortedMerge(a, b-next);
}
return(result);
}
a : 10 20 30
b : 10 25 35
wats the o/p??? 10 20 25 30 35
or 10 10 20 25 30- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: use of sentinel in linked list
Exactly. The other trick is when maintaining a list in ascending
sorted order, to give the sentinel a key of infinite. This way you
need not check for the end of list at all. The key comparison will
always stop before the last element. I vaguely recall Wirth uses this
example in his book Algorithms + Data Structures = Programs, but I
haven't picked it up for years, so this could be false.
On Feb 21, 2:00 pm, Don dondod...@gmail.com wrote:
What are you using the sentinel for? A marker for the end of the list?
A common way to implement a linked list is to use a sentinal as the
head of a circularly linked list.
Thus, an empty list is a pointer to the sentinal which is linked to
itsself.
The advantage is that there are fewer special cases to consider when
you need to insert or delete an item from the list.
For example, to delete an item from the list, you don't need a special
case to handle deleting the first item.
For instance:
class node
{
public:
int data;
struct node *next;
};
class list
{
public:
list() // Construct an empty list
{
_head = new node;
_head-next = _head;
_head-data = 0;
}
bool isEmpty() { return _head == _head-next; }
void insert(int n) // Insert n at head of list
{
node *tmp = new node;
tmp-data = n;
tmp-next = _head-next;
_head-next = tmp;
}
void delete(int n) // Delete first node with value n
{
node *p;
for(p = _head; p != _head; p = p-next)
{
if (p-next-data == n)
{
node *tmp = p-next;
p-next = tmp-next;
delete tmp;
break;
}
}
etc...
}
private:
node *_head;
};
On Feb 21, 12:00 pm, karthikeya s karthikeya.a...@gmail.com wrote:
How to implement a linked list using sentineli mean sentinel will
be having some non-null address.then how would u identify it
except remembering the address.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Finding closest double in a Btree
Not to mention the subject line seems to be asking about B-Trees,
which is no kind of binary tree, so the OP gets it wrong, too.
On Feb 20, 7:28 pm, Dave dave_and_da...@juno.com wrote:
@Don: By that measure, it also is trivial if the tree is a BST. You
just find the largest node x and the smallest one x and choose
between them.
But since the original problem did not specify a BST, your solution is
non-responsive. If I were grading a test, I'd have to count your
solution as wrong, figuring that you do not know the difference
between a binary tree and a binary search tree.
Dave
On Feb 20, 5:13 pm, Don dondod...@gmail.com wrote:
Yes, I am assuming a binary search tree. The problem is trivial
otherwise.
If it is just a binary tree, you visit each node and keep track of the
closest.
Don
On Feb 20, 5:02 pm, Dave dave_and_da...@juno.com wrote:
@Don: Aren't you assuming a binary _search_ tree? Only a binary tree
was specified by the OP.
Dave
On Feb 20, 10:44 am, Don dondod...@gmail.com wrote:
Supraja,
I think that your solution will work, but it does more work than is
necessary. You don't need to traverse the entire tree.
node findClosest(node root, double k)
{
node result = root;
double diff = fabs(root-value - k);
for(node loc = root; loc; loc = (loc-value k) ? loc-left :
loc-right)
{
double newDiff = fabs(loc-value - k);
if (newDiff diff)
{
result = loc;
diff = newDiff;
}
}
return result;
}
On Feb 20, 5:24 am, Supraja Jayakumar suprajasank...@gmail.com
wrote:
Hi
Question is given a binary tree and a key K, code to find the node
with the
closest value.
I'd be happy to receive some feedback about my solution too.
Pls find the code below:
class FindingClosestNodeInTree {
private static double difference = 0.0;
private static doule key = 0.0;
int main() {
BinaryTree bt;
bt.insert(20.43);
bt.insert(12.78);
bt.insert(19.89);
bt.insert(32.69);
bt.insert(2.54);
cout Please provide the key value endl;
cin key;
const Node closestNode = closestValue(bt);
cout Node that has the closest value to
closestNode.value;
return 1;}
const Node closestValue(const BinaryTree node) {
if(node==null)
return;
int val = node.value;
int currDiff = val key ? val-key:key-val;
difference = currDiff difference ? currDiff:difference;
if(node.left!=null)
closestValue(node.left);
if(node.right!=null)
closestValue(node.right);
return difference;
}
}
Thanks
Supraja J- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Finding closest double in a Btree
Sure the algorithm works for any binary tree, but a B-Tree is a more
general data structure. So the problem statement is confusing. This
is probably the reason some people gave alternatives that only work
with a BST. A BST is a special case of a B-Tree.
On Feb 20, 8:58 pm, saurabh singh saurab...@gmail.com wrote:
@gene probably you are saying this on the basis of the subject of the
mail?Please read the problem statement stated in the mail.Even its a B
tree doesn't effects the algorithm proposed by don which says *traverse
each node and keep track of minimum.*
So irrespective of the data structure used this solution is bound to
work
closest:
arguments: dataStructure T,int number
tmp:=getelem(T);
min=tmp.value
while( getelem returns non null values)
do
nxt:=getelem(T);
if(abs(nxt.value-number)min) then
tmp=nxt
min=nxt.value
done
done
return tmp
The nextelem function can be written according to the data structure used.
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Tue, Feb 21, 2012 at 6:06 AM, Gene gene.ress...@gmail.com wrote:
Not to mention the subject line seems to be asking about B-Trees,
which is no kind of binary tree, so the OP gets it wrong, too.
On Feb 20, 7:28 pm, Dave dave_and_da...@juno.com wrote:
@Don: By that measure, it also is trivial if the tree is a BST. You
just find the largest node x and the smallest one x and choose
between them.
But since the original problem did not specify a BST, your solution is
non-responsive. If I were grading a test, I'd have to count your
solution as wrong, figuring that you do not know the difference
between a binary tree and a binary search tree.
Dave
On Feb 20, 5:13 pm, Don dondod...@gmail.com wrote:
Yes, I am assuming a binary search tree. The problem is trivial
otherwise.
If it is just a binary tree, you visit each node and keep track of the
closest.
Don
On Feb 20, 5:02 pm, Dave dave_and_da...@juno.com wrote:
@Don: Aren't you assuming a binary _search_ tree? Only a binary tree
was specified by the OP.
Dave
On Feb 20, 10:44 am, Don dondod...@gmail.com wrote:
Supraja,
I think that your solution will work, but it does more work than is
necessary. You don't need to traverse the entire tree.
node findClosest(node root, double k)
{
node result = root;
double diff = fabs(root-value - k);
for(node loc = root; loc; loc = (loc-value k) ? loc-left :
loc-right)
{
double newDiff = fabs(loc-value - k);
if (newDiff diff)
{
result = loc;
diff = newDiff;
}
}
return result;
}
On Feb 20, 5:24 am, Supraja Jayakumar suprajasank...@gmail.com
wrote:
Hi
Question is given a binary tree and a key K, code to find the
node with the
closest value.
I'd be happy to receive some feedback about my solution too.
Pls find the code below:
class FindingClosestNodeInTree {
private static double difference = 0.0;
private static doule key = 0.0;
int main() {
BinaryTree bt;
bt.insert(20.43);
bt.insert(12.78);
bt.insert(19.89);
bt.insert(32.69);
bt.insert(2.54);
cout Please provide the key value endl;
cin key;
const Node closestNode = closestValue(bt);
cout Node that has the closest value to
closestNode.value;
return 1;}
const Node closestValue(const BinaryTree node) {
if(node==null)
return;
int val = node.value;
int currDiff = val key ? val-key:key-val;
difference = currDiff difference ? currDiff:difference;
if(node.left!=null)
closestValue(node.left);
if(node.right!=null)
closestValue(node.right);
return difference;
}
}
Thanks
Supraja J- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Finding closest double in a Btree
Just the topic line:
Finding closest double in a Btree
On Feb 20, 9:37 pm, Dave dave_and_da...@juno.com wrote:
@Gene: I don't know what is confusing about the OP's problem
statement:
Question is given a binary tree and a key K, code to find the node
with the
closest value.
What do you find confusing about that?
Are you opposed to using shorthand in the subject line that is then
clarified in the body of the posting?
Dave
On Feb 20, 8:19 pm, Gene gene.ress...@gmail.com wrote:
Sure the algorithm works for any binary tree, but a B-Tree is a more
general data structure. So the problem statement is confusing. This
is probably the reason some people gave alternatives that only work
with a BST. A BST is a special case of a B-Tree.
On Feb 20, 8:58 pm, saurabh singh saurab...@gmail.com wrote:
@gene probably you are saying this on the basis of the subject of the
mail?Please read the problem statement stated in the mail.Even its a B
tree doesn't effects the algorithm proposed by don which says *traverse
each node and keep track of minimum.*
So irrespective of the data structure used this solution is bound to
work
closest:
arguments: dataStructure T,int number
tmp:=getelem(T);
min=tmp.value
while( getelem returns non null values)
do
nxt:=getelem(T);
if(abs(nxt.value-number)min) then
tmp=nxt
min=nxt.value
done
done
return tmp
The nextelem function can be written according to the data structure used.
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Tue, Feb 21, 2012 at 6:06 AM, Gene gene.ress...@gmail.com wrote:
Not to mention the subject line seems to be asking about B-Trees,
which is no kind of binary tree, so the OP gets it wrong, too.
On Feb 20, 7:28 pm, Dave dave_and_da...@juno.com wrote:
@Don: By that measure, it also is trivial if the tree is a BST. You
just find the largest node x and the smallest one x and choose
between them.
But since the original problem did not specify a BST, your solution is
non-responsive. If I were grading a test, I'd have to count your
solution as wrong, figuring that you do not know the difference
between a binary tree and a binary search tree.
Dave
On Feb 20, 5:13 pm, Don dondod...@gmail.com wrote:
Yes, I am assuming a binary search tree. The problem is trivial
otherwise.
If it is just a binary tree, you visit each node and keep track of
the
closest.
Don
On Feb 20, 5:02 pm, Dave dave_and_da...@juno.com wrote:
@Don: Aren't you assuming a binary _search_ tree? Only a binary
tree
was specified by the OP.
Dave
On Feb 20, 10:44 am, Don dondod...@gmail.com wrote:
Supraja,
I think that your solution will work, but it does more work
than is
necessary. You don't need to traverse the entire tree.
node findClosest(node root, double k)
{
node result = root;
double diff = fabs(root-value - k);
for(node loc = root; loc; loc = (loc-value k) ? loc-left :
loc-right)
{
double newDiff = fabs(loc-value - k);
if (newDiff diff)
{
result = loc;
diff = newDiff;
}
}
return result;
}
On Feb 20, 5:24 am, Supraja Jayakumar suprajasank...@gmail.com
wrote:
Hi
Question is given a binary tree and a key K, code to find the
node with the
closest value.
I'd be happy to receive some feedback about my solution too.
Pls find the code below:
class FindingClosestNodeInTree {
private static double difference = 0.0;
private static doule key = 0.0;
int main() {
BinaryTree bt;
bt.insert(20.43);
bt.insert(12.78);
bt.insert(19.89);
bt.insert(32.69);
bt.insert(2.54);
cout Please provide the key value endl;
cin key;
const Node closestNode = closestValue(bt);
cout Node that has the closest value to
closestNode.value;
return 1;}
const Node closestValue(const BinaryTree node) {
if(node==null)
return;
int val = node.value;
int currDiff = val key ? val-key:key-val;
difference = currDiff difference ? currDiff:difference;
if(node.left!=null)
closestValue(node.left);
if(node.right!=null)
closestValue(node.right);
return difference;
}
}
Thanks
Supraja J- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group
[algogeeks] Re: Finding closest double in a Btree
The topic of the discussion is:
Finding closest double in a Btree
A binary tree that is also a B-Tree is (roughly) a Binary Search
Tree.
On Feb 20, 9:37 pm, Dave dave_and_da...@juno.com wrote:
@Gene: I don't know what is confusing about the OP's problem
statement:
Question is given a binary tree and a key K, code to find the node
with the
closest value.
What do you find confusing about that?
Are you opposed to using shorthand in the subject line that is then
clarified in the body of the posting?
Dave
On Feb 20, 8:19 pm, Gene gene.ress...@gmail.com wrote:
Sure the algorithm works for any binary tree, but a B-Tree is a more
general data structure. So the problem statement is confusing. This
is probably the reason some people gave alternatives that only work
with a BST. A BST is a special case of a B-Tree.
On Feb 20, 8:58 pm, saurabh singh saurab...@gmail.com wrote:
@gene probably you are saying this on the basis of the subject of the
mail?Please read the problem statement stated in the mail.Even its a B
tree doesn't effects the algorithm proposed by don which says *traverse
each node and keep track of minimum.*
So irrespective of the data structure used this solution is bound to
work
closest:
arguments: dataStructure T,int number
tmp:=getelem(T);
min=tmp.value
while( getelem returns non null values)
do
nxt:=getelem(T);
if(abs(nxt.value-number)min) then
tmp=nxt
min=nxt.value
done
done
return tmp
The nextelem function can be written according to the data structure used.
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Tue, Feb 21, 2012 at 6:06 AM, Gene gene.ress...@gmail.com wrote:
Not to mention the subject line seems to be asking about B-Trees,
which is no kind of binary tree, so the OP gets it wrong, too.
On Feb 20, 7:28 pm, Dave dave_and_da...@juno.com wrote:
@Don: By that measure, it also is trivial if the tree is a BST. You
just find the largest node x and the smallest one x and choose
between them.
But since the original problem did not specify a BST, your solution is
non-responsive. If I were grading a test, I'd have to count your
solution as wrong, figuring that you do not know the difference
between a binary tree and a binary search tree.
Dave
On Feb 20, 5:13 pm, Don dondod...@gmail.com wrote:
Yes, I am assuming a binary search tree. The problem is trivial
otherwise.
If it is just a binary tree, you visit each node and keep track of
the
closest.
Don
On Feb 20, 5:02 pm, Dave dave_and_da...@juno.com wrote:
@Don: Aren't you assuming a binary _search_ tree? Only a binary
tree
was specified by the OP.
Dave
On Feb 20, 10:44 am, Don dondod...@gmail.com wrote:
Supraja,
I think that your solution will work, but it does more work
than is
necessary. You don't need to traverse the entire tree.
node findClosest(node root, double k)
{
node result = root;
double diff = fabs(root-value - k);
for(node loc = root; loc; loc = (loc-value k) ? loc-left :
loc-right)
{
double newDiff = fabs(loc-value - k);
if (newDiff diff)
{
result = loc;
diff = newDiff;
}
}
return result;
}
On Feb 20, 5:24 am, Supraja Jayakumar suprajasank...@gmail.com
wrote:
Hi
Question is given a binary tree and a key K, code to find the
node with the
closest value.
I'd be happy to receive some feedback about my solution too.
Pls find the code below:
class FindingClosestNodeInTree {
private static double difference = 0.0;
private static doule key = 0.0;
int main() {
BinaryTree bt;
bt.insert(20.43);
bt.insert(12.78);
bt.insert(19.89);
bt.insert(32.69);
bt.insert(2.54);
cout Please provide the key value endl;
cin key;
const Node closestNode = closestValue(bt);
cout Node that has the closest value to
closestNode.value;
return 1;}
const Node closestValue(const BinaryTree node) {
if(node==null)
return;
int val = node.value;
int currDiff = val key ? val-key:key-val;
difference = currDiff difference ? currDiff:difference;
if(node.left!=null)
closestValue(node.left);
if(node.right!=null)
closestValue(node.right);
return difference;
}
}
Thanks
Supraja J- Hide quoted text -
- Show quoted text -
--
You received this message
[algogeeks] Re: find the sum of very large binary sequence in O(n)
What language are you using? In most languages a bool is either 1 byte
or 4 bytes long. So you'd be wasting a tremendous amount of time and
space if you're doing the additions one bit at a time.
Here's roughly how it work work in C, but you'll get a faster result
with GNU mp on most machines because inner loops use assembly language
inserted to get access to the carry register. My code is untested,
but ought to be at least very close.
typedef unsigned long long LIMB;
#define N_BITS 10
#define L sizeof(LIMB)
#define LIMB_SIZE ((N_BITS + L - 1) / L)
typedef struct big_num {
LIMB bits[LIMB_SIZE]; // 12,500 long longs hold bits
} BIG_NUM;
// Add a and b. Put result in r. Return the carry out.
LIMB add(BIG_NUM *r, BIG_NUM *a, BIG_NUM *b)
{
int i;
LIMB c = 0;
for (i = 0; i LIMB_SIZE; i++) {
LIMB ia = a-bits[i];
LIMB ib = b-bits[i];
LIMB it = ia + ib;
LIMB ir = it + c;
r-bits[i] = ir;
c = (ir it) || (it ia);
}
return c;
}
On Feb 13, 2:12 am, rspr ravishanker@gmail.com wrote:
I have two binary sequences x and y (10 bits long)...I am taking a
bool array to store it.I have to implement the summation
operation( at most 40 summation operation)...while the bits patter
in changing in x and yin my approach before performing a sum I am
taking care of a. to check is sequence A or B is changed b. is the sum
operations are continuousso i have not to sum up it again bcz in
between there is no change in A and B
But the output is killingwhat could be the better approach to
implement the sum operation.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: suggestions?
If you want to do something of practical importance that has not already been done many times, you can look at parallel collision detection. Collision detection is very important in physical simulations (as in mechanical design tools, CGI, and computer games). On Feb 12, 10:58 am, Arun Vishwanathan aaron.nar...@gmail.com wrote: hi, I need to a final project in a course called Parallel Programming. Does anyone have suggestions for a good topic to take up in this??Some challenging problem maybe that is computationally intensive but can benefit from multicore and parallel processing. Thanks! -- People often say that motivation doesn't last. Well, neither does bathing - that's why we recommend it daily. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Finding pre order representation of expression
I think all the answers are wrong. Also pre-order is probably the wrong term here. The conventional term is prefix or Polish notation. You'd break up this expression at the level of lowest precedence as: (A - B) - C where A = ~16, B = ~14 / ~12, and C = 2 * 8 . Note I'm using ~ for unary negation because prefix notation is ambiguous if you can't tell a unary minus from a binary minus (and you aren't using parentheses like lisp). In prefix this is - - A B C. Term A is already in prefix. Term B in prefix is / ~14 ~12 Term C is * 2 8. Substituting you get - - ~16 / ~14 ~12 * 2 8 Now if you instead broke up the top level as A - (B - C) the prefix is - A - B C so you'd get the third answer - ~ 16 - / ~14 ~12 * 2 8 But for this to be correct the problem would have to say that subtraction is _right_ associative. Normally it's not. I.e. 1 - 2 - 3 is -4, not 2. On Feb 9, 8:28 am, Rahul Menon menonrahul1...@gmail.com wrote: From the following options, select the correct pre-order representation of the following expression. – 16 – – 14 / – 12 - 2 * 8 Please do answer how you arrived at the answer! Answers - –16--/14–12*28 - –16--/-1412*28 - –16 - / –1 4 –1 2 *28 */--–16-14–1228 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Divisibility by five
You can extend this thinking to finding the value mod M of any string
of base B digits. (In this case M=5, B=2, and you are looking for a
mod 5 value of zero.) Construct a finite automaton with M states 0 to
M-1. The current state of the automaton tells you the value mod M of
the digits seen so far. For current state m and new digit d, the
automaton's next state table has value (m * B + d) mod M. Of course
you don't compute this value while reading the string. It's stored
explicitly in the table. For this problem the next state table looks
like this:
d
m 0, 1
0 = {0, 1}
1 = {2, 3}
2 = {4, 0}
3 = {1, 2}
4 = {3, 4}
Then the algorithm is just:
state = 0;
while another digit remains
d = next digit
state = next_state[state, d]
end;
return state;
For this particular problem you'd check that the return value is zero.
On Jan 22, 10:26 am, Lucifer sourabhd2...@gmail.com wrote:
@above...
The above explanation is based on the answer that i gave to the
following question asked:
Given an infinite stream of bits, at any given point of time u have
tell whether the no. formed by the bits sent till now is divisible by
3.
The catch in the above question is that you can't store the integral
value formed by the bit pattern. At any given point of time u will
only have the current bit. Hence, we need to preprocess the bits sent
to us and then generate the answer.
The same approach can be applied here..
2^0, 2^1 gives remainder 1 and 2(-1) when divided by 3.
Code:
int r[2]= {1,2};
int i =0;
While(there is an incoming bit X)
{
if(X1)
{
currRem += r[i%2];
if (currRem =3) currRem -=3;
}
++i;
}
-
Hence, the actual question can be changed saying that given an
infinite stream of bits, at any given point of time we need to figure
out whether its divisible by 5.
The above given code will work for this case as well.
On Jan 22, 12:19 pm, Lucifer sourabhd2...@gmail.com wrote:
@another approach..
The remainders when the following nos. are divided by 5 are :
Numbers Remainder
2^0 1
2^1 2
2^2 4 (-1)
2^3 3 (-2)
Now, we know that given a product of nos. a1, a2, ... aN when divided
by a no. K, the remainder is:
the product of (a1 mod K) (aN mod K) i.e
[ Lets call this as NumTheoProp1]
a1* a2* a3*...*aN = x*K + (a1 mod K)*(a2 mod K)**(aN mod K)..
[ the above can be proved by representing ai = xi * K + (ai mod K),
and then multiplying all the ai's..]
We can then recursively apply the same approach to the product of
remainders until and unless the remainder is smaller than K.
But a complete reduction into a value K is not the point here. We
are going to use the above fact for the following:
Say, the given no. is 2^R ...
Now, the above can be interpreted as,
2^R = 2^(4q) * 2^r, where R = 4q + r and 0=r 4
Now we know that, 2^4 when divided by 5 gives a remainder 1..
Hence applying the [NumTheoProp1] :
2^(4q) = (2^4)*(2^4)*... (q times)..
when 2^(4q) = x*5 + (2^4 mod 5)^q..
= x* 5 + 1..
Hence,
2^R = 2^(4q) * 2^r
= x*5 + (2^4q mod 5)*(2^r mod 5)
= x*5 + (2^r mod 5)..
Now, as 0=r 4, based on the remainder jolted at the starting..
2^r mod 5 = one of (1, 2, 4, 3)..
But if you closely observe there is a pattern..
For any no. 2^R where R= 4 we can reduce it to 2^r where r 4 by
using [NumTheoProp1]
Hence,
No.( 2^r) Remainder
0 1
1 2
2 4
3 3
4 1
5 2
6 4
7 3
and the cycle continues..
Now. say a no. N is given, then it can be represented as,
N = b0* (2^0) + b1* (2^1) + + bN* (2^logN)..
where bi is either 0 or 1 [ basically it mimics the bit pattern)
N mod 5 = ( [sum over all i ( (bi* (2^i)) mod 5 )] mod 5)
Now, the inner mod 5 can be directly calculated based on the index of
i (as there is a pattern). Btw it also depends on the value of bi. If
bi =0, then the remainder will be 0 otherwise we will get the
remainder based on the pattern..
The outer mod 5, can be handled by following an incremental process,
i.e whenever the current remainder becomes =5 we will subtract 5 from
it.
Code:
int N; // given number..
int r[4] = {1, 2, 4, 3};
int currRem = 0;
int i = 0;
while (N)
{
if (N1)
{
currRem += r[i%4];
if (currRem =5)
currRem -=5;
}
++i;
N = 1;}
if ( currRem == 0)
{
printf(N is divisible by 5);
}
On Jan 22, 2:42 am, Dave dave_and_da...@juno.com wrote:
@Arun: Proof that n = 4*a + b is a multiple of 5 if and only if a - b
is a
[algogeeks] Re: Time Complexity Ques
To find sqrt(a), this is equivalent to Newton's Method with f(x)=x^2 -
a. Newton is: x_{i+1} = x_i + f'(x_i) / f'(x_i). So you have x_{i+1}
= x_i + (x_i^2 - a) / (2 x_i) = (x + a/x) / 2, which is just what the
Babylonian method says to do.
Newton's method roughly doubles the number of significant bits in the
answer with every iteration _when it converges_. The problem is that
it doesn't converge to every root. There's a huge literature on this,
which I'll let you find yourself.
On Jan 15, 10:22 pm, Ankur Garg ankurga...@gmail.com wrote:
Hello
I was going through this link
http://www.geeksforgeeks.org/archives/3187
Wonder what is the time complexity for this..?Can anyone explain
Regards
Ankur
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Sorting for large data
If the interviewer actually said 10^80 data items, he/she was expecting you to say it's a silly question. Do you realize how much 10^80 is? A terabyte is 10^12 bytes. So we are talking about 10^68 1 Tb disk drives just to hold 1 byte records. The number of grains of sand that would make up the volume of the Earth is only about 10^32. It's fair to say that at least for a few decades there won't be enough storage capacity in the world to hold 10^80 data items. If the interviewer actually said 10^8, we have 100 million records. This is more reasonable. The interviewer probably wanted you to ask how big the records are. If small, you can do a regular sort in memory. If large, you could sort a list of keys or disk offsets. External sort would start being a valid technique with 10^9 or 10^10 records depending on how much main memory you have available. As to tools, gnusort does external sort when the data are very big. At least it did about 10 years ago when I looked at the source code. On Jan 14, 1:09 pm, Abhishek Goswami zeal.gosw...@gmail.com wrote: Hi, Could any point out me any algorithm and program if we need to sort to large data like 10 ^ 80 with memory constraint. Suppose you have minimum memory like 4 MB. I am not sure that this algo discussed or not but i was not able to find in this group. Thanks Abhishek -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: hextoint program MS Q
Which language? On Jan 15, 8:23 pm, Ashish Goel ashg...@gmail.com wrote: Hi, given a string in hex, convert it into int. Write test cases for the same. 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] Re: hextoint program MS Q
And it ought to. Did you try it?
On Jan 15, 9:55 pm, Ashish Goel ashg...@gmail.com wrote:
a 0x should come as a negative number
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, Jan 16, 2012 at 8:19 AM, Gene gene.ress...@gmail.com wrote:
Okay. Normally you want to use a library that someone else has
tested. So:
sscanf(%x, i);
If you don't have access to any libraries, then:
/*
* Return the integer value of the hex string s. Allowable characters
* are 0-9, a-f, A-F. Any other character causes scanning to stop and
* the hex value of the string up to that character is returned. If
the first
* character is non-hex, then zero is returned.
*/
int hex_to_int(char *s)
{
int i = 0;
while (*s) {
if ('0' = *s *s = '9')
i = (i 4) + (*s - '0');
else if ('a' = *s *s = 'f')
i = (i 4) + *s + (10 - 'a');
else if ('A' = *s *s = 'F')
i = (i 4) + *s + (10 - 'A');
else break;
s++;
}
return i;
}
On Jan 15, 9:16 pm, Ashish Goel ashg...@gmail.com wrote:
i would assume C or C++
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, Jan 16, 2012 at 7:40 AM, Gene gene.ress...@gmail.com wrote:
Which language?
On Jan 15, 8:23 pm, Ashish Goel ashg...@gmail.com wrote:
Hi,
given a string in hex, convert it into int.
Write test cases for the same.
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] Re: hextoint program MS Q
More detail: For nearly all compilers, int is 32 bits. So I think you
mean should return a negative number. I just ran the code,
and it does this as expected.
To stop parsing prior to overflow, say something like
int hex_to_int(char *s)
{
int i = 0;
while (*s) {
if ('0' = *s *s = '9')
i = (i 4) + (*s - '0');
else if ('a' = *s *s = 'f')
i = (i 4) + *s + (10 - 'a');
else if ('A' = *s *s = 'F')
i = (i 4) + *s + (10 - 'A');
else break;
if (i 0xf00) break;
s++;
}
return i;
}
On Jan 15, 10:01 pm, Gene gene.ress...@gmail.com wrote:
And it ought to. Did you try it?
On Jan 15, 9:55 pm, Ashish Goel ashg...@gmail.com wrote:
a 0x should come as a negative number
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, Jan 16, 2012 at 8:19 AM, Gene gene.ress...@gmail.com wrote:
Okay. Normally you want to use a library that someone else has
tested. So:
sscanf(%x, i);
If you don't have access to any libraries, then:
/*
* Return the integer value of the hex string s. Allowable characters
* are 0-9, a-f, A-F. Any other character causes scanning to stop and
* the hex value of the string up to that character is returned. If
the first
* character is non-hex, then zero is returned.
*/
int hex_to_int(char *s)
{
int i = 0;
while (*s) {
if ('0' = *s *s = '9')
i = (i 4) + (*s - '0');
else if ('a' = *s *s = 'f')
i = (i 4) + *s + (10 - 'a');
else if ('A' = *s *s = 'F')
i = (i 4) + *s + (10 - 'A');
else break;
s++;
}
return i;
}
On Jan 15, 9:16 pm, Ashish Goel ashg...@gmail.com wrote:
i would assume C or C++
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, Jan 16, 2012 at 7:40 AM, Gene gene.ress...@gmail.com wrote:
Which language?
On Jan 15, 8:23 pm, Ashish Goel ashg...@gmail.com wrote:
Hi,
given a string in hex, convert it into int.
Write test cases for the same.
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] Re: Time Complexity Ques
To find sqrt(a), this is equivalent to Newton's Method with
f(x)=x^2 - a.
Newton is:
x_{i+1} = x_i + f'(x_i) / f'(x_i).
So you have
x_{i+1} = x_i + (x_i^2 - a) / (2 x_i) = (x + a/x) / 2,
which is just what the Babylonian method says to do.
Newton's method roughly doubles the number of significant bits in the
answer with every iteration _when it converges_. The problem is that
though it works fine for sqrt(), it won't converge for arbitrary f.
There's
a huge literature on this, which I'll let you find yourself.
On Jan 15, 4:22 pm, Ankur Garg ankurga...@gmail.com wrote:
Hello
I was going through this link
http://www.geeksforgeeks.org/archives/3187
Wonder what is the time complexity for this..?Can anyone explain
Regards
Ankur
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Time Complexity Ques
I'm sorry for not being specific. I meant it doesn't converge for all
roots, e.g. cube root.
On Jan 15, 10:18 pm, Dave dave_and_da...@juno.com wrote:
@Gene: Actually, Newton's Method for sqrt(a), where a 0, also
sometimes called Heron's Method, converges for every initial guess x_0 0.
This is not true generally for Newton's Method, but it is true
for Newton's Method applied to f(x) = x^2 - a.
Dave
On Jan 15, 5:39 pm, Gene gene.ress...@gmail.com wrote:
To find sqrt(a), this is equivalent to Newton's Method with f(x)=x^2 -
a. Newton is: x_{i+1} = x_i + f'(x_i) / f'(x_i). So you have x_{i+1}
= x_i + (x_i^2 - a) / (2 x_i) = (x + a/x) / 2, which is just what the
Babylonian method says to do.
Newton's method roughly doubles the number of significant bits in the
answer with every iteration _when it converges_. The problem is that
it doesn't converge to every root. There's a huge literature on this,
which I'll let you find yourself.
On Jan 15, 10:22 pm, Ankur Garg ankurga...@gmail.com wrote:
Hello
I was going through this link
http://www.geeksforgeeks.org/archives/3187
Wonder what is the time complexity for this..?Can anyone explain
Regards
Ankur
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: MS Q
Part of the problem must be rules that specify how 1's can be
connected to form an island.
From the discussion, it looks like the rules are that a 1 must be
connected North, West, East, or South. This is called a 4-connected
grid.
Another possibility would be an 8-connected grid. This is probably
what you have in mind. In this case a 1 can be connected to another 1
North, Northeast, East, Southeast, South, Southwest, West, or
NorthWest. In the code I gave in a previous message, you'd just add 4
more erase() calls for the diagonal corners.
Since the OP never said which rule to use, you are not wrong. You're
just answering a different question than he/she had in mind. This is
a difficulty that often occurs when a question is asked imprecisely.
An excellent lesson to learn for anyone who wants to be a software
engineer...
On Jan 11, 1:28 am, Umer Farooq the.um...@gmail.com wrote:
I still don't get how are they two islands. As long as I have understood,
diagonals abridge the two islands into one. In this case, these two islands
are connected so they form one single island?
1 1 0 0
1 1 0 0
0 0 1 1
This can be either one single island. Or they are three island if a change
in direction makes a whole new island.
Can anyone please clear me the problem?
On Wed, Jan 11, 2012 at 10:24 AM, prakash y yprakash@gmail.com wrote:
I think atul/Ramakanth's approach will work fine, if we include one more
condition
for each arr[i][j]
if(arr[i][j]==1)
{
if (arr[i-1][j]==0 arr[i][j-1]==0 arr[i-1][j-1]==0)
count++;
else if (arr[i-1][j]==1 arr[i][j-1]==1 arr[i-1][j-1]==0)
count--;
}
On Wed, Jan 11, 2012 at 8:10 AM, surender sanke surend...@gmail.comwrote:
@gene
in that case ur erase() should even consider diagonal elements as well,
else there would be 2 islands in example
surender
On Wed, Jan 11, 2012 at 7:19 AM, Gene gene.ress...@gmail.com wrote:
Guys,
You are making this way too hard. It's really a graph problem. The
nodes are the 1's and adjacent 1's are connected by undirected edges.
You must count components in the graph. So the algorithm is easy:
Find a component, erase it, repeat. Count components as you go.
What's an efficient way to do this with this special kind of graph we
have? Just erase components by erasing 1's.
So we get:
#include stdio.h
int a[100][100] = {
{1, 1, 0, 0},
{1, 1, 0, 0},
{0, 0, 1, 1},
};
int m = 3, n = 4;
// Erase the undirected component rooted at i,j.
void erase(int i, int j)
{
// If we're off the graph or already erased,
// there's nothing to do.
if (i 0 || j 0 || i = m || j = n || !a[i][j])
return;
// Erase!
a[i][j] = 0;
// Recursively erase the 4 neighbors.
erase(i+1, j); erase(i-1, j);
erase(i, j+1); erase(i, j-1);
}
void count_islands()
{
int i, j, n_islands = 0;
// Search for a component.
for (i = 0; i m; i++) {
for (j = 0; j n; j++) {
if (a[i][j] == 1) {
// Found one! Count and erase.
n_islands++;
erase(i, j);
}
}
}
printf(found %d islands\n, n_islands);
}
int main(void)
{
count_islands();
return 0;
}
On Jan 9, 9:06 pm, 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.com
wrote:
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.com
wrote:
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
--
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
[algogeeks] Re: MS Q
The OP is not clear on how to handle diagonals. If adjacent 1's on the
diagonal are considered connected, then just add 4 more calls to
erase().
The standard terms are 4-connected and 8-connected. Both come up when
working with grid graphs or pixel matrices.
On Jan 10, 9:40 pm, surender sanke surend...@gmail.com wrote:
@gene
in that case ur erase() should even consider diagonal elements as well,
else there would be 2 islands in example
surender
On Wed, Jan 11, 2012 at 7:19 AM, Gene gene.ress...@gmail.com wrote:
Guys,
You are making this way too hard. It's really a graph problem. The
nodes are the 1's and adjacent 1's are connected by undirected edges.
You must count components in the graph. So the algorithm is easy:
Find a component, erase it, repeat. Count components as you go.
What's an efficient way to do this with this special kind of graph we
have? Just erase components by erasing 1's.
So we get:
#include stdio.h
int a[100][100] = {
{1, 1, 0, 0},
{1, 1, 0, 0},
{0, 0, 1, 1},
};
int m = 3, n = 4;
// Erase the undirected component rooted at i,j.
void erase(int i, int j)
{
// If we're off the graph or already erased,
// there's nothing to do.
if (i 0 || j 0 || i = m || j = n || !a[i][j])
return;
// Erase!
a[i][j] = 0;
// Recursively erase the 4 neighbors.
erase(i+1, j); erase(i-1, j);
erase(i, j+1); erase(i, j-1);
}
void count_islands()
{
int i, j, n_islands = 0;
// Search for a component.
for (i = 0; i m; i++) {
for (j = 0; j n; j++) {
if (a[i][j] == 1) {
// Found one! Count and erase.
n_islands++;
erase(i, j);
}
}
}
printf(found %d islands\n, n_islands);
}
int main(void)
{
count_islands();
return 0;
}
On Jan 9, 9:06 pm, 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.com
wrote:
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.com
wrote:
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
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: extracting vector (digitization) from an ECG image
This is pretty funny because modern ECG machines generate digital output. You might first look into whether you can get the digits directly from the machine rather than scans of paper. But suppose you can't. I assume you asking how to find numerical coordinates for the curve by scanning and then analysing the scan. The process of converting a pixmap or bitmap--a big 2d array of pixel data--to polyline coordinates is called vectorzation. I did a quick Google search and came up with this page, which mentions several open source vectorizers: http://wiki.inkscape.org/wiki/index.php/Tools Most of these tools are going to produce SVG files. You'll probably need to look up the SVG file format to determine how to extract the coordinates you need. Since you are training neural nets, you are going to have to clean the results: put them all on the same vertical and horizontal scale, ensure the grid in the background isn't interpreted as data, etc. If you are required to implement the vectorizer yourself, write back. I have done that and can give you pointers. Once you have numerical descriptions of the code, I'd stay in MATLAB. Just so you know, professional ECG analyzers usually work in the _frequency_ domain. I.e. they work on the DFT of the ECG signal, not the signal itself. Or they use both, but the DFT is primary. With MATLAB, taking the DFT is one line of code. And MATLAB has a neural net toolkit. On Jan 8, 1:08 am, Deepak Garg deepakgarg...@gmail.com wrote: my question is about how to achieve digitization of an image/graph image. for example i have the following ECG image( taken from a normal camera ):- http://i.stack.imgur.com/QAMfk.png so what algorithm should i follow to get the digitized image, my final aim is to feed this information to a neural network that can classify the given ECG image into a disease class. please suggest me which platform is more feasible MATLAB or JAVA? please help me guys!! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: MS Q
Guys,
You are making this way too hard. It's really a graph problem. The
nodes are the 1's and adjacent 1's are connected by undirected edges.
You must count components in the graph. So the algorithm is easy:
Find a component, erase it, repeat. Count components as you go.
What's an efficient way to do this with this special kind of graph we
have? Just erase components by erasing 1's.
So we get:
#include stdio.h
int a[100][100] = {
{1, 1, 0, 0},
{1, 1, 0, 0},
{0, 0, 1, 1},
};
int m = 3, n = 4;
// Erase the undirected component rooted at i,j.
void erase(int i, int j)
{
// If we're off the graph or already erased,
// there's nothing to do.
if (i 0 || j 0 || i = m || j = n || !a[i][j])
return;
// Erase!
a[i][j] = 0;
// Recursively erase the 4 neighbors.
erase(i+1, j); erase(i-1, j);
erase(i, j+1); erase(i, j-1);
}
void count_islands()
{
int i, j, n_islands = 0;
// Search for a component.
for (i = 0; i m; i++) {
for (j = 0; j n; j++) {
if (a[i][j] == 1) {
// Found one! Count and erase.
n_islands++;
erase(i, j);
}
}
}
printf(found %d islands\n, n_islands);
}
int main(void)
{
count_islands();
return 0;
}
On Jan 9, 9:06 pm, 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.com wrote:
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.com wrote:
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
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Maximum size square sub-matrix with all 1s
The 1's and 0's are in matrix R. We want to compute an integer matrix M of the same dimensions as R such that Mij is the size of the largest square of 1's of which Rij is the bottom right corner. As we go we can keep track of max(Mij), and this will be the answer. So how to compute Mij? The values north, west, and northwest of Mij tells us about the sizes of squares of 1's in those directions. If we take the min; call it M, then we can be sure all the elements of the square with diagonal (i,j)-(i-M,j-M) are all 1's and moreover that if we tried a bigger square we'd either run off the edge of the matrix or hit a zero. So the size of this new square is M+1. Atul anand's algorithm is almost the story. He left out the base cases. The left and top edges of M are just the same as R. So to write a program, for (i = 0; i m; i++) for (j = 0; j n; j++) M[i][j] = (i == 0 || j == 0 || R[i][j] == 0) ? R[i][j] : 1 + min3(M[i-1][j], M[i-1,j-1], M[i][j-1]); If you recode this carefully, you don't need a 2d matrix for M. You can get away with a single row plus one integer variable. On Jan 10, 11:37 am, Sanjay Rajpal sanjay.raj...@live.in wrote: Its a square matrix containing 0s and 1s. Will u plz elaborate about this equation ? * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286 * On Tue, Jan 10, 2012 at 8:36 AM, atul anand atul.87fri...@gmail.com wrote: i dint get...you should provide more details , if it is all 1 then whole matrix is a max square.. anyways equation to find max sub square is this. M[i,j]=R[i,j]==0 ? 0 : 1+min(M[i-1][,j] , M[i][j-1], M[i-1][j-1] ) On Tue, Jan 10, 2012 at 10:00 PM, Sanjay Rajpal sanjay.raj...@live.inwrote: Suggest an algorithm guyzzz. * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286 * -- 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] Re: Binary Search Problem
Exactly. And note that if pointers and unsigned integers have the same number of bits, overflow can't be a problem as long as the array elements are 2 bytes or more long. I.e. if you have an n-bit machine, the last 2-byte array element can't have index more than 2^n/2 - 1 = 2^(n-1) - 1. Consequently when doing the addition in (lo+hi)/2, the numerator can't be more than 2*[2^(n-1)-1] = 2^n - 2, which isn't an overflow, though you do have to be careful to use unsigned arithmetic in this case. On Jan 9, 4:48 pm, Don dondod...@gmail.com wrote: The intermediate value of start+end may be too large to store in an integer, even though start and end by themselves are in the valid range. If you know this to not be the case, you can use the simpler form. Don On Jan 8, 5:04 am, Sanjay Rajpal srn...@gmail.com wrote: In binary search, mid = start + (end-start)/2 is used to avoid overflow, as said by a book. why can't we use mid = (start + end)/2, it says this statement may result in overflow ? * Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286 * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: find point lies in side circle
If the graph is planar and you have it's embedding, then you can do better than O(N), at least on a random graph. Otherwise this has to be impossible because the graph gives you no information, and you must look at each vertex. On Jan 5, 1:17 pm, dabbcomputers dabbcomput...@gmail.com wrote: you are given with N points on graph. and a point A on graph and range R you have to find the points that lies within the radius of R from point A. with complexity less than O(N). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: find point lies in side circle
An embedding is the information that says how the graph is laid out with no edges crossing. As a data structure, it can be given in various ways. The simplest is for adjacency lists of each vertex to be given in sorted order clockwise or anti-clockwise. On Jan 7, 5:10 pm, sravanreddy001 sravanreddy...@gmail.com wrote: @Gene: I didn't understand on what you termed as embedding Can you provide more insights on this? @dabbcomputers: also, listing set of points (not just one) isn't going to be a better than O(n) solution. for eg: a value of R that eliminates only half the points outside the circle. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: All possible permutations of a given string
Don't forget repeats. The string aaa has only one permutation.
A related interesting question is how to write a permutation
iterator. Here is the interface:
typedef struct {
// your code here
} PERMUTATION_ITERATOR;
/* Initialize the given permutation iterator with the string of n
characters
to be permuted. */
void init_permutation_iterator(PERMUTATION_ITERATOR *iterator, char
*str, int n)
{
// your code here
}
/* Get the next unique permutation of the initialization string into
the
given buffer. The first string returned is always the string
provided
to the initializer. Return true unless the permutation being
returned
is the last one. I.e. next time this function is called, it will
wrap back
to the initialization string. */
int get_next_permutation(PERMUTATION_ITERATOR *iterator, char *buf)
{
// your code here
}
Use like this:
{
PERMUTATION_ITERATOR iterator[1];
char s = Cool or what?;
char buf[100];
init_permutation_iterator(iterator, s, strlen(s));
while (get_next_permutation(iterator, buf))
printf(%.*s\n, buf);
}
On Dec 28, 8:15 am, Karthikeyan V.B kartmu...@gmail.com wrote:
Hi,
Using Backtracking,
void swap(char* x,char* y)
{
char temp;
temp=*x;
*x=*y;
*y=temp;
}
void permute(char* a,int i,int n)
{
int j;
if(i==n)
printf(%s\n,a);
else
{
for(j=i;j=n;j++)
{
swap((a+i),(a+j));
permute(a,i+1,n);
swap((a+i),(a+j));
}
}
}
But this takes O(n*n!) time
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Frequency Sort Algo
Any reasonable algorithm is goingto compute a histogram of the data then sort into frequency order to produce the output. The histogram (map from data values to frequency counts) can be stored in a simple array if the data are small integers as in the example. If the data are not nice, then a hash table is a good choice. Run time will be O(n + N log N) where n is the number of input data and N is the number of unique data values. If you have many data but only a few ( O(1 / log n) ) unique values, the run time is linear. If you have O(n) unique values, it's n log n. I think this bound is tight. Note: It does not make much sense to use heaps in this problem (unless you're sorting with heapsort) as some have proposed because you can't use the min or max frequency values until you've scanned all the input. On Dec 24, 12:27 pm, Ankur Garg ankurga...@gmail.com wrote: how can one do frequency sort . Suppose we have an integer array like 1,2,3,1,2,3,1,1,2,3,4,4,3,5,3 Then 1 is appearing 4 times 2 - 3 3- 5 4-2 5-1 Then if we sort by frequency we shud have this as result 5,4,4,2,2,2,1,1,1,1,3,3,3,3,3 How to do 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.
[algogeeks] Re: correctness of point inside polygon: algorithm ?
The description is fine. It is tricky to get implementation exactly right for the cases where the ray pierces a vertex or coincides exactly with an edge, especially with floating point rather than rational arithmetic. Franklin's code (link is given on the page) works well. I'd never code it myself when his is available, and it's only 6 lines. On Dec 18, 1:30 pm, WgpShashank shashank7andr...@gmail.com wrote: Would anyone will interested to discuss ? Algo is simple but i am wondering about correctness ofhttp://en.wikipedia.org/wiki/Point_in_polygonalgorithm ? Thanks Shashank CSE, BIT Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Facebook Question
The simplest algorithm is probably to check each point against all
others while maintaining a list of the top 3. Since 3 is a small
number, you can just maintain the top 3 in sorted order by insertion.
For a bigger K top-K you'd use a max heap.
This can also be done in O(n log n) time by building the right data
structure. A kd-tree would be O(n log n) on random data, for example.
The simple algorithm would code this way:
#include stdio.h
#define N_PTS 1000
#define N_TOP 3
struct pt_s { int id; double x, y; } pts[N_PTS];
struct top_s { struct pt_s pt; double d2; } tops[N_TOP];
int n_top = 0;
void clear() { n_top = 0; }
void check_and_add(struct pt_s *hub, struct pt_s *sat)
{
double dx = hub-x - sat-x;
double dy = hub-y - sat-y;
double d2 = dx * dx + dy * dy;
struct top_s top = { *sat, d2 };
if (n_top 3) { // must insert somewhere
int i = n_top++;
while (i 0 d2 tops[i - 1].d2) {
tops[i] = tops[i - 1];
i--;
}
tops[i] = top;
}
else if (d2 tops[N_TOP - 1].d2) { // may insert
int i = N_TOP - 1;
while (i 0 d2 tops[i - 1].d2) {
tops[i] = tops[i - 1];
--i;
}
tops[i] = top;
}
}
void print(struct pt_s *hub)
{
int i;
printf(%d %d, hub-id, tops[0].pt.id);
for (i = 1; i n_top; i++)
printf(,%d, tops[i].pt.id);
printf(\n);
}
int main(void)
{
int n = 0, id, i, j;
double x, y;
while (n N_PTS scanf(%d%lf%lf, id, x, y) == 3) {
struct pt_s pt = { id, x, y };
pts[n++] = pt;
}
for (i = 0; i n; i++) {
clear();
for (j = 0; j n; j++)
if (j != i)
check_and_add(pts + i, pts + j);
print(pts + i);
}
return 0;
}
On Dec 21, 1:00 am, SAMMM somnath.nit...@gmail.com wrote:
You are given a list of points in the plane, write a program that
outputs each point along with the three other points that are closest
to it. These three points ordered by distance.
The order is less then O(n^2) .
For example, given a set of points where each line is of the form: ID
x-coordinate y-coordinate
1 0.0 0.0
2 10.1 -10.1
3 -12.212.2
4 38.3 38.3
5 79.99179.99
Your program should output:
1 2,3,4
2 1,3,4
3 1,2,4
4 1,2,3
5 4,3,1
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Dynamic programming question
Longest path won't work so well because it will return infinity if a path contains a positive cycle, which doesn't apply here because once you pick up an apple, it's gone. On Dec 13, 7:17 am, vikas vikas.rastogi2...@gmail.com wrote: Graph take up, right and bottom as nodes connected to current and do find max path. On Dec 13, 3:44 pm, Azhar Hussain azhar...@gmail.com wrote: We have apples arranged in a mxn matrix. We start from the upper left corner and have to reach bottom right corner with maximum apples. We can only move either down or right. Now if we can start any where in the matrix and have to reach anywhere on the right(reach n column). We can either up, down, right(but not left). We have to collect maximum apples from a given location. I am trying to solve problem. solution for the first one is given athttp://community.topcoder.com/tc?module=Staticd1=tutorialsd2=dynProg. What data structure would be suitable for the second problem and will dynamic programming work. Thanks in advance. Azhar. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Cliched 'k' largest elements in billion numbers: Heaps or median-of-medians?
If N is big enough so that all data will not fit in main memory and k is small enough so that the k top elements fit in memory, then the heap is likely to be the best.This is because disk access is so incredibly slow compared to memory access: A few milliseconds (10^-3) vs. a few nanoseconds (10^-9), a factor of a million. The heap-based algorithms need to touch the disk only once per data item. It would be difficult if not impossible to implement m-of-m that achieves this. On the other hand, if both k and N are so big that this many data do not fit in memory, then the m-of-m algorithm will probably win. I say this because Quicksort is known to have better performance than heapsort, including memory access patterns on large data. (In fact heaps can have terrible access patterns if implemented in the typical textbook way where the children of a[i] are at a[2*i] and a[2*i+1].) This is a strong indicator that m-of-m (which is at heart a Quicksort that stops early) will do better than keeping the top k elements in a heap for this problem when both algorithms need disk i/o. Needing to find the top 10 billion out of a few trillion data is actually a realistic problem in some areas of research. So this is a useful thing to discuss. Gene On Dec 11, 8:11 pm, bharath sriram bharath.sri...@gmail.com wrote: Hey group This is kind of a cliched question but given a file with billion numbers and the task is to compute 'k' largest numbers from this file, what approach is preferred? 1) Using heaps 2) Using Median-of-median algorithm. Have read few links which prefer heaps but clearly median of median algorithm has a linear time complexity and don't see how its any less if not better than using heaps? Any thought? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Backtracking algorithm for binpacking-like problem
Guys, if you can find a solution that is not exponential time in the
worst case you are going to be famous because this problem is NP-Hard
in the strong sense. I.e. there is not even a pseudo-polynomial time
algorithm. To get a perfect solution every time, you can't do better
than heuristic search, and the search might take a very long time to
find an optimal answer.
http://en.wikipedia.org/wiki/Bin_packing_problem gives some bounds on
how bad the solution can get if you use the standard heuristics: First
fit and best fit. They also mention your sorting strategy there.
A method that works well in practice is to implement first fit and
best fit and then keep reordering the input with a random permutation
generator, trying first and best fit on each permutation, keeping
track of what you've tried so far so as not to duplicate work
(although if N is large, this is a waste of time because the number of
permutations is N!) and the best result. With this method, you can
set a timer and always have a result when the timer expires.
A more scientific variation on this is simulated annealing, which I'll
let you look up. It's not clear that SA will do better than the simple
randomization above, however.
Backtracking alone is probably not a good idea because it explores the
search space depth first. If it makes a bad decision early on, there
may not be enough nanoseconds in the life of the universe for it ever
to backtrack far enough to undo the damage.
Cheers.
On Dec 12, 1:13 pm, Lucifer sourabhd2...@gmail.com wrote:
A slightly different approach on the lines of data access and ease of
understanding:
1) Sort the input array i.e the weights array W[N] .
2) Identify the no. of unique elements in it and create the following:
a) Count[R] - count of each unique element based on its sorted
order.
// Maintain a copy of Count[R] to used later for
generating the unique subsets. Say, DupCount[R]
b) A[R, C] - the array used for solving the bin-packing (or the
maximal subset problem)
c) W[R] - the unique sorted weight array
Here, R is the no. of unique elements.
Now, the recurrence relation will get modified as follows:
A[i , j] = A[i-1, j] or ( Count[i] != 0 ? { A[ i, j - W[i] ] ; --
Count[i] ;} : A[ i-1 , j - W[i] ] )
While generating the unique subsets we won't need a second array (B[N,
C]) as explained in the previous post. All we need to do is whenever
we add an element to the subset we will decremented the corresponding
count in array DupCount[R]. If the value of DupCount[i] at any
instance becomes 0, then that means that usage of that particular
unique element is exhausted.
On Dec 12, 4:54 pm, Lucifer sourabhd2...@gmail.com wrote:
@ania
My idea is based on the post that i had replied
inhttp://groups.google.com/group/algogeeks/browse_thread/thread/8a58ea0...
A simple tweak to the above algo can be used to solve bin-packing
problem in a (probably) faster time. First, please go through the
above post.
The maximal possible subset problem says that we need to find all
subsets for the maximum sum that doesn't exceed Wmax. Now, to
understand how it maps to the bin-packing problem you need to do the
following..
In bin-packing problem :
1) N maps to the no. of input elements.
2) Wmax maps to C, the capacity of a bin.
3) The no. of bins maps to finding the no. of unique subsets, i.e no
repeating element in any 2 subsets found, and the no. of such subsets
should be atleast = no. of bins provided.
Hence, keeping the above things in mind all we need to do is:
a) Check if A[N, C] = 1, if this fails that means there is no
solution. If it is equal to 1, then there is possibility of uniquely
filling K bins of C capacity. (if 1, then goto step 2)
b) As you can see that while finding the no. of subsets an element can
occur in 2 different subsets, for eg- {a,b,c} and {a,b,d}. To generate
unique subsets we can take another array of size B[N, C] and
initialize it with 0. Now, whenever we find a valid subset by using
A[N,C] we will simultaneously mark the corresponding elements in B[N,
C] to 1. A value of 1 in B[N, C] will indicate that the element has
already been added and need not be traversed. Hence, while generating
more subsets we can check for B[i, j] to see if its 1, if yes then we
would skip/not-include it.
c) If we are able to generate atleast K unique subsets then we are
done.
Note: There might be slight modifications that you might need to make
apart from the above cited steps. In case, you feel that something is
missing please reply and let us know if the above algo works.
On Dec 11, 4:09 am, Ania anka.step...@gmail.com wrote:
Hi,
I'm really interested in your idea as my solution is probably far from
being optimal.
On 11 Gru, 00:00, Lucifer sourabhd2...@gmail.com wrote:
@ania,
I think there is a faster
[algogeeks] Re: Find Largest number in log(n)
Exactly. Really you should see this with almost no thought. It's called an adversary argument and goes like this. Since you don't know the order of elements in A, envision them as being put in order by an adversary that always knows in advance what element you're going to examine next. Now no matter which element you choose to examine, the adversary will have placed the searched-for element at a different place that's still unseen (of course he doesn't get to put it in an element you've already looked at; the adversary can't cheat). In all, he is going to do that N-1 times before you will finally beat his shell game. So unordered search is Omega(N) time. The adversary won't let you get away with fewer probes in the array. Another example: Proving that sorting is Omega(N log N) is also an adversary argument. There are N! possible orders of the elements. Sorting is equivalent to learning which of the N! orders the elements are in, because if you know which it is, you can easily unscramble them in the O(N) time it takes to move them to their correct locations and vice versa. Well by asking the adversary a yes/no question, you can eliminate at most half of the remaining orders with each question. After all, if you split the remaining set into other than 50-50 parts, say 70-30, betting that the right answer is in the smaller 30% part, the adversary will beat you with his perfect knowledge, ensuring the order you want is in the bigger 70% part. This will only slow you down, so you might as well use the 50-50 partition. Eliminating half the orders with each question means you need log_2(N!) = Omega(N log N) yes/no questions to finally beat the adversary. Since comparisons are binary decisions, the same bound must apply for comparison sorting. The point is that the adversary way of thinking is very powerful. On Dec 12, 5:16 pm, Don dondod...@gmail.com wrote: No. To find the largest number in an unsorted array requires looking at each number, which is order n by definition. Don On Dec 12, 10:02 am, sagar pareek sagarpar...@gmail.com wrote: Hi every one. Can we find largest number from an unsorted array in log(n) ? -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: A binary tree question
You can do a zig-zag traversal of a tree by using 2 stacks in place of the 2 queues you'd use for level order traversal. As you do the zig- zag traversal, just keep track of the current and previous node visited and set previous-zznext = current at each visit. On Dec 11, 1:52 am, AMAN AGARWAL mnnit.a...@gmail.com wrote: Hi, Given a tree, in addition to the left and right pointer, it has a third pointer, that is set to NULL. Set the third pointer to a node, which will be the successor of the current node, when the tree is traversed in the zig-zag order. In other words, if we traverse the tree using this third pointer alone, then we will be traversing the tree in the zig-zag order. Regards, Aman -- AMAN AGARWAL Success is not final, Failure is not fatal: It is the courage to continue that counts! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: convert a sorted DLL to bst
This is nice. There is also an article on how to do this iteratively
with a stack:
http://groups.google.com/group/comp.programming/msg/41f46b2801c4f84e
This solution actually traverses a BST of any shape, tears it apart,
and reassembles it as a perfectly balanced tree. However, it will
also work on a sorted list. Just replace the BST traversal with a list
traversal.
On Dec 11, 12:33 pm, Lucifer sourabhd2...@gmail.com wrote:
1) Get the count of nodes in the given DLL. Say its, n.
2) Call convert(0, n-1, headPtrToDLL);
node* convert(int start, int end, node **head)
{
node * root = NULL;
if (start end)
return NULL;
int mid = (start + end) / 2;
node * left = convert( start, mid -1, head);
root = *head;
(*head) = (*head)-next; // (*head)-right;
node * right = convert( mid + 1, end, head);
root-left = left;
root-right = right;
return root;
}
On Dec 11, 12:00 pm, AMAN AGARWAL mnnit.a...@gmail.com wrote:
Hi,
WAP to convert a sorted DLL to a balanced BST.
Regards,
Aman.
--
AMAN AGARWAL
Success is not final, Failure is not fatal: It is the courage to continue
that counts!- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: finding duplicate set of paranthesis
We talked about the problem of removing as many parentheses as possible: http://groups.google.com/group/algogeeks/browse_thread/thread/26ce36ad34dce9dc/e8fb40ab2ba0ecc0 You didn't define duplicate. For (a*b)+c, the parens don't add any information. Should they be removed? The algorithm given in the article above does that. On Dec 10, 6:22 pm, rahul venkat rahul911...@gmail.com wrote: hi everyone, can u suggest an algorithm for finding the duplicate paranthesis in a given expression ? for example , the expression (( a + b ) * (( c + d ))) has a set of duplicate paranthesis. thanks in advance . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: A binary tree question
One queue certainly suffices. Sometimes two are very nice. E.g. if you have the task of printing all nodes at level N and you don't have level numbers in the nodes. With two queues, all the nodes in a queue at a given time are on the same level, so this problem is elegantly solved. WIth one it's possible but messier. You have to track the last node added at each level or something equally messy and error prone. By the same logic, you can do the zig-zag order with a single deque, but it's also messier this way. On Dec 11, 12:23 pm, atul anand atul.87fri...@gmail.com wrote: @Gene : if i am not wrong , level order traversal can be done using only 1 queuewhy 2 queue??? On Sun, Dec 11, 2011 at 9:53 PM, AMAN AGARWAL mnnit.a...@gmail.com wrote: Hi, Suppose we have a binary search tree as 15,12,18,17,21,11,14 then O/P will be 15 12 18 21 17 14 11. so the successor of 15 is 12 the successor of 12 is 18 and so on. I hope now its clear. Regards, Aman. On Sun, Dec 11, 2011 at 6:26 PM, WgpShashank shashank7andr...@gmail.comwrote: @atul zig-zag mean spiral traversal of tree e.g. alternate the level while traversing , if previous traversal is left to right , then next level will be right to left . @aman .quest has little ambiguity its says successor but ebvery nodes can have we can ore-order , inorder ,postorder successor isn't it ?? but i am assuming u r interesting in pre-order succesor so then 1st find the per-order successor of each node then set it , finally traverse it ? correct me if i am wrong ? Thanks Shashank Mani Computer Science BIT Mesra -- 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/-/b51VObaoMZIJ. 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. -- AMAN AGARWAL Success is not final, Failure is not fatal: It is the courage to continue that counts! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Java Collections
You can make them immutable and hide the constructor (make it
private), then provide a factory function
public createPerson(String firstName, String lastName, Date dob)
that internally maintains a hash of all Person's created so far and
never creates the same one twice. If you request the same more than
once, it returns the one already created.
Then collections can make comparisons based entirely on pointer values
rather than string and date comparisons.
On Dec 5, 1:48 am, DT pa7...@gmail.com wrote:
Hi
I have a Person Object that has members: firstname, lastname and DOB
public class Person {
private String firstName;
private String lastName;
private Date dob;
/** Construct a Person given the first name, last name, and birth
date. */
public Person(String firstName, String lastName, Date dob) {
if (firstName == null || lastName == null || dob == null) {
throw new IllegalArgumentException();
}
this.firstName = firstName;
this.lastName = lastName;
this.dob = dob;
}
}
The application uses Person objects in Collections, placing them into
Collection implementations and querying if a Person is in a Collection
using the Collection.contains() method. The application also uses
Person objects as keys in Maps to associate other objects with Persons
and to efficiently look up those objects based on Person.
How can I modify this Person Object so that the lookup is efficient?
Any help??
--
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.
