verma.tech
BAN USERwe can use tries on 5 length patterns and use last node to store no of occurrences.
read files sequentially and pick a pattern and increase the no f occurrence in the trie with one, if the patten is not in tries first make a branch for that pattern.
after we are done with making the trie completely, means processed all the occurences. travel the trie and pik the largest one.
OR we can use a hashtable also, as the no of pages are (less 5 only) there can be 5*5*5*5*5 = 3125 patterns only, read a pattern and check if that is in hashtable, increase the occurnece or store a new pattern.
now the way we can read a pattern, sort the file using user name and inplace sorting (which will maintain the timestamps).
@sudhir it's per-order traversal node will come first then it's child, you algo will not work though you are on right track,
rather than storing child store N, when u find L store it to the last node stored, and make that N to L, you have travel the array log(n) times ; equal to the height of tree, you have to consider all the cases but you can write algo for this .
A
\
B
and
A
/
B
both are two different trees but with same post-order, even with the N L notation.
what about such case ?
for O(n) we have to check every char only once.
we can maintain a stack and after we read every char peek the stack and if the char is same as stack it will be a middle of palindrome . keep track the size of stack.(A)
then change mode and ever new char pop the stack and if the trend breaks means new char is not same as the top in stack, palindrome ended here; A-StackCurrentSize multiple 2
is the length of it, now start pushing chars to stack again....
this need max O(n) extra space for stack and solves in O(n) time.
same we can do for odd palindrome too...
please review if you find some bug in it...
you are right , it's recursion
can you please give algo using dynamic programming,
inorder traversal then check for the total inevery drection of that node.
this may not be best solution.
please update if you find something better
I did one sample implementation ;
package com.ashish.test;
/**
* @author Ashish Verma
*
*/
public class PathSearch {
public static void main(String[] args) {
BstNode root = new BstNode(5);
BstNode a = new BstNode(1);
BstNode b = new BstNode(10);
BstNode c = new BstNode(0);
BstNode d = new BstNode(2);
BstNode e = new BstNode(6);
BstNode f = new BstNode(11);
root.left = a;
root.right = b;
a.parent = root;
b.parent = root;
a.left = c;
a.right = d;
c.parent = a;
d.parent = a;
b.left = e;
b.right = f;
e.parent = b;
f.parent = b;
searchPath(root, 16);
}
public static void searchPath(BstNode node, int total) {
if (node == null)
return;
if (node.left != null)
searchPath(node.left, total);
searchCurrent(node, null, total,0);
if (node.right != null)
searchPath(node.right, total);
}
public static boolean searchCurrent(BstNode node, BstNode last, int total,
int tillnow) {
if (node.data+tillnow == total) {
System.out.println("found at"+node.data);
return true;
}
if (tillnow > total) {
return false;
}
boolean b = false;
if (node.left != null && node.left != last) {
b = searchCurrent(node.left, node, total, tillnow+node.data);
if (b)
System.out.println(node.data);
}
if (node.right != null && node.right != last) {
b = searchCurrent(node.right, node, total, tillnow+node.data);
if (b)
System.out.println(node.data);
}
if (node.parent != null && node.parent != last) {
b = searchCurrent(node.parent, node, total, tillnow+node.data);
if (b)
System.out.println(node.data);
}
return b;
}
}
class BstNode {
public BstNode(int i) {
this.data = i;
}
BstNode parent = null;
BstNode left = null;
BstNode right = null;
int data;
}
if you find some bug please do update
- verma.tech December 30, 2010can u explain this a little more
- verma.tech December 29, 2010I tested this for variety of inputs and seems to be working fine.
input int[] a = { 5, 5, 10, 2, 3 }; is not sorted and it works for that and returns 4
also, we need not generate all combinations, if we can check mid-way that whether the current combi is valid one or not.
please update if u find some bug in above.
public static void main(String[] args) {
int[] a = { 5, 5, 10, 2, 3 };
// int[] a={1, 2, 3, 4, 5};
int i = find15Combi(a, 0, 15);
System.out.println(i);
}
private static int find15Combi(int[] a, int start, int toSearch) {
int i = 0;
for (; start < a.length; start++) {
if (a[start] == toSearch) {
i++;
} else if (a[start] < toSearch)
i = i + find15Combi(a, start + 1, toSearch - a[start]);
}
return i;
}
where will the root go?
anyways, may be we can maintain 3 arrays and while BFS, fill those arrays and after BFS print those.
public static void main(String[] args) {
int[] a = { 5, 5, 10, 2, 3 };
// int[] a={1, 2, 3, 4, 5};
int i = find15Combi(a, 0, 15);
System.out.println(i);
}
private static int find15Combi(int[] a, int start, int toSearch) {
int i = 0;
for (; start < a.length; start++) {
if (a[start] == toSearch) {
i++;
} else if (a[start] < toSearch)
i = i + find15Combi(a, start + 1, toSearch - a[start]);
}
return i;
}
I am suggesting for the minimum case only
- verma.tech December 22, 2010if we take example of m*n grid, for minimum total tiles we need to travel is m+n only.
and so steps
so 2pow(m+n)
can be the possible way.
please suggest if I am wrong.
RepEvieBBlack, AT&T Customer service email at ASAPInfosystemsPvtLtd
I am Evie from Santa Fe Springs USA, I am working as a manager in a worldwide company. I also ...
"Also, consider an example of a user accessing the website in following sequence : ABCDAEBC So that means the patterns ABCDA, BCDAE, CDAEB, DAEBC are the patterns that will be incremented right ?"
- verma.tech February 12, 2011yaa we need to increment for all the valid pattern.
space: we need to store trie ds in memory which is of content space i.e. more no of files will just increase the no of occurences. so constant space.
running time: O(nlogn) for sorting, if 30 files are there for all the days in months , it is O(30nlogn)= O(nlogn) only.
for reading patterns we need to read every file once only, so it is O(m) if m is no of lines in a file on an average.
so final is O(m) + O(nlogn),
this is as far as i understand, update if u find something wrong/unclear