## Google Interview Question for Software Engineers

• 0

Country: United States

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

``````package main

import "fmt"

type TreeNode struct {
v    string
l, r *TreeNode
}

type Step struct {
pos int
v   string
}

func AllPath(root *TreeNode, offset int) [][]Step {
if root == nil {
return [][]Step{}
}
lP := AllPath(root.l, offset-1)
rP := AllPath(root.r, offset+1)
res := [][]Step{}
if len(lP) == 0 && len(rP) == 0 {
res = append(res, []Step{Step{pos: offset, v: root.v}})
} else {
for _, path := range lP {
res = append(res, append(path, Step{pos: offset, v: root.v}))
}
for _, path := range rP {
res = append(res, append(path, Step{pos: offset, v: root.v}))
}
}
return res
}

func FindMin(path []Step) int {
min := path[0].pos
for i := 1; i < len(path); i++ {
if min > path[i].pos {
min = path[i].pos
}
}
return min
}

func PrintPaths(paths [][]Step) {
for _, path := range paths {
min := FindMin(path)
for s := len(path) - 1; s >= 0; s-- {
step := path[s]
for i := min; i < step.pos; i++ {
fmt.Print("_ ")
}
fmt.Println(step.v)
}
fmt.Println()
}
}

func main() {
root := &TreeNode{"A", nil, nil}
root.l = &TreeNode{"B", nil, nil}
root.r = &TreeNode{"C", nil, nil}
root.l.l = &TreeNode{"D", nil, nil}
root.l.r = &TreeNode{"E", nil, nil}
root.r.l = &TreeNode{"F", nil, nil}
root.r.r = &TreeNode{"G", nil, nil}
root.r.r.r = &TreeNode{"H", nil, nil}
PrintPaths(AllPath(root, 0))
}``````

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

``````import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Queue;
import java.util.Stack;

public class PrintTreePathWithHyphen2 {
static class Node{
Character c;
Node l,r;
Node(Character c){
this.c = c;
this.l=null;
this.r = null;
}
}

static String GetStringForHyphen(int count){
String hyphenString = "";
for (int i=0; i<count; i++){
hyphenString+="-";
}
return hyphenString;
}

static void PrintTree(Node head, int hyphenCnt, int minHyphenCnt, ArrayList<Node> q, HashMap<Node, Integer> map){

for (int i=0; i<q.size(); i++){
Node n = q.get(i);
String hyphenStr = GetStringForHyphen(map.get(n) - minHyphenCnt);
System.out.println(hyphenStr + n.c);
}
System.out.println("");
q.remove(q.size()-1);
return;
}
PrintTree(head.l, hyphenCnt-1, Integer.min(minHyphenCnt, hyphenCnt-1), q, map);
}
PrintTree(head.r, hyphenCnt+1, Integer.min(minHyphenCnt, hyphenCnt+1), q, map);
}
q.remove(q.size()-1);
}

static public void main(String[] val){

ArrayList<Node> stack = new ArrayList<Node>();
PrintTree(head, 0, 0, stack, new HashMap<Node, Integer>());

/*
A
B                C
D       E        F       G
H   I   J   K    L   M   N   O
*/
}
}``````

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

share my java solution!

``````public static void printTreePath(TreeNode root){
List<int[]> path = new ArrayList<>();
printTreePathHelper(root,path,0,0);
}

public static void printTreePathHelper(TreeNode root,List<int[]> path,int pos,int left_most){

if(root.left==null && root.right==null){
List<String> ans = new ArrayList<>();
for(int[] ele:path){
String temp = "";
int count = ele[1]-left_most;
for(int i=0;i<count;i++){
temp+="_";
}
temp+=ele[0];
}
for(String str:ans){
System.out.println(str);
}
System.out.println();
}else{

if(root.left!=null){
printTreePathHelper(root.left,path,pos-1,Math.min(left_most,pos-1));
}
if(root.right!=null){
printTreePathHelper(root.right,path,pos+1,left_most);
}
}

path.remove(path.size()-1);
}``````

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

``````#include <iostream>
#include <vector>

using namespace std;

class Node
{
public:
Node(int val) : val_(val)
{
left_ = right_ = NULL;
}
int val_;
Node *left_, *right_;
};

class Entry
{
public:
Entry(Node* n, int pos) : n_(n), pos_(pos) {}
Node *n_;
int pos_;
};

void Print(Node* n, Node* leaf, vector<Entry>& path, int min_pos = 0, int pos = 0)
{
if (n)
{
min_pos = min(min_pos, pos);
path.push_back(Entry(n, pos));
if (n == leaf)
{
for (Entry& e : path)
{
cout << string(e.pos_ - min_pos, '_') << e.n_->val_ << "\n";
}
return;
}
Print(n->left_, leaf, path, min_pos, pos - 1);
Print(n->right_, leaf, path, min_pos, pos + 1);
path.pop_back();
}
}

int main()
{
/*
(1)
/
(2)
\
(4)
\
(3)
\
(7)
/ \
(5) (8)
*/
Node n1(1);
Node n2(2);
Node n3(3);
Node n4(4);
Node n5(5);
Node n6(6);
Node n7(7);
Node n8(8);
n1.left_ = &n2;
n2.right_ = &n4;
n4.right_ = &n3;
n3.right_ = &n7;
n7.left_ = &n5;
n7.right_ = &n8;

vector<Entry> path;
Print(&n1, &n5, path);

return 0;
}``````

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

``````import java.util.ArrayList;

public class PrintTreePathWithHyphen {
static class Node{
Character c;
Node l,r;
Node(Character c){
this.c = c;
this.l=null;
this.r = null;
}
}

static void PrintList(ArrayList<String> list){
System.out.println("Output:");
for (String s: list){
System.out.println(s);
}
System.out.println();
}

for (int j=list.size()-1; j>=0; j--){
String s = list.get(j);
s ="-" + s;
list.set(j, s);
}
}

static String GetStringForHyphen(int count){
String hyphenString = "";
for (int i=0; i<count; i++){
hyphenString+="-";
}
return hyphenString;
}

static void PrintTree(Node node, ArrayList<String> list, int hyphenCount){
if (node.l == null && node.r == null){
PrintList(list);
return;
}else{

if (node.r != null){
PrintTree(node.r, list, hyphenCount+1);
list.remove(list.size()-1);
}

int hyphenCountL = hyphenCount;
if (node.l != null){
if (hyphenCountL > 0) {
hyphenCountL--;
PrintTree(node.l, list, hyphenCountL);
list.remove(list.size()-1);
} else {
ArrayList<String> listL = (ArrayList<String>)list.clone();
PrintTree(node.l, listL, hyphenCountL);
}
}
}
}

static public void main(String[] val){
Node node = new Node('A');
node.l = new Node('B');
node.r = new Node('C');

node.l.l = new Node('D');

node.l.r = new Node('E');
node.r.l = new Node('F');
node.r.r = new Node('G');

node.l.l.l = new Node('H');
node.l.l.r = new Node('I');
node.l.r.l = new Node('J');
node.l.r.r = new Node('K');
node.r.l.l = new Node('L');
node.r.l.r = new Node('M');
node.r.r.l = new Node('N');
node.r.r.r = new Node('O');

ArrayList<String> list = new ArrayList<String>();
PrintTree(node, list, 0);
/*
A
B                C
D       E        F       G
H   I   J   K    L   M   N   O
*/
}
}``````

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.