N/A Interview Question
Software Engineer / DevelopersTeam: ERP
Country: India
public class ArrayEx1 {
/**
* @param args
*
* Having a list of int [1,1,1,3,1,2,1,1,4,1]
* Output needed [1,5,6,3,7,2,8,9,4,10]
* without changing 2,3,4
*
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = {1,1,1,3,1,2,1,1,4,1};
int len = a.length;
System.out.println("Before Changing");
for(int i : a){
System.out.print(i+",");
}
int j = 5;
for(int i=1;i<len;i++){
if(a[i]<2){
a[i]=j++;
}
}
System.out.println();
System.out.println("After Changing ");
for(int k : a){
System.out.print(k+",");
}
}
}
Without much more description of what you're asking, I'm assuming that you mean to remove duplicate numbers in the array while preserving the original value when possible.
I can do this in O(n) with the following algorithm:
-Scan the array to figure out which numbers are already present
-for each number, replace it if necessary using a 1-upped counted value that skips already used numbers
public static void replaceDups(int[] arr){
HashMap<Integer, Boolean> isSafe = new HashMap<Integer, Boolean>();
for(int i : arr){
isSafe.put(i, true);
}
int c = 1;
for( int i = 0; i < arr.length; i++){
Boolean isUsed = isSafe.get(arr[i]);
if(!isUsed){
while(used.containsKey(c)){
c++;
}
arr[i] = c;
c++;
}
else{
isSafe.put(arr[i], false);
}
}
}
public class ArrayEx1 {
/**
* @param args
*
* Having a list of int [1,1,1,3,1,2,1,1,4,1]
* Output needed [1,5,6,3,7,2,8,9,4,10]
* without changing 2,3,4
*
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = {1,1,1,3,1,2,1,1,4,1};
int len = a.length;
System.out.println("Before Changing");
for(int i : a){
System.out.print(i+",");
}
int j = 5;
for(int i=1;i<len;i++){
if(a[i]<2){
a[i]=j++;
}
}
System.out.println();
System.out.println("After Changing ");
for(int k : a){
System.out.print(k+",");
}
}
}
Not knowing full description I can write this simple one:
public class Driver
{
public static void main(String[] ars)
{
int[] arr = {1,1,1,3,1,2,1,1,4,1};
int max = Integer.MIN_VALUE;
for (int val : arr)
{
max = (max < val) ? val: max;
}
for (int i=1; i<arr.length; i++)
{
if (arr[i] != 2 && arr[i] != 3 && arr[i] != 4)
{
arr[i] += max;
max = arr[i];
}
}
for(int val : arr)
{
System.out.print(val + " ");
}
} // end of main
} // end of class
public class ArrayEx1 {
/**
* @param args
*
* Having a list of int [1,1,1,3,1,2,1,1,4,1]
* Output needed [1,5,6,3,7,2,8,9,4,10]
* without changing 2,3,4
*
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = {1,1,1,3,1,2,1,1,4,1};
int len = a.length;
System.out.println("Before Changing");
for(int i : a){
System.out.print(i+",");
}
int j = 5;
for(int i=1;i<len;i++){
if(a[i]<2){
a[i]=j++;
}
}
System.out.println();
System.out.println("After Changing ");
for(int k : a){
System.out.print(k+",");
}
}
}
#include<stdio.h>
#include<stdlib.h>
int main(int argc, char *argv[])
{
int list[] = {1,1,1,3,1,2,1,1,4,1};
int max= 0,i;
int len = sizeof(list)/sizeof(int);
for(i=0;i<len;i++)
{
if(max<list[i])
{
max= list[i];
}
}
for(i=1;i<len;i++)
{
if(list[i] == 1)
{
list[i] = ++max;
}
}
for(i=0;i<len;i++)
{
printf("%d\n",list[i]);
}
return 0;
}
~
~
public class Logic {
void change(int a[])
{
int temp = 5 ;
int n = a.length;
for(int i = 1 ; i<n ; i++)
{
if(a[i]==3 || a[i]==2 || a[i]==4)
continue ;
a[i]= temp++ ;
}
}
public static void main(String args[])
{
Logic l = new Logic();
int a[]= {1 , 1 , 1 , 3 , 1 , 2 , 1 , 1 , 4 , 1};
int m = a.length ;
l.change(a);
for(int j=0 ; j<m ; j++)
System.out.print(" "+a[j]);
}
}
and
public static void main (String args[]) {
int input [] = new int[] {1,1,1,3,1,2,1,1,4,1};
int maxValue = 0;
// find max value
for (int i : input) {
if (i > maxValue) {
maxValue = i;
}
}
// core logic
Map<Integer, Integer> map = new HashMap <Integer, Integer> ();
int output [] = new int[input.length];
int counter = 0;
for (int i : input) {
if (map.get(i) == null) {
map.put (i, 0);
output [counter++] = i;
}
else {
output[counter++] = ++maxValue;
}
}
// print values
for (int i : output) {
System.out.print (i + " ");
}
}
and
public class MakeConsecutiveList
{
public static void main(String [] args)
{
int [] arr={1,1,1,3,1,2,1,1,4,1};
int max=0;
for(int ele:arr)
{
if(ele>max)
{
max=ele;
}
}
for(int i=0;i<arr.length-1;i++)
{
for(int j=i+1;j<arr.length;j++)
{
if(arr[i]==arr[j] )
{
arr[j]=++max;
}
}
}
for(int ele:arr)
System.out.print(ele+" ");
}
public static void removeDuplicatedByReplacingNextNumbers(int[] arr){
HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();
int maxValue=0;
for(int i=0;i<arr.length;i++){
if(!map.containsKey(arr[i])){
map.put(arr[i],false);
}
if(arr[i] > maxValue){
maxValue = arr[i];
}
}
for(int j=0;j<arr.length;j++){
if(!map.get(arr[j])){
map.put(arr[j], true);
}else{
maxValue = maxValue+1;
arr[j] = maxValue;
}
}
}
public static void main(String[] args) {
Integer a[] = { 1, 1, 1, 3, 1, 2, 1, 1, 4, 1 };
LinkedList<Integer> ll = new LinkedList<Integer>();
boolean found = false;
int max = 0;
for (int i = 0; i < a.length; i++) {
max = max > a[i] ? max : a[i];
if (!found) {
if (a[i] == 1)
found = true;
} else {
if (a[i] == 1) {
ll.add(i);
}
}
}
while (!ll.isEmpty()) {
a[ll.removeFirst()] = ++max;
}
System.out.println(Arrays.toString(a));
public class ArrayEx1 {
/**
* @param args
*
* Having a list of int [1,1,1,3,1,2,1,1,4,1]
* Output needed [1,5,6,3,7,2,8,9,4,10]
* without changing 2,3,4
*
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = {1,1,1,3,1,2,1,1,4,1};
int len = a.length;
System.out.println("Before Changing");
for(int i : a){
System.out.print(i+",");
}
int j = 5;
for(int i=1;i<len;i++){
if(a[i]<2){
a[i]=j++;
}
}
System.out.println();
System.out.println("After Changing ");
for(int k : a){
System.out.print(k+",");
}
}
}
#include<iostream>
using namespace std;
int safe(int i,int count[])
{
for(int j=1;j<10;j++)
{
if(count[j]==0)
{
count[j]=1;
return j;
break;
}
}
}
int main()
{
int a[]={1,1,1,1,3,1,2,4,1};
int n=sizeof(a)/sizeof(a[0]);
int count[10]={0};
for(int i=0;i<n;i++)
{
count[a[i]]++;
}
cout<<a[0];
for(int i=1;i<n;i++)
{
if(count[a[i]]==1)
{
cout<<a[i];
}
else if(count[a[i]]>1)
{
int ind=safe(a[i],count);
cout<<ind;
}
}
}
#include<iostream>
using namespace std;
int safe(int i,int count[])
{
for(int j=1;j<10;j++)
{
if(count[j]==0)
{
count[j]=1;
return j;
break;
}
}
}
int main()
{
int a[]={1,1,1,1,3,1,2,4,1};
int n=sizeof(a)/sizeof(a[0]);
int count[10]={0};
for(int i=0;i<n;i++)
{
count[a[i]]++;
}
cout<<a[0];
for(int i=1;i<n;i++)
{
if(count[a[i]]==1)
{
cout<<a[i];
}
else if(count[a[i]]>1)
{
int ind=safe(a[i],count);
cout<<ind;
}
}
}
# list = [1,1,1,3,1,2,1,1,4,1]
# result = [1, 5, 6, 3, 7, 2, 8, 9, 4, 10]
list = [1,1,1,3,1,2,1,1,4,1]
hash = Hash.new(0)
list.each do |element|
hash[element] += 1
end
i = counter = 1
while i < list.size
if hash[list[i]] > 1
until hash[counter].zero? do
counter += 1
end
list[i] = counter
counter += 1
end
i += 1
end
puts 'Result: ' + list.to_s
/*
c language program
Linked list problem
input [1,3,1,4,1,1,6,]
output[2,3,3,4,4,5,6]
note:- only change 1 value given input
*/
#include<stdio.h>
#include<malloc.h>
int a=0;
struct Node{
int data;
struct Node *next;
}*head=NULL;
void insert(int);
void show();
main()
{
int value;
char choise='y';
while(choise=='Y'||choise=='y')
{
printf("\nEnter integer values:-");
scanf("%d",&value);
insert(value);
fflush(stdin);
printf("\nEneter another element (y/n):-");
scanf("%c",&choise);
}
show();
}
void insert(int value)
{
struct Node *temp=head,*element=(struct Node*)malloc (sizeof(struct Node));
element->data=value;
if(head==NULL)
{
element->next=head;
head=element;
}
else
{
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=element;
element->next=NULL;
}
}
void show()
{
printf("\n");
struct Node *temp=head;
while(temp!=NULL)
{
if(temp->data==1)
{a++;
printf(" %d",(temp->data)+a);
}
else
printf(" %d",temp->data);
temp=temp->next;
}
}
/*
Linked list problem
input [1,3,1,4,1,1,6,]
output[2,3,3,4,4,5,6]
note:- only change 1 value given input
*/
#include<stdio.h>
#include<malloc.h>
int a=0;
struct Node{
int data;
struct Node *next;
}*head=NULL;
void insert(int);
void show();
main()
{
int value;
char choise='y';
while(choise=='Y'||choise=='y')
{
printf("\nEnter integer values:-");
scanf("%d",&value);
insert(value);
fflush(stdin);
printf("\nEneter another element (y/n):-");
scanf("%c",&choise);
}
show();
}
void insert(int value)
{
struct Node *temp=head,*element=(struct Node*)malloc (sizeof(struct Node));
element->data=value;
if(head==NULL)
{
element->next=head;
head=element;
}
else
{
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=element;
element->next=NULL;
}
}
void show()
{
printf("\n");
struct Node *temp=head;
while(temp!=NULL)
{
if(temp->data==1)
{a++;
printf(" %d",(temp->data)+a);
}
else
printf(" %d",temp->data);
temp=temp->next;
}
}
Here's O(1) solution in Python. Performs exactly what is requested and handles all edge cases in a robust way with 0 overhead. I exhaustively tested it on ALL possible inputs.
Sorry, couldn't resist :)
- Visitor January 01, 2015