## cjang

BAN USER
Comments (2)

Reputation 0

Page:

1

Comment hidden because of low score. Click to expand.

Comment hidden because of low score. Click to expand.

0

of 0 vote

Similar approach to Rabin-Karp string search algorithm.

```
// prime number based hash.
#define PRIME 103
uint64_t hash(const char *s, int len)
{
uint64_t h = 0;
for (int i = 0; i < len; ++i) {
h = h*PRIME + s[i];
}
return h;
}
int findAnagram(const char *A, const char *B, char *T)
{
int A_len = strlen(A);
int B_len = strlen(B);
if (A_len > B_len) {
return B_len;
}
// PRIME^(A_len-1)
uint64_t P = 1;
for (int i = 1; i < A_len; ++i) Hk *= PRIME;
// get hash value of input string.
uint64_t H = hash(A, A_len);
uint64_t h = hash(B, A_len);
for (int i = 0; i < (B_len - A_len); ++i) {
if (H == h) {
strncpy(T, B+i, A_len);
std::sort(T, T+A_len);
if (strncmp(A, T, A_len) == 0) {
return i;
}
}
h = h - B[i] * P + B[i+A_len];
}
return B_len;
}
```

Assume that A is already sorted. When a substring of B shows the same hash value with A, the substring is copied to T and compared one-by-one after being sorted. The time complexity will be O(n + c*m*logm) where n is length of B, m is length of A, and c is the number of false positive cases.

- cjang March 28, 2014Page:

1

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Suppose that a graph has been constructed as follows:

- All nodes are ordered by its value.

- Each node has an sorted list of edges.

- An edge belongs to only at a single node with less value among two nodes.

For example, the above graph will be represented by

0: {1, 2}

1: {2, 4}

2: {}

4: {}

Then, the number of triangles can be obtained by counting the number of common nodes between every pair of nodes (n0, n1) where n0 < n1.

The time complexity of this algorithm consists of two parts. First, constructing the graph will be inserting each edge to the proper node. Each insertion of an edge takes O(E/N). (Assume that the number of edges connected for each node is even). So, graph construction takes O(E*log(E/N)).

- cjang March 31, 2014Second, counting the number of triangles takes O(N * E/N * E/N). The outer loop and inner loop iterate N and E/N times, respectively, and countIntersection takes O(E/N).

If we assume dense graph, i.e., E=O(N^2), then the time complexity is O(N^3). If it is sparse, i.e., E=O(N), then O(N).