Find the rotation count in rotated sorted array

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

**Question : **Find the minimum element in the rotated sorted array. 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 Solution This can be solved in linear time and logarithmic time. If we notice the above array, we see the array has been rotated 2 times, which is also the index of smallest element in the array. [Read More]
ArraySearch  kodeknight  recursion  array  rotated array  count  min  sorted-array 

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 

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 

Find the minimum element in the rotated sorted sorted array

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

def findMin(arr): print(“Finding min in a…

Anonymous - Sep 4, 2014

def findMin(arr):
print(“Finding min in a rotated sorted array of integers”)

low = 0
high = len(arr) - 1
while low < high:
mid = int((low + high)/2)
left = mid - 1
right = high

if arr[mid] > arr[left] and arr[mid] > arr[right]:
low = mid
elif arr[mid] > arr[left] and arr[mid] < arr[right]:
high = mid
else:
return arr[mid]

search  ArraySearch  kodeknight  recursion  array  binary search  rotated array  min  sorted-array 

Find the minimum element in the rotated sorted sorted array

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

Question : Find the minimum element in the rotated sorted array. 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 - The answer to this lies on the fact that if we can find the point on inflection and things will be simple. So if we can have 2 sub arrays A and B, [Read More]
search  ArraySearch  kodeknight  recursion  array  binary search  rotated array  min  sorted-array 

Stack DS to implement constant time Minimum element lookup

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

Problem: You need to implement a stack data structure that can also report the minimum element in constant-time. Solution Method 1 - Using extra stack This is not all that difficult if you think about it. Regular stacks support push() and pop() functions. We need to add a new read-only property, Minimum. You can’t just add a new variable to track the minimum because when the stack is popped you wouldn’t be know how to update the minimum variable without scanning through all items in the stack which would require you to pop and re-push each item, which is downright ugly. [Read More]
kodeknight  O(1)  CrackingTheCodingInterview  stack  min 

IsBST : Check whether the tree provided is BST or not

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

Problem This background is used by the next two problems: Given a plain binary tree, examine the tree to determine if it meets the requirement to be a binary search tree. To be a binary search tree, for every node, all of the nodes in its left tree must be <= the node, and all of the nodes in its right subtree must be > the node. Consider the following four examples… [Read More]
max  tree  kodeknight  boolean  binary-search-tree  BST  min  check 

Find the minimum data value find in Binary Search tree (using cpp)

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

Given a non-empty binary search tree (an ordered binary tree), return the minimum data value found in that tree. Note that it is not necessary to search the entire tree. A maxValue() function is structurally very similar to this function. This can be solved with recursion or with a simple while loop. int minValue(struct node* node) { /\* Given a non-empty binary search tree, return the minimum data value found in that tree. [Read More]
tree  kodeknight  binary-search-tree  BST  min