array

Find increasing 3-tuple (sub-sequence)

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

Problem: You given an array: 3, 2, 1, 6, 5, 4, 9, 8, 7 you have to find a 3 tuple which has property a < b < c, also a is before b, b is before c in array. Answer can have multiple tuples, you have to find any one. In this array, answer will be 3, 6, 9 Solution: Simple. Time complexity = O(n ^ 2) Create an array of indexes, and sort the original array keeping track of the indexes in the second array. [Read More]

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 the maximum repeating number in array where all the elements are in range 0 to k-1, k ∈ [0,N]

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

Given an array of size n, the array contains numbers in range from 0 to k-1 where k is a positive integer and k <= n. Find the maximum repeating number in this array. For example, let k be 10 the given array be arr[] = {1, 2, 2, 2, 0, 2, 0, 2, 3, 8, 0, 9, 2, 3}, the maximum repeating number would be 2. Expected time complexity is O(n) and extra space allowed is O(1). [Read More]

kodeknight duplicate array

Finding the max repeated element in an array

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

Problem : Find the element which occurs maximum number of times. METHOD 1 : Sorting the array and scanning the array The simple solution is to Sort the array Scan the array such that keep the track of the elements which occurred max number of times METHOD 2 : Using Binary Search Tree We can have a binary search tree with an extra field count, which indicates the number of times an element appeared in the input. [Read More]

max kodeknight duplicate array

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

Introduction of Array

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

This is the basic or simplest type of data structure. An array can be defined as, a list of a finite number “n” of similar data elements referenced respectively by a set of n consecutive numbers, usually 1, 2, 3, …, n. If A is chosen for the name of some array, then the elements of A are denoted as, a1, a2, a3, a4, …, an OR A(1), A(2), A(3), A(4), …, A(n) [Read More]

kodeknight array

find four elements in array whose sum equal to a given number X

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

This can be solved efficiently via using HashTables. We can have a hashtable sums sums will store all possible sums of two different elements. For each sum S it returns pair of indexes i and j such that a[i] + a[j] == S and i != j. But initially it’s empty, we’ll populate it on the way. So, this can be done in O(n^2) time. Pseudocode for (int i = 0; i < n; ++i) { // 'sums' hastable holds all possible sums a

k

+ a

l

// where k and l are both less than i for (int j = i + 1; j < n; ++j) { int current = a

i

+ a

j

; int rest = X - current; // Now we need to find if there're different numbers k and l // such that a

k

+ a

l

== rest and k < i and l < i // but we have 'sums' hashtable prepared for that if (sums

rest

! [Read More]

kodeknight array hashtable sum

Array Implementation of Heap

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

The parent function seems to be a bit in-correct. …

Anonymous - Apr 3, 2014

The parent function seems to be a bit in-correct. It should return i/2 if i is even.
parent(i)
{
if(i is even)
return i/2;
else
return floor(i/2);
}

Thanks mate for the correction. I have corrected it.

kodeknight array heap Data Structure