## Qual Ex Interview Question for Software Engineer / Developers

• 2

Country: United States
Interview Type: In-Person

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

Say p is the pointer of the node with value being 50, pNew is the pointer of the node with value being 40. Then we can do like this:

pNew->next = p->next;
p->next = pNew;
p->val = 40;
pNew->val = 50;

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

Aaah! Good logic! :)

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

Good One. . !!

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

it should be :

pNew->val = p->val;
pNew->val = newvalue;

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

If it's not a doubly linked list, then I think it's impossible.

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

Yes, I second this opinion.

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

Yes, there will be no way to look back to know where the element will be. If the input is 40 then its OK. For that the code is as belows:

void insertInAscendingOrder(Node node, int insertData) {

while (node.data < insertData && node.next != null) {
node = node.next;
}

if (node.next != null) {
int temp = node.data;
Node newNode = new Node(temp);
newNode.next = node.next;
node.data = insertData;
node.next = newNode;
} else {
if (node.data > insertData) {
int temp = node.data;
Node newNode = new Node(temp);
newNode.next = node.next;
node.data = insertData;
node.next = newNode;
} else {
Node newNode = new Node(insertData);
node.next = newNode;
}
}
}

But if the input is 20, then the code will fail and will give the output 10->30->20->50->70

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

I agree with this opinion as well. If we are only given a pointer to the node with value 50, and no pointers to any node before 50, then by inserting 40 in front of 50 we create a malformed singly linked list. The resulting linked list would have two heads instead of one, which is not allowed according to the traditional definition of linked list.

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

Never mind my last comment. I see now that if you replace the data in node 50 it is possible to avoid having to create a malformed linked list when inserting the new node. In other words, it is possible to insert node 40 correctly if you assume the node values are not fixed.

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

// 10->30->50->70->NULL
// curNode is 50, newNode is 40
// first, insert newNode after curNode;

newNode.next = curNode.next;
curNode.next = newNode;

// now we have
// 10->30->50->40->70->NULL

// now swap values of curNode and curNode.next
int tempVal = curNode.value;
curNode.value = curNode.next.value;
curNode.next.value = tempVal;

// now we have
// 10->30->40->50->70->NULL

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

Yes value swap, that one way to do it.

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

We can also do it by maintaining a prev pointer taking care of the insertion at head.. below is an idea ..

node prev = null;

while(newNode.value > Curr.value)
{
prev = curr;
curr = curr.next;
}

if(prev == null)
{
}
else
{
//insertion at middle or tail

prev.next = newNode;
newNode.next = curr;

}

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

newNode.next = oldNode.next ;
newNode.value = 50 ;
oldNode.value = 40;
oldNode.next = newNode;

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

Logic be:
1) Check pointer value with new value to be added
2) If pointer value is greater than new value Than: store pointer value in temp and replace pointer value with new value
3) add a node by using temp value next to pointer node.

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

Node * new_node = new Node();
new_node->data = node50->data;
new_node->next = node50->next;
node50->data = 40;
node50->next = new_node;

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

Suppose in the linked list, the first node has a pointer 'first'. and as said in the question, let us assume p is the pointer pointing to node containing value 50. We need to insert node 40 ( let the node be pointer as new) before node 50. So we traverse till we reach a node beofre node 50, and then insert the 'new' node.
Node first = head; //just creating a pointer to move till node before 'p'.
while(first.next != p)
{
first = first.next
} // when this loop is over, you are pointing to a node just ahead of 'p'.
first.next = new;
new.next = p;

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

Strt with two pointers. One slow and anothoer Fast. Below is the code in Python.

class Node:

"""
Basic Node Object
"""
__slots__ = 'elements', 'Next'

def __init__(self, element, Next):
self.element = element
self.Next=Next

"""
Create a linkedlist object using the Node Object
"""
size = 0 # Let size be the attribute of the LinkedList Class Object

def __init__(self):

"""
"""

# Create a newNode Object
newNode = Node(e, None)
else:

def displayList(self):
#Create a tempNode and iterate
while(tempNode):
print "Current element is [%d]"% tempNode.element
tempNode = tempNode.Next

# Create a slow pointer and a Fast pointer
# Travel through the list and place the element
# immediately after the element smaller than the given
# element.
# We will also address the edge cases here

