Re: [algogeeks] Hash Table ( A hashtable class in c++)
#includecstdio
#includemap
#includevector
#includecstdlib
using namespace std;
// It is not advisable to list all elements in this hash table.
#define HASH_SIZE 51439
class HashTable
{
public:
vector maplong long,int table;
HashTable()
{
table = vector maplong long,int (HASH_SIZE);
}
int hashF(long long key)
{
if( key 0)
{
key = key + HASH_SIZE*( abs(key)/HASH_SIZE + 1);
}
return key%HASH_SIZE;
}
pair maplong long,int::iterator, bool insert(long long key, int
value)
{
int index = hashF(key);
return table[index].insert(pairlong long,int(key,value));
}
int getCount(long long key)
{
int index = hashF(key);
int count = table[index].count(key);
return count;
}
int getValue(long long key)
{
int index = hashF(key);
return table[index][key];
}
};
On Sat, Sep 3, 2011 at 10:44 AM, Rahul Verma rahulverma@gmail.comwrote:
I am facing some difficulty in the implementation of Hash Table. Anyone can
please share the good resources for Hash Table?
--
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/-/DmcDxyNXfwEJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: remove duplicate words in a string
you can write a python program to do that easily. program starts here : c=str.split(raw_input()) d=[] for x in c: d[x]=0 print list(d) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 the distance between two permutations of a string of length N
For the sake of simplicity assume that one permutation is identity permutation and the other one is pi. Write pi as product of disjoint cycles, which can be done in O(n) time. If the number of disjoint cycles is k, then the distance between identity permutation and pi is (n - k). Proof of correctness is by induction on number of cycles. thx aj --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Median of 2 combined array X[1...n] and Y[1...n] sorted in 0(lgn)
How about finding the median of (X + Y) in subquadratic time.
X + Y = {z | z = xi + yj for some i and j}.
I could only reduce the space complexity from O(n^2) to O(n) but time
complexity still
remains O(n^2).
thx
Aj
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Median of 2 combined array X[1...n] and Y[1...n] sorted in 0(lgn)
well the set (X + Y) will have O(n^2) elements, where X and Y have n
elements.
As an example
X = {1, 2}
Y = {3, 5}
X + Y = {1 + 3, 1 + 5, 2 + 3, 2 + 5} = {4, 5, 6, 7}
Now the problem is to find the median of X + Y in subquadratic time.
thx
aj
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: A problem related to palindromes
hi daizi, I was expecting a solution that does not use suffix trees. Using suffix trees the problem can be solved easily, but I was just wondering if it is mandatory to use complex data structures like suffix trees to solve this problem. thx aj --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: A problem related to palindromes
linear worst case 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] A problem related to palindromes
Given a binary string x of length n, find the longest prefix of x in linear time which is a palindrome. thx aj --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: How to find, efficiently, the maximum sum of atleast L consecutive integers from a sequence of N integers.
geek4u, I agree with you that the original problem description is not very clear, but I guess by sequence of consecutive integers he means a substring of the sequence (not just a sequence). If the problem is to find a subsequence (without any restriction on the length of the subsequence) then your solution is excellent with O(n) time and O(1) space complexity. thx Aj --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: How to find, efficiently, the maximum sum of atleast L consecutive integers from a sequence of N integers.
Consider a specific case of this problem where L = 1, which corresponds
to the problem of
finding a substring with maximum sum. This problem can be easily solved
using dynamic programming in O(n) as shown below:
construct an array A[1,2...n], such that A[i] denotes the largest sum
of a substring with starting point a_i.
A[i] = a_i if A[i + 1] is negative
= a_i + A[i + 1] otherwise.
Now come back to the original problem and in a similar way construct
the array B[1,2...n], such that B[i] denotes the largest sum of a
substring starting at a_i and has length at least L. Note that B can be
constructed using the recurrence
B[i] = a_i + a_{i+1} +.a_{i + L - 1} + A[i + L -1];
once we have all the B[i]'s, choosing maximum of them should not be a
difficult task.
time complexity = O(n) which is the best that can be achieved
space complexity = O(n)
hope it helps
Aj
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: determine whether a matrix is rearrangeable
SPX2 wrote: what complexity aj ? O(ne) where e is the n is the number of rows and e is the number of 1's in the matrix. worst case O(n^3). --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: determine whether a matrix is rearrangeable
the matrix 1 1 1 1 1 1 1 1 1 has rank 1, but is still rearrangable, so it seems linear dependence has not much to do with the problem. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] scheduling problem
Hello,
Suppose we want to add n numbers using multi processors. Each
of these numbers arrive at different time. The goal is to find a
scheduling such that the final sum can be computed as early as possible
(assume that each addition takes unit time). As can be verified easily
that the following greedy algorithm solves this problem optimally
Add (L = {t1, t2,, tn}) // t1, t2, ...tn are the arrival
times of inputs
{
if (L has only one element)
return;
choose the two smallest value in L (say x and y), remove the two
values from
L and, insert 1 + max(x, y) in L. Call this new set as L'
Add (L' );
}
Now suppose that we have an advanced adder which takes less than unit
time to perform an
addition (Also it takes different amount of time to add two different
pair of numbers). For the simplicity we can also assume that we use
this adder only to add the base elements (i.e.,
all the intermediate sum values will be added using the normal adder
having delay of unit
time).
The nC2 (n choose 2) values which represent the delay of the advanced
adder on the pairs of
base elements are given as input. In this case how can we find the
optimal scheduling, or this
small modification moves the problem from the class P to the class of
NP-complete.
thanks in advance
Aj
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
