swapsmagic
BAN USERLooks good but it won't handle scenario when a single file has duplicate names in it. I think in that case we need to split hashes and add file1 entry in hash2 and file2 entry in hash1. For file1 entry look into hash1 and for file2 entry look into hash2.
- swapsmagic April 27, 2012I think the time complexity is going to be O(n^n) in worst case. Any thoughts on it?
Can we improve this?
Algo:
Find left closest and right closest node of the given node in tree by traversing the tree.
At end return whichever of right and left is closer to the node
public Node find_closest(Node root, Node nodeToFound, Node left, Node right) {
if(root == NULL){
if(left != NULL && right != NULL){
if(abs(nodeToFound, left) < abs(nodeToFound, right)){
return left;
} else {
return right;
}
}
if(left == NULL){
return right;
}
return left;
}
if(nodeToFound.compare(root) < 0){
return find_closest(root->left, nodeToFound, left, root);
} else {
return find_closest(root->right, nodeToFound, root, right);
}
}
public static int[] sum(int[] a, int[] b){
int len1 = a.length;
int len2 = b.length;
int len = (len1 > len2) ? len1: len2;
len = len+1;
int[] result = new int[len];
int i=len1-1;
int j=len2-1;
int k=0;
int carry = 0;
while(i >= 0 && j >= 0){
int sum = a[i] + b[j] + carry;
carry = sum / 10;
result[k++] = sum % 10;
i--;
j--;
}
while(i >= 0){
int sum = a[i] + carry;
carry = sum / 10;
sum = sum % 10;
result[k++] = sum;
i--;
}
while(j >= 0){
int sum = b[j] + carry;
carry = sum / 10;
sum = sum % 10;
result[k++] = sum;
j--;
}
if(carry > 0)
result[k++] = carry;
//reverse
int[] finalResult = new int[k];
i =0;
k--;
while(k>=0){
finalResult[i++] = result[k--];
}
return finalResult;
}
can you give more detail as how Trie can be used here? Any pointers?
- swapsmagic March 28, 2012can you get more detail as how Trie can be used here? Any pointers?
- swapsmagic March 28, 2012I got one of the result as: [[9], [5], [7, 4, 7]]
Is this a valid result? If yes, i think i misunderstood the question. Can you explain why it's a valid seq?
Here is the recursive brute force solution:
public class PatternSearch {
public static boolean patternFind(char[][] array, String pattern, int rowLen, int colLen, int[][] matrix, int prevMatchIndex_i, int prevMatchIndex_j){
boolean result = false;
//Nothing to match
if(pattern == null || pattern.length() == 0){
return true;
}
int i = prevMatchIndex_i;
int j = prevMatchIndex_j;
char charToMatch = pattern.charAt(0);
if(i > 0) {
//check upper character
if(matrix[i-1][j] == 0 && array[i-1][j] == charToMatch){
matrix[i-1][j] = 1;
result = patternFind(array, pattern.substring(1), rowLen, colLen, matrix, i-1, j);
if(result == true){
return result;
}
matrix[i-1][j] = 0;
}
if(j > 0){
//Check left upper corner
if(matrix[i-1][j-1] == 0 && array[i-1][j-1] == charToMatch){
matrix[i-1][j-1] = 1;
result = patternFind(array, pattern.substring(1), rowLen, colLen, matrix, i-1, j-1);
if(result == true){
return result;
}
matrix[i-1][j-1] = 0;
}
}
}
if(j > 0){
//check left character
if(matrix[i][j-1] == 0 && array[i][j-1] == charToMatch){
matrix[i][j-1] = 1;
result = patternFind(array, pattern.substring(1), rowLen, colLen, matrix, i, j-1);
if(result == true){
return result;
}
matrix[i][j-1] = 0;
}
}
if(i+1 < rowLen) {
//check bottom character
if(matrix[i+1][j] == 0 && array[i+1][j] == charToMatch){
matrix[i+1][j] = 1;
result = patternFind(array, pattern.substring(1), rowLen, colLen, matrix, i+1, j);
if(result == true){
return result;
}
matrix[i+1][j] = 0;
}
if(j > 0) {
//check left bottom corner
if(matrix[i+1][j-1] == 0 && array[i+1][j-1] == charToMatch){
matrix[i+1][j-1] = 1;
result = patternFind(array, pattern.substring(1), rowLen, colLen, matrix, i+1, j-1);
if(result == true){
return result;
}
matrix[i+1][j-1] = 0;
}
}
}
if(j+1 < colLen) {
if(i > 0){
//check right upper corner
if(matrix[i-1][j+1] == 0 && array[i-1][j+1] == charToMatch){
matrix[i-1][j+1] = 1;
result = patternFind(array, pattern.substring(1), rowLen, colLen, matrix, i-1, j+1);
if(result == true){
return result;
}
matrix[i-1][j+1] = 0;
}
}
//check right character
if(matrix[i][j+1] == 0 && array[i][j+1] == charToMatch){
matrix[i][j+1] = 1;
result = patternFind(array, pattern.substring(1), rowLen, colLen, matrix, i, j+1);
if(result == true){
return result;
}
matrix[i][j+1] = 0;
}
if(i+1 < rowLen) {
//check right bottom corner
if(matrix[i+1][j+1] == 0 && array[i+1][j+1] == charToMatch){
matrix[i+1][j+1] = 1;
result = patternFind(array, pattern.substring(1), rowLen, colLen, matrix, i+1, j+1);
if(result == true){
return result;
}
matrix[i+1][j+1] = 0;
}
}
}
return result;
}
public static void main(String[] argv){
char[][] array = { {'A', 'C', 'P', 'R', 'C'},
{'X', 'S', 'O', 'P', 'C'},
{'V', 'O', 'V', 'N', 'I'},
{'W', 'G', 'F', 'M', 'N'},
{'Q', 'A', 'T', 'I', 'T'} };
String pattern = "MICROSOFT";
char chToMatch = pattern.charAt(0);
int rowLen = 5;
int colLen = 5;
int[][] matrix = new int[rowLen][colLen];
boolean result = false;
for(int i=0; i<rowLen; i++){
for(int j=0; j<colLen; j++){
if(array[i][j] == chToMatch){
matrix[i][j] = 1;
result = patternFind(array, pattern.substring(1), rowLen, colLen, matrix, i, j);
if(result == true){
break;
}
matrix[i][j] = 0;
}
}
if(result == true){
break;
}
}
System.out.println("Pattern FOUND: " + result);
}
}
I feel we can't solve it by transforming it to maximum subarray problem. Can you elaborate more on how you can solve it using this approach?
- swapsmagic February 07, 2012----------------Recursive Solution----------------------
recFindSubSets("", "abc");
public static ArrayList<String> recFindSubSets(String str1, String str2){
ArrayList<String> subSets = new ArrayList<String>();
if(str2.length() == 0){
subSets.add(str1);
return subSets;
}
ArrayList<String> subSets1 = recFindSubSets(str1 + str2.substring(0, 1), str2.substring(1, str2.length()));
ArrayList<String> subSets2 = recFindSubSets(str1, str2.substring(1, str2.length()));
subSets.addAll(subSets1);
subSets.addAll(subSets2);
return subSets;
}
------------Non Recursive Solution-----------------
nonRecFindSubSets("abc");
public static ArrayList<String> nonRecFindSubSets(String str){
ArrayList<String> subSets = new ArrayList<String>();
int len = str.length();
int totalSets = (int) Math.pow(2, len) - 1;
StringBuilder str1 = new StringBuilder();
for(int i=totalSets; i>=0; i--){
str1.delete(0, str1.length());
int bitmask = (int) Math.pow(2, len-1);
for(int j=0;j<len; j++) {
if((i & bitmask) > 0){
str1.append(str.charAt(j));
}
bitmask = bitmask >> 1;
}
subSets.add(str1.toString());
}
return subSets;
}
Replisapyara, abc at 247quickbookshelp
I am motivated and organized professional with proven years of experience in mail services and industry having vast experience as ...
Repabbyherza, Animator at ASAPInfosystemsPvtLtd
I am Viola .I am A public relations consultant, a communications specialist who works as an intermediary between the public ...
Repdebbiewilsond, Software Trainee at Electronic Arts
I am Debbie from Nashua in Us.I Done my study from Us university .Now I am working in Science ...
Repmelissattaylor, AT&T Customer service email at Bankbazaar
Je suis membre participant du chapitre de Virginie de l'Association nationale du travail social. J'aime lire et écrire ...
This can be solved using Min Heap data structure.
- swapsmagic April 22, 2015- Keep a min heap of size K.
- Add first K of the 2 billion records in the heap. O(K log K)
- Iterate through rest of the records and for each record
- If the record is greater than the heap top element (which is the smallest of all the heap elements) , pop the top element out of the min heap and insert the new element. O (log K)
- At the end the K elements remain in the heap are the top K elements.
Time Complexity: O (K log K) + N * O(log K) = O (K log K) + O (log K) as N is constant here.
Space Complexity: O(K)