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 

Maximum value in a Sliding Window

 Posted on November 12, 2013  (Last modified on August 7, 2020)  |  11 minutes  |  Kinshuk Chandra

Problem Statement Question: A long array A[] is given to you. There is a sliding window of size w, which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Example: The array is [1 3 -1 -3 5 3 6 7], and w is 3. Window position Max \--------------- ----- 13−11 3 -1 -3 5 3 6 7 3 1 3−1−33 -1 -3 5 3 6 7 3 1 3 −1−35-1 -3 5 3 6 7 5 1 3 -1 −353-3 5 3 6 7 5 1 3 -1 -3 5365 3 6 7 6 1 3 -1 -3 5 3673 6 7 7 Input: A long array A[], and a window width w [Read More]
max  Algorithms  kodeknight  queue  deque  Amazon  PriorityQueue  facebook  stack  window 

Maximum continuous sum subarray problem

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  6 minutes  |  Kinshuk Chandra

Problem You are given an array of integers (both positive and negative). Find the continuous sequence with the largest sum. Return the sum. EXAMPLE Input: {2, -8, 3, -2, 4, -10} Output: 5 (i.e., {3, -2, 4}) Solution  Method 1 - Brute force The outer loop picks the beginning element, the inner loop finds the maximum possible sum with first element picked by outer loop and compares this maximum with the overall maximum. [Read More]
max  kodeknight  sub-array  Dynamic Programming  DP  Moderate  array  integer-array  CrackingTheCodingInterview 

Majority element in the array

 Posted on October 9, 2011  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Majority Element: A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element). Problem: Given an array consisting of N integers, find the number with the maximum occurrences, i.e. majority element, given the assumption that the number occurs more than N/2 times in the array. Example I/P : 3 3 4 2 4 4 2 4 4 [Read More]
max  kodeknight  time complexity  duplicate  Interview Question  array 

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 

Compute Maximum Depth or Height of binary search tree

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

Given a binary tree, compute its “maxDepth” – the number of nodes along the longest path from the root node down to the farthest leaf node. The maxDepth of the empty tree is 0, the maxDepth of the tree below is 3.  1 / \ 2 3 / \ / \ 4 5 6 7 Recursive approach /\* Compute the "maxDepth" of a tree -- the number of nodes along the longest path from the root node down to the farthest leaf node. [Read More]
max  tree  kodeknight  binary-search-tree  BST