tag:blogger.com,1999:blog-47750556238840648052024-02-20T10:34:49.669-08:00Interesting AlgorithmsLakshman Abburihttp://www.blogger.com/profile/16622225315502007403noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-4775055623884064805.post-22231511961291987852015-12-28T14:56:00.001-08:002015-12-28T14:58:20.185-08:00Binary Search Tree<div dir="ltr" style="text-align: left;" trbidi="on">
Deletion Explained:<br />
https://www.youtube.com/watch?v=gcULXE7ViZw<br />
<br />
Complete Series<br />
http://www.youtube.com/playlist?list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P </div>
Lakshman Abburihttp://www.blogger.com/profile/16622225315502007403noreply@blogger.com2tag:blogger.com,1999:blog-4775055623884064805.post-33300557196785279532015-06-25T09:05:00.001-07:002015-06-25T09:05:26.377-07:00Data Structures and their applications<div dir="ltr" style="text-align: left;" trbidi="on">
http://www.cs.cmu.edu/~adamchik/15-121/lectures/Stacks%20and%20Queues/Stacks%20and%20Queues.html<br />
<br /></div>
Lakshman Abburihttp://www.blogger.com/profile/16622225315502007403noreply@blogger.com0tag:blogger.com,1999:blog-4775055623884064805.post-88741055885931770462012-01-22T00:09:00.001-08:002012-01-22T00:09:45.219-08:00Prim's algorithm - Greedy Approach<div dir="ltr" style="text-align: left;" trbidi="on">
<a href="http://en.wikipedia.org/wiki/Prim%27s_algorithm">Wikipedia</a> : http://en.wikipedia.org/wiki/Prim%27s_algorithm<br />
<br />
Refer to Example Run. </div>Lakshman Abburihttp://www.blogger.com/profile/16622225315502007403noreply@blogger.com0tag:blogger.com,1999:blog-4775055623884064805.post-12740143915416166132012-01-21T19:56:00.001-08:002012-01-21T19:56:18.625-08:00Dijkstra Algorithm - Very simple explanation<div dir="ltr" style="text-align: left;" trbidi="on">
<a href="http://renaud.waldura.com/doc/java/dijkstra/">Dijkstra </a>: http://renaud.waldura.com/doc/java/dijkstra/</div>Lakshman Abburihttp://www.blogger.com/profile/16622225315502007403noreply@blogger.com1tag:blogger.com,1999:blog-4775055623884064805.post-52837811012781577712012-01-21T15:57:00.000-08:002012-01-21T16:00:16.451-08:00Phone Number - Permutation of charspackage com.algorithms;<br /><br />// @author - Lakshman<br />// Does not validate input.<br /><br />public class PhoneNumbers {<br /> <br /> private static final boolean debug = false;<br /> private static final char[][] digits = {{'0'}, {'1'}, <br /> {'a', 'b', 'c'}, {'d', 'e', 'f'}, <br /> {'g', 'h', 'i'}, {'j', 'k', 'l'},<br /> {'m', 'n', 'o'}, {'p', 'q', 'r', 's'},<br /> {'t', 'u', 'v'}, {'w', 'x', 'y', 'z'}<br /> };<br /> private int permutationsCount = 0;<br /> <br /> private void numberDisplay() {<br /> for (int i=0; i<digits.length; i++) {<br /> System.out.print("array[" + i + "] length = " + digits[i].length);<br /> System.out.print(" :: Characters are : ");<br /> for (int j=0; j<digits[i].length; j++) {<br /> System.out.print(digits[i][j] + " , ");<br /> }<br /> System.out.println();<br /> }<br /> System.out.println("Total number of array elements = " + digits.length);<br /> }<br /> <br /> <br /> // Recursively display permutations.<br /> private void numberPerms(String number, String result) {<br /> int digit = Integer.parseInt(number.substring(0,1));<br /> if (debug) {<br /> System.out.println("digit = " + digit);<br /> System.out.println("digits[numberCh].length = " + digits[digit].length);<br /> } <br /> <br /> // Exit condition<br /> if (number.length() == 1) {<br /> for (int i=0; i<digits[digit].length; i++) {<br /> permutationsCount++;<br /> System.out.println("Permutation [" + permutationsCount + "] = " + result + digits[digit][i]);<br /> }<br /> return;<br /> }<br /> <br /> // Recursive function<br /> for (int i=0; i<digits[digit].length; i++) {<br /> String result1 = result + digits[digit][i];<br /> numberPerms(number.substring(1), result1);<br /> }<br /> } <br /> <br /> public static void main(String[] args) {<br /> PhoneNumbers phone = new PhoneNumbers();<br /> if (debug) {<br /> phone.numberDisplay();<br /> }<br /> phone.numberPerms("246", "");<br /> }<br /><br />}<br /><br />*******<br />Output<br />*******<br />Permutation [1] = agm<br />Permutation [2] = agn<br />Permutation [3] = ago<br />Permutation [4] = ahm<br />Permutation [5] = ahn<br />Permutation [6] = aho<br />Permutation [7] = aim<br />Permutation [8] = ain<br />Permutation [9] = aio<br />Permutation [10] = bgm<br />Permutation [11] = bgn<br />Permutation [12] = bgo<br />Permutation [13] = bhm<br />Permutation [14] = bhn<br />Permutation [15] = bho<br />Permutation [16] = bim<br />Permutation [17] = bin<br />Permutation [18] = bio<br />Permutation [19] = cgm<br />Permutation [20] = cgn<br />Permutation [21] = cgo<br />Permutation [22] = chm<br />Permutation [23] = chn<br />Permutation [24] = cho<br />Permutation [25] = cim<br />Permutation [26] = cin<br />Permutation [27] = cioLakshman Abburihttp://www.blogger.com/profile/16622225315502007403noreply@blogger.com0tag:blogger.com,1999:blog-4775055623884064805.post-15315247371073810142012-01-20T15:55:00.000-08:002012-01-20T15:58:13.284-08:00Longest Increasing SequenceAlgorithm : Two ways.<br />1. LCS with one array - being input array a[]; second array - sort input array b[];<br />So complexity = nlogn (for sort) + DP<br /><br />2. Another approach<br /><a href="http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence">Algorithm</a>: http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence<br />Impl: http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence.cLakshman Abburihttp://www.blogger.com/profile/16622225315502007403noreply@blogger.com0tag:blogger.com,1999:blog-4775055623884064805.post-21435162364153702692012-01-20T14:23:00.000-08:002012-01-20T14:24:53.012-08:00LCS - Longest Common SubsequenceVery Easy approach :<br /><a href="http://en.wikipedia.org/wiki/Longest_common_subsequence_problem">Wikipedia</a> - http://en.wikipedia.org/wiki/Longest_common_subsequence_problemLakshman Abburihttp://www.blogger.com/profile/16622225315502007403noreply@blogger.com0tag:blogger.com,1999:blog-4775055623884064805.post-54832082012514257322012-01-20T13:18:00.000-08:002012-01-20T13:21:16.055-08:00Dynamic Programming<a href="http://www.codeforces.com/blog/entry/325">Problem Varieties</a> - http://www.codeforces.com/blog/entry/325<br /><br /><a href="http://mat.gsia.cmu.edu/classes/dynamic/node2.html#SECTION00020000000000000000">CMU edu</a> - http://mat.gsia.cmu.edu/classes/dynamic/node2.html#SECTION00020000000000000000<br /><br /><a href="http://www.codechef.com/wiki/tutorial-dynamic-programming">Code Chef</a> - http://www.codechef.com/wiki/tutorial-dynamic-programmingLakshman Abburihttp://www.blogger.com/profile/16622225315502007403noreply@blogger.com0tag:blogger.com,1999:blog-4775055623884064805.post-21303592659392107662012-01-20T12:58:00.000-08:002012-01-20T12:59:51.661-08:00Problem : Minimum Steps to OneProblem : Minimum Steps to One<br />===============================<br /><br />Problem Statement: On a positive integer, you can perform any one of the following 3 steps. <br />1.) Subtract 1 from it. ( n = n - 1 ) , <br />2.) If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2 ) , <br />3.) If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3 ). Now the question is, given a positive integer n, find the minimum number of steps that takes n to 1<br /><br />eg: 1.)For n = 1 , output: 0 2.) For n = 4 , output: 2 ( 4 /2 = 2 /2 = 1 ) 3.) For n = 7 , output: 3 ( 7 -1 = 6 /3 = 2 /2 = 1 )<br /><br />Approach / Idea: One can think of greedily choosing the step, which makes n as low as possible and conitnue the same, till it reaches 1. If you observe carefully, the greedy strategy doesn't work here. Eg: Given n = 10 , Greedy --> 10 /2 = 5 -1 = 4 /2 = 2 /2 = 1 ( 4 steps ). But the optimal way is --> 10 -1 = 9 /3 = 3 /3 = 1 ( 3 steps ). So, we need to try out all possible steps we can make for each possible value of n we encounter and choose the minimum of these possibilities.<br /><br />It all starts with recursion :). F(n) = 1 + min{ F(n-1) , F(n/2) , F(n/3) } if (n>1) , else 0 ( i.e., F(1) = 0 ) . Now that we have our recurrence equation, we can right way start coding the recursion. Wait.., does it have over-lapping subproblems ? YES. Is the optimal solution to a given input depends on the optimal solution of its subproblems ? Yes... Bingo ! its DP :) So, we just store the solutions to the subproblems we solve and use them later on, as in memoization.. or we start from bottom and move up till the given n, as in dp. As its the very first problem we are looking at here, lets see both the codes.<br /><br />Memoization<br /><br />[code]<br /><br />int memo[n+1]; // we will initialize the elements to -1 ( -1 means, not solved it yet )<br /><br />int getMinSteps ( int n )<br /><br />{<br /><br />if ( n == 1 ) return 0; // base case<br /><br />if( memo[n] != -1 ) return memo[n]; // we have solved it already :)<br /><br />int r = 1 + getMinSteps( n - 1 ); // '-1' step . 'r' will contain the optimal answer finally<br /><br />if( n%2 == 0 ) r = min( r , 1 + getMinSteps( n / 2 ) ) ; // '/2' step<br /><br />if( n%3 == 0 ) r = min( r , 1 + getMinSteps( n / 3 ) ) ; // '/3' step<br /><br />memo[n] = r ; // save the result. If you forget this step, then its same as plain recursion.<br /><br />return r;<br /><br />}<br /><br />[/code]<br /><br />Bottom-Up DP<br /><br />[code]<br /><br />int getMinSteps ( int n )<br /><br />{<br /><br />int dp[n+1] , i;<br /><br />dp[1] = 0; // trivial case<br /><br />for( i = 2 ; i < = n ; i ++ )<br /><br />{<br /><br />dp[i] = 1 + dp[i-1];<br /><br />if(i%2==0) dp[i] = min( dp[i] , 1+ dp[i/2] );<br /><br />if(i%3==0) dp[i] = min( dp[i] , 1+ dp[i/3] );<br /><br />}<br /><br />return dp[n];<br /><br />}<br /><br />[/code]<br /><br />Both the approaches are fine. But one should also take care of the lot of over head involved in the function calls in Memoization, which may give StackOverFlow error or TLE rarely.<br /><br /><a href="http://www.codechef.com/wiki/tutorial-dynamic-programming">Reference </a>: http://www.codechef.com/wiki/tutorial-dynamic-programmingLakshman Abburihttp://www.blogger.com/profile/16622225315502007403noreply@blogger.com0tag:blogger.com,1999:blog-4775055623884064805.post-9306324518154982562012-01-19T13:29:00.000-08:002012-01-19T13:31:49.181-08:00Generate SubsetsQuestion: <br />How to generate a list of subsets with restrictions?<br />Input<br />{1,2,3}<br /><br />Output<br />{{1},{2,3}}<br />{{2},{1,3}}<br />{{3},{1,2}}<br /><br />Input<br />{1,2,3,4}<br /><br />Output<br />{{1},{2,3,4}}<br />{{2},{1,3,4}}<br />{{3},{1,2,4}}<br />{{4},{1,2,3}}<br />{{1,2},{3,4}}<br />{{1,3},{2,4}}<br />{{1,4},{2,3}}<br /><br />Input<br />{1,2,2,3}<br /><br />Output<br />{{1},{2,2,3}}<br />{{2},{1,2,3}}<br />{{3},{1,2,2}}<br />{{1,2},{2,3}}<br />{{1,3},{2,2}} <br /><br />Great Answer :<br />---------------<br />If you were generating all subsets you would end up generating 2n subsets for a list of length n. A common way to do this is to iterate through all the numbers i from 0 to 2n-1 and use the bits that are set in i to determine which items are in the ith subset. This works because any item either is or is not present in any particular subset, so by iterating through all the combinations of n bits you iterate through the 2n subsets.<br /><br />For example, to generate the subsets of (1, 2, 3) you would iterate through the numbers 0 to 7:<br /><br /> 0 = 000b → ()<br /> 1 = 001b → (1)<br /> 2 = 010b → (2)<br /> 3 = 011b → (1, 2)<br /> 4 = 100b → (3)<br /> 5 = 101b → (1, 3)<br /> 6 = 110b → (2, 3)<br /> 7 = 111b → (1, 2, 3)<br /><br />In your problem you can generate each subset and its complement to get your pair of mutually exclusive subsets. Each pair would be repeated when you do this so you only need to iterate up to 2n-1 - 1 and then stop.<br /><br /> 1 = 001b → (1) + (2, 3)<br /> 2 = 010b → (2) + (1, 3)<br /> 3 = 011b → (1, 2) + (3)<br /><br />To deal with duplicate items you could generate subsets of list indices instead of subsets of list items. Like with the list (1, 2, 2, 3) generate subsets of the list (0, 1, 2, 3) instead and then use those numbers as indices into the (1, 2, 2, 3) list. Add a level of indirection, basically.<br /><br />Here's some Python code putting this all together.<br /><br />#!/usr/bin/env python<br /><br />def split_subsets(items):<br /> subsets = set()<br /><br /> for n in xrange(1, 2 ** len(items) / 2):<br /> # Use ith index if ith bit of n is set.<br /> l_indices = [i for i in xrange(0, len(items)) if n & (1 << i) != 0]<br /> # Use the indices NOT present in l_indices.<br /> r_indices = [i for i in xrange(0, len(items)) if i not in l_indices]<br /><br /> # Get the items corresponding to the indices above.<br /> l = tuple(items[i] for i in l_indices)<br /> r = tuple(items[i] for i in r_indices)<br /><br /> # Swap l and r if they are reversed.<br /> if (len(l), l) > (len(r), r):<br /> l, r = r, l<br /><br /> subsets.add((l, r))<br /><br /> # Sort the subset pairs so the left items are in ascending order.<br /> return sorted(subsets, key = lambda (l, r): (len(l), l))<br /><br />for l, r in split_subsets([1, 2, 2, 3]):<br /> print l, r<br /><br />Output:<br /><br />(1,) (2, 2, 3)<br />(2,) (1, 2, 3)<br />(3,) (1, 2, 2)<br />(1, 2) (2, 3)<br />(1, 3) (2, 2)<br /><br />Reference : <a href="http://stackoverflow.com/questions/1521589/how-to-generate-a-list-of-subsets-with-restrictions">Stack Overflow</a>Lakshman Abburihttp://www.blogger.com/profile/16622225315502007403noreply@blogger.com0tag:blogger.com,1999:blog-4775055623884064805.post-44622287907941392612012-01-19T12:10:00.001-08:002012-01-22T00:10:47.388-08:00Terms and Definitions<div dir="ltr" style="text-align: left;" trbidi="on">
Combinations:<br />
*************<br />
Combinations is used to refer to picking k items from a set of n items, where the order of the k items does not matter. <br />
The related concept of picking k items from a set of n items, where the order of the k items does matter, is referred to as a permutation.<br />
<br />
Dynamic Programming :<br />
**********************<br />
Dynamic programming (usually referred to as DP ) is a very powerful technique to solve a particular class of problems. It demands very elegant formulation of the approach and simple thinking and the coding part is very easy. The idea is very simple, If you have solved a problem with the given input, then save the result for future reference, so as to avoid solving the same problem again.. shortly 'Remember your Past' :) . If the given problem can be broken up in to smaller sub-problems and these smaller subproblems are in turn divided in to still-smaller ones, and in this process, if you observe some over-lappping subproblems, then its a big hint for DP. Also, the optimal solutions to the subproblems contribute to the optimal solution of the given problem ( referred to as the Optimal Substructure Property ).<br />
<br />
There are two ways of doing this.<br />
<br />
1.) Top-Down : Start solving the given problem by breaking it down. If you see that the problem has been solved already, then just return the saved answer. If it has not been solved, solve it and save the answer. This is usually easy to think of and very intuitive. This is referred to as Memoization.<br />
<br />
2.) Bottom-Up : Analyze the problem and see the order in which the sub-problems are solved and start solving from the trivial subproblem, up towards the given problem. In this process, it is guaranteed that the subproblems are solved before solving the problem. This is referred to as Dynamic Programming.<br />
<br />
Note that divide and conquer is slightly a different technique. In that, we divide the problem in to non-overlapping subproblems and solve them independently, like in mergesort and quick sort.<br />
<br />
In case you are interested in seeing visualizations related to Dynamic Programming, you could also see : http://www.thelearningpoint.net/computer-science/dynamic-programming <br />
<br />
<a href="http://www.codechef.com/wiki/tutorial-dynamic-programming">Reference </a>: http://www.codechef.com/wiki/tutorial-dynamic-programming<br />
<br />
<a href="http://en.wikipedia.org/wiki/Adjacency_matrix">Adjacency Matrix</a> : http://en.wikipedia.org/wiki/Adjacency_matrix </div>Lakshman Abburihttp://www.blogger.com/profile/16622225315502007403noreply@blogger.com0tag:blogger.com,1999:blog-4775055623884064805.post-43743335197761707832012-01-17T19:48:00.000-08:002012-01-17T19:54:53.450-08:00Problems1. <a href="http://stackoverflow.com/questions/2344496/how-can-i-print-out-all-possible-letter-combinations-a-given-phone-number-can-re">1. Print all possible letter combination in a phone number</a>: http://stackoverflow.com/questions/2344496/how-can-i-print-out-all-possible-letter-combinations-a-given-phone-number-can-re<br /><br />2. <a href="http://stackoverflow.com/questions/2070359/finding-three-elements-in-an-array-whose-sum-is-closest-to-an-given-number">Finding 3 elements whose sum is closest to the input number</a> : http://stackoverflow.com/questions/2070359/finding-three-elements-in-an-array-whose-sum-is-closest-to-an-given-number<br /><br />3. <a href="http://stackoverflow.com/questions/7692653/google-interview-arrangement-of-blocks">Arrangement of blocks</a> : http://stackoverflow.com/questions/7692653/google-interview-arrangement-of-blocks<br /><br />4. <a href="http://stackoverflow.com/questions/6135443/dynamic-programming-question">Dynamic Programming</a> : http://stackoverflow.com/questions/6135443/dynamic-programming-questionLakshman Abburihttp://www.blogger.com/profile/16622225315502007403noreply@blogger.com0tag:blogger.com,1999:blog-4775055623884064805.post-76248893295398950102012-01-17T19:47:00.000-08:002012-01-17T19:48:18.669-08:00Dynamic ProgrammingTop Coders - <a href="http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg">Dynamic Programming tutorial</a> : http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProgLakshman Abburihttp://www.blogger.com/profile/16622225315502007403noreply@blogger.com0tag:blogger.com,1999:blog-4775055623884064805.post-41876878808641661972009-10-28T19:57:00.000-07:002009-10-28T19:58:12.720-07:00How to test a product?1. Requirements based testing - Test it based on Product Requirements doc<br />2. Parallel testing - Test it against competitor and peer products<br />3. Scenario testing - Assume different scenarios for different kinds of end users.<br />4. Usability testing - Based on usage of the product<br />5. Function testing - Based on functionality<br />6. Fault Injection - Inject problems<br />7. Stress testing - Stress it out<br />8. Performance testing - metrics<br />9. Regulations - specs<br /><br />A blog article on all possible test scenarios for a stapler is available in the following location:<br />http://www.testingreflections.com/node/view/928Lakshman Abburihttp://www.blogger.com/profile/16622225315502007403noreply@blogger.com0tag:blogger.com,1999:blog-4775055623884064805.post-45407527688282963162009-10-23T14:40:00.001-07:002009-10-23T14:52:43.829-07:00About this blog...This blog will help us to prepare for a Software Job Interview.<br />For questions, comments or to contribute, contact Lakshman Abburi - abburi.lakshman attherate gmail.comLakshman Abburihttp://www.blogger.com/profile/16622225315502007403noreply@blogger.com0