Hitachi Data Systems Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
public static Node reverse(Node head, int k) {
Node temp = head;
Node prevTemp = temp;
Node out = null;
Node newNode = null;
if (head != null)
{
temp = head;
int i = 0;
while (temp.Next!=null) {
if(i == k)
break;
prevTemp = temp;
temp = temp.Next;
i++;
}
prevTemp.Next = null;
newNode = reverse(head);
out = merge(newNode,temp);
}
return out;
}
public static Node reverse(Node node) {
if (node == null)
return null;
else if (node.Next == null)
return node;
else {
Node second = node.Next;
node.Next = null;
Node reverseRest = reverse(second);
second.Next = node;
return reverseRest;
}
}
private static Node merge(Node node1, Node node2) { // 3,2,1 -- 4,5
Node temp = node1;
if(temp.Next == null)
return temp.Next = node2;
else {
merge(temp.Next, node2);
}
return temp;
}
public static Node reverse(Node head, int k) {
Node temp = head;
Node prevTemp = temp;
Node out = null;
Node newNode = null;
if (head != null)
{
temp = head;
int i = 0;
while (temp.Next!=null) {
if(i == k)
break;
prevTemp = temp;
temp = temp.Next;
i++;
}
prevTemp.Next = null;
newNode = reverse(head);
out = merge(newNode,temp);
}
return out;
}
public static Node reverse(Node node) {
if (node == null)
return null;
else if (node.Next == null)
return node;
else {
Node second = node.Next;
node.Next = null;
Node reverseRest = reverse(second);
second.Next = node;
return reverseRest;
}
}
private static Node merge(Node node1, Node node2) { // 3,2,1 -- 4,5
Node temp = node1;
if(temp.Next == null)
return temp.Next = node2;
else {
merge(temp.Next, node2);
}
return temp;
}
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* head;
void Insert(int a){
struct Node* temp1= (struct Node*)malloc(sizeof(struct Node));
temp1->data=a;
temp1->next=NULL;
if(head==NULL)
{
head=temp1;
return;
}
struct Node* temp2=head;
while(temp2->next!=NULL){
temp2=temp2->next;
}
temp2->next=temp1;
return;
}
void Print(){
struct Node* temp=head;
while(temp!=NULL){
printf(" %d",temp->data);
temp=temp->next;
}
}
struct Node* grprev(struct Node* start, int k){
struct Node* prev=NULL;
struct Node* curr=start, *next;
int i;
for(i=1;i<=k&&curr!=NULL;i++){
next=curr->next;
curr->next=prev;
prev=curr;
curr=next;
}
start->next=curr;
if(start==head){
head=prev;
}
return prev;
}
int main()
{
head=NULL;
Insert(1);
Insert(2);
Insert(3);
Insert(4);
Insert(5);
Print();
printf(" \n");
struct Node* temp=head, *temp1;
grprev(temp,3);
while(temp->next!=NULL)
{
temp1=temp->next;
temp->next=grprev(temp1,3);
temp=temp1;
}
Print();
printf(" \n");
return 0;
}
void pushBack(Node **dest, Node **src)
{
Node *tmp=*src;
if(!tmp) return;
*src=tmp->next;
tmp->next=*dest;
*dest=tmp;
}
void blockReverse(Node **head, int count)
{
// reverse count nodes
int i=1;
Node *trav=*head;
Node *first_node;
Node *res=NULL,*prev=NULL;
int end=0,first=0;
while(trav &&!end)
{
for(i=1;i<=count;i++)
{
if(trav==NULL)
{
end=1;
} else {
pushBack(&(res),&trav);
}
}
//traverse res count times;
if(prev == NULL) {prev=res;}
else {
while(prev->next) prev=prev->next;
prev->next=res;
while(prev->next) prev=prev->next;
}
if(first==0) {
first_node=res;
first=1;
}
res=NULL;
}
*head=first_node;
}
void pushBack(Node **dest, Node **src)
{
Node *tmp=*src;
if(!tmp) return;
*src=tmp->next;
tmp->next=*dest;
*dest=tmp;
}
void blockReverse(Node **head, int count)
{
// reverse count nodes
int i=1;
Node *trav=*head;
Node *first_node;
Node *res=NULL,*prev=NULL;
int end=0,first=0;
while(trav &&!end)
{
for(i=1;i<=count;i++)
{
if(trav==NULL)
{
end=1;
} else {
pushBack(&(res),&trav);
}
}
//traverse res count times;
if(prev == NULL) {prev=res;}
else {
while(prev->next) prev=prev->next;
prev->next=res;
while(prev->next) prev=prev->next;
}
if(first==0) {
first_node=res;
first=1;
}
res=NULL;
}
*head=first_node;
}
void pushBack(Node **dest, Node **src)
{
Node *tmp=*src;
if(!tmp) return;
*src=tmp->next;
tmp->next=*dest;
*dest=tmp;
}
void blockReverse(Node **head, int count)
{
// reverse count nodes
int i=1;
Node *trav=*head;
Node *first_node;
Node *res=NULL,*prev=NULL;
int end=0,first=0;
while(trav &&!end)
{
for(i=1;i<=count;i++)
{
if(trav==NULL)
{
end=1;
} else {
pushBack(&(res),&trav);
}
}
//traverse res count times;
if(prev == NULL) {prev=res;}
else {
while(prev->next) prev=prev->next;
prev->next=res;
while(prev->next) prev=prev->next;
}
if(first==0) {
first_node=res;
first=1;
}
res=NULL;
}
*head=first_node;
}
public LinkedList<T> reverse(T k) {
LinkedList<T> result = new LinkedList<>();
Node<T> current = head;
current = reverse(result, current, k);
reverse(result, current);
return result;
}
private Node<T> reverse(LinkedList<T> result, Node<T> current, T k) {
if (current != null && k != null) {
if (current.value.equals(k)) {
k = null;
}
Node<T> temp = reverse(result, current.next, k);
if (current != null) {
result.add(current.value);
}
return temp;
}
return current;
}
Improved Solution:-
public LinkedList<T> reverse(T k) {
LinkedList<T> result = new LinkedList<>();
Node<T> current = head;
current = reverse(result, current, k);
reverse(result, current);
return result;
}
private Node<T> reverse(LinkedList<T> result, Node<T> current, T k) {
if (current != null && k != null) {
if (current.value.equals(k)) {
k = null;
}
Node<T> temp = reverse(result, current.next, k);
if (current != null) {
result.add(current.value);
}
return temp;
}
return current;
}
- dmitry.labutin April 29, 2017