Hewlett Packard Interview Question
Software Engineer / DevelopersTeam: Networking
Country: United States
Interview Type: In-Person
public class Merge {
private LinkedList<String> listOne;
private LinkedList<String> listTwo;
public Merge() {
listOne = new LinkedList<String>();
listOne.add("One");
listOne.add("Two");
listOne.add("Three");
listOne.add("Four");
listTwo = new LinkedList<String>();
listTwo.add("A");
listTwo.add("B");
listTwo.add("C");
listTwo.add("D");
listTwo.add("E");
listTwo.add("F");
listTwo.add("G");
}
private int getBiggerSize() {
int result;
int sizeListOne = listOne.size();
int sizeListTwo = listTwo.size();
if(sizeListOne < sizeListTwo) {
result = sizeListTwo;
} else {
result = sizeListOne;
}
return result;
}
public void merge() {
LinkedList<String> result = new LinkedList<String>();
int len = getBiggerSize();
for(int i=0; i<len; i++) {
if(!listOne.isEmpty()) {
result.add(listOne.element());
listOne.remove();
}
if(!listTwo.isEmpty()) {
result.add(listTwo.element());
listTwo.remove();
}
}
System.out.println("List One: "+ listOne.toString());
System.out.println("List Two: "+ listTwo.toString());
System.out.println("List Merged: "+ result.toString());
}
}
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<process.h>
typedef struct node
{
int data;
struct node*link;
}node;
node*create()
{
node *start,*last,*temp;
start=NULL;
char choice;
printf("enter choice:");
fflush(stdin);
scanf("%c",&choice);
do
{
temp=(node*)malloc(sizeof(node));
printf("enter data");
scanf("%d",&(temp->data));
if(temp==NULL)
printf("not enough memory to create node");
else
{
if(start==NULL)
{
start=temp;
last=start;
}
else
{
last->link=temp;
last=temp;
}
}
printf("enter choice:");
fflush(stdin);
scanf("%c",&choice);
}while(choice=='y');
if(start!=NULL)
last->link=NULL;
return(start);
}
void print(node*start)
{
node*temp;
for(temp=start;temp!=NULL;temp=temp->link)
printf("%d\t",temp->data);
}
node*convert(node*x,node*y)
{
node*z,*temp;
z=x;
temp=z;
x=x->link;
while(x!=NULL&&y!=NULL)
{
temp->link=y;
temp=y;
y=y->link;
temp->link=x;
temp=x;
x=x->link;
}
while(x!=NULL)
{
temp->link=x;
x=NULL;
}
while(y!=NULL)
{
temp->link=y;
y=NULL;
}
return z;
}
int main()
{
node*x,*y,*z;
printf("1st ll");
x=create();
printf("2nd ll");
y=create();
z=convert(x,y);
print(z);
}
public static void merge2LinkedLists(LinkedList<String> list1, LinkedList<String> list2){
int size = Math.max(list1.size(), list2.size());
LinkedList<String> result = new LinkedList<>();
while(size > 0) {
if(!list1.isEmpty()){
result.add(list1.remove());
}
if(!list2.isEmpty()) {
result.add(list2.remove());
}
size--;
}
System.out.println(result.toString());
}
If there are no restrictions, this could be done in O(n).
Assuming the following structure:
And assuming the interface of the function... This is my solution:
A nice optimization would be to have another structure for the list head, saving the last element as such:
Then, an O(1) solution is possible:
- JonathanBarOr November 01, 2015