3 sum problem

 Posted on January 17, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem Statement: Problem Given a set S of n integers find all possible subsets(a,b,c) such that a + b + c = 0.  Making more generic:  Given a set S of n integers find all possible subsets(a,b,c) such that a + b + c = T. Solution Brute force approach is of O(n^3) but we can solve it in O(n^2) by using the approach in 2 sum problem approach. [Read More]
kodeknight  2Sum  array  CrackingTheCodingInterview 

Find all subsets of a given set OR Find power set of a given set

 Posted on January 6, 2012  (Last modified on August 7, 2020)  |  6 minutes  |  Kinshuk Chandra

Problem Write a method that returns all subsets of a set. Example If we’re given a set of integers such that S = {1, 2, 3}, how can we find all the subsets of that set? For example, given S, the set of all subsets i.e. P(S) we get are {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, and {1, 2, 3}. Here is {} is empty set denoted by Φ. [Read More]
kodeknight  recursion  subset  CrackingTheCodingInterview 

Maximum continuous sum subarray problem

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  6 minutes  |  Kinshuk Chandra

Problem You are given an array of integers (both positive and negative). Find the continuous sequence with the largest sum. Return the sum. EXAMPLE Input: {2, -8, 3, -2, 4, -10} Output: 5 (i.e., {3, -2, 4}) Solution  Method 1 - Brute force The outer loop picks the beginning element, the inner loop finds the maximum possible sum with first element picked by outer loop and compares this maximum with the overall maximum. [Read More]
max  kodeknight  sub-array  Dynamic Programming  DP  Moderate  array  integer-array  CrackingTheCodingInterview 

Shuffle a deck of cards perfectly

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Question Write a method to shuffle a deck of cards. It must be a perfect shuffle – in other words, each 52! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect. OR How can you shuffle an array in O(n) time and O(1) space? For example, if input is an array of (1, 2, 3, 4, 5), one of the output can be (5, 4, 3, 2, 1) or (4, 2, 3, 1, 5). [Read More]
kodeknight  probability  shuffle  array  CrackingTheCodingInterview  random 

Remove duplicates from an unsorted linked list

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Write code to remove duplicates from an unsorted linked list. FOLLOW UP: How would you solve this problem if a temporary buffer is not allowed? **Example ** Input/Output Original linked list: 2 -> 3 -> 2 -> 5 -> 2 -> 8 -> 2 -> 3 -> 8 -> null After deleting duplicate node: 2 -> 3 -> 5 -> 8 -> null We have already seen deleting duplicates from the sorted list. [Read More]
kodeknight  link list  duplicate  Single Link List  CrackingTheCodingInterview  remove-duplicates 

Check if 2 strings are rotated versions of each other

 Posted on December 31, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem : Given two string s1 and s2 how will you check if s1 is a rotated version of s2 ? OR Assume you have a method isSubstring() which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring.ie: ‘waterbottle’ is a rotation of ‘erbottlewat’ [Read More]
kodeknight  String  java-code  rotated array  CrackingTheCodingInterview 

Check if Tree is a Balanced Tree

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one Solution Method 1 - Difference of height at each node should not be greater than 1 Here is the code : public boolean isBalanced(Node root){ if(root==null){ return true; //tree is empty } else{ int lh = root. [Read More]
tree  kodeknight  balanced trees  binary-search-tree  BST  CrackingTheCodingInterview  check 

Implement 3 stacks in 1 array

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem - Implement 3 stacks in 1 array Solutions Method 1 - Create 3 stacks with fixed max size Divide the array in three equal parts and allow the individual stack to grow in that limited space (note: “[” means inclusive, while “(” means exclusive of the end point). for stack 1, we will use [0, n/3) for stack 2, we will use [n/3, 2n/3) for stack 3, we will use [2n/3, n) Here is the code : [Read More]
kodeknight  array  CrackingTheCodingInterview  stack