## Interview Question for Software Engineer / Developers

• 2

Country: United States

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

The procedure can be divided into four steps:
(1)break up the list into the first half and the second half
(2)reverse the second half to use it as subtrahend
(3)minus each node of first half with each node of reverse of second half
(4)reverse the second half and connect it back to the first half's end
Complexity: time O(n), space O(1)
Following is C++ code:

``````struct ListNode{
int val;
ListNode* next;
};
/*
minus each of node in first half with the symmetric one in the second half
*/
{
}
//Step 1: use fast and slow pointer to break the list up at the (n + 1)/2 node
while(true){
if(pFast == NULL) break;//now pSlow points to the last node of the first half
//and length of first half = length of second half + 1
if(pFast->next == NULL) break;//now pSlow points to the last node of the first half
//and length of first half = length of second half
pSlow = pSlow->next;
pFast = pFast->next->next;
}
//if total length is odd, we set middle node' value to zero!!!
if(pFast == NULL) pSlow->val = 0;
//now slow->next is the head of second half
ListNode* pSecondHalf = pSlow->next;
pSlow->next = NULL;
//Step 2: reverse second half and use it as subtrahend
pSecondHalf = reverseList(pSecondHalf);
//Step 3: minus each node of first half with each node of reverse of second half
//Step 4: reverse the second half and connect it to the first half's end
pSlow->next = reverseList(pSecondHalf);

}
{

ListNode *pre = NULL, *next = NULL;
}
return pre;
}
void minus(ListNode* minuend, ListNode* subtrahend)//minus each of minuend by each of subtrahend
{
while(minuend != NULL && subtrahend != NULL){
minuend->val -= subtrahend->val;
minuend = minuend->next;
subtrahend = subtrahend->next;
}
}``````

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

Hi
I assume that it is a single linked list.
Basically my idea is to find the middle of the single linked list by using a quick (2 steps) and a slow (1 step) "pointer". After I found the middle, I push all values (the second half of the given array) into a stack (cache). The algorithm runs in O(n) and takes O(n) space. Hope this helps :-)

``````private static final Integer ZERO = 0;

public List<Integer> createNewList(final SingleLinkedNode<Integer> input) {
List<Integer> newList = null;
if (input != null) {
final Deque<Integer> cache = createNewListCache(input);
newList = new ArrayList<Integer>(cache.size() * 2);

while (current != null) {

Integer tmp = cache.size() > 0 ? cache.pop() : ZERO;
current = current.getNext();
}
}
return newList;
}

private Deque<Integer> createNewListCache(final SingleLinkedNode<Integer> input) {
Deque<Integer> cache = new ArrayDeque<Integer>();

while (quick != null) {

quick = quick.getNext();
if (quick != null) {
quick = quick.getNext();
slow = slow.getNext();
}
}

while (slow != null) {
cache.push(slow.getElement());
slow = slow.getNext();
}
return cache;
}``````

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

Space:O(n), Time :O(n)

``````rev = reverse_list(list);
while(true) {
if (list == rev || list.next == rev) {
list.data = list.data-rev.data;
break;
}
list.data = list.data-rev.data;
list = list.next;
rev = rev.next;
}``````

One thing to add is while reversing, we shouldn't just swap the values. But must swap the nodes to get the stopping condition right..

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

``````package datastructures.list;
class Node {
int data;
Node next;

public Node(int data2) {
data = data2;
next = null;
}

public Node() {
}

Node newnode(Node head, int data) {
return new Node(data);
} else {
while (temp.next != null) {
temp = temp.next;
}
temp.next = new Node(data);
}
}

}
System.out.println("No nodes in the linked list");
else
}

return null;

while(hare !=null && hare.next !=null){
tortoise=tortoise.next;
hare=hare.next.next;
}
}

while(lastNode!=null){
lastNode=lastNode.next;
}
}

while(current!=null){
next=current.next;
current.next=temp;
temp=current;
current=next;
}

return temp;
}
}

public static void main(String[] args) {

System.out.println();
}
}``````

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

The idea is to use only 1 Loop.
1. Use Rabbit Haire method to traverse tree.
2. keep pushing elements from haire pointer onto stack. untill the rabbit reaches the end.
3. Everytime Haire pointer is incremented pop a element from stack.
4. Minus the value.
5. Add it to new node.

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

``````/*
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/

/**
*
* @author nkbansal
*/
public class SubstractReverse {
static class ListNode{
ListNode next;
int data;
public ListNode(int data, ListNode next){
this.data = data;
this.next = next;
}
}
public static void main(String[] args) {
int[] input = {5, 4, 3, 2, 1};
ListNode next = null;
for(int i=input.length-1; i>=0;i--){
next = new ListNode(input[i], next);
}
printList(next);
System.out.println("Substract Reverse:");
substractReverse(next,next);
printList(next);
}
public static ListNode substractReverse(ListNode first, ListNode second){
ListNode toSubstract=null;
if (second.next != null){
if(second.next.next != null){
toSubstract =  substractReverse(first.next, second.next.next);
}
else{
//E
toSubstract = first.next;
}
}
else{
//Even case
toSubstract = first;
}
first.data-=toSubstract.data;
}
public static void printList(ListNode node){
while(node!=null){
System.out.print(node.data+"->");
node = node.next;
}
System.out.println(""+null);
}
}``````

1. Use recursion with two pointer to get the center node.
2. Start backtracking from the center node by returning next pointer to each call.
3. Substract the value of next pointer from the current nodes values

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

Recursion works well here:

``````public void firstMinusLast(Node first, Node lastPlusOne) {

// are we done?
if (first == lastPlusOne)
return;

// find the last node (it's just before lastPlusOne)
Node last = first;
while (last.next != lastPlusOne)
last = last.next;

// now subtract the last value from the first value
first.val = first.val - last.val;

// recurse!
firstMinusLast(first.next, last);
}``````

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

Base condition, needs to be modified slightly. The proposed will not work for even number of nodes.

``````if(first == lastplusone || first.next == lastplusone)
return;``````

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.