## Walmart Labs Interview Question for Applications Developers

Country: India
Interview Type: In-Person

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

void ExchangeAlternate(struct node *pList)
{
while(pList)
{
if(pList->next)
{
pList->next->data = pList->data ^ pList->next->data;
pList->data = pList->data ^ pList->next->data;
pList->next->data = pList->data ^ pList->next->data;

pList = pList->next;
}

if(pList)
pList = pList->next;
}
}

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

Yep, swapping node values is a reasonable way to go. Can squeeze this a bit, possibly?

``````void ExchangeAlternate(struct node *pList)
{
while(pList && pList->next)
{
std::swap(pList->data, pList->next->data);
pList = pList->next->next;
}
}``````

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

Swap two nodes and recur for remaining list

``````ListNode* swapPairs(ListNode* head) {
}
return prev;
}``````

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

I can think of two ways to do this:
1. read two elements of the list at one time and swap them
2. Read the entire list into two separate lists, even elements to one and odds to the other, and then rebuild the lists

both approaches are O(n) and would roughly use the same memory.

Here's approach 1:

``````//definition of the list:
static class Node<T>{
Node<T> nextNode
T value;
}

public static Node<T> swapAlternates(Node<T> inputList){
if(inputList == null || inputList.nextNode == null){
return inputList;
}

Node<T> head = inputList.nextNode; // pointer to new front
Node<T> endLastSection = null; //don't have one yet
Node<T> node1 = inputList; //first node to swap
Node<T> node2 = inputList.nextNode; //second node to swap
Node<T> end = node2.nextNode; // end of the section for the swapping
node2.nextNode = node1;
node1.nextNode = end;
endLastSection = node1;
while(endLastSection != null){
node1 = endLastSection.nextNode;
if(node1 == null){
break;
}
node2 = node1.nextNode;
if(node2 == null){
break;
}
end = node2.nextNode;
endLastSection.nextNode = node2;
node2.nextNode = node1;
node1.nextNode = end;
endLastSection = node1;
}
}``````

Here's the other approach:

``````public static Node<T> swapAlternates(Node<T> inputList){
Node<T> list1End;
Node<T> list2End;
boolean list2= false;
//split into two lists
while(inputList != null){
if(list2){
list2End = inputList;
}
else{
list2End.nextNode = inputList;
list2End = list2End.nextNode;
}
list2= false;
}
else{
list1End = inputList;
}
else{
list1End.nextNode = inputList;
list1End = list1End.nextNode;
}
list2= true;
}
Node<T> temp = inputList.nextNode;
inputList.nextNode = null;
inputList = temp;
}

//rebuild the list for output
list2 = false;
inputList = list2End;
list2End = list2End.nextNode;
while(list1End != null && list2End != null){
if(list2){
inputList.nextNode = list2End;
list2End = list2End.nextNode;
list2 = false;
}
else{
inputList.nextNode = list1End;
list1End = list1End.nextNode;
list2 = true;
}
}
while(list1End != null){
inputList.nextNode = list1End;
inputList = inputList.nextNode;
list1End = list1End.nextNode;
}
while(list2End != null){
inputList.nextNode = list2End;
inputList = inputList.nextNode;
list2End = list2End.nextNode;
}
}``````

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

``````public LinkedList<String> reverseAlternate(LinkedList<String> list) {
if (list == null) return null;

for (int i = 0; i < list.size(); i+2) {
String s1 = list.get(i);
String s2 = list.get(i + 1);
}

return result;``````

}

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

Doesn't list.get(i) take i iterations to find the element and therefore operate in O(n^2) ? With a similar implementation you could do this:

``````public static List<String> reverseAlternate(List<String> list){
if(list == null) return null;
while(!list.isEmpty()){
String str1 = list.removeFirst();
if(list.isEmpty()){
break;
}
String str2 = list.removeFirst();
}
return results;
}``````

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

The observation looks correct from the Java API documentation. In .NET, ArrayList and it's generic descendent List<T> are backed by an array so would be O(n) overall. However, I'd say the point of this question is to show the interviewee understands pointers so using an array based data structure would not be a good start.

The pattern take from head of one list and push to head of another is classic for the question of reversing a singly linked list. Does the test case work for your answer?

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

Better way would be to use iterator instead of get(i) as it's anyway linear approach

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

Here's a C++/C implementation assuming you are implementing your own list.

``````typedef struct _NODE
{
struct _NODE* Next;
char Value;
} NODE, *PNODE;

// pointer (it's a reference) to reflect the swap.
// Returns the new tail on success, nullptr when the swap not possible.
static PNODE
SwapPair(
)
{
{
return nullptr;
}

return newTail;
}

// Swaps elements in list in a pairwise fashion.
// Returns a pointer to the modified lists head.
static PNODE
SwapListPairs(
)
{

PNODE current = SwapPair(retval);
while (nullptr != current)
{
current = SwapPair(current->Next);
}

return retval;
}``````

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

Generic solution of reversing linklist, set k =2 for this particular problem.

``````static LinkedListNode reverse_k (LinkedListNode head, int k) {

while (k > 0 && cur != null) {
next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
k--;
}
}

/*
* <pre>
* 1. Reverse first k nodes, and get new head of list
* 2. Get head of remaining list (Size - k) as oldhead.next will now be pointing to start of remaining list
* 3. recusrively call this function with this newHead
* 4. To build complete list, merge oldhead of old list and newhead of remaining list.
* 		oldhead.next was pointing to previous head of newlist, and it should point to newHead of remaining list.
* 		and this makes complete list. This is done recursively for all sub-lists
* </pre>
*/
return null;
}
}``````

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

