Harjit Singh
BAN USER- 0of 4 votes
Answers2.Given an integer linked list of which both first half and second half are sorted independently. Write a function to merge the two parts to create one single sorted linked list in place [do not use any extra space].
- Harjit Singh in India for TCS
Sample test case:
Input: List 1:1->2->3->4->5->1->2; Output: 1->1->2->2->3->4->5
Input 2: 1->5->7->9->11->2->4->6; Output 2: 1->2->4->5->6->7->9->11
C/C++/Java/C#
struct node
{
int val;
node *next;
}
node* sortList(node* list1) {
}
Java
class Node
{
int val;
Node next;
}
Node sortList(Node list1) {
}| Report Duplicate | Flag | PURGE
Amazon SDE1 Linked Lists - 0of 0 votes
AnswersQuestion 3 / 3 (Find first unique character)
- Harjit Singh in India for TCS
Find the first unique character in a Stream. Please note that you are being provided a stream as a source for these characters.
The stream is guaranteed to eventually terminate (i.e. return false from a call to the hasNext() method), though it could be very long. You will access this stream through the provided interface methods.
A call to hasNext() will return whether the stream contains any more characters to process.
A call to getNext() will return the next character to be processed in the stream.
It is not possible to restart the stream.
If there is no unique character, then return the character '#'. # won't be any character in the character stream.
You just have to complete the function getUniqueCharacter() using the functions hasNext() and getNext() which are already defined.
Example:
Input:
aAbBABac
Output:
b
Input:
aBBa
Output:
#| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm C++ Data Structures - 2of 2 votes
AnswersQuestion 1 / 3 (Odd even level difference)
- Harjit Singh in India for TCS
You are given a function calcDifference which takes in the root pointer of a binary tree as it's input. Complete the function to return the sum of values of nodes at odd height - sum of values of node at even height. Consider the root node is at height 1
Sample Input:
Sample Output
-74
Explanation:
[ (1 + 4 + 5 + 6 + 7 ) ? (2 + 3 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15) = -74 ]| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm C++ Trees and Graphs
#include<iostream>
using namespace std;
int main()
{
char str[1000];
int arr[256],i,j=0;
for(i=0;i<256;i++)
arr[i]=0;
cout<<"Enter the stream of characters:";
cin>>str;
char* ptr=str;
while(*ptr)
{
if(arr[*ptr]==0)
arr[*ptr++]=++j;
else if(arr[*ptr] > 0)
arr[*ptr++]=-arr[*ptr];
else
{
ptr++;
j++;
}
}
int min=257;
for(i=0;i<256;i++)
{
if(arr[i] > 0 && arr[i]<min)
min=arr[i];
}
if(min!=257)
cout<<min<<" "<<str[min-1];
else
cout<<"#";
return 0;
}
#include<iostream>
using namespace std;
struct node
{
int val;
node* next;
};
void add(struct node** p,int n)
{
struct node* temp= new node;
//struct node* temp =
// (struct node*) malloc(sizeof(struct node));
temp->val=n;
temp->next=NULL;
if(*p==NULL)
{
*p=temp;
}
else
{
struct node* mover=*p;
while(mover->next!=NULL)
mover=mover->next;
mover->next=temp;
}
}
void display(struct node* p)
{
struct node*temp=p;
cout<<endl;
while(temp->next!=NULL)
{
cout<<temp->val<<" --> ";
temp=temp->next;
}
cout<<temp->val<<" --> NULL"<<endl;
}
void mergelist(struct node**p)
{
struct node*temp=*p;
while(temp->next->val > temp->val)
temp=temp->next;
struct node*ptr1,*ptr2,*ptr1_prev,*ptr2_prev;
ptr1=*p;
ptr1_prev=NULL;
ptr2=temp->next;
ptr2_prev=NULL;
temp->next=NULL;
while(ptr1!=NULL && ptr2!=NULL)
{
if(ptr1->val > ptr2->val)
{
if(ptr1_prev==NULL && ptr2_prev ==NULL)
{
ptr2_prev=ptr2;
ptr2=ptr2->next;
ptr2_prev->next=*p;
*p=ptr2_prev;
ptr1_prev=*p;
ptr2_prev=NULL;
}
else
{
ptr2_prev=ptr2;
ptr2=ptr2->next;
ptr1_prev->next=ptr2_prev;
ptr2_prev->next=ptr1;
ptr1_prev=ptr2_prev;
ptr2_prev=NULL;
}
}
else
{
ptr1_prev=ptr1;
ptr1=ptr1->next;
}
}
if(ptr1==NULL)
{
ptr1_prev->next=ptr2;
}
}
int main()
{
struct node *p=NULL;
int n;
cout<<"\nEnter space separated input(-1 at the end of input)\n\n";
while(cin>>n)
{
if(n==-1)
break;
else
add(&p,n);
}
cout<<"\nInput\n";
display(p);
mergelist(&p);
cout<<"\nOutput\n";
display(p);
}
I am a little confused in the question def. Is it like we have to print 45, 60, 71, 82, 93 ? Is it the case that no digit should repeat again?
- Harjit Singh September 25, 2013Posting solution on behalf of Abhishek.
Here the idea is to traverse from the bottom to top.
1) consider a[i][j], check if i'th row is zero and j'th column is 1. if yes, return true. Note that we have started from a[n][n];
2) else if a[i][j] ==0
move one column left and check (1).
if a[i][j]==1
move one row up and check(1)..
In this code isrow checks if all the row element are 0's except a[i][j] and iscolumn checks if all the column elements are 1's except a[i][j].
isbooleanmatrix(A,i,j,n)
{
if(i==0 && j ==0)
{
if(isrow && iscoulumn)
return true;
else
{
printf("Not Present");
return;
}
}
else
{
if(isrow && iscoulumn)
return true;
else
{
if(A[i][j] == 0 && j)
isbooleanmatrix(A,i,j-1,n);
else
isbooleanmatrix(A,i-1,j,n);
if(i)
isbooleanmatrix(A,i-1,j,n);
else
isbooleanmatrix(A,i,j-1,n);
}
}
}
Traverse the matrix diagonally.
1) traverse each diagonal element.
2) while traversing, check if a[i-1][j]==0 && a[i][j-1]==1;
3) if (2) satisfies then i and j could be the row and column we are looking for. Traverse the entire column up and down and check if all are ones, then traverse the entire row left and right and check if all are zeros.
4) If still we don't get the row and column , traverse diagonally till the end repeating (2) and (3)
For this., first we should have a dictionary of valid words. Then for each word formed after pressing key, we will map the same to dictionary using hash key , if it matches then its a valid word otherwise not.
- Harjit Singh March 17, 2012
- Harjit Singh April 07, 2015