My software development journey
This problem is from SPOJ (Sphere Online Judge – A site to practice your problem solving skills). If you want to solve this problem on your own, please follow the link.The simplified problem description is as follows. A teacher has n packets of candies of varying sizes. The problem is to find the number of…
This problem is from Codeforces. If you want to solve this problem on your own. Follow the link.Following is the abridged(simplified) problem statement for the above problem.Given an array containing values in the range [-10,10], find out how many number of matching pairs are possible? A pair of numbers is said to be matching if…
Given a binary tree, write a program to count the number of leaf nodes. A leaf node is a node which does not have left and right children.For example consider the following binary tree. It has 3 leaf nodes namely 1, 4 and 7. The solution is simple. The number of leaf nodes of a…
Given a list of strings, how do we find the longest common prefix of all the strings?For example consider { “Anomaly”, “Anatomy”, “Analog”, “Angry” } the longest common prefix is “An”.This is a simple algorithm. Assume the first string as the longest common prefix, and try to match with the other strings and modify the…
Given a sorted linked list, how do we delete duplicate nodes from it?This question is simple and straightforward, we take two pointers, current and next which points the adjacent nodes. In each iteration we compare the values at these two nodes, if they are equal, we delete the node pointed by next and advance the…
Given an arbitrarily large number, how to check if it is same as it’s mirror image. For example 101 is a mirror image of itself, where as 1811 is not a mirror image of itself. This problem is from Hacker earth (A website for competitive programming). If you want to solve this problem on your…
Given a single linked list, how do we split it into two halves. For example the list 1->2->3->4 should be divided into 1->2 and 3->4 If the length of the list is odd, add the extra node to first half; so 1->2->3 should be split to 1->2 and 3. This problem can be efficiently solved…
In one of my previous posts, we have seen how a linked list can be sorted using bubble sort approach. In this post we will see how we can sort a linked list using insertion sort algorithm. Like bubble sort this approach will also take O(n2) time. Here is the strategy for linked list insertion…
Given an array of sorted numbers, we have to find the right most occurrence of a number.For example given an array {1,2,2,2,3}, the right most occurrence of 2 is at index 3 (0-based index). This post is related to one of my previous posts ( Finding the left most occurrence in sorted array).Similar to the…
Given an array of integers which might contain both positive and negative integers, how do you modify the array such that all the positive and all the negative elements appear together. For example consider the following array. [36, -2, -18, 24, 42, -3, 6] This should be transformed to some thing like [-2, -18, -3,…