Facebook Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
public void flatten(Node head){
if(head == null){
return;
}
if(head.right ==null && head.down == null){
System.out.print(head.a);
return;
}
Node current = null;
Node down = null;
while(head != null){
current = head;
down = head.down;
head = head.right;
//This is just to print pretty,
System.out.print(current.a+"->");
while(down != null){
if(down.down == null && head == null)
System.out.print(down.a)
else
System.out.print(down.a+"->");
down = down.down;
}
}
}
In-place solution.
// Definition for singly-linked list.
struct ListNode {
char val;
ListNode *next, *down;
ListNode(char x) : val(x), next(NULL), down(NULL) {}
};
class Solution {
public:
ListNode* flatten(ListNode* head) {
ListNode* current = head;
while( current ){
ListNode* tmp = current -> next;
while( current -> down ){
current -> next = current -> down;
current -> down = NULL;
current = current -> next;
}
current -> next = tmp;
current = current -> next;
}
return head;
}
};
typedef struct _MNode
{
struct _MNode* right;
struct _MNode* down;
char a;
} MNode;
void flattenOneNode(MNode*& head)
{
MNode* tmphead = head;
while (tmphead->down != nullptr)
{
tmphead->right = tmphead->down;
tmphead = tmphead->down;
}
head = tmphead;
}
void flatten(MNode*& head)
{
MNode* tmphead = head;
MNode* next = nullptr;
while (tmphead != nullptr)
{
next = tmphead->right;
flattenOneNode(tmphead);
tmphead->right = next;
tmphead = next;
}
}
public Node flatten(Node head){
if(head==null){
return null;
}
Node headNew=head;
Node nodeRight=head.getRight();
while(head!=null){
Node nodeDown=head.getDown();
if(nodeDown!=null){
head.setRight(nodeDown);
head=nodeDown;
}else{
head.setRight(nodeRight);
head=nodeRight;
if(nodeRight.right!=null){
nodeRight=nodeRight.right;
}else{
nodeRight=null;
head=null;
}
}
}
return headNew;
}
public Node flatten(Node head){
if(head==null){
return null;
}
Node headNew=head;
Node nodeRight=head.getRight();
while(head!=null){
Node nodeDown=head.getDown();
if(nodeDown!=null){
head.setRight(nodeDown);
head=nodeDown;
}else{
head.setRight(nodeRight);
head=nodeRight;
if(nodeRight.right!=null){
nodeRight=nodeRight.right;
}else{
nodeRight=null;
head=null;
}
}
}
return headNew;
}
public Node flatten(Node head){
if(head==null){
return null;
}
Node headNew=head;
Node nodeRight=head.getRight();
while(head!=null){
Node nodeDown=head.getDown();
if(nodeDown!=null){
head.setRight(nodeDown);
head=nodeDown;
}else{
head.setRight(nodeRight);
head=nodeRight;
if(nodeRight.right!=null){
nodeRight=nodeRight.right;
}else{
nodeRight=null;
head=null;
}
}
}
return headNew;
}
public Node flatten(Node head){
if(head==null){
return null;
}
Node headNew=head;
Node nodeRight=head.getRight();
while(head!=null){
Node nodeDown=head.getDown();
if(nodeDown!=null){
head.setRight(nodeDown);
head=nodeDown;
}else{
head.setRight(nodeRight);
head=nodeRight;
if(nodeRight.right!=null){
nodeRight=nodeRight.right;
}else{
nodeRight=null;
head=null;
}
}
}
return headNew;
}
function flattenNode($head) {
if($head) {
if($head->next == NULL && $head->down == NULL) {
return $head;
}
while($head) {
$temp = $head->next;
while($head->down) {
$head->next = $head->down;
$head->down = NULL;
$head = $head->next;
}
$head->next = $temp;
$head = $head->next;
}
}
return $head;
}
class Node {
public $next,$down,$data;
public function __construct($data) {
$this->data = $data;
}
}
function flattenNode($head) {
if($head) {
if($head->next == NULL && $head->down == NULL) {
return $head;
}
while($head) {
$temp = $head->next;
while($head->down) {
$head->next = $head->down;
$head->down = NULL;
$head = $head->next;
}
$head->next = $temp;
$head = $head->next;
}
}
return $head;
}
class Node {
public $next,$down,$data;
public function __construct($data) {
$this->data = $data;
}
}
function flattenNode($head) {
if($head) {
if($head->next == NULL && $head->down == NULL) {
return $head;
}
while($head) {
$temp = $head->next;
while($head->down) {
$head->next = $head->down;
$head->down = NULL;
$head = $head->next;
}
$head->next = $temp;
$head = $head->next;
}
}
return $head;
}
class Node {
public $next,$down,$data;
public function __construct($data) {
$this->data = $data;
}
}
function flattenNode($head) {
if($head) {
if($head->next == NULL && $head->down == NULL) {
return $head;
}
while($head) {
$temp = $head->next;
while($head->down) {
$head->next = $head->down;
$head->down = NULL;
$head = $head->next;
}
$head->next = $temp;
$head = $head->next;
}
}
return $head;
}
public class FlattenNode {
static class Node {
Node right;
Node down;
char a;
}
public static void main(String[] args) {
Node E = new Node();
E.a = 'E';
Node L = new Node();
L.a = 'L';
Node D = new Node();
D.a = 'D';
D.down = L;
D.right = E;
Node Y = new Node();
Y.a = 'Y';
Node T = new Node();
T.a = 'T';
T.down = Y;
T.right = E;
Node Z = new Node();
Z.a = 'Z';
Node X = new Node();
X.a = 'X';
X.down = Z;
Node N = new Node();
N.a = 'N';
N.down = X;
N.right = T;
Node A = new Node();
A.a = 'A';
Node C = new Node();
C.a = 'C';
C.down = A;
Node M = new Node();
M.a = 'M';
M.down = C;
M.right = N;
flatten(M);
}
static void flatten(Node head) {
if(head == null)
return;
System.out.print(head.a + "->");
flatten(head.down);
flatten(head.right);
}
}
Why not just:
class Node{
public:
void flatten();
Node *right;
Node *down;
char a;
};
void Node::flatten(){
for ( Node *r = this; r; r = r->right ){
cout << r->a << " ";
for ( Node *d = r->down; d; d = d->down ){
cout << d->a << " ";
}
}
cout << endl;
}
this approach assumes:
1. There is only 1 way to each node from the root
2. Nodes do not point to theirselves
3. Nodes below the first level do not have neighbours to the right
Recursive:
public void flatten(Node head){
if(head != null){
System.out.println(head.a);
flatten(head.down);
flatten(head.right);
}
}
Iterative:
public void flatten(Node head){
Stack<Node> stack = new Stack<>();
stack.push(head);
while(!stack.isEmpty()){
head = stack.pop();
while(head != null){
System.out.println(head.a);
if(head.right != null)
stack.push(head.right);
head = head.down;
}
}
}
- dorashine September 14, 2016