Lost in Compilation

Given k-sorted array, find the minimum interval such that there is at least one element from each array within the interval. Eg. [1,10,14],[2,5,10],[3,40,50]. Output : 1-3 To solve this problem, we perform a k-way merge as described here . At each point of 'popping' an element from an array. We keep track of the minimum and maximum head element (the first element) from all the k-lists. The minimum and maximum will obviously contain the rest of the header elements of the k-arrays. As we keep doing this, we find the smallest interval (max - min). That will be our solution. Here's a pictorial working of the algorithm. And here's the Python code. Time Complexity : O(nlogk)

Problem - Given k-sorted lists, merge them into a single sorted list. A daft way of doing this would be to copy all the list into a new array and sorting the new array. ie O(n log(n)) The naive method would be to simply perform k-way merge similar to the auxiliary method in Merge Sort. But that is reduces the problem to a minimum selection from a list of k-elements. The Complexity of this algorithm is an abysmal O(nk). Here's how it looks in Python. We maintain an additional array called Index[1..k] to maintain the head of each list. We improve upon this by optimizing the minimum selection process by using a familiar data structure, the Heap! Using a MinHeap, we extract the minimum element from a list and then push the next element from the same list into the heap, until all the list get exhausted. This reduces the Time complexity to O(nlogk) since for each element we perform O(logk) operations on the heap. An important implementation detail is we need to keep track

Problem - Given an integer array A[1..n], find an instance of i,j,k where 0 < i < j < k <= n and A[i] < A[j] < A[k]. Let's start with the obvious solution, bruteforce every three element combination until we find a solution. Let's try to reduce this by searching left and right for each element, we search left for an element smaller than the current one, towards the right an element greater than the current one. When we find an element that has both such elements, we found the solution. The complexity of this solution is O(n^2). To reduce this even further, One can simply apply the longest increasing subsequence algorithm and break when we get an LIS of length 3. But the best algorithm that can find an LIS is O(nlogn) with O( n ) space . An O(nlogn) algorithm seems like an overkill! Can this be done in linear time? The Algorithm: We iterate over the array and keep track of two things. The minimum value iterated over (min) The minimum increa

Problem - Given 4 arrays A,B,C,D. Find out if there exists an instance where A[i] + B[j] + C[k] + D[l] = 0 Like the Find the Triple problem, we're going to develop 4 algorithms to solve this. Starting with the naive O(n^4) solution. Then we proceed to eliminate the inner-most loop with a Binary Search, reducing the complexity to O(n^3 logn) Now, we replace the last 2 loops with the left-right traversal we did in the previous 3 posts. Now the complexity is O(n^3). Finally, we reduce the complexity to O(n^2 logn) at the cost of O(n^2) Space Complexity. We store every combination of A[i] + B[j] and store it in AB[]. Similarly we make CD[] out of C[i] + D[j]. So, AB = A x B CD = C x D We then sort AB and CD (which costs O(n^2 log(n^2)) ~ O(n^2 logn) ) and then run a left-right linear Algorithm on AB and CD. (Note : Their size is of the order O(n^2)) So the overall complexity is due to sorting the large array of size n^2. which is O(n^2 logn).

Problem : Given 3 Integer Arrays A,B,C. Find out if an instance exists where A[i] + B[j] + C[k] == 0. Very deceptive question but very similar to the  3SUM  Problem. The Naive solution is O(n^3). If you're a little clever, you can do a O(n^2 logn). At this point, you might give up assuming that this is pretty efficient. But then there is also a O(n^2) solution as well! Let's go from worst to best. The Naive solution is trivial. Try every combination until we hit a solution, if we don't there is no solution. So let's try to speed things up a bit, since the solution is already O(n^3), I think we can afford to sort any of the  arrays since nlogn = o(n^3). Therefore, we cleverly sort the Array C. Now in the third loop we replace the linear scan with a binary search to find (-A[i]-B[j]). The complexity is now reduced to O(n^2 logn) At this point, you've leveled up. The next algorithm might not be immediately apparent but works. In fact the method is simila

