iammrigank
BAN USERPoint out error cases if you find them. Thanks.
- iammrigank July 27, 2013This is another solution. Iam sorry, it might not be too clear. And im too sleepy to write the comments.
Its a non-recursive solution.
It basically checks for a wildcard(*) and if found, it takes the substring between this wildcard and the next, and finds it in S. If found, it moves on to the next wildcard, else returns false.
#include <stdio.h>
#include <string.h>
#define bool _Bool
#define true 1
#define false 0
bool canTransform(char* s, char* p)
{
char* sub = malloc(strlen(p) * sizeof(p));
while(*p != '\0')
{
if(*p != '*' && *p++ != *s++)
return false;
else
{
int i=1, j=0;
sub[0] = '\0';
while(*(p+i) != '\0' && *(p+i) != '*')
*(sub + j++) = *(p + i++);
sub[j] = '\0';
if(sub[0] == '\0')
return true;
i = 0, j = 0;
int slen = strlen(s), sublen = strlen(sub);
while(i <= slen - sublen)
{
int ch;
for(j=0; (ch = sub[j]) != '\0' && s[i+j] == sub[j]; j++)
;
if(ch == '\0') //match!!
{
s = s + i + j;
p = p + j + 1;
break;
}
i++;
} //while
if(slen == strlen(s))
return false;
} //else
}
return true;
}
int main()
{
char* s = "user@mymail.com";
char* p = "*@*.*";
printf(canTransform(s,p) ? "Yes" : "No");
return 0;
}
i dindn't read "C/C++".
My bad!
A HashMap solution...
public static int findMostFrequent(int ar[]) {
int freq = -1;
int freqNum = ar[0];
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i=0; i<ar.length; i++) {
if(map.get(ar[i]) == null)
map.put(ar[i], 1);
else
map.put(ar[i], map.get(ar[i]) + 1);
}
for(int i : map.keySet()) {
if(map.get(i) > freq) {
freq = map.get(i);
freqNum = i;
}
}
System.out.printf("%d %d", freq, freqNum); //prints frequency and the number.
return freqNum; //returns the most freqent number
}
Undoubtedly, @Ashok's solution is very elegant. But i believe that ^this^ solution is more
general because the numbers just have to be "evenly" spaced for this to work.
x, x+a, x+2a, ... , x + (n-1)*a
for (n-1) elements (missing one)
...can also be found.
Yes, for very large inputs, this will break down. But that ignored, this is more general.
Actually, the problem with merging like the way its done in mergesort, is that, minimum abs. difference pair may come from same array (as @anirudh pointed out)..
- iammrigank July 23, 2013@Anirudh: you are right. thanks for pointing it out. Simple merging will cause that problem.
@Guru: it actually is way different from merge. Thanks.
This is my implementation... (...others posted here are also pretty good)
public static int[] getMinDiff(int a[], int b[]) {
int mindiff = Integer.MAX_VALUE;
/*
* pos1, pos2 : positions of the numbers forming the min-pair
* ...one from each array
*/
int pos1 = 0, pos2 = 0, i=0, j=0;
while(i < a.length && j < b.length) {
if(mindiff > abs(a[i] - b[j])) {
mindiff = abs(a[i] - b[j]);
pos1 = i; pos2 = j;
}
if(a[i] <= b[j])
i++;
else
j++;
}
return new int[] {pos1, pos2, mindiff};
}
We can perform a Breadth First Search, from the node of the tree to any one of the two given nodes (say node1). This can be done in linear O(n) time. Also, we store this path, as an array of node numbers (assuming we number the nodes from 0 (root) to n-1 (last) leaf node), that form the path. (this array is sorted)
We then start moving up (using parents) from the other node (node2), towards the root. Now, while moving, whenever we find a node, that is in the array of node1's path upto root, we stop moving. Now we merge both the paths to get shortest path between them.
This is exactly same to the case of "merge"-ing in merge-sort.
Two sorted arrays can merged in linear time. And while merging, absolute difference between any pair of consecutive elements in the final sorted array is stored (along with the pair), such that it is lesser than previous one.
Hence the final value yields the required result.
Here is one implementation in python:
time: linear
space: constant
- iammrigank August 19, 2013