## Adobe Interview Question for Software Engineer / Developers

• 0

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

I think the following code should work

``````node* inorderconvert(node *T, node *lastprinted) {
if(T->left != NULL)
lastprinted = inorderconvert(T->left, lastprinted);
if lastprinted == NULL
else {
lastprinted->right = T;
T->left = lastprinted;
lastprinted = T;
}
if(T->right != NULL)
lastprinted = inorderconvert(T->right, lastprinted);
return lastprinted;
}

call the function with

tail = inorderconvert(root, NULL);``````

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

Small change in the above code

lastprinted = T;

should come outside the else block. (It does not depend on the condition)

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

Thanks Pratap. This is the best solution in terms of understandability as well as time complexity O(n).

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

Here is the solution:
Tree* Convert(Tree *T)
{
Tree *l1,*l2;
if(T!=NULL)
{
l1=Convert(T->left);
l2=Convert(T->right);
if(l1!=NULL)
l1->right=T;
T->left=l1;
T->right=l2;
if(l2!=Null)
{
l2-left=T;
return l2;
}
else
return T;
}
}

I am assuming we will use the left pointer to point to back node and right pointer to point to forward node.

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

the following code works:

node * Tree :: convLnLst(node *T){
node *l1,*l2;
node * temp;

if(T!=NULL){
l1=convLnLst(T->left);
l2=convLnLst(T->right);

T->left=l1;
T->right=l2;

if(l2!=NULL){
l2->left=T;
}

if(l1!=NULL){
temp=l1;
while(temp->right)
temp=temp->right;
temp->right=T;
l1->left=NULL;
return l1;
}
else
return T;

}
else
return NULL;

}

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

There is small correction in the above code:

if(l1!=NULL){
temp=l1;
while(temp->right)
temp=temp->right;
temp->right=T;
l1->left=NULL;
return l1;
}

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

Hi Ravi ,Why have u added this loop
while(temp->right)
temp=temp->right;
temp->right=T;
l1->left=NULL;
Just asking as when I uploaded the algo I didn't implement it, just thought the possible solution.

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

hi anonymous,

T
/ \
/ \
A B

where T is the root and A and B are sorted linked list.
u have to join
1.A's last node to T
2.T to B's first node

1.l1 holds last node of A
2.l2 also holds last node of B

so you join last node of A to T which is correct
but u join T to last node of B(l2->left=T).

it doesnt solve the purpose.

what u can do is ,
while(l2->left!=NULL)
l2=l2->left;
now it points to the head of the sorted list B
now u can join T to l2

if u have any query
bye

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

the above algo posted by me takes O(n*n) time

the following algo takes O(n) time

call this fuction with flag = -1

node * Tree :: convLnLst(node *T,int flag){
node *l1,*l2;

if(T!=NULL){
l1=convLnLst(T->left,0);
l2=convLnLst(T->right,1);

T->left=l1;
T->right=l2;

if(l1!=NULL){
l1->right=T;
}

if(l2!=NULL){
l2->left=T;
}
if(flag==0 && T->right)
return T->right;

if(flag==1 && T->left)
return T->left;

if(flag==-1){
while(T->left)
T=T->left;
}

return T;
}
return NULL;
}

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

Good, Simple n Elegant solution...

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

//This 1 'll work i guess

struct node
{
int data;
struct node *right;
struct node *left;
};

typedef struct node* nodeptr;

main()
{
nodeptr root=NULL;

//populate the tree

change(root);

//traversing back to the beginning of list by using left node of root

}

void change(nodeptr temp)
{
nodeptr nextNode;
if(temp->left && temp->right)//if the root has both childs
{
nextNode = temp->left;//store the left child as it is needed to link to its parent
change(temp->left);
nextNode->right = temp;

nextNode = temp->right;
//store the right child as it is needed to link to its parent
change(temp->right);
nextNode->left = temp;
}
else if(temp->left && !temp->right)//onli left child is present
{
nextNode = temp->left;
change(temp->left);
nextNode->right = temp;
}
else if(!temp->left && temp->right) //onli right child is present
{
nextNode = temp->right;
change(temp->right);
nextNode->left = temp;
}
}

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

Hey naveen

when will the recursive call to change() end ?? there is no termination condition??

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

Observe that recursive function calls itself only when 1 of the conditions are met(if, else if or else) if not it will return.

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

Observe that recursive function calls itself only when 1 of the conditions are met(if or else if or else if) if not it will return.

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

