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 

Spiral printing of a two dimensional array

 Posted on September 19, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Given a 2D array, print it in spiral form. Examples See the following examples. Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Output: 1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11 Code is : [Read More]
kodeknight  Microsoft  2DArray  Interview Question  array  matrix 

All permutations of a string

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

small trick ,but a very nice solution for duplicat…

nikhil - Feb 4, 2014

small trick ,but a very nice solution for duplicates!!!!

Thanks Nikhil. :)

can u please write the main function for duplicate program. I ran the duplicate program and it is not giving me the desired output

backtracking  Permutation and Combination  kodeknight  String  Permutation  Interview Question  recursion  CrackingTheCodingInterview  java 

All permutations of a string

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

Problem Write a method to compute all permutations of a string. Example For a string of length n, there are n! permutations. INPUT: “abc” OUTPUT: “abc” “acb” “bac” “bca” “cab” “cba” So, we have 3! = 6 items for string abc. Solution There are several ways to do this. Common methods use recursion, memoization, or dynamic programming. The basic idea is that you produce a list of all strings of length 1, then in each iteration, for all strings produced in the last iteration, add that string concatenated with each character in the string individually. [Read More]
backtracking  Permutation and Combination  kodeknight  String  Permutation  Interview Question  recursion  CrackingTheCodingInterview  java 

Sorting binary array - Array containing only 0 and 1 in one pass OR two color sort

 Posted on April 26, 2010  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

in your Pseudocode, the if condition should be if …

RM - May 3, 2014

in your Pseudocode, the if condition should be if (low < high).

Thanks Rish. I have made the change a[low] > a[high] rather than low < low. :). Thanks for correcting me.

kodeknight  interview  quicksort  binary array  sorting  Interview Question  array  programCPP  integer-sort  zero 

Sorting binary array - Array containing only 0 and 1 in one pass OR two color sort

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

Problem Sort a binary array - array containing 0s and 1s in 1 pass. This is also called two color sort. Example Input - Binary unsorted array A = {0,1,1,0,0,1}; Output - binary sorted array B = {0,0,0,1,1,1} Solution This is similar to quicksort partition algorithm. Though normal sorting takes O(n log n) time, but we have to just partition 0 from 1, and hence it should only take time of partitioning - O(n). [Read More]
kodeknight  interview  quicksort  binary array  sorting  Interview Question  array  programCPP  integer-sort  zero 

Given an array of n integers from 1 to n with one integer repeated twice

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

Problem - Given an array of n integers from 1 to n with one integer repeated twice This can be done via normal array traversal or hash table to find duplicates. But since we are given that the integers are from 1 to n, then there are better methods available. Approach 1 - Arithmetic sum approach So, the efficient method to solve it calculate the sum of actual input array, and expected sum of the array. [Read More]
integer series  kodeknight  ranged-array  duplicate  integer  programming  Interview Question  array  integer-array 

Routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without making use of any floating point computations at all.

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

Problem Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without making use of any floating point computations at all. Solution Let (x ^ 2 + y ^2 = r ^ 2)……………………………..1 The basic idea is to draw one quadrant and replicate it to other four quadrants. Assuming the center is given as (a,b) and radius as r units, then start X from (a+r) down to (a) and start Y from (b) up to (b+r). [Read More]
kodeknight  programming  graphics  incomplete  Interview Question  maths 

Given two strings A and B, how would you find out if the characters in B were a subset of the characters in A?

 Posted on December 5, 2009  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Here is a code in c: #include <stdio .h> #include <conio .h> int isSubset(char \*a, char \*b); int main(){ char str1="defabc"; char str2="abcfed"; if(isSubset(str1, str2)==0) printf("\\nYes, characters in B=%s are a subset of characters in A=%s\\n",str2,str1); } else { printf("\\nNo, characters in B=%s are not a subset of characters in A=%s\\n",str2,str1); } getch(); return(0); } // Function to check if characters in "b" are a subset // of the characters in "a" int isSubset(char \*a, char \*b) { int letterPresent256256; int i; for(i=0; i<256; i++) letterPresentii=0; for(i=0; aii! [Read More]
kodeknight  String  two-string  Interview Question