Finding an integer that repeats odd number of times in an array of positive integers

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

Question: In an array of positive integers, all but one integer repeats odd number of times. Can you find that integers in O(n) time complexity? Solutions Answer: in order to solve this problem in O(n) time, we need to use bitwise manipulation. Since there is only one integer that repeats odd number of times, we can use the XOR operator to find out that number. When a number XOR with itself, it will become 0. [Read More]
search  Algorithms  ArraySearch  kodeknight  duplicate  Interview Question  array  integer-sort  bits 

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 

AVL Trees : Inserting a new Item

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

Initially, a new item is inserted just as in a binary search tree. Note that the item always goes into a new leaf. The tree is then readjusted as needed in order to maintain it as an AVL tree. There are three main cases to consider when inserting a new node. Case 1: New Node added to (BF = 0) Node A node with balance factor 0 changes to +1 or -1 when a new node is inserted below it. [Read More]
tree  kodeknight  balanced trees  avl 

Huffman Codes

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

Background When we encode characters in computers, we assign each an 8-bit code based on an ASCII chart. But in most files, some characters appear more often than others. So wouldn’t it make more sense to assign shorter codes for characters that appear more often and longer codes for characters that appear less often? This is exactly what Claude Shannon and R.M. Fano were thinking when they created the first compression algorithm in the 1950’s. [Read More]
Algorithms  kodeknight  Dynamic Programming  DP  incomplete