Problem - Given an Array of integers, A. Find out if there exists a triple (i,j,k) such that A[i] + A[j] + A[k] == 0. The 3SUM  problem is very similar to the 2SUM  problem in many aspects. The solutions I'll be discussing are also very similar. I highly recommend you read the previous post first, since I'll explain only the differences in the algorithm from the previous post. Let's begin, We start with the naive algorithm. An O(n^3) solution with 3 nested loops each checking if the sum of the triple is 0. Since O(n^3) is the higher order term, we can sort the array in O(nlogn) and add a guard at the nested loops to prune of parts of the arrays. But the complexity still remains O(n^3). The code is pretty simple and similar to the naive algorithm of 2SUM. Moving on, we'll do the same thing we did in 2SUM, replace the inner-most linear search with a binary search. The Complexity now drops to O(n^2 logn) Now, the hash table method, this is strictly not

Problem : Given an array with distinct elements. Find out if there exists an instance where sum of two distinct elements is equal to a given constant K. Say, A = [1,2,3,4], K = 7. Output should be 3,4 The naive solution for this problem is pretty trivial. Brute force every pair-sum and check if the sum is K. You could be a little smart about this. You initially sort the array O(nlogn) and iterate the array pairwise and quit when the sum exceeds K, you can quit the inner loop since the array is sorted the sum can only increase. For the rest of the article, I'll be assuming K = 0, this doesn't affect the solutions in any way and it's trivial to introduce a new variable into the code without major changes. Here's the code, should be easy to follow... I'll be using Java today. Now that the naive solution is out of the way, let's try and do some clever stuff. So notice we can afford to sort the array since the brute solution was already O(n^2) (which

As promised, this is the follow up to the first posted earlier that there was a more efficient algorithm for finding the longest increasing subsequence, better than the O(n^2) DP solution we came up with. It's not easy to understand, but once you get what the variables mean, it seems pretty straight forward. We'll be implementing another DP solution, similar to the previous one, except with an additional data structure that'll reduce the overall complexity to O(nlogn). The wikipedia seems no help. The explanation is contrived and not easy to visualize. Hope this post will clear a lot of doubts. So we need 3 arrays for solving an instance of LIS. M[i] - where M[i] is the minimum ending element of a increasing subsequence of length i. This is the key part of the new algorithm. Unlike the earlier solution where we kept the longest length discovered at index i , we store an Array which holds the minimum value of a subsequence of length i. I[i] - where M[i] = A[I[i]] si

Problem: Given an array of positive non-zero integers. Find out the minimum hops required to traverse the array, if the value at an index denotes the maximum length you can hop from that index. To perform a brute force solution, we can use a depth first search with pruning. This usually explodes with arrays of size greater than 50. But never the less, it's important to understand how it works. Following our dismal performance using DFS, we move on to the big guns, Dynamic Programming. We define minHop[i]   as the minimum hops you need from index i to reach the end of the array. Therefore, minHop[i] = 1 { if arr[i] + i > len(arr) } needs just one hop, trivial. minHop[i] = 1 + min ( minHop[i+1 : i+arr[i]] ) { the minimum hop from my range which will reach the end of the array } We start with i = len(arr) - 1 and count down to i  = 0 . At which point minHop[0] will be the minimum hops required to reach the end of the array from index = 0. So here we have an

Problem : In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn't know anyone in the party.  We can only ask questions like “does A know B? Find the celebrity in minimum number of questions. This is a very interesting problem. The answer, ie the least number of questions required, changes based on what's given. Are we guaranteed there's one celebrity in the party? Does every non-celeb know every other non-celeb? ( not very ideal, but under a best case scenario. ) Once again, the rules There is at most one celebrity at the party Everyone knows the celebrity. The celebrity knows no one. We can only ask the question "Does A know B?" When we ask the question, we can get a "yes" or "no". Each conveying information about both the participants in the question. Let's see those outcomes... If the Answer is "Yes", we know A is definitely not a celebrit

Problem - Given an array of integers. Find the longest increasing subsequence in the array. Eg. [42, 91, 46, 73, 75, 91, 95]. The LIS for this array is 6 which is [42,46,73,75,91,95]. Note: Subsequence does not require the elements to be contiguous As always, we begin with our naive solution which is a DFS/Bruteforce search trying every possible combination until we get the longest sequence. This is simply exhaustive and will explode on bigger arrays. Time Complexity : O(2^n) ~ Exponential Now, If you notice we repeatedly try a prefix subsequence repeatedly. This tells us, the problem is a good candidate for a dynamic programming algorithm. We define lis[0...L] , where L is the length of the array. We define lis[i] as the length of longest increasing subsequence that ends at i.  lis[0] = 1 { trivial since, the longest increasing sequence that ends at the start of the array contains just the first element, also true for the arr[i] where arr[i] is the smaller than preced

Problem - Write an algorithm capable of rotating a matrix, in-place without any auxiliary storage. I don't have an elaborate thought process to develop this algorithm. It's a few rules you ought to remember to implement rotations in the matrix. To implement these rules, you need some helper functions which are quite simple really. You need to be able to transpose a matrix, reverse a row, reverse a column. That's it. The rest is just a combination of these 3 functions. Python is awesome, isn't it? Note : These functions create copies of the matrix, we can design algorithms that modify the original matrix with ease for square matrices. For non-square matrices, we have to create new matrices. Okay, let's get to the rotations. So we need to perform three kinds of rotations. 90,180,270. 1) Rotation by 90/-270  degrees Transpose the Matrix Reverse each row 2) Rotation by 180/-180 degrees There are two methods: First Method, is clearly obviou

Problem : Given a set of integers A, find out if there is a subset of A which add up to a particular integer K. Formally called the Subset Sum Problem , we are given an NP-Complete problem. To solve this, we have to exhaustively search every subset and verify if they add up to an integer K. Let's begin with a Brute force DFS search, we're going to construct subsets incrementally until the sum exceeds K. The elements are assumed sorted in the increasing order. So we perform a DFS trying to perform every combination of the elements in the set. The recursive function either will include an element in the sum or exclude it. The guard prunes off DFS paths that exceed the sum required. There is an efficient method for this, using Dynamic Programming. Essentially, we start with a single element, add the next element together to get the new sums possible. These new sums will be the input for the next iteration. I'll explain with an example, say we have {a,b,c} You

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, there

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. If arr[mid] <= arr[r

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

Problem : Implement a stack with push() , pop() and a min() (which returns the minimum element in the stack). All operations should be O(1). Another popular question, I've searched around a lot came across many answers, but only one had completeness. It's important to note that with the stack you don't have random access to the contents of the stack when implementing your solution. The solution I'm describing involves using 2 stacks, one is to store the data elements themselves ( mainstack ) and the other to store minimum values, which i'll refer to as minstack. Now we can have 2 parallel stacks where we push and pop on the minstack along with the mainstack, keeping track of the minimum value of course. But we can optimize this further. We only need to push values on the minimum stack only when you push a value on the main stack that is less than or equal to the current top element of the minstack. Here's are the two stacks after pushing 67,44,20,77,99,1

Problem : Given an array of integers in strictly increasing order (no duplicates), find the first number not present in the array. Eg. [11,12,13,25,37,49] The output should be 14. Seems simple enough? Let's go with our intuition first and use a naive algorithm. Time Complexity : O(n) Notice, if we don't have any gaps, say [11,12,13,14,15] then the upper bound of the array is equal to the highest - lowest element in the array. (4 = 15 - 11). So we can check if there is a gap simply by checking if high - low == arr[high] - arr[low] Let's be clever about this fact and solve this in O(logn). We use our trusty Binary Search but instead of "finding" an element we're going to partition the array into two halves. We first check if the First Half is "complete", if it is, we find the gap in the second half else we check the first half. We keep doing this till we have just 2 elements left (which is trivial to solve). Here's a recursive algorith

This will be a 3 Part series of posts where I will be implementing the Dijkstra's Shortest Path algorithm in Python. The three parts will be 1) Representing the Graph 2) Priority Queue 3) The Algorithm To represent a graph we'll be using an  Adjacency List . Another alternative is using an Adjacency Matrix, but for a sparse graph an Adjacency List is more efficient. Adjacency List An Adjacency List is usually represented as a HashTable (or an Array) where an entry at `u` contains a Linked List. The Linked List contains `v` and optionally another parameter `w`. Here `u` and `v` are node(or vertex) labels and `w` is the weight of the edge. By Traversing the linked list we obtain the immediate neighbours of `u`. Visually, it looks like this. For implementing this in Python, we'll be using the dict()  for the main HashTable. For the Linked List we can use a list of 2 sized tuples (v,w).  Sidenote: Instead of a list of tuples, you can use a dict(), wi

Find the problem statement here . The 3n + 1 problem is also known as The Collatz Conjecture  in Mathematics. The problem is simple, you are given a positive integer 'n'. We perform the following operations. If n = 1, Stop If n is even, n = n / 2 If n is odd, n = 3 * n + 1 The problem statement asks to count the number of iterations we need to perform till we get to 1. (Note : 0 is a corner case.) It's a Conjecture because it's still hasn't been proved that every number will end up at 1.  I've decided to approach UVaOJ with C++ so that I can brush up my C++ skills. Here's my solution . I've used recursion combined with memoization. Memoization is a type of dynamic programming. It's kind of a cache memory which stores solutions to already solved subproblems so that you don't need to solve them again. Comments are welcome! Cheers.

Problem : Given an array of integers of odd length such that each element is repeated twice except for one. Find the non-repeating element. Eg. For array [3,2,1,5,1,2,3] the solution is 5. A tiny variation of the question which doesn't really change the answer is as follows. Problem : Given an array of integers of odd length such that each element is repeated even number of times except for one element. Eg. For array [1,5,5,1,2,2,4,4,4] the solution is 4. Let's begin with the naive solution, we use a Hash Table to keep track of the frequencies of my each element in the array. Finally, we find the element in the Hash Table with the odd frequency which is the solution required. The space and time complexity is O(n). We'll try and reduce the space complexity. This is one of those questions which will be solved using our trusty Xor operator. You should know X ^ X = 0 and also Xor is Commutative and associative. ie X ^ Y is Y ^ X. Therefore, (X ^ Y) ^ X is

Problem : Given two integers a and b (a <= b ). Find the value of a ^ (a+1) ^ ... (b-1) ^ b. (^ is the xor operator). This will be a short post. It's pretty trivial once you understand the pattern. I'd first refer you to this post first. In the alternate solutions, I've described how you can obtain the value of 1 ^ 2 ^ 3 .... ^ N. Therefore, our solution simply applies that concept. xor(b) ^ xor(a - 1) where xor function is implemented in Python as follows For Python, this will work for negative integers as well, since the mod operator always returns a positive integer. For other languages, make sure you make appropriate changes to the xor() function. Until next time...

This is a pretty silly question I came up with. Problem : You are given 3 integers a,b,c. You are given 2 functions, "int max(int,int)" and "void print(int)". Using these 2 function and these only, print the numbers in increasing order. You're allowed to use math operators, but NOT programming language constructs like "if", "for", "while", including the ternary operation etc So here's the solution. Again, beware of integer overflows. The idea here is if we negate the number, we can use the max() function to find the minimum number! Nifty eh? We don't need to use the auxiliary variables, those were added for clarity. Do you have an alternate solution? I'd love to see it. Leave a Comment.

For my first post, let's start with an easy one. It's a popular question among interviewers and you prolly have heard about this one. Never the less, let's solve it, for old times sake. :) Problem : Given an Array of integers of size N. The array contains all the numbers from 1 to N in arbitrary order. But one number (say X) has been replaced with 0. Find the missing number in the most efficient way possible. Solution: Before we get to the solution, we'll build a test case using the following Python Snippet. The Naive method is an O(n^2) algorithm, where we perform a linear search (ie O(n) ) for each element 1-N. For small values of N, this is perfectly fine but can we do better? Of course, with a small bit of help from 8th grade maths. Hopefully, you remember that, 1+2+3....+n = n (n+1)/2 So how does that help? Say we didn't have any missing number and the problem was simply to sum all the elements of the array? Since we know the array contains

Hi, I'm a Computer Science Masters student. I'll be posting some questions about Algorithms, Data Structures, a bit of maths. Occasionally, these questions will be academically relevant. But you can bet these questions at some point were asked by interviewers when someone applies for a position at a software company. I plan to post the question, and post my immediate thoughts...I'll be updating my posts frequently improving upon my solutions. I may occasionally quote or refer to an external website and adapt their solutions. If the update is a complete redesign, I'll make a brand new post referring to the old one. I'll be using Java or Python for most of my code samples. I'll also upload most of it to my github account. This blog not strictly targeted for Computer Science students. Puzzle aficionados will enjoy them as much as they enjoy their daily sudoku. The code provided is just to prove the feasibility of the implementation. The subject of Algo