``````Here is a way to do it recursively. LLN stands for Linked List Node
public static LLN reverseAlt(LLN head) {
}
LLN temp = sec.next;
return sec;
}``````

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

``````Here is a way to do it recursively. LLN stands for Linked List Node
public static LLN reverseAlt(LLN head) {
}
LLN temp = sec.next;
return sec;
}``````

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

``````public class LLNode<E>
{
public E data;
public LLNode<E> next;

public static LLNode<Integer> getList(int... a)
{
LLNode<Integer> start = new LLNode<Integer>();
start.data = a[0];

LLNode<Integer> current = start;
for (int i = 1; i < a.length; i++)
{
LLNode<Integer> next = new LLNode<Integer>();
next.data=a[i];
current.next = next;
current = next;
}
return start;
}

public static LLNode<Integer> reverse(LLNode<Integer> s, int numOfElement)
{
LLNode<Integer> end = s;
LLNode<Integer> previous = null;
LLNode<Integer> current = s;
int count = 0;
while(current!=null)
{
LLNode<Integer> temp = current.next;

current.next = previous;
previous = current;
if(temp==null || ++count == numOfElement)
{
end.next = reverse(temp, numOfElement);
s = current;
break;
}
current = temp;
}
return s;
}
}``````

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

``````public class LLNode<E>
{
public E data;
public LLNode<E> next;

public static LLNode<Integer> getList(int... a)
{
LLNode<Integer> start = new LLNode<Integer>();
start.data = a[0];

LLNode<Integer> current = start;
for (int i = 1; i < a.length; i++)
{
LLNode<Integer> next = new LLNode<Integer>();
next.data=a[i];
current.next = next;
current = next;
}
return start;
}

public static LLNode<Integer> reverse(LLNode<Integer> s, int numOfElement)
{
LLNode<Integer> end = s;
LLNode<Integer> previous = null;
LLNode<Integer> current = s;
int count = 0;
while(current!=null)
{
LLNode<Integer> temp = current.next;

current.next = previous;
previous = current;
if(temp==null || ++count == numOfElement)
{
end.next = reverse(temp, numOfElement);
s = current;
break;
}
current = temp;
}
return s;
}
}``````

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

First method is only to help writing testcase

``public static LLNode<Integer> getList(int... a)``

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

Code without using recursion .

``````static Node reverseAlternateElements(Node node) {
Node retNode1= null;
Node temp = node;
Node first = null;
Node second = null;
Node current = temp.next.next;
temp.next.next = null;
first = temp;
second = temp.next;
first.next = null;
second.next = null;
second.next = first;
temp = null;
retNode1 = second;
Node returnNodeTemp = null;
//		returnNodeTemp = returnNode;
returnNodeTemp = retNode1.next;
while (current != null ) {
temp = null;
temp = current;
if( current.next == null ) {
returnNodeTemp.next = current;
break;
}
current = current.next.next;
first = null;
second = null;
first = temp;
second = temp.next;
first.next = null;
second.next = null;
second.next = first;
returnNodeTemp.next = second;
returnNodeTemp = returnNodeTemp.next.next;
}
return retNode1;
}``````

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

``````public class LinkedList
{

class Node
{
int data;
Node next;
Node(int d) {data = d; next = null; }
}

/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);

/* 3. Make next of new Node as head */

/* 4. Move the head to point to new Node */
}

/* Inserts a new node after the given prev_node. */
public void insertAfter(Node prev_node, int new_data)
{
/* 1. Check if the given Node is null */
if (prev_node == null)
{
System.out.println("The given previous node cannot be null");
return;
}

/* 2 & 3: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);

/* 4. Make next of new Node as next of prev_node */
new_node.next = prev_node.next;

/* 5. make next of prev_node as new_node */
prev_node.next = new_node;
}

/* Appends a new node at the end.  This method is
defined inside LinkedList class shown above */
public void append(int new_data)
{
/* 1. Allocate the Node &
2. Put in the data
3. Set next as null */
Node new_node = new Node(new_data);

/* 4. If the Linked List is empty, then make the
{
return;
}

/* 4. This new node is going to be the last node, so
make next of it as null */
new_node.next = null;

/* 5. Else traverse till the last node */
while (last.next != null)
last = last.next;

/* 6. Change the next of last node */
last.next = new_node;
return;
}

/* This function prints contents of linked list starting from
the given node */
public void printList()
{
while (tnode != null)
{
System.out.print(tnode.data+" ");
tnode = tnode.next;
}
}

public void printList(Node he)
{
Node tnode = he;
while (tnode != null)
{
System.out.print(tnode.data+" ");
tnode = tnode.next;
}
}

public Node reverse()
{
Node r = e.next;
Node o = null, n=null;
while(e.next!=null)
{
o=e.next;
n=o.next;
o.next=e;
e.next=(n.next!=null)?n.next:n;
e=n;
}
System.out.println(r.data);
return r;
}

/* Driver program to test above functions. Ideally this function
should be in a separate user class.  It is kept here to keep
code compact */
public static void main(String[] args)
{

// Insert 6.  So linked list becomes 6->NUllist
llist.append(6);

// Insert 7 at the beginning. So linked list becomes
// 7->6->NUllist
llist.push(7);

// Insert 1 at the beginning. So linked list becomes
// 1->7->6->NUllist
llist.push(1);

// Insert 4 at the end. So linked list becomes
// 1->7->6->4->NUllist
llist.append(4);

// Insert 8, after 7. So linked list becomes
// 1->7->8->6->4->NUllist

llist.printList();
System.out.println("");
llist.printList(llist.reverse());
}
}``````

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.

### 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.