Lost in Compilation

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(), ...

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...