fungled
BAN USERPretty simple. Bail early if the difference in string length is more than 1. Definitely true if the length difference == 1. Otherwise apply a Hamming distance on the two strings
Time O(n)
Space O(1)
Ruby
def string_difference(a, b)
d = (a.length - b.length).abs
case d
when 0
x = 0
for i in 0..a.length
if a[i] != b[i] then x += 1 end
if x > 1 then return false end
end
return x == 1
when 1
return true
end
false
end
Based on the henrywang's suggested solution I implemented this quickly. Ideally you would want to use a set implementation that can return n distinct objects randomly but efficiently. Here I'm converting the set to an array each time and taking the first two objects. This might be efficient in a Ruby set, not sure.
require 'set'
def knows(i, j)
#
end
def celebrity(set)
while set.length > 1
# ideally use a set that can
# return any two distinct objects
array = set.to_a
a = array[i]
b = array[i + 1]
if knows(a, b)
set.delete(a)
else
set.delete(b)
end
end
set.to_a[0]
end
I struggled with this until I was advised of the trick of two-step, reverse entire sentence, reverse each word. Then it's easy
Complexity O(2.n)
Space O(1)
Ruby code, but C with C-str would be very similar
def reverse(s)
def swap(s, l, r)
for i in 0..(r - l) / 2
s[l + i], s[r - i] = s[r - i], s[l + i]
end
s
end
s = swap(s, 0, s.length - 1)
l = 0
r = 0
loop do
loop do
break if r >= s.length - 1 || s[r] == " "
r += 1
end
s = swap(s, l, r - 1)
l = r + 1
r = l
break if r >= s.length - 1
end
s
end
puts reverse("i wish you a merry christmas")
Found this is a little weird to do. Obviously can be done very efficiently with some extra storage, so this is more of a procedural sort of task.
1. Traverse both nodes up to their roots, at the same time calculate the height of each branch.
2. If the roots are different we know that there's no ancestor, so return NULL
3. Otherwise the approach is to traverse up the tree at varying "rates", in a similar way to how loops in linked lists are found, to see if we encounter an ancestor deeper in the tree. We start by stepping one level at a time, but the step size of the deeper node then increases until we've exhausted all the possibilities.
4. If we didn't find a deeper ancestor then the root is the only shared ancestor.
Time O(h ^ 2)
Space O(1)
Node* closest_common_ancester(Node *n1, Node *n2)
{
int n1Height = 1, n2Height = 1;
Node *n1Root = n1, n2Root = n2;
// find height and roots
while (n1Root.parent) {
n1Root = n1Root.parent;
n1Height++;
}
while (n2Root.parent) {
n2Root = n2Root.parent;
n2Height++;
}
// don't have same roots; bail early
if(n1Root != n2Root) {
return NULL;
}
Node *deepest, *other;
int deepestHeight;
if (n1Height >= n2Height) {
deepest = n1;
other = n2;
deepestHeight = n1Height;
} else {
deepest = n2;
other = n1;
deepestHeight = n2Height;
}
for (int step = 1; step < deepestHeight; ++step) {
Node *bigStep = deepest;
Node *smallStep = other;
while (bigStep.parent && smallStep.parent) {
for (int i = 0; i < step; ++i) {
bigStep = bigStep.parent;
}
smallStep = smallStep.parent;
if(bigStep = smallStep) {
return bigStep;
}
}
}
// root is only ancestor
return n1Root;
}
There's an error in the supplied data: the question specifies that the arrays are each already sorted, so it's a merging operation. The last array isn't sorted.
In any case, this is easy to do if you push the arrays themselves onto the heap, and the heap's comparison operation examines the first object in each array.
1. Create heap with comparison operation that compares an array's first object.
2. To prepare, push each array onto the heap
3. Then while all of the heaps aren't empty
3a. Pop the minimum array
3b. Push its first object into the result
3c. Push the minimum array back onto the heap
Complexity:
Time O(n log k) -> k = number of arrays
Space O(k) -> the number of arrays
Ruby implementation. Cocoa has CFBinaryHeap, but it's a pain to use.
require 'algorithms'
def merge_arrays(arrays)
result = Array.new
heap = Containers::Heap.new { |x, y| (x.first <=> y.first) == -1 }
for array in arrays
heap.push(array)
end
loop do
min_array = heap.pop
result << min_array.shift
if min_array.count > 0
heap.push(min_array)
end
break if heap.empty?
end
result
end
Ruby O(n) solution with O(n) extra space. First attempt overlooked the opportunity to return true as soon as the first anagram is encountered.
require 'set'
def anagrams(array)
set = Set.new
for word in array
sorted = word.chars.sort.join
if set.include? sorted
return true
else
set << sorted
end
end
false
end
puts anagrams(["bag","bat","tab"]) # true
puts anagrams(["gab","bat","laf"]) # false
My method uses two heaps:
1. Max heap to track values less than the median
2. Min heap to track values greater than the median
Inserting n
1. If no median, assign n as median
Else
2a. If n >= median, push onto min heap
2b. If n < median, push onto max heap
3. Balance the heaps. Whichever heap is larger;
3a. Push median onto the *other* heap
3b. Pop from the larger heap, assign as median
Note that the behaviour is undefined if the n is even, but I think that's a given from the task?
Performance:
Insert: O(log n) => requires two heap insert operations, heaps are not "full size". I believe it's satisfactory to state that it's in the order of log n?
Get median: O(1)
Space: O(n)
Written is my slightly amateur Ruby :)
require 'algorithms'
class Median
@min_heap
@max_heap
@median
def initialize
@min_heap = Containers::MinHeap.new
@max_heap = Containers::MaxHeap.new
end
def median
@median
end
def add(number)
if @median.nil?
@median = number
else
if number >= @median
@min_heap.push(number)
elsif number < @median
@max_heap.push(number)
end
if @min_heap.size > @max_heap.size
@max_heap.push(@median)
@median = @min_heap.pop
elsif @max_heap.size > @min_heap.size
@min_heap.push(@median)
@median = @max_heap.pop
end
end
@median
end
alias_method :<<, :add
end
The question is a little vague. It states "given" the tree, therefore I think that methods that take advantage of adding features to an AVL tree wouldn't be acceptable. Also, taking the node (or close to the node) seems a little easy, so I would have to say that the traversal methods are the only acceptable ones. Would like clarification on the question.
- fungled January 15, 2015Think I have a solution here, since there doesn't seem to be a way to do this without two temporary queues. Mine has O(n+h) time complexity, O(w+h) space complexity where h is the height of the tree and w is the maximum width of the tree.
Method:
1. Build a queue of the tree's right side
2. Do a level-order traversal of the tree using another queue
2a. For each object, print the character
2b. If the character matches the head of the queue, print a new line and pop from the queue.
Seems to do the job. Semi pseudo-code (hopefully no typos):
void printTree(BinaryTree *tree) {
Queue rightSide = new Queue();
Node *node = tree.root;
while (root) {
[rightSide push:root.object];
root = root.rightChild;
}
Queue queue = new Queue();
[queue addObject:tree.root];
while (queue.count) {
Node *node = queue.pop;
printf("%s", node.object);
if (node.object == rightSide.head) {
printf("\n");
[rightQueue pop];
}
if (node.leftChild) {
[queue push:node.leftChild];
}
if (node.rightChild) {
[queue push:node.rightChild];
}
}
}
Most of these examples don't cover edge cases where the string contains little or no alphabetical characters:
bool isPalindrome(const char *start, const char *end) {
while (start != end && !isalpha(*start)) {
start++;
}
while (start != end && !isalpha(*end)) {
end--;
}
if (tolower(*start) != tolower(*end)) {
return false;
} else {
if (isalpha(*start) && (start == end || end == start + 1)) {
return true;
} else {
return isPalindrome(start + 1, end - 1);
}
}
}
Test cases:
"A man, a plan, a canal -- Panama!" == 1
"cheeze whiz" = 0
" a " = 1
" " = 0
Took me a while to get a O(log n) solution to this that I was happy with and could write from scratch with confidence.
1. lower bound binary search for the value
2. if no lower bound found return nil
3. otherwise return upper bound binary search value minus lower bound plus 1
You could a general version that does both upper and lower bound but I think it's much clearer and more understandable to have two explicit different versions that are only slightly different:
- fungled February 08, 2015