kodeknight

Problem  Divide a number by 3 without using any of operators (%,/,*) Solution Method 1 int divideby3 (int num) { int sum = 0; while (num > 3) { sum += num >> 2; num = (num >> 2) + (num & 3); } if (num == 3) ++sum; return sum; } **Dry running the above method : ** For example if your number is 10 then convert to binary [Read More]

**Problem **  Write a program to add one to a given number. You are not allowed to use operators like ‘+’, ‘-’, ‘*’, ‘/’, ‘++’, ‘–’ …etc. Examples Input: 12 Output: 13 Input: 6 Output: 7 Solution We can use bitwise operators to achieve this. Following are different methods to achieve same using bitwise operators. Method 1 - Flipping the bits To add 1 to a number x (say 0011000111), we need to flip all the bits after the rightmost 0 bit (we get 0011000000). [Read More]

C style string Reverse a c-style string Replace all spaces in a string with “%20″ in c-style string atoi() in Java itoa() in Java Implementing strcpy Implementing strcat Implementing strcmp Implementing a strstr() / indexOf function CPP strings C Strings Making a String class in cpp String Class in cpp(Standard cpp strings) Internal functions in C Miscellaneous cases with printf String search algorithms Karp-Rabin algorithm Boyer Moore Algorithm String Searching Algorithm - Knuth Morris Pratt or KMP Algorithm [Read More]

Problem : There is an m x n grid. One can only move either down or right at any point in time. One is trying to reach the bottom-right corner of the grid. How many possible unique paths are there? (project euler problem 15) The similar question has been asked in Cracking the coding interview: Here we have to count the unique paths, but there we have to find the unique paths. [Read More]

Problem - Implement a stack using a queue Solution Method 1 - Implement a stack using 2 queues We have already discussed the problems here. Method 2 - Implement a stack using a single queue Here are the operations(note that push operation is expensive) push: enqueue new element. If n is the number of elements in the queue, then remove and insert element n-1 times. pop: dequeue push 1 front +----+----+----+----+----+----+ | 1 | | | | | | insert 1 +----+----+----+----+----+----+ push2 front +----+----+----+----+----+----+ | 1 | 2 | | | | | insert 2 +----+----+----+----+----+----+ front +----+----+----+----+----+----+ | | 2 | 1 | | | | remove and insert 1 +----+----+----+----+----+----+ insert 3 front +----+----+----+----+----+----+ | | 2 | 1 | 3 | | | insert 3 +----+----+----+----+----+----+ front +----+----+----+----+----+----+ | | | 1 | 3 | 2 | | remove and insert 2 +----+----+----+----+----+----+ front +----+----+----+----+----+----+ | | | | 3 | 2 | 1 | remove and insert 1 +----+----+----+----+----+----+ Code: [Read More]

The pseudo / java code find only global minima and… Himadri Sarkar - Mar 0, 2014The pseudo / java code find only global minima and that too when no other local minima exist. I don’t think this problem can be solved in less than O(n) Hi Himadri, thanks for the comment. But I think the code is intended to give us local minima, and as we are apply binary search logic, it is possible in O(log n). [Read More]

Problem: Given an array ‘a’ of N distinct integers, design an O(log N) algorithm to find a local minimum: an index i such that a[i-1] > a[i] < a[i+1]. Examples: a = [1,2,3,4,5] (increasing, increasing) a[0] is an LM a = [5,4,3,2,1] (decreasing, decreasing) a[n] is an LM a = [1,2,2,2,1] (increasing, decreasing) a[0] and a[n] are LMs Solution: **Brute force ** Go through each element 3 tuples, and compare them. [Read More]

Problem : Given a Singly Linked List which has data members sorted in ascending order. Construct a Balanced Binary Search Tree which has same data members as the given Linked List. **Example : ** Input: Linked List 1->2->3->4->5->6->7 Output: A Balanced BST 4 / \\ 2 6 / \\ / \\ 1 3 4 7 Lets discuss 2 approaches for this problem. Solution Method 1 (Simple) Following is a simple algorithm where we first find the middle node of list and make it root of the tree to be constructed. [Read More]

Problem  Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height. Examples Input: 1 2 3 4 5 6 7 Output: 4 / \\ 3 6 / \\ / \\ 3 4 6 7 Solutions ** Method 1 - Take the array’s middle element and insert it recursively** Pick up the middle element of the array Set it as the root Recursively build up left and right subtrees with lower and higher halves of the array Here is the code in java: [Read More]

Problem : Implement a stack using 2 queues and standard operations (enqueue, dequeue, isempty, size) Solution A similar problem has been blogged here, where we implement a queue using 2 stacks. There should be TWO versions of the solution. Version A: The stack should be efficient when pushing an item. Version B: The stack should be efficient when popping an item. Method 1 - When push is efficient and pop is costly [Read More]