Amazon Interview Question for SDETs


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

- Arun September 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

- Arun September 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]

- Sergey September 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Doesn't work for

a = [1]

.

- anon September 17, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Seems pretty simple, in Haskell:

merge _ _ 0 = []
merge [] a@(_:ys) k = take k a
merge a@(_:xs) [] k = take k a
merge  (x:xs) (y:ys) k
	| x > y = x : merge xs (y:ys) (k-1)
	| otherwise = y : merge (x:xs) ys (k-1)

- evhiness September 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }

- Amrita September 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }

- Ams September 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- mrsurajpoudel.wordpress.com September 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

}

- sj September 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- sergey.a.kabanov September 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// 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;
	}

- getPDat September 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

- Anonymous September 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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;
    }
}

- Anonymous September 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }
}

- karthik.kamaraj September 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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+" ");
        }
    }

- alam.adil12 September 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- mohsum October 27, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

int *merge(int *nums1, int nums1Size, int *nums2, int nums2Size, int k) {
}

- Anonymous September 16, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More