Implement a stack using 2 queues

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

Problem : Implement a stack using 2 queues and standard operations (enqueue, dequeue, isempty, size) Solution A similar problem has been blogged here, where we implement a queue using 2 stacks. There should be TWO versions of the solution. Version A: The stack should be efficient when pushing an item. Version B: The stack should be efficient when popping an item. Method 1 - When push is efficient and pop is costly [Read More]
kodeknight  queue  Data Structure  stack 

Stack with find-min/find-max in O(1) time

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

Problem Stack with find-min/find-max in O(1) time Solution Method 1 - using extra stacks for min and max The basic idea of the solution can be found here. Here instead of 2 stacks we will be using 3 stacks -1 stack with normal elements, 1 with only max elements and 1 with min element. Now the operations will be following : push: - If the element being pushed is less than the top element of ‘min_stack’ then push it on ‘min_stack’ as well. [Read More]
max  kodeknight  minmax  O(1)  stack  min 

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 

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 

Find Maximum Value in the unsorted array

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

**Problem : **
Find Maximum Value in the unsorted array

Solution
Method 1 - Linear search

Here is the code to do that :

public int findMax(int\[\] numbers)  
{  
    int max = 0;  
  
    for (int i = 0; i < numbers.length; ++i)  
        if (numbers\[i\] > max) max = numbers\[i\];  
  
    return max;  
}

So, in worst case the number of comparisons will be (n-1).

Time complexity - O(n)

max  kodeknight  unsorted-array  min 

Find kth largest in an Array

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

**Problem : **  You have an array of numbers; you need to find the k-th largest in the arra Solution ** Method 1 - Tournament principle** We have to find the element which has competed with largest element, and is just (k-1)th level.We have discussed this principle here. Method 2 - Using max heap Consider the array of length n. Here is the algo :  Build a max heap in O(n) ;  Now remove k elements from the heap; wherein each removal costs log(n) time to maintain the heap property. [Read More]
max  kodeknight  largest  minmax  unsorted-array  kth-largest  min  smallest 

find out the largest and second largest number in an array

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

Question: Write an efficient C program to find smallest and second smallest element in an array. Solution Method 1 - Compare each element with current max and second max Algorithm 1) Initialize both first and second smallest as a\[0\] first = second = a\[0\] 2) Loop through all the elements. a) If the current element is greater than firstMax, then update firstMax and secondMax. b) Else if the current element is greater than second then update secondMax pseudocode [Read More]
max  kodeknight  largest  minmax  unsorted-array  min  second-largest 

How to find max. and min. in array using minimum comparisons?

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

Problem : Given an array of integers find the max. and min. using minimum comparisons. Solution Method 1 (Naive) - Iterate through the array, and update min and max pointers 1\. Iterate through the array, select element a 2\. Update min by comparing (min, a) 3\. Update max by comparing (max, a) Number of comparison here will be ~2N, if N is number of element. Time complexity will be O(n) though. [Read More]
max  kodeknight  browserstack  minmax  array  unsorted-array  min 

Determine if a small tree T2 is the subtree of a huge tree T1

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

You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1. Solution Method 1 - Traversing through T1 and finding subtree at each node, if T1’s node = T2.root Here’s what we will do: Traverse T1.  If the current node is equal to the root node of T2, traverse both of the trees (T2 and the current subtree of T1) at the same time. [Read More]
Binary Tree  BT  kodeknight  CrackingTheCodingInterview