Asymptotic Notation

 Posted on March 11, 2016  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Its been a while, since I have blogged. To start with I am posting a basics of asymptotic analysis of algorithm, which we study at the start of the course. Now we are going to be less precise and worry only about approximate answers for large inputs. The Big-Oh Notation Definition: Let f(n) and g(n) be real-valued functions of a single non-negative integer argument. We write f(n) is O(g(n)) if there is a positive real number c and a positive integer n0such that f(n)≤cg(n) for all n≥n0. [Read More]
Algorithms  AlgorithmAnalysis 

Growth Rate - The Importance of Asymptotics

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

It really is true that if algorithm A is o(algorithm B) then for large problems A will take much less time than B. Definition: If (the number of operations in) algorithm A is o(algorithm B), we call A asymptotically faster than B. Example:: The following sequence of functions are ordered by growth rate, i.e., each function is little-oh of the subsequent function. log(log(n)), log(n), (log(n))2, n1/3, n1/2, n, nlog(n), n2/(log(n)), n2, n3, 2n, 4n, n! [Read More]
Algorithms  AlgorithmAnalysis 

Algorithm Interview Questions - Set 1

 Posted on July 30, 2014  (Last modified on August 7, 2020)  |  11 minutes  |  Kinshuk Chandra

A period of time where users login and logout, given a sets of login and logout time pairs, write a function that can show the number of users online at any given time. Intersection of n sets without using a hash table. Implement a LRU(Least Recently Used) cache Implement a function to compute cubic root what is the time complexity? Given a matrix with 1′s and 0′s, find the number of groups of 1′s. [Read More]
Algorithms  kodeknight  interview-set 

Given an array arr[], find the maximum j – i such that arr[j] > arr[i]

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

Problem Given an array arr[], find the maximum j – i such that arr[j] > arr[i]. Example Input: {34, 8, 10, 3, 2, 80, 30, 33, 1} Output: 6 (j = 7, i = 1) Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0} Output: 8 ( j = 8, i = 0) Input: {1, 2, 3, 4, 5, 6} Output: 5 (j = 5, i = 0) Input: {6, 5, 4, 3, 2, 1} Output: -1 Solution Method 1 (Simple but Inefficient) [Read More]
Algorithms  kodeknight  sorting  array  distance 

Algorithm Analysis

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

In computer science, the analysis of algorithms is the determination of the amount of resources (such as time and storage) necessary to execute them. Most algorithms are designed to work with inputs of arbitrary length. Usually, the efficiency or running time of an algorithm is stated as a function relating the input length to the number of steps (time complexity) or storage locations (space complexity). In computer science there can be multiple algorithms exist for solving the same problem (for example, sorting problem has many algorithms like insertion sort, selection sort, quick sort and many more). [Read More]
Algorithms  kodeknight  AlgorithmAnalysis 

Deterministic Selection - Select the i th smallest element

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

We have already seen RSelect or Random Selection here. Now lets focus on DSelect. Though RSelect is good, and works in linear time, but it deterministically runs in O(n) time, even in worst case. But the downside is that it doesn’t runs as fast as RSelect, but its worst case is still better. Like in quicksort, we had it better than merge sort, but worst case of quicksort was worse than mergesort. [Read More]
Algorithms  kodeknight  randomized algorithm  largest  sorting  Data Structure  selection  kth-largest  smallest 

Finding the celebrity group

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

Problem Given the group of people in party find the group of celebrities Suppose we have N people and there might be a group of celebrities inside. Every person knows every celebrity and every celebrity knows only every other celebrity. If you are given the function of Knows(x,y) which returns true if x knows y, false otherwise. identify the group of celebrities. This problem is to identify a group of celebrities, and it is not identifying the only celebrity among the people, such as http://k2code. [Read More]
Algorithms  kodeknight  celebrity 

Find all pairs (x, y) in a sorted array so that x + y < z

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

Problem

Given a sorted integer array and number z find all pairs (x, y) in the array so that x + y < z. Can it be done better than O(n^2)?

Solution

Method 1

The solution can be found in O(n^2) where we select 1st element from n elements and 2nd element y from n-1 elements, and hence n(n-1)/2 ~ O(n^2)

Reference - stackoverflow

Algorithms  kodeknight  Data Structure 

Algorithm Introduction

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

**Definition: ** An algorithm is a finite set of discrete statements (or Steps) in some particular sequence (or Order) to accomplish a predefined particular task. **Properties: ** An algorithm must have the following properties: Input(s) : An algorithm must have one(1) or more pre-specified input(s). Output(s) : An algorithm must have one(1) or more output(s). Definiteness : Each steps of an algorithm must define clearly (i.e. without any confusion or Contradiction or Ambiguity). [Read More]
theory  Algorithms  kodeknight  Data Structure