tangqiyuan
BAN USERU r right. A small fix is needed. After getting the set with the same sum as array 2, we need to compare the elements in the set with those in array 2, by using hash table. Put all elements in array 2 in hash table, then map all elements in the set to hash table entries; if there is a match, decrease the counter(for duplicates), or delete the node if the counter becomes 0. At last, the table should be empty.
- tangqiyuan May 13, 2010It's not good to use a method only applied for this question. e.g. what if the interviewer want you to swap every 3 adjacent nodes instead of 2? like a->b->c->d->e->f => c->b->a->f->e->d ? I think use recursive function could solve this problem. Can someone give the code?
- tangqiyuan May 13, 2010First, subtract all the numbers in the array from the key, so we get a new array; Second, use hash function to map each number in the new array to an entry in hash table; Third, try to map each number in the original array to an entry in hash table, if the entry already contains a node with the same value, then we found a pair.
- tangqiyuan May 10, 2010Mark all nodes "unexplored" at first. Then use depth first search, mark the nodes we visited as "explored". Whenever we meet a node which has already been marked as "explored", a cycle is detected.
- tangqiyuan May 10, 2010
@a.p: May I ask how to convert it to RMQ? since you can't identify any node of tree by its value, we can't create a cartesian tree.
- tangqiyuan May 13, 2010