CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Google Interview Question for Software Engineers


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))
}

- dmitry.labutin March 10, 2017 | Flag Reply
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.LinkedList;
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){
		map.put(head, hyphenCnt);
		q.add(head);

		if (head.r == null && head.l == null){
			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;
		}
		if (head.l != null) {
			PrintTree(head.l, hyphenCnt-1, Integer.min(minHyphenCnt, hyphenCnt-1), q, map);
		}
		if (head.r != null) {
			PrintTree(head.r, hyphenCnt+1, Integer.min(minHyphenCnt, hyphenCnt+1), q, map);
		}
		q.remove(q.size()-1);
	}

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

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

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

		head.l.l.l = new Node('H');
		head.l.l.r = new Node('I');
		head.l.r.l = new Node('J');
		head.l.r.r = new Node('K');
		head.l.r.r.l = new Node('P');
		head.l.r.r.l.l = new Node('Q');
		head.l.r.r.l.l.l = new Node('R');
		head.l.r.r.l.l.l.l = new Node('S');

		head.r.l.l = new Node('L');
		head.r.l.r = new Node('M');
		head.r.r.l = new Node('N');
		head.r.r.r = new Node('O');

		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
		 */
	}
}

- havefun March 11, 2017 | Flag Reply
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){
          path.add(new int[]{root.val,pos});
        
         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];
                ans.add(temp);
            }
            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);
    }

- tiandiao123 September 24, 2017 | Flag Reply
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;
}

- Alex November 02, 2018 | Flag Reply
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();
	}

	static void AddHyphenPrefix(ArrayList<String> list){
		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){
				list.add(GetStringForHyphen(hyphenCount+1) + node.r.c);
				PrintTree(node.r, list, hyphenCount+1);
				list.remove(list.size()-1);
			}

			int hyphenCountL = hyphenCount;
			if (node.l != null){
				if (hyphenCountL > 0) {
					hyphenCountL--;
					list.add(GetStringForHyphen(hyphenCountL) + node.l.c);
					PrintTree(node.l, list, hyphenCountL);
					list.remove(list.size()-1);
				} else {
					ArrayList<String> listL = (ArrayList<String>)list.clone();
					AddHyphenPrefix(listL);
					listL.add("" + node.l.c);
					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>();
		list.add("" + node.c);
		PrintTree(node, list, 0);
		/*
		              A
		      B                C
		  D       E        F       G
		H   I   J   K    L   M   N   O
		 */
	}
}

- havefun March 11, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More