2 Sum Problem : Given an integer array and a number T, find all unique pairs of (a, b) whose sum is equal to T

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

You are given an array of n integers and a target sum T. The goal is to determine whether or not there are two numbers x,y in A with x+y=T. Example : Suppose we have an int array = {5, 3, 7, 0, 1, 4, 2} and T = 5. The unique pairs that sum up to 5 are (5, 0) (3, 2) and (1, 4). There are three approaches to solve this problem - 1) brute force, 2) sort the array and use binary and search, and 3) Using the hashtable. [Read More]
kodeknight  2Sum  sorting  array  hashtable  pair  unique  sum 

Finding an integer that repeats odd number of times in an array of positive integers

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

Question: In an array of positive integers, all but one integer repeats odd number of times. Can you find that integers in O(n) time complexity? Solutions Answer: in order to solve this problem in O(n) time, we need to use bitwise manipulation. Since there is only one integer that repeats odd number of times, we can use the XOR operator to find out that number. When a number XOR with itself, it will become 0. [Read More]
search  Algorithms  ArraySearch  kodeknight  duplicate  Interview Question  array  integer-sort  bits 

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 

Find the First Duplicated Integer in an Array containing numbers from 1 to N Without Using Extra Memory

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

let the array be 3 1 2 1 3 4 first repeated integ… Unknown - Mar 6, 2013let the array be 3 1 2 1 3 4 first repeated integer is 3 here start from the first and go till the end add n+1 to the a[a[i]] where i is the current index. iterate again dividing the values by n+1 if values comes 1 . the remainder is the repeated one. [Read More]
kodeknight  ranged-array  duplicate  incomplete  array  integer-array 

Find the First Duplicated Integer in an Array containing numbers from 1 to N Without Using Extra Memory

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

Question: There is a size-N array of integers whose values range from 1 to N. Some integers are duplicated. Find the first duplicate and its index without using any extra memory (not even O(1)). Solution There are a few keys in the question that we should consider: The array size is a finite number N which is also the upper limit for any integer inside the array. Hence, if the array size is 10, then there are ten elements in the array and each of those elements is between 1 and 10. [Read More]
kodeknight  ranged-array  duplicate  incomplete  array  integer-array 

Sorting Array of Three Kinds or The Dutch National Flag Problem OR three color sort

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

Question: given an array of three different kinds of value such as array(1, 2, 0, 2, 1) and array(a, b, a, c, b), write an algorithm to sort the array. For example, input array(1, 2, 0, 2, 1) becomes array(0, 1, 1, 2, 2) and input array(a, b, a, c, b) becomes array(a, a, b, b, c). This problem is also called three color sort. Solution: the Dutch National Flag Algorithm sorts an array of red, blue, and white objects by separating them from each other based on their colors. [Read More]
kodeknight  quicksort  binary array  sorting  incomplete  array  integer-sort  zero 

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 

Minimum Distance Between Two Elements in an Array

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

Question Given an unsorted array and two elements, find the minimum distance between the elements in the array. The array may have duplicates. Example For example, if the Input array is (2, 1, 3, 4, 0, 2, 5) and the two elements are 4 and 5, then the min distance is 3 because 4 is at index 3 and 5 is at index 6. Solution Method 1 - Brute force [Read More]
kodeknight  array  distance  min 

Convert array of positive numbers to sorted array

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

You are given an array of positive integers. Convert it to a sorted array with minimum cost. Only valid operation are Decrement -> cost = 1 Delete an element completely from the array -> cost = value of element For example: 4,3,5,6, -> cost 1 (decrement 4) 10,3,11,12 -> cost 3 (delete 3) Trying out DP We can make the DP more efficient You don’t need to scan the whole previous column when calculating costs of decrementing. [Read More]
conversion  kodeknight  Dynamic Programming  DP  array  sorted-array