newNode = Node(e,None)
# Check if the element that is added is less than the head
# Travel until you reach dead end
else:
while(fastNode):
#stop traversing as soon as you find element larger than target
if fastNode.element > e:
break
else:
# Continue traversing otherwise
slowNode=slowNode.Next
fastNode=fastNode.Next
#Make changes to the node
newNode.Next=fastNode
slowNode.Next=newNode

if __name__== "__main__":

nums = [70, 60, 50, 30, 20, 10]
for n in nums:
print "Inserting num = %d" % n

print "=================================\n"

print "=================================\n"

print "=================================\n"

Output:

Inserting num = 70
Inserting num = 60
Inserting num = 50
Inserting num = 30
Inserting num = 20
Inserting num = 10
=================================

Current element is [10]
Current element is [20]
Current element is [30]
Current element is [50]
Current element is [60]
Current element is [70]
=================================

The Length of LinkedList is 6
=================================

Current element is [10]
Current element is [20]
Current element is [30]
Current element is [40]
Current element is [50]
Current element is [60]
Current element is [70]

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

You can do it, if you are allowed to change the node values (which may not be a good idea in a practical use case), but for the sake of this problem, we can edit 50 to 40 and can insert a new 50.

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

/**
*
* @param <T>
* @param midNode points to 50
* @param newNode contains 40
*/
public void myAnswer(Node<T> midNode, Node<T> newNode) {
T prevVal = newNode.getValue();
T currValue = null;
while(midNode!=null) {
currValue = midNode.getValue();
midNode.setValue(prevVal);
if(midNode.getNext()!=null) midNode = midNode.getNext();
prevVal = currValue;
}
midNode.setNext(new Node(prevVal));
}

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

nice code

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

Lets say head is node with value 50 and newNode is a node with value 40:

newNode.next = tmp

Its just reordering of nodes.

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

Node * LinkedList::InsertInOrder(Node *h, Node *p, int data)
{
Node *newNode = new Node(NULL, data);

if(h==NULL || p==NULL)
{
return h;
}
Node *tmp=h, *prev=h;

while(tmp->data<=data)
{
prev=tmp;
tmp=tmp->next;
}

if(tmp==h)
{
newNode->next=tmp;
h=newNode;
}
else
{
prev->next=newNode;
newNode->next=tmp;
}

return h;
}

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

One Possible Solution is this... Code is modifiable

l1.next = l2;
l2.next = l3;
l3.next = l4;

pointer = l3;
}

public void insertbeforeAsc(int data){
// add the new node where the pointer is pointing..
if(node.data < pointer.data) {
node.next = pointer.next;
pointer.next = node;
// Swap the data in both the nodes..
node.data = pointer.data;
pointer.data = data;
}
else {
while(pointer!=null)
{
if(pointer.data < data)
pointer = pointer.next;
else
{
node.next = pointer.next;
pointer.next = node;
// Swap the data in both the nodes..
node.data = pointer.data;
pointer.data = data;
break;
}
}
}
}

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

public void addNodeMaintainOrder(Node current, int given){

Node fast= current.next;
Node slow= current;
while(fast!=null &&(fast.data<given )){
slow = fast;
fast = fast.next;
}

if(slow.data<given){
Node tmp = new Node(given);
slow.next= tmp;
tmp.next = fast;
}else{
Node tmp = new Node(slow.data);
tmp.next = slow.next;
slow.data = given;
slow.next = tmp;
}

}

public static void main(String[] args){

System.out.println("After adding elements  into the LL \n");
l.display();

Node current = l.getNodeAtIndex(0);
l.display();
}

-----------------------------------------------------------------------
Testcase 1:

given pointer to Node: 50

I/P:     10 30 50 70
O/P :  10 30 40 50 70
-----------------------------------------------------------
Testcase 2:
given pointer to Node: 5

I/P :    5    14   18    23     25    37   44
O/P:   5	14	18	23	25	31	37	44

------------------------------------------------------------------------------
Testcase 3:

given pointer to Node: 44

I/P:    5	14	18	23	25	37	44
O/P:  5	14	18	23	25	37	44	47

-------------------------------------------------------------------------
Testcase 4:

given pointer to Node: 44

I/P:    5	14	18	23	25	37	44
O/P:  5	14	18	23	25	37	40	44

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.