Cracking the coding interview | Step-9

DAY 9: coding interview questions

Question 1:

Simple Encoded Array: Maya has stored few confidential numbers in an array (array of int). To ensure that others do not find the numbers easily, she has applied a simple encoding.

Encoding used : Each array element has been substituted with a value that is the sum of its original value and its succeeding element’s value.

i.e. arr[i] = original value of ​arr[i] + original value of ​arr[i+1]

e.g. value in arr[0] = original value of arr[0] + original value of arr[1]

Also note that value of last element i.e. arr[last index] remains unchanged.

For example, 

If the encoded array is {7,6,8,16,12,3}

The original array should have been {2,5,1,7,9,3}

Provided the encoded array, you are expected to find the –

First number (value in index 0) in the original array

Sum of all numbers in the original array

Write the logic in the function  findOriginalFirstAndSum(int[] input1, int input2);

where, 

input1 represents the encoded array, and 

input2 represents the number of elements in the array input1

The method is expected to –

find the value of the first number of the original array and store it in the member output1 and

find the sum of all numbers in the original array and store it in the member output2

Note that the output1 and output2 should be returned as -

- members of a Result object (if the code is being written in Java, C# or C++)

- members of a Result struct  (if the code is being written in C)

Assumption: The array elements can be positive and/or negative numbers

Example 1:

If the encoded array is {7,6,8,16,12,3}

The Original array should have been {2,5,1,7,9,3}

So, First number in original array = 2

Sum of all numbers in original array = 27

Example 2:

If the encoded array is {-2,-7,-12,-15}

The Original array should have been {8,-10,3,-15}

So, First number in original array = 8

Sum of all numbers in original array = -1

//Code:

import java.io.*;
import java.util.*;
class UserMainCode
{
 public class Result
  {
    public final int output1;
    public final int output2;
public Result(int out1,int out2){
  output1=out1;
  output2=out2;
}}
  public Result findOriginalFirstAndSum(int[] input1,int input2){
int[] arr=new int[input2];
  arr[input2-1]=input1[input2-1];
  int sum=arr[input2-1];
  for(int i=input2-2;i>=0;i--)
        {
   arr[i]=input1[i]-arr[i+1];
   sum+=arr[i];
  }
         Result r1= new Result(arr[0],sum);
   return r1;
  }
    }

Question 2: 

Decreasing sequence: Given an integer array, find the number of decreasing sequences in the array and the length of its longest decreasing sequence.

You are expected to complete the logic within the given function, 

where, 

input1 represents the integer array and,

input2 represents the number of elements in the integer array

The function should set the  output1 variable to the number of decreasing sequences in the array, and set the  output2 variable to the length of the longest decreasing sequence in the array.

Example 1: 

If  input1[ ] = {11,3,1,4,7,8,12,2,3,7} 

and  input2 = 10

output1 should be 2

output2 should be 3

Explanation: 

In the given array  input1, the decreasing sequences are “11,3,1” and “12,2”, i.e. there are two decreasing sequences in the array, and so  output1 is assigned  2. The first sequence i.e. “11,3,1” is the longer one containing  three items, when compared to the second sequence “12,2” which contains 2 items. So, the length of the longest decreasing sequence  output2 =  3.

Example 2: 

If  input1[ ] = {9} 

and  input2 = 1

output1 should be 0

output2 should be 0

Example 3: 

If  input1[ ] = {12,51,100,212,15,12,7,3,57,300,312,78,19,100,102,101,99,74,0,-5} 

and  input2 = 20

output1 should be 3

output2 should be 6

//Code:

class UserMainCode
{
public class Result{
 public final int output1;
 public final int output2;
 public Result(int out1,int out2)
 {
  output1=out1;
  output2=out2;
 }
}
public Result decreasingSeq(int[] input1,int input2)
{
 int c1=0,c2=0,max=0;
for(int i=0;i<input2-1;i++)
        {
            if(input1[i]>input1[i+1])
            {
                c1++;
            }
            if((input1[i]<input1[i+1] && c1!=0) || ((i==input2-2) && c1!=0))
            {
                if(max<c1)
                {
                    max=c1;
                }
                c2++;
                c1=0;
            }
        }
        max=max+1;
        if(c2==0)
        {
            max=0;
        }
        if(input2==0)
        {
            max=0;
            c2=0;
        }
        Result r1= new Result(c2,max);
        return r1;
}
}

Question 3: 

Find the Most Frequently Occurring Digit in a series of numbers.

Kamal is a data analyst in a lottery management organization.

One of the tasks assigned to Kamal is to find the Most Frequently Occurring Digit in a series of input numbers.

Below are a couple of examples to illustrate how to find the Most Frequently Occurring Digit in a series of input numbers.

Example1 –

If the series of input numbers are [1237, 262, 666, 140]

We notice that,

0 occurs 1 time

1 occurs 2 times

2 occurs 3 times

3 occurs 1 time

4 occurs 1 time

5 occurs 0 times

6 occurs 4 times

7 occurs 1 time

8 occurs 0 times

9 occurs 0 times

We observe that –

4 is the highest frequency in this series, and,

6 is the digit that occurs 4 times.

Thus, the Most Frequently Occurring Digit in this series is 6.

NOTE: If more than one digit occur the most frequent time, then the largest of the digits should be chosen as the answer. See below example for clarity on this point.

Example2 –

If the series of input numbers is [1237, 202, 666, 140]

We notice that,

0 occurs 2 times

1 occurs 2 times

2 occurs 3 times

3 occurs 1 time

4 occurs 1 time

5 occurs 0 times

6 occurs 3 times

7 occurs 1 time

8 occurs 0 times

9 occurs 0 times

We observe that –

3 is the highest frequency in this series, and,

2 and 6 are the digits that occur 3 times.

The larger of the two digits (2 and 6) is 6. Thus, the Most Frequently Occurring Digit in this series is 6.

Help Kamal by writing the logic in the function mostFrequentlyOccurringDigit for finding the Most Frequently Occurring Digit in the provided series of numbers.

The function takes two inputs - 

input1 is the array of numbers

input2 is the number of elements in the array input1

//Code:

import java.io.*;
import  java.util.*;
class UserMainCode
{
public int mostFrequentlyOccurringDigit(int[] input1,int input2)
{
               int[] arr=new int[10];
  for(int i=0;i<input2;i++)
  {
    while(input1[i]!=0){
    int rem=input1[i]%10;
    arr[rem]++;
    input1[i]/=10;
   }
 }
 int max=0;
 int higest_occur_number=0;
 for(int i=0;i<10;i++)
 {
  if(arr[i]>=max)
  {max=arr[i];
    higest_occur_number=i;
  }
 }
 return higest_occur_number;
}}

Cracking the coding interview | Step-8   Cracking the coding interview | Step-10

C/C++/java/Python practice questions with solution

SQL Queries   Android Project Ideas