Lost in Compilation

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

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

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