Zycus Interview Question
Software Engineer / DevelopersFor the first one i have done this recursively but iam not sure that it was right or worng can anyone help on this part...
for Second question
i have used
missingElement=0;
for(int i=1; i<n;i++)
{
missingElement^=i;
}
I think xoring would be the most optimised way..
well this only when duplicates are not allowed.
can any one know the answer
For question 1:
void first_second(int* a, int n, int* first, int* second)
{
int first1, second1;
if (n < 0) {
first = -infty;
second = -infty;
}
else {
first_second(a,n-1,&first1,&second1);
if (a[n] > first1)
*first = a[n];
*second = first1;
}
else if (a[n] > second1) {
*first = first1;
*second=a[n];
}
else {
*first = first1;
*second = second1;
}
}
Assuming we have to find a missing element in an unsorted set of n consecutive positive integers 1..n
Use formula Sum(1..n) = n(n+1)/2 to find what the sum of n consecutive integers starting from 1 should be.
Then take the actual sum of numbers in the array = S.
Missing integer = (n(n+1)/2) - S.
This solution can be adapted for consecutive numbers starting with a number >1
It can also be adapted for consecutive numbers starting with a negative number.
This algorithm runs in O(n). We have to handle errors such as integer overflow and use long data type if needed.
This solution is better than sorting the array and then iterating to find the missing element. Such an approach will take O(n. log(n)).
But the approach u have mentioned here is for consecutive nos. It is not a generic solution.
and besides, to sum up all elements, it seems like you need to iterate through them somehow, with a loop for example:)
Here is the code for part1..
#include<stdio.h>
int find(int * a, int n, int largest, int second);
void main()
{
int n, i, a[100],largest = 0 ,second = 0;
printf("Enter the no. of elements of the array\n");
scanf("%d", &n);
printf("Enter the elements of the array\n");
for(i = 0 ;i<n; i++)
scanf("%d", &a[i]);
if(n == 1)
printf("No Second largest element exist");
else
{
largest = a[0];
second = a[1];
second = find(a,n,largest,second);
if(second == -1)
printf("No Second largest element exist");
else
printf("The second largest element is %d\n", second);
}
}
int find(int * a, int n, int largest, int second)
{
int temp;
static int start = 0;
if(start == n)
{
if(second == largest)
return -1;
else
return second;
}
if(a[start] > largest)
{
temp = largest;
largest = a[start];
second = temp;
}
start++;
second = find(a,n,largest,second);
}
The answer of first one would be like this:
int SecondL(int[] arr,int i)
{
if (i<n)
{
if(arr[i]>mark1)
{
mark2=mark1;
mark1=arr[i];
}
SecondL(arr,++i);
}
else
return mark2;
return mark2;
}
for a given array int[] arr ={5,8,2,10,9,6}, the above program will return 8 as 2nd largest element instead of 9.
The program should be as:
class SecondLargestElOfArray {
static int[] arr = {5,8,2,10,9,6};
static int len = arr.length;
private static int m1 = arr[0];
private static int m2 =0;
private static int i=1;
public static void main(String[] args){
calculateValue(arr,i);
System.out.println("2nd largest element is :- "+m2);
}
private static void calculateValue(int[] arr,int i){
if(i<len){
if(arr[i]>m1){
m2=m1;
m1=arr[i];
}
else if(arr[i]>m2){
m2 = arr[i];
}
calculateValue(arr,++i);
}
}
}
The simplest solution for the 1st one to find the 2nd largest i tried is,
private static void fun3()
{
int[] arr = {0,12,32,21,24,144,22,124,2,54};
int l = arr[0];
int l2=0;
for(int i=0;i<arr.length;i++)
{
if(arr[i] > l)
{
l = arr[i];
}
else if(l2<arr[i] && l2 < l )
{
l2=arr[i];
}
}
System.out.println("Largest "+l +", 2nd Lrgest"+l2);
}
I have a very simple logic to find second largest number in array.
I am using array basic functions here
1) Find the max number from array by max() function. & put that max number into another array.
2) Now take the difference of above two arrays by array_diff() function. It will return u a new array without that largest number.
3) Now again put max() function on third array which we got from array_diff() function.
& this number is second largest number. according to question.
Code :
<?php
/// get the second largest number in array without using loop
$array = array(9,10,5,19,678,45,89);
// get the max number in array
$max[] = max($array);
print_r($array);
$second_array = array_diff($array,$max);
//print_r($second_array);
$second_max = max($second_array);
print_r($second_max);
?>
How is this for the first, this is more like pseudo code then actual Java code.
Class Test{
static int maxPos;
static int secondMax(int i){
if(i == arr.length - 1){
maxPos = i;
return arr[secondMaxPos];
}
int secondMax = secondMax(i+1);
int max = arr[maxPos];
int current = arr[i];
if(current > max){
maxPos = i;
return max;
}else if(current > secondMax){
return current;
}
return secondMax;
}
p s v m(){
int max = secondMax(0);
}
}
corrected
Class Test{
static int maxPos;
static int [] arr;
static populateArray(String[] numbers){
// code to populate array
}
static int secondMax(int i){
if(i == arr.length - 1){
maxPos = i;
return arr[i];
}
int secondMax = secondMax(i+1);
int max = arr[maxPos];
int current = arr[i];
if(current > max){
maxPos = i;
return max;
}
if(current > secondMax){
return current;
}
return secondMax;
}
p s v m(String[] args){
populateArray(args);
int secondMax = Test.secondMax(0);
}
}
// How to find a second largest number within an array without using any loop.
public class Test {
public static int findSecondHigest(int[] arr) {
int firstHighest = arr[0], secondHigest = firstHighest;
for(int i = 0; i<arr.length; i++) {
if(arr[i] > firstHighest) {
secondHigest = firstHighest;
firstHighest = arr[i];
}
}
System.out.println(firstHighest+", "+secondHigest);
return 0;
}
public static void main(String[] args) {
int[] arr = { -5, 8, -2, 2, -4, 9, 5, -9, 3, -8, -3, 7, 4, -7, 10 };
System.out.println(Test.findSecondHigest(arr));
}
}
How to find a second largest number within an array without using any loop:::::::
- vivek January 14, 2011#include<stdio.h>
int find(int * a, int n, int largest, int second);
void main()
{
int n, i, a[100],largest = 0 ,second = 0;
printf("Enter the no. of elements of the array\n");
scanf("%d", &n);
printf("Enter the elements of the array\n");
for(i = 0 ;i<n; i++)
scanf("%d", &a[i]);
if(n == 1)
printf("No Second largest element exist");
else
{
largest = a[0];
second = a[1];
second = find(a,n,largest,second);
if(second == -1)
printf("No Second largest element exist");
else
printf("The second largest element is %d\n", second);
}
}
int find(int * a, int n, int largest, int second)
{
int temp;
static int start = 0;
if(start == n)
{
if(second == largest)
return -1;
else
return second;
}
if(a[start] > largest)
{
temp = largest;
largest = a[start];
second = temp;
}
else if(a[start]>second)
{
second=a[start];
}
start++;
second = find(a,n,largest,second);
}