Merge two sorted arrays - One having big enough buffer to hold another

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

Problem You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order. Another way to ask same question Given a sorted array of size n with n elements (array1) and a sorted array of size 2n with n elements (array2), merge them to get a sorted array of size 2n. [Read More]
kodeknight  merge  sorting  two-arrays  two-sorted-arrays  CrackingTheCodingInterview  sorted-array  sorting-and-searching 

Number of unique elements in sorted array with repeated elements

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

Problem Find the number of unique elements in sorted array with repeated elements. Follow up - How can you do it without using extra space Example Input = [1,1,1, 2] Output = 2 i.e. 1 and 2. Example for follow up Input = [1,1,2] Output = 2 Solution It’s not really possible to know in constant time how many unique items are in a collection, even if the collection is sorted, unless you only allow one instance of the item in the collection at any given time. [Read More]
kodeknight  duplicate  count  sorted-array  java 

Finding the biggest difference between sorted array values

 Posted on March 21, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem finding the biggest difference between sorted array values **Example ** Consider the array : var array = array(1,4,7,8,12,15); The values in the array will always be integers and is sorted, and elements may repeat. Now, we want to print out the biggest step in the array. step is difference between adjacent element: step array - (-,3,3,1,4,3) The biggest step is 4, between 8 and 12. Solution Method 1- Brute force [Read More]
max  kodeknight  sorted-array 

Sorted Linked List to Balanced BST

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

Problem : Given a Singly Linked List which has data members sorted in ascending order. Construct a Balanced Binary Search Tree which has same data members as the given Linked List. **Example : ** Input: Linked List 1->2->3->4->5->6->7 Output: A Balanced BST 4 / \\ 2 6 / \\ / \\ 1 3 4 7 Lets discuss 2 approaches for this problem. Solution Method 1 (Simple) Following is a simple algorithm where we first find the middle node of list and make it root of the tree to be constructed. [Read More]
conversion  sorted-list  kodeknight  binary-search-tree  BST  sorted-array 

Convert sorted array to Balanced BST

 Posted on February 26, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem  Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height. Examples Input: 1 2 3 4 5 6 7 Output: 4 / \\ 3 6 / \\ / \\ 3 4 6 7 Solutions ** Method 1 - Take the array’s middle element and insert it recursively** Pick up the middle element of the array Set it as the root Recursively build up left and right subtrees with lower and higher halves of the array Here is the code in java: [Read More]
conversion  kodeknight  balanced trees  binary-search-tree  BST  CrackingTheCodingInterview  sorted-array 

Find the minimum and maximum in the array

 Posted on February 16, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Here are few question we find on finding min and max in the array, but array type changes. Unsorted 1D array Find the maximum (OR minimum) in an array Find the maximum AND minimum in an array with min number of comparisons Find the max and second maximum in an array (likewise for minimum) Find the max and nth max in an array Rotated Sorted array Find the minimum element in the rotated sorted array. [Read More]
max  kodeknight  Page  minmax  2DSortedArray  unsorted-array  min  sorted-array 

Merge two arrays efficiently - one sorted, another unsorted

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

Problem Given a sorted array of n elements followed by an unsorted array of length n. Sort the 2 list into one efficiently. Solution Method 1 - Insert the elements in sorted array using binary search Since inserting a single element into array and keeping it sorted is O(n), you cannot get better then that. Thus, for both cases - sorting the smaller array and then using merge(part1,part2) will be O(n), and thus optimal in terms of asymptotic complexity. [Read More]
kodeknight  merge  union  sorting  array  two-arrays  two-sorted-arrays  sorted-array 

Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space].

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

Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space].
e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to: [-5,-2,1,3,3,6,8,8]

http://stackoverflow.com/questions/6153915/merging-of-two-sorted-halfs-without-extra-memory

kodeknight  merge  incomplete  array  bitonic  sorted-array 

k-way merge - Merging k sorted arrays of n elements

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

Given k sorted arrays of size n each, merge them and print the sorted output. Example: **Input:** k = 3, n = 4 arr = { {1, 3, 5, 7}, {2, 4, 6, 8}, {0, 9, 10, 11}} ; **Output:** 0 1 2 3 4 5 6 7 8 9 10 11 Method 1 - Merging from 1 array to other It does so by using the “merge” routine central to the merge sort algorithm to merge array 1 to array 2, and then array 3 to this merged array, and so on until all k arrays have merged. [Read More]
kodeknight  merge  divide and conquer  sorting  array  two-sorted-arrays  min-heap  sorted-array 

Find Nth largest element in the rotated sorted array

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

Please give review to this post http://rawjava.blo…

Unknown - Apr 1, 2015

Please give review to this post
http://rawjava.blogspot.com/2015/04/java-program-to-find-maximum-number.html

Good question and equally good answer..Enjoyed your post :)

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