Lost in Compilation

This is a slightly trickier version of The Missing Duplicate Number . Instead of one single missing number, we have 2. Problem : Given an array of Integers. Each number is repeated even number of times. Except 2 numbers which occur odd number of times. Find the two numbers Ex. [1,2,3,1,2,3,4,5] The Output should be 4,5. The naive solution is similar to the previous solution. Use a hash table to keep track of the frequencies and find the elements that occur an odd number of times. The algorithm has a Time and Space Complexity of O(n). Say those two required numbers are a and b If you remember the previous post, we used the XOR over all the elements to find the required element. If we do the same here, we get a value xor which is actually a ^ b. So how can we use this? We know that a and b are different, so their xor is not zero. Infact their XOR value has its bit set for all its dissimilar bits in both a and b. (eg.  1101 ^ 0110 = 0011). It's important to notice ...

Word ladder is a word game invented by Lewis Carroll. A word ladder puzzle begins with two words, and to solve the puzzle one must find a chain of other words to link the two, in which two adjacent words (that is, words in successive steps) differ by one letter. Eg. SPORT <-> SHORT Source: Wikipedia If you've followed my previous Dijkstra's Shortest Path Algorithm Tutorial, you'll be able to solve this challenge with minimum effort. Essentially, we create a graph where each word is a vertex and there exists an edge if two words differ by a single character. To find the word ladder is basically running any shortest path algorithm. You could also use a Breadth First Search. Some important observations The length of the source and destination words must be the same for a path to exist. The path from source to destination  can only contain words of the same length. So we can prune off the rest of the dictionary. The graph is undirected. Here's my ...

Problem : Given an array A of integers, maximize A[j] - A[i] such that 0 <= i < j < len(A). A very interesting problem, as always lets begin with a naive solution. Clearly, the solution has quadratic time complexity. Now, step back and look at the solution. Essentially what we are doing is iterating over the array, splitting the array into two parts. From the first part we always pick the lowest element, (clearly since that will give us the maximum difference). Since we already know the minimum element we encountered, we simply need to check if the difference with the new element improves upon the earlier solution. This idea can be implemented in Linear Time. Here's how. Update : So I just discovered this problem is called the Single Sell Profit problem. It's been discussed quite thoroughly by templatetypedef here . It includes 4 solutions (including this one).

Here's  Part 1  and  Part 2 And now for the third and final part of the tutorial. We'll be implementing the actual algorithm here. But before we get started, let's go over some theory. Dijkstra's Shortest Path Algorithm, (V - Number of Vertices, E - Number of Edges) Applies to both Directed graph and Undirected graphs. Greedy Algorithm. Always picks the local minimum to extend it's solution. Uses Dynamic Programming. Stores solutions from source to every other vertex on the shortest path to the destination. Edges cannot be negative. Original Implementation by Dijkstra was O(V 2 ) since it did not use a Minimum Priority Queue. Tarjan & Fredman introduced the modern version of the algorithm using a Fibonacci Heap to pick the vertex closest to the source. The Complexity thus became O(E + V logV).  Using a Binary Heap instead of a Fibonacci Heap increases the complexity to  O( (E+V) log V). Variations. There are two variants of the algorithm, t...

This is an experimental post. I'm trying out Scarky.com . Seems promising, but we can't an create account and manage challenges. Apparently, I have to save this secret URL if I want to edit a challenge. Very inconvenient! :( I've created a simple programming challenge for my readers. If it's a hit, expect more.

Problem : A Sorted Array is rotated by a certain number of elements, find the point of rotation.   Example, For [3,4,5,1,2] , since [1,2] was rotated to the back, point of rotation is 3. And of course, for a sorted array the point of rotation can be assumed 0. Naive Solution: This is pretty obvious Linear Solution, simply scan the array for a pair a[i] > a[i+1]. If we find it, i is the point of rotation,   if there's no such pair, then i = 0 clearly. Time Complexity : O(n) Binary Search Variant:  Using a variation of Binary Search method, we can find the rotation point in O(logn) steps. At each iteration we compare the middle element of the list with the right (or left) element. For a rotated array, arr[left] > arr[right] , so every time we pick a middle element, the point of rotation can lie on either side of mid . If arr[mid] > arr[right] , it means the rotation point is in the second half of the array. So we move left to mid...

For Part 2 of the series, we'll be developing a Priority Queue implemented using a Heap  . Continuing from Part 1 , we'll be using Python for the implementation. Fortunately, Python has a PriorityQueue class in the `queue` module. It's more than enough for our purposes, but the Queue module was designed thread safe, so there is a small overhead that comes with it. The Priority Queue is a Minimum Priority Queue by default, it takes in tuples which are compared together to determine their position in the queue. For those unfamiliar with tuple comparison in Python, it works something like this. >>> (1,2) < (3,4) True >>> (1,2) < (1,3) True >>> (1,2) < (1,1) False >>> (1,2) < (1,2,3) True >>> (1,2,3,4) < (1,2,3) False The first non equal element  of the both tuples determine the output of the comparison operation. So say you have a bunch of Tasks Ti with Priorities Pi, then we push (Pi, Ti) into the...