Amazon Interview Question
SDETsCountry: United States
Interview Type: In-Person
public static class Node {
int data;
Node next;
public Node(int data){
this.data = data;
this.next = null;
}
}
public static void main(String[] args) {
Node head1 = new Node(1);
head1.next = new Node(3);
head1.next.next = new Node(5);
head1.next.next.next = new Node(7);
Node head2 = new Node(2);
head2.next = new Node(4);
head2.next.next = new Node(6);
head2.next.next.next = new Node(8);
Node result = sortedMergeK(head1,head2,5);
while (result!= null){
System.out.println(result.data);
result = result.next;
}
}
public static Node sortedMergeK(Node list1, Node list2,int k){
Node result = null;
if (k < 1){
return null;
}else if ((list1 == null) && (list2 ==null)){
return null;
}else if (list1 == null) {
k--;
result = list2;
result.next = sortedMergeK(null,list2.next,k);
}else if (list2 == null) {
k--;
result = list1;
result.next = sortedMergeK(list1.next,null,k);
}else if (list1.data<list2.data){
k = k-1;
result = list1;
result.next = sortedMergeK(list1.next,list2,k);
}else {
k = k-1;
result = list2;
result.next = sortedMergeK(list1,list2.next,k);
}
return result;
}
UPD:
def merge_k(k, a, b):
result = []
i, j = 0, 0
while i + j < k and i < len(a) and j < len(b):
if a[i] < b[j]:
result.append(a[i])
i += 1
else:
result.append(b[j])
j += 1
while i + j < k and i < len(a):
result.append(a[i])
i += 1
while i + j < k and j < len(b):
result.append(b[j])
j += 1
return result
print(merge_k(4, [1,2,3,4], [2,3,4,5])) #[1, 2, 2, 3]
print(merge_k(8, [1,2,3,4], [2,3,4,5])) #[1, 2, 2, 3, 3, 4, 4, 5]
print(merge_k(15, [1,2,3,4], [2,3,4,5])) #[1, 2, 2, 3, 3, 4, 4, 5]
print(merge_k(15, [1], [2,3,4,5])) #[1, 2, 3, 4, 5]
private static List mergeList(ArrayList<Integer> arr1, ArrayList<Integer> arr2, int k){
List <Integer> resultArr = new ArrayList<>(k);
int size = 0;
int i = 0;
int j = 0;
if(arr1.size() == 0 && arr2.size() == 0){
return null;
} else if (arr1.size() == 0){
size = arr2.size() > k ? k:arr2.size();
resultArr = arr2.subList(0,size);
return resultArr;
} else if (arr2.size() == 0){
size = arr1.size() > k ? k:arr1.size();
resultArr = arr1.subList(0,size);
return resultArr;
}
while(k > 0){
if(i >= arr1.size() && j >= arr2.size() ){
break;
} else if(i >= arr1.size() && j < arr2.size() ){
resultArr.add(arr2.get(j++));
k -=1;
} else if(i < arr1.size() && j >= arr2.size() ){
resultArr.add(arr1.get(i++));
k -=1;
} else if(i < arr1.size() && j < arr2.size() ){
if(arr1.get(i) == arr2.get(j)) {
resultArr.add(arr1.get(i++));
resultArr.add(arr2.get(j++));
k -=2;
} else if(arr1.get(i) < arr2.get(j)){
resultArr.add(arr1.get(i++));
k -=1;
} else {
resultArr.add(arr2.get(j++));
k -=1;
}
}
}
return resultArr;
}
private static List mergeList(ArrayList<Integer> arr1, ArrayList<Integer> arr2, int k){
List <Integer> resultArr = new ArrayList<>(k);
int size = 0;
int i = 0;
int j = 0;
if(arr1.size() == 0 && arr2.size() == 0){
return null;
} else if (arr1.size() == 0){
size = arr2.size() > k ? k:arr2.size();
resultArr = arr2.subList(0,size);
return resultArr;
} else if (arr2.size() == 0){
size = arr1.size() > k ? k:arr1.size();
resultArr = arr1.subList(0,size);
return resultArr;
}
while(k > 0){
if(i >= arr1.size() && j >= arr2.size() ){
break;
} else if(i >= arr1.size() && j < arr2.size() ){
resultArr.add(arr2.get(j++));
k -=1;
} else if(i < arr1.size() && j >= arr2.size() ){
resultArr.add(arr1.get(i++));
k -=1;
} else if(i < arr1.size() && j < arr2.size() ){
if(arr1.get(i) == arr2.get(j)) {
resultArr.add(arr1.get(i++));
resultArr.add(arr2.get(j++));
k -=2;
} else if(arr1.get(i) < arr2.get(j)){
resultArr.add(arr1.get(i++));
k -=1;
} else {
resultArr.add(arr2.get(j++));
k -=1;
}
}
}
return resultArr;
}
vector<int> merge_k_elements(vector<int>& a, vector<int>& b, size_t k) {
assert( a.size() + b.size() >= k );
vector<int> merged_vec(k);
size_t i = 0, // a's iterator
j = 0; // b's iterator
while( i + j < k ){
if( j >= b.size() || ( i < a.size() && a[i] <= b[j] ) ) {
merged_vec[i + j] = a[i];
i++;
}
else {
merged_vec[i + j] = b[j];
j++;
}
}
return merged_vec;
}
assuming lists are sorted in ascending order
public static int[] getmergedarray(ArrayList<Integer> l1,
ArrayList<Integer> l2, int k) {
int[] merged = new int[k];
int l1_index = 0;
int l2_index = 0;
for (int i = 0; i < k; i++) {
if (l1.size() > l1_index && l2.size() > l2_index
&& l1.get(l1_index) <= l2.get(l2_index)) {
merged[i] = l1.get(l1_index);
l1_index++;
} else if (l1.size() > l1_index && l2.size() > l2_index) {
merged[i] = l2.get(l2_index);
l2_index++;
} else if (l1.size() > l1_index) {
merged[i] = l1.get(l1_index);
l1_index++;
}
else if (l2.size() > l2_index) {
merged[i] = l2.get(l2_index);
l2_index++;
}
}
return merged;
}
}
class COurList
{
public:
COurList()
{
iValue = 0;
pNext = 0;
}
int iValue;
COurList* pNext;
};
//.............................................................................................................
// Merge 2 sorted lists:
COurList* MergeSortedLists(COurList* pHead1, COurList* pHead2)
{
COurList *pCurrent1, *pCurrent2, *pCurrentRez, *pResultHead;
pCurrent1 = pHead1;
pCurrent2 = pHead2;
// what if we have only one valid pointer?
if ((!pHead1) && (pHead2))
return pHead2;
if ((!pHead2) && (pHead1))
return pHead1;
// first, set up the result header:
if (pCurrent1->iValue < pCurrent2->iValue)
{
pResultHead = pHead1;
pCurrent1 = pHead1->pNext;
pCurrentRez = pResultHead;
}
else
if (pCurrent1->iValue > pCurrent2->iValue)
{
pResultHead = pHead2;
pCurrent2 = pHead2->pNext;
pCurrentRez = pResultHead;
}
else
if (pCurrent1->iValue > pCurrent2->iValue)
{
pResultHead = pHead1;
pCurrent1 = pHead1->pNext;
pResultHead->pNext = pHead2;
pCurrentRez = pHead2;
pCurrent2 = pHead2->pNext;
}
// Now go through the list:
while (pCurrent1 && pCurrent2)
{
if (pCurrent1->iValue < pCurrent2->iValue)
{
pCurrentRez->pNext = pCurrent1;
pCurrentRez = pCurrent1;
pCurrent1 = pCurrent1->pNext;
}
else
if (pCurrent1->iValue > pCurrent2->iValue)
{
pCurrentRez->pNext = pCurrent2;
pCurrentRez = pCurrent2;
pCurrent2 = pCurrent2->pNext;
}
else
if (pCurrent1->iValue > pCurrent2->iValue)
{
pCurrentRez->pNext = pCurrent1;
pCurrentRez = pCurrent1;
pCurrentRez->pNext = pCurrent2;
pCurrentRez = pCurrent2;
pCurrent1 = pCurrent1->pNext;
pCurrent2 = pCurrent2->pNext;
}
}//while
// list remainder:
if (pCurrent1)
pCurrentRez->pNext = pCurrent1;
if (pCurrent2)
pCurrentRez->pNext = pCurrent2;
if (!pCurrent1 && !pCurrent2)
pCurrentRez->pNext = NULL;
return pResultHead;
}
//.............................................................................................................
void CutToFirstKelements(COurList* pHead, const int& k)
{
int i;
if (k <= 0) pHead=NULL;
for (i = 0; i < k - 1; ++i)
pHead = pHead->pNext;
pHead->pNext = NULL;
}
// Using the power of recursion:
public static Node mergerSortedKthList(Node list1, Node list2, int k) {
if (k == 0) {
return null;
}
Node node;
if (list1.val > list2.val) {
node = list2; k = k-1;
node.next = mergerSortedKthList(list1, list2.next, k);
} else {
node = list1; k = k-1;
node.next = mergerSortedKthList(list1.next, list2, k);
}
return node;
}
public class MergeSortedList {
public static void main(String args[]) {
MergeSortedList merge = new MergeSortedList();
int i = 0;
List<Integer> l1 = new ArrayList<>();
List<Integer> l2 = new ArrayList<>();
Random r = new Random();
while (i < 3) {
l1.add(r.nextInt((i+2)*2));
l2.add(r.nextInt((i+2)*2));
i++;
}
System.out.println(merge.buildSortedListWithLen(l1, l2, 3));
}
List<Integer> buildSortedListWithLen(List<Integer> a, List<Integer> b, int len) {
List<Integer> sortedList = new ArrayList<>(len);
if (a == null || b == null) {
return null;
}
System.out.println(a);
System.out.println(b);
int i = 0, j = 0;
while (sortedList.size() < len) {
if (a.get(i) <= b.get(j)) {
sortedList.add(a.get(i++));
} else {
sortedList.add(b.get(j++));
}
}
return sortedList;
}
}
public class MergeSortedList {
public static void main(String args[]) {
MergeSortedList merge = new MergeSortedList();
int i = 0;
List<Integer> l1 = new ArrayList<>();
List<Integer> l2 = new ArrayList<>();
Random r = new Random();
while (i < 3) {
l1.add(r.nextInt((i+2)*2));
l2.add(r.nextInt((i+2)*2));
i++;
}
System.out.println(merge.buildSortedListWithLen(l1, l2, 3));
}
List<Integer> buildSortedListWithLen(List<Integer> a, List<Integer> b, int len) {
List<Integer> sortedList = new ArrayList<>(len);
if (a == null || b == null) {
return null;
}
System.out.println(a);
System.out.println(b);
int i = 0, j = 0;
while (sortedList.size() < len) {
if (a.get(i) <= b.get(j)) {
sortedList.add(a.get(i++));
} else {
sortedList.add(b.get(j++));
}
}
return sortedList;
}
}
package com.samples;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/**
* Created by kkama4 on 9/17/16.
*/
public class MergeSortedList {
public static void main(String args[]) {
MergeSortedList merge = new MergeSortedList();
int i = 0;
List<Integer> l1 = new ArrayList<>();
List<Integer> l2 = new ArrayList<>();
Random r = new Random();
while (i < 5) {
l1.add(r.nextInt((i+2)*2));
l2.add(r.nextInt((i+2)*2));
i++;
}
System.out.println(merge.buildSortedListWithLen(l1.subList(0, 2), l2.subList(0, 4), 4));
}
List<Integer> buildSortedListWithLen(List<Integer> a, List<Integer> b, int len) {
List<Integer> sortedList = new ArrayList<>(len);
if (a == null || b == null) {
return null;
}
System.out.println(a);
System.out.println(b);
int i = 0, j = 0;
while (sortedList.size() < len) {
if (i < a.size() && j < b.size())
if (a.get(i) <= b.get(j)) {
sortedList.add(a.get(i++));
} else {
sortedList.add(b.get(j++));
} else if (j < b.size()) {
sortedList.add(b.get(j++));
} else if (i < a.size()){
sortedList.add(a.get(i++));
}
}
return sortedList;
}
}
I wrote the code taking arrays instead of lists. Suggest if there is any scope of optimization.
public void mergeArraysUptoK(int[] a, int[] b, int n){
int i=0,j=0,k=0;
int[] mergedArr = new int[n];
while (k<n&&i<a.length&&j<b.length){
if (a[i]<b[j]){
mergedArr[k]=a[i];
i++;
}else{
mergedArr[k]=b[j];
j++;
}
k++;
}
while (k<n&&i<a.length){
mergedArr[k]=a[i];
i++;
k++;
}
while (k<n&&j<b.length){
mergedArr[k]=b[j];
j++;
k++;
}
for (int val:mergedArr){
System.out.print(val+" ");
}
}
def sort_k_elem():
l1 = [1, 13, 50, 184, 187, 239, 245, 262, 326, 391, 428]
l2 = [10, 74, 130, 151, 239, 336, 457, 494,517, 529, 544,]
k = int(input())
a = []
if (len(l1) and len(l2))< k:
print("enter the valid range of k")
else:
while k > 0:
if l1[0]<l2[0]:
a.append(l1[0])
l1.pop(0)
else:
a.append(l2[0])
l2.pop(0)
k -=1
print(a)
public static class Node {
- Arun September 16, 2016int data;
Node next;
public Node(int data){
this.data = data;
this.next = null;
}
}
public static void main(String[] args) {
Node head1 = new Node(1);
head1.next = new Node(3);
head1.next.next = new Node(5);
head1.next.next.next = new Node(7);
Node head2 = new Node(2);
head2.next = new Node(4);
head2.next.next = new Node(6);
head2.next.next.next = new Node(8);
Node result = sortedMergeK(head1,head2,5);
while (result!= null){
System.out.println(result.data);
result = result.next;
}
}
public static Node sortedMergeK(Node list1, Node list2,int k){
Node result = null;
if (k < 1){
return null;
}else if ((list1 == null) && (list2 ==null)){
return null;
}else if (list1 == null) {
k--;
result = list2;
result.next = sortedMergeK(null,list2.next,k);
}else if (list2 == null) {
k--;
result = list1;
result.next = sortedMergeK(list1.next,null,k);
}else if (list1.data<list2.data){
k = k-1;
result = list1;
result.next = sortedMergeK(list1.next,list2,k);
}else {
k = k-1;
result = list2;
result.next = sortedMergeK(list1,list2.next,k);
}
return result;
}