Find all the pythagorean triplets in an array of integer

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

Given an array a of n integers find all possible Pythagorean triplets from the array. A Pythagorean triple consists of three positive integers a, b, and c, such that a2 + b2 = c2. this formula is derived from Pythagoras theorem: _“For every right angle triangle with side lengths a, b, and c=> a_2 + b2 = c2“. Solution: Conceptually it is similar to Find Non duplicate pairs that sum to S and 3 SUM problem [Read More]
kodeknight  2Sum  pythagorean triplet  Amazon 

Maximum value in a Sliding Window

 Posted on November 12, 2013  (Last modified on August 7, 2020)  |  11 minutes  |  Kinshuk Chandra

Problem Statement Question: A long array A[] is given to you. There is a sliding window of size w, which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Example: The array is [1 3 -1 -3 5 3 6 7], and w is 3. Window position Max \--------------- ----- 13−11 3 -1 -3 5 3 6 7 3 1 3−1−33 -1 -3 5 3 6 7 3 1 3 −1−35-1 -3 5 3 6 7 5 1 3 -1 −353-3 5 3 6 7 5 1 3 -1 -3 5365 3 6 7 6 1 3 -1 -3 5 3673 6 7 7 Input: A long array A[], and a window width w [Read More]
max  Algorithms  kodeknight  queue  deque  Amazon  PriorityQueue  facebook  stack  window 

Given a dictionary of word - Group all words into set of anagrams of each other

 Posted on August 10, 2013  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Given a set of words in a dictionary, write a program to group all words which are anagrams of each other in to sets. input: “bat”, “tar”, “xyz” , “tab”, “tar” output:[[“bat”, tab”], [“tar”, rat”],”xyz” ] Anagrams Two words are anagrams if one of them has exactly same characters as that of the another word. Example : Anagram & Nagaram are anagrams (case-insensitive). Approach The simpler logic would be to : [Read More]
kodeknight  Microsoft  String  Amazon  anagrams 

K – Reverse a linked list

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

This is one of the questions asked in Microsoft Interview. Given a linked list, we need to write a function that reverses the nodes of a linked list ‘k’ at a time and returns modified linked list. The following are the constraints given: If the no. of nodes in a link list is not a multiple of k then left-out nodes in the end should remain as it is You have to retain the memory address of the nodes without modifying it i. [Read More]
kodeknight  Microsoft  link list  reverse  Amazon  Single Link List  incomplete 

Find the point of transition from 0 to 1 in an infinite sorted array containings only 0 and 1 .

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

for(int j=arrIndex/2 ; j < arrIndex;j++) …

shanky - Nov 0, 2014

for(int j=arrIndex/2 ; j < arrIndex;j++)
{
if(array[j]==1)
return j;//this is our index
}

This makes the approach O(n)
Do a regular binary search after finding the cap , with range i/2 to i

Hi Shanky, you are right. That’s what I have done :)

search  ArraySearch  kodeknight  binary array  Amazon  Interview Question  array  binary search  integer-array  integer-sort  zero 

Find the point of transition from 0 to 1 in an infinite sorted array containings only 0 and 1 .

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

Approach 1(bad): Iterating over the array until we find 1, as the array is sort. In worst case it will go till the last element, and hence this is bad approach. Approach 2 : Club binary search approach and array’s random access property Since the array is infinitely increasing i.e. we don’t know array size in advance, so we can’t directly apply traditional BinarySearch (in which we partition the problem size in half in each iteration, kind of top down approach). [Read More]
search  ArraySearch  kodeknight  binary array  Amazon  Interview Question  array  binary search  integer-array  integer-sort  zero 

Minimum number of coins to get particular amount, given multiple denomination

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

Question: You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount OR S), find the minimum number of coins required to get the exact amount. Problem statement “Given a list of N coins, their values (V1, V2, … , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it’s not possible to select coins in such a way that they sum up to S. [Read More]
kodeknight  knapsack problem  coin  Dynamic Programming  DP  Amazon  min 

Search an element in the sorted rotated array

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

Question: Implement a search function for a sorted rotated array. Duplicates are allowed. Returning any one of the duplicates is acceptable. So for example we have sorted array as - 2,3,6,12, 15, 18. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 15, 18,2,3,6,12 Answer: We can do a binary search with some modified checks. So lets take arr as array, start be start of the array, end be arr. [Read More]
ArraySearch  kodeknight  Amazon  recursion  array  binary search  rotated array  CrackingTheCodingInterview  sorted-array  sorting-and-searching  java 

Longest increasing subsequence

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

Longest Increasing Subsequence has been a classic Dynamic Programming problem. O(N^2) has been around for a while but more interesting is the following O(n log n) solution. Problem Input : Sequence of integers (or any comparable items) Output : Longest increasing subsequence of the sequence, which may not be contiguous. For example : We have sequence : 1,8,2,7,3,6,4,5 which has the longest increasing subsequence : 1,2,3,4,5. Note that the numbers are non-contiguous. [Read More]
kodeknight  Dynamic Programming  DP  Amazon  incomplete  Interview Question  google