Walmart Labs Interview Question Applications Developers
Country: India
Interview Type: In-Person
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;
}
return head;
}
Here's the other approach:
public static Node<T> swapAlternates(Node<T> inputList){
Node<T> list1Head;
Node<T> list1End;
Node<T> list2Head;
Node<T> list2End;
boolean list2= false;
//split into two lists
while(inputList != null){
if(list2){
if(list2Head == null){
list2Head = inputList;
list2End = inputList;
}
else{
list2End.nextNode = inputList;
list2End = list2End.nextNode;
}
list2= false;
}
else{
if(list1Head == null){
list1Head = inputList;
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;
list1End = list1Head;
list2End = list2Head;
inputList = list2End;
Node<T> head = inputList;
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;
}
return head;
}
public LinkedList<String> reverseAlternate(LinkedList<String> list) {
if (list == null) return null;
LinkedList<String> result = new LinkedLis<>();
for (int i = 0; i < list.size(); i+2) {
String s1 = list.get(i);
String s2 = list.get(i + 1);
result.add(s2);
result.add(s1);
}
return result;
}
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;
LinkedList<String> results = new LinkedList<String>();
while(!list.isEmpty()){
String str1 = list.removeFirst();
if(list.isEmpty()){
results.add(str1);
break;
}
String str2 = list.removeFirst();
results.add(str2);
results.add(str1);
}
return results;
}
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?
Here's a C++/C implementation assuming you are implementing your own list.
typedef struct _NODE
{
struct _NODE* Next;
char Value;
} NODE, *PNODE;
// Swaps node pointed to by head with it's successor and updates the head
// pointer (it's a reference) to reflect the swap.
// Returns the new tail on success, nullptr when the swap not possible.
static PNODE
SwapPair(
PNODE& head
)
{
if (nullptr == head || nullptr == head->Next)
{
return nullptr;
}
PNODE newHead = head->Next;
PNODE newTail = head;
newTail->Next = newHead->Next;
newHead->Next = newTail;
head = newHead;
return newTail;
}
// Swaps elements in list in a pairwise fashion.
// Returns a pointer to the modified lists head.
static PNODE
SwapListPairs(
PNODE head
)
{
PNODE retval = head;
PNODE current = SwapPair(retval);
while (nullptr != current)
{
current = SwapPair(current->Next);
}
return retval;
}
Generic solution of reversing linklist, set k =2 for this particular problem.
Logic in in comments
static LinkedListNode reverse_k (LinkedListNode head, int k) {
LinkedListNode prev = null;
LinkedListNode cur = head;
LinkedListNode next = head;
while (k > 0 && cur != null) {
next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
k--;
}
head.next = cur;
head = prev;
return head;
}
/*
* <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.
* So oldhead.next = newHeadOfRemainingList
* and this makes complete list. This is done recursively for all sub-lists
* </pre>
*/
static LinkedListNode rec_reverse_k (LinkedListNode oldhead, int k) {
if (oldhead == null) {
return null;
}
LinkedListNode newhead = reverse_k (oldhead, k);
LinkedListNode nextListHead = oldhead.next;
LinkedListNode nextListNewHead = rec_reverse_k (nextListHead, k);
oldhead.next = nextListNewHead;
return newhead;
}
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;
}
}
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;
}
}
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;
}
public class LinkedList
{
Node head; // head of list
/* Linked list Node*/
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 */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = 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
new node as head */
if (head == null)
{
head = new Node(new_data);
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 */
Node last = head;
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()
{
Node tnode = head;
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 e = head;
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)
{
/* Start with the empty list */
LinkedList llist = new LinkedList();
// 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.insertAfter(llist.head.next, 8);
System.out.println("\nCreated Linked list is: ");
llist.printList();
System.out.println("");
llist.printList(llist.reverse());
}
}
void ExchangeAlternate(struct node *pList)
- Tarak December 09, 2014{
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;
}
}