How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Microsoft during technical interviews.

Solve binary-tree reverse printing and LPS | Microsoft Interview Question

Quick Overview

This question evaluates proficiency with tree data structures and level-order traversal semantics for reverse level printing, as well as string algorithmic reasoning and dynamic programming concepts for computing the longest palindromic subsequence, categorized under Coding & Algorithms.

You are given a binary tree node definition:

TreeNode { int val; TreeNode left; TreeNode right; }

Answer the following two algorithmic questions.

1) Reverse-print a binary tree

Implement a function that returns the values of the tree level by level from bottom to top.

Input: root (possibly null )
Output: a list of levels, where each level is a list of node values
Order requirement: within each level, nodes are listed from left to right , but the levels are returned in reverse (deepest level first).

Example

Tree:

1
- left: 2 (children: 4 , 5 )
- right: 3 (right child: 6 )

Output: [[4,5,6],[2,3],[1]]

2) Longest palindromic subsequence (LPS)

Given a string s, return the length of the longest subsequence of s that is a palindrome.

A subsequence keeps relative order but may delete characters.
Input: string s
Output: integer length

Example

Input: "bbbab"
Output: 4 (one LPS is "bbbb" )

Constraints (assume typical interview constraints)

0 <= number_of_nodes <= 10^5 for the tree
1 <= |s| <= 2000 for LPS

Quick Overview

1) Reverse-print a binary tree

Implement a function that returns the values of the tree level by level from bottom to top.

Input: root (possibly null )

Output: a list of levels, where each level is a list of node values

Order requirement: within each level, nodes are listed from left to right , but the levels are returned in reverse (deepest level first).

Example

Tree:

1

left: 2 (children: 4 , 5 )
right: 3 (right child: 6 )

Output: [[4,5,6],[2,3],[1]]

2) Longest palindromic subsequence (LPS)

Given a string s, return the length of the longest subsequence of s that is a palindrome.

A subsequence keeps relative order but may delete characters.

Input: string s

Output: integer length

Example

Input: "bbbab"

Output: 4 (one LPS is "bbbb" )

Constraints (assume typical interview constraints)

0 <= number_of_nodes <= 10^5 for the tree

1 <= |s| <= 2000 for LPS

Solve binary-tree reverse printing and LPS

Quick Overview

1) Reverse-print a binary tree

2) Longest palindromic subsequence (LPS)

Constraints (assume typical interview constraints)

Comments (0)

Solve binary-tree reverse printing and LPS

Quick Overview

1) Reverse-print a binary tree

2) Longest palindromic subsequence (LPS)

Constraints (assume typical interview constraints)

Comments (0)