Expand the Array from [a2b3c4d2] to [aabbbccccdd] in O(n) and O(1) Space

By rahul - Last updated: Thursday, September 18, 2014

Given an array of length 11 which contains items as [a2b3c4d2] we need to expand it to [aabbbccccdd]

The best solution I know is that start reading array from back and write it down from back of an array as I have shown below.

Expand the Array from [a2b3c4d2] to [aabbbccccdd]

This method wont take more than O(n) time and O(1) Space complexity.

If you know better or other method than this then please let us know. Write your solution below.

Filed in Interview Questions

Find the Largest number from a given array of numbers

By rahul - Last updated: Thursday, September 18, 2014

We need to find the greatest number from the elements of an array.

For Example: Array = 2, 3, 9, 4

Solution is  Arrange elements of an array in descending order like 9,4,3,2 and this is the largest number.

If you know the better solution then write it down in the Comments below

 

Filed in Interview Questions

Tell me about yourself

By rahul - Last updated: Thursday, September 18, 2014

Assume that you are sitting in front of the HR manager. Take the initiative to attend this question and tell your real answers.

Post your answer in Facebook box below.

Filed in HR Interview Questions

Get the number with maximum repetitions in a sorted array of integers

By rahul - Last updated: Thursday, August 28, 2014

This question is very common question. Given a sorted array of integers, write a function that will return the number with the biggest or maximum number of repetitions. This means that we have to find the number with the maximum repetition in a sorted array of numbers. So we need to write an algorithm to find maximum number of repetition of a number in a sorted array.

There can be various ways to do this. I am mentioning two methods to implement this.

Method1:  O(n)

Method2: Less than O(n) by using jumping logic.

Implementation of Method1 is below:

Method2 is based on jumping logic. In this algorithm we will first traverse the array till the first element is encountering. We will maintain the count of occurrence of first element. Now as we know that first number occurred N number of times then we will jump N steps till second number of array is occurring. We will jump in multiple of N, let M times. If we are encountering third number then we will step back one by one till we are getting second number of the array, let S is the number of steps we have taken back.

So second number’s occurrence can be calculated as below formula

Number of Occurrence = (M*N) – S

 

Now if we will reach to some point where remaining number of elements in an Array is less than Number of Occurrence of some number then we can skip traversing the array.

Implementation of Method2 is below:

Let us know if you have any better idea to solve this algorithm. You can post your solution in the comments below.

 

 

 

Filed in Interview Questions