Proper working code is here:
#include <stdio.h>
#include<stdlib.h>
typedef struct node1{
int val;
struct node1* left;
struct node1 *right;
}tree;
tree* insert(tree *root,int val);
tree ** convert(tree *root);
void print(tree *root);
void printL(tree *root);
int main(){
int n,temp,i;
tree *root=NULL;
list *tail=NULL;
printf("Enter the no of nodes");
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&temp);
if(root==NULL)
root=insert(root,temp);
else insert(root,temp);
}
printf("ans \n\n");
print(root);
tree ** temp1 = convert(root);
printL(temp1[0]);
getch();
return 0;
}
}
}
tree ** convert(tree *root){
tree ** ret,**left,**right;
left = NULL;
right=NULL;
tree *temp = (tree *)malloc(sizeof(list));
temp->val=root->val;
ret = (tree **)malloc(2);
if(root->left!=NULL)left=convert(root->left);
if(root->right!=NULL)right=convert(root->right);
if(left!=NULL){
temp->left=left[1];
left[1]->right=temp;
left[0]->left=NULL;
ret[0]= left[0];
}
if(right!=NULL){
temp->right=right[0];
right[0]->left=temp;
right[1]->right=NULL;
ret[1]=right[1];
}
if(left==NULL){
temp->left=NULL;
ret[0]=temp;
}
if(right==NULL){
temp->right=NULL;
ret[1]=temp;
}
return ret;
}
void print(tree *root){
if(root==NULL)return;
if(root!=NULL){
print(root->left);
printf("%d",root->val);
print(root->right);
}
}
tree* insert(tree *root,int val){
if(root ==NULL){
tree *temp = (tree *)malloc(sizeof(tree));
temp->val=val;
temp->right=NULL;
temp->left=NULL;
root=temp;
return root;
}
if(root->val>val && root->left == NULL){
tree *temp = (tree *)malloc(sizeof(tree));
temp->val=val;
temp->right=NULL;
temp->left=NULL;
root->left=temp;
return root;
}
if(root->val<val && root->right == NULL){
tree *temp = (tree *)malloc(sizeof(tree));
temp->val=val;
temp->right=NULL;
temp->left=NULL;
root->right=temp;
return root;
}
if(val<root->val)insert(root->left,val);
else insert(root->right,val);
}

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

I guess the question is to covert in place. Moreover for every node, you are allocating two values. Whats the purpose of it?

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

left->backward
right ->forward

BS *convert(BS *root){
if(!root)return root;
if(!root->left && !root->right) return root;

BS *left=convert(root->left);
BS *right=convert(root->right);
if(left){
left->right=root;
if(right)right->left=root;
return left;
}
else{
if(right)right->left=root;
return root;

}
}

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

same as
thecareerplus.com/forum/viewtopic.php?p=414#414

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

This works

static TNode* Tree::ConvertToDList(TNode* root, bool IsLeft)
{
if( NULL == root)
return NULL;

TNode* left = ConvertToDList(root->left, true);
TNode* right = ConvertToDList(root->right, false);

root->left = left;
root->right = right;

if(left)
left->right = root;
if(right)
right->left = root;

if(IsLeft)
{
while(root->right)
root = root->right;
}
else
{
while(root->left)
root = root->left;
}

return root;
}

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

I think Inorder traversing would suffice.

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

Tested to be working.

``````Node* BST2List(Node* bst)
{
Node* first = NULL;
static Node* last = NULL;

if (bst == NULL) return NULL;

if (bst->left == NULL) first = bst;
else first = BST2List(bst->left);

if (last != NULL) last->right = bst;
bst->left = last;
last = bst;

if (bst->right != NULL) bst->right = BST2List(bst->right);

return first;
}``````

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

this line is not necessary: else bst->right = NULL;

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

Thanks

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

hghg

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

node * convertDouble (node *root,node **prev )
{
static node * first = NULL;

if(!root) return NULL;
if(root->left==NULL && first == NULL) first = root ;

convertDouble(root->left,prev);
root->left=*prev;
if(*prev) (*prev)->right = root;
*prev=root;
convertDouble(root->right,prev);

return first;

}

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

void convert_to_dll(tree_node *node, tree_node **head, tree_node **tail) {

tree_node *temp_l_tail = node;

if(node == NULL)
return;

if(node->left != NULL) {
temp_l_tail->right = node;
node->left = temp_l_tail;
} else {
}

if(node->right != NULL) {
}else {
*tail = node;
}

}

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

struct node
{
int data;
struct node * lptr;
struct node * rptr;
}

struct node * sort_tree(struct node * root)
{
struct node * previous = NULL;
struct node * start_link = NULL;
}

struct node * sorted_link (struct node * root, struct node ** previous, struct node ** start_link)
{
if(root == NULL || previous == NULL || start_link == NULL) return NULL;

if(*previous != NULL)
{
}
*previous = root;
}

This is for singly linked list, which could be easily extended for doubly linked list... have fun ;-)

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

for a doubly linked list ... i guess this algo will work fine..

If we do inorder traversal for a tree T
say call to inorder traversal return a node NODE each time (i mean one by one so that we can easily modify that NODE)

while((NODE=InorderTraversal(tree T))!=NULL)
{
NODE->right=Successor(NODE);
NODE->left=Predeccesor(NODE);
}
The code for finding a successor and predecessor is very well given in alorithm book by Prof Cormen.
This Algo only changes the pointers(left and right) without using any temporary variable..and also it does not modify the pointer value unless required...

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

Shown below is the working program. This will return the pointer to the last element of the linked list.

``````Node* convert_BST_DLL(Node *root){

if(root)
{

if( (orig_head == NULL) && (tail == NULL)) { root->back=NULL; root->next== NULL; return root;}
else if(tail == NULL) { orig_head->next = root; root->back = orig_head; root->next=NULL;return root;}
}

return NULL;

}``````

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

Sorry find was skipped, pasting it here

``````Node* find(Node *ptr){
if(!ptr) return NULL;
else{
while(ptr->back !=NULL) ptr=ptr->back;
return ptr;
}
}``````

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

``````tree * head, *curr

convert_to_dll(tree *t)
{
if(!t)return;
convert_to_dll(t->left);
curr->right=t;
t->left=curr;
curr=t;
convert_to_dll(t->right);
}

int main()
{
convert_to_dll(root);
return 0;
}``````

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

this is simply to convert the BST to Singly link list. We can easily create a doubly link list from a singlt link list.

Node inOrder(Node n){
if(n->left==null)
return n;
else
inOrder(n->left)->right = n;

if(n->right==null) return n;
else
n->right= inOrder(n->right);

}

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.