infix expression to construct binary expression tree

July 13, 2018

Introduction

It is my favorite thing to do to scan the code qucikly in less than 15 minutes. Here is C++ for the algorithm.

Using stack

The really important tips are to use stack, so the time complexity can be implemented using O(n) time to parse the infix expression. And the binary express tree can be built in bottom up way. The similar idea using stack can be see in multiple places.

The ) bracket is used to determine when to pop the stack and handle the operand and also operator.


Here is the gist I created how to use stack to parse the infix expression and then construct the binary expression tree.

Here is the output of stack working on a simple test case:

My bet was wrong

 I knew that stack is used on reverse polish notation. And it is widely used to parse the input. There is a hard level algorithm Leetcode 301 to parse parentheses, I did write 10 blogs on that. I also did work on hard level algorithm using more than 10 ideas.

 But the performance on 30 minutes is beyond my control. I could not think clearly using stack and stop on close bracket ), and then start to pop and then construct binary express tree from bottom up.

 What I did is to think about finding operator (1 + 2) so that I can use the string manipulation to get the result. I am not aiming highest potential I can reach in those 30 minutes.

 Through the performance, I understood that it is very important for me to calm down, and list all the options I have. Stack or not using stack, what is time complexity? Can I beat other people to write an optimal time complexity solution.

 I still remembered that I practiced a hard level algorithm on hackerrank and learn the power of using stack. The algorithm is called Reverse shuffle merge.

Actionable Items

Review all past practice using stack.

Here is the first one, Leetcode 109: convert sorted list to binary search tree.

Review one of solution using O(n) time O(1) space, the link is here.

Follow up

Most important is to understand the space is cheap, using space to expedite the time is always best choice, need to scale the problem in large expression. This time I failed to give it a try in 30 minutes using stack to get linear time complexity.

Hackerrank - practice - problem solving - hard - algorithms

June 21, 2018

Introduction

It is time for me to get organized. I like to check in all my practice on hackerrank.com into github. I did solve 3 hard level algorithms.

Hard level

Matrix layer rotation

String Function calculation

Reverse shuffle merge

Medium level

Sherlock and anagrams
Connected Cells in a Grid
Even Tree

Easy level 

Intro to Tutorial Challenges
Pangrams
Funny String
Gemstones
Alternating Characters
The Love-letter mystery
Palindrome index
Anagram
Making angrams
Game of thrones - 1
Two strings
Sherlock and array

It is also a good idea to review the code I wrote 2 years ago. It is so exciting to read the code I wrote two years ago. 

Will come back to write more here. 

Top 10 Ranking Algorithm problems - June 2016

June 2, 2016

 Julia likes to rank her favorite algorithms and also her practice, then she has to chance to dig into more and develop some skills through the practice.

 Here are top 10 practice she likes most:

1. LRU cache - Leetcode 146 - third practice:
http://juliachencoding.blogspot.ca/2016/06/leetcode-146-lru-cache-practice-makes_2.html

http://juliachencoding.blogspot.ca/2016/06/leetcode-146-lru-cache-practice-makes_45.html

 Practice a few more times.

2. Leetcode 126 - Word Ladder II (hard)  - fifth practice
http://juliachencoding.blogspot.ca/2016/05/leetcode-126-word-ladder-ii-using-bfs.html


3. HackerRank: String - Reverse Shuffle Merge (advanced) 5 practices
https://gist.github.com/jianminchen/7572e92ea48211d3d05c557d97601dbf

4. Serialize and Deserialize Tree - 2 study cases
http://juliachencoding.blogspot.ca/2016/05/leetcode-297-serialize-and-deserialize.html

5. Binary Tree Maximum Path sum - second practice
http://juliachencoding.blogspot.ca/2016/05/leetcode-124-binary-tree-maximum-path.html

6. Binary Tree Preorder Traversal - Iterative solution -
http://juliachencoding.blogspot.ca/2016/05/binary-tree-preorder-traversal.html

7. Leetcode 159 - longest substring with at most two distinct characters
http://juliachencoding.blogspot.ca/2016/05/leetcode-159-longest-substring-with-at.html

8. Leetcode 236 - Binary Tree Lowest Common Ancestor - Recursive, Backtracking 
First blog: (5 practices)
http://juliachencoding.blogspot.ca/2016/05/leetcode-236-lowest-common-ancestor.html
Second blog:
http://juliachencoding.blogspot.ca/2016/05/leetcode-236-lowest-common-ancestor_21.html

Third blog:
http://juliachencoding.blogspot.ca/2016/05/leetcode-236-lowest-common-ancestor_22.html

Fourth blog:
http://juliachencoding.blogspot.ca/2016/05/leetcode-236-binary-tree-lowest-common.html

9. Binary Tree Post Order Traversal - Iterative solution
http://juliachencoding.blogspot.ca/2016/05/binary-tree-post-order-traversal.html

10. Leetcode 17: Phone Number Combination
http://juliachencoding.blogspot.ca/2016/04/window-sum.html

There are so many algorithms to list here. But just keep 10 a time.

Forget what everybody else is doing. @kikimladenovic is the first on court and the last one off. #CreateYourMark pic.twitter.com/3E7n6psKdF

— adidas tennis (@adidastennis) May 18, 2016

HackerRank: string algorithm - Reverse Shuffle Merge - Stack, backtracking techniques

May 26, 2016

Reverse Shuffle Merge - Problem statement:

https://www.hackerrank.com/challenges/reverse-shuffle-merge

Algorithm analysis:

Use test case: "abcacb" to explain the solution: 

int[] add = new int[26], 

int[] skip = new int[26]

a - 0, b - 1, c -2 

add[0] = 1, add[1] = 1, add[2] = 1, 

skip[0] = 1, skip[1] = 1, skip[1] =1, 

Find smallest lexical string. 

reverse input char one by one:

push b into stack, 

'c' > ''b', then, push c into stack

stack:

c

b

Now, a is scanned, 'a' < stack.peek() = 'c', skip[2] = 1 > 0, 

backtracking, pop c out of stack, skip[2] = 0

Now, 'a' < stack.peek() = 'b', skip[1] = 1 > 0, 

backtracking, pop b out of stack, then adjust skip[1] = 0

add[0] >  0, push a into stack, add[0] = 0, 

next, c is scanned, cannot skip, push into stack, 

next, b is scanned, cannot skip, push into stack, 

next, a is scanned, skip a. 

stack.ToArray(), keep stack iterator order, "bca", 

Array.Reverse(stack.ToArray()) -> "acb"

Lexical smallest string. 

previous blog: 

http://juliachencoding.blogspot.ca/2016/04/april-3-2016-httpsgist.html

warmup practice:

https://gist.github.com/jianminchen/f3c4b8249b8233771183f1a7f5d01c12

Second practice:

https://gist.github.com/jianminchen/c695be78345751a5f389ba3332c33342

so many bugs in second practice:

1. confused on skip, add array --, ++; line 71, line 80 did the opposite.

2. string reverse, char[], string, Array.Reverse etc. lookup

3. add one more test case: "abcacb",

    b in stack, c in stack, then, run into a, pop up c, and pop up b, let 'a' in the stack. Two in row pop up in stack. While loop is tested on line 64 - 67.

4. while statement from line 64 - 67, fix compile error.

   both are ok to compile:

(char)stack.Peek() > runner)

(char)stack.Peek() - runner > 0)

Third practice:
The code passes HackerRank online test cases as well.

A few good changes:
1. add comment from line 67 - line 72, test case: "abcacb", 
use test case, stack top -'c' is removed, help to ensure the code is correct.
2. line 73, avoid bug to overwrite the variable runner, create a new variable called backTracked.

https://gist.github.com/jianminchen/8e2c28262dd3d13c4db856feaed5603e

Fourth practice:

1. create a new function getIndex - on line 100 - 103
2. after reading through the code, still missed a bug in writing - on line 55; debug the code and find
the result of first test case "abcacb" should be "acb", but it was "bca".

Julia examined line by line, but still missed the bug on line 55.

https://gist.github.com/jianminchen/7572e92ea48211d3d05c557d97601dbf

Read C# string constructor char[]: spend 10 - 20 minutes to read all constructors of string in C#.
https://msdn.microsoft.com/en-us/library/aa331865(v=vs.71).aspx

Binary Tree Preorder Traversal - Iterative Solution - Warm up Practice

May 25, 2016

Review blogs - Leetcode binary tree preorder traversal

C# practice:

use stack, and also know the order to push child nodes: right child first, and then left child next.

Code is here.

Question and Answer:
1. How is the practice?

Julia first thought about using queue to implement the solution, left child first, and then right child next. But, it does not work, since left child's left child should go to traversal first before right child. So, she had to stop.

Then, she tried to look into iterative solutions in general through Google, and also checked her previous practice.

Next time, go through a test case, do some analysis on the test case. Draw some diagram, help yourself to analyze, at least behaves like a teacher.

2. Things to work on through the practice?
queue -> stack -> opposite order to push into stack

3. Can you describe the process using your own words, a few of drawings to help the thinking process?

First, read the wiki article about stack.

Let us work on a simple test case:

The preorder traversal of tree: 1 2 3 4 5 6 7
When the root node 1 is visited, 2 and 5 should be added to some data structure, 3 and 4 will be added after 5, but output of 3 and 4 should be before 5.
In other words, the data structure should accommodate last in first out feature. So, it is stack!
Once stack is chosen to use, then work out the simple tree first with 3 nodes:

preorder traversal: 1 2 5
so, push 1 into stack, and then, pop out. 5 is pushed in stack first, and then it is turn of 2.

Next, work on the test case: tree - preorder traversal 1 2 3 4 5 6 7
1 is pushed into stack,
1 is on the top of stack, 1 is popped out,

1's right child 5 is pushed into stack,
1's left  child 2 is pushed into stack,

2 is popped out from stack,

2's  right child 4 is pushed into stack,
2's  left  child 3 is pushed into stack,

3 is popped out from stack,
4 is popped out from stack,

5 is popped out from stack,

5's right child 7 is pushed into stack,
5's left  child 6 is pushed into stack.

6 is popped out from stack,
7 is popped out from stack.

3. Most favorite problem solving using stack?

HackerRank: string algorithm - Reverse Shuffle Merge (IV)

warmup practice - C# practice code

Second practice:

C# code

so many bugs in second practice:
1. confused on skip, add array --, ++; line 71, line 80 did the opposite.
2. string reverse, char[], string, Array.Reverse etc. lookup
3. add one more test case: "abcacb",
    b in stack, c in stack, then, run into a, pop up c, and pop up b, let 'a' in the stack. Two in row pop up in stack. While loop is tested on line 64 - 67.
4. while statement from line 64 - 67, fix compile error.
   both are ok to compile:

(char)stack.Peek() > runner)
(char)stack.Peek() - runner > 0)

Third practice:

The code passes HackerRank online test cases as well.

A few good changes:
1. add comment from line 67 - line 72, test case: "abcacb",
use test case, stack top -'c' is removed, help to ensure the code is correct.
2. line 73, avoid bug to overwrite the variable runner, create a new variable called backTracked.

C# practice

August 8, 2016

Work on facebook code lab, preorder iterative solution. Chicken out! Forget to enforce the rule, right child goes to stack first, and then, left child goes to stack afterwards. And then, instead, nervousness kicked in, gave up in 5 minutes, looked up blogs.

Need more practice!

3 smart choices to ask myself: 

stack vs queue ->
left, right who goes first ->
enforce rule, null pointer will not go into stack, save time ->

one node ->
3 node tree - complete binary tree ->
7 node tree - complete binary tree

HackerRank: string algorithm - Reverse Shuffle Merge (IV)

April 3, 2016


C# solution:

https://gist.github.com/jianminchen/346970ad058d64041ab7b8cbe9ecb495

Read the code, and talk about the ideas:
Best way to explain the algorithm - greedy one, the following, is to take away reverse, and also merge two parts (these are noisy!), work on a string, simple test case, how to construct a string with minimum lexically value, using stack to do greedy design, and also allow the back and forth two ways to optimize.

Here is the simple example:
1. string a2b2c2, for example, aabbcc, so abc is shortest one.
For string bbccaa,
first b, put in stack, second b, have to skip; and then, c is coming,
'c' > 'b', push c to stack, so stack is like this
b
c
and then, second c, skip it; now 'a' is coming,
'a' is bigger than 'b', but b does have any number to skip; need to put 'a' in anyhow.

the output will be "bca";

2. Try another one:
babcac
First one, b, go into the stack:
b,
meet a, and then, 'a' <'b', because b still have one to skip, so pop out b, skip the b, push 'a' in the stack;
Now, another b is coming, we have to hold one b in output, push it in the stack:
b
a
And then, c is coming, push it in c.
c
b
a

Now, a is coming, skip it; c is coming, also skip it.

the result is 'abc', smallest one in lexical sense.

3. Try third one:
work on first test case, make small change. move bbccaa, one of b, so the string is ccbaab,
c - put in the stack
c - skip it.
b - compare to stack top, b ( b has one left to skip);
so b into stack
b
c

c- second c, skip it
a- compare to the stack top: b
'a'<'b', still 'b' can skip one, one more is coming
pop up b, push a in,
a
c
and then, last char 'b' into stack
b
a
c
the output is "cab"

The question is to ask yourself, do you have genius to design it at the beginning, called thinking about in stack to cover mistake in greedy approach! Julia has no clue right now, she spent 9 hours to take this lesson. Backtracking is better term for using stack in the design.

April 5, 2016
Go over a2b2c2 case, the lexical smallest substring (Julia's first practice):
bccaba,
visit first 'b', skip 'b', because a has 2 of them to visit
visit first 'c', skip 'c',
visit second 'c', cannot skip, has to take it. Now, best one is starting from c, of course it is worse than the one starting from 'b', such as "bca".

So, greedy algorithm is to take what ever you can, and then, backtracking, make it smaller iteratively.
--
code source:  a box employee

HackerRank: string algorithm - Reverse Shuffle Merge (III)

April 3, 2016


Study the code written by some one in Google, need to get the idea how it is designed. It should not be difficult, since I already worked on this problem over 10 hours.

https://goo.gl/Rbh3B4

up to April 3, 2016

statistics:    1300 score 50.00 

Julia score rank:  1403

C# rank: 58

HackerRank: string algorithm - Reverse Shuffle Merge (II) - next - forming a partial correct idea

April 2, 2016

  Problem statement is here.   

  Introduction

Julia likes to share her experience, advance level on HackerRank. It is not bad in the weekend, spend 2 hours messing around the ideas/ hackerRank, come out a clear greedy algorithm. The hackerRank definitely helps Julia to shape her idea from start to end.

Practice talk 

  First two hours work - failed twice, detail here in the blog.     

  Here is the idea after 2 hours intensive work:
of course, "abc" is the smallest one in lexicographical order, but the possible string formats:
  *a*b*c*, not *abc*, now * means any number of any chars.

 Let us count how many of a, b, c can be skipped when we do linear scan of a string.

 Now, it should be very easily to introduce greedy algorithm.

 For example, if linear scan from left to right, visiting char b, then, we have to check how many b's left can be skipped, if it is bigger than 0, we have to check any char before b has anything left or not. For example, if a still has some number left to skip; we hold on b, just skip current b.

 Otherwise, count current b into the string we are looking for, and decrease the number count of b (recording how many b can be skipped).

Use an example to explain:
  a2b2c2 case,
 ba*, the half should be a1b1c1,
 so, skip first char 'b', since greedy algorithm / let 'a' go first.

 Give it a try, implement the idea:

 Some statistics: advanced algorithm 4+ hours - A mountain - "Sea to sky Gondola" to climb

Spent 9:47 am - 11:47 am, wrote code, but still failed most of case; only pass "eggegg";
Hard to concentrate, and think about the issue - this reverse is tricky!

Here is the C# solution - 3 rd failed try. Code is here.

Baby hacker is crying, still score zero: 4 hours work. Code is here.

Now, it is 1:47 pm, another 2 hours with music, the code was submitted, now score 16.67/ 50. Still need to work on more before Julia plan to read other people's solution:

Some statistics: advanced algorithm 6+ hours - A mountain - Sea to sky Gondola to climb. Code is here. 

Need to stop, go to enjoy outdoor activities!

Baby hacker is showing off her baby steps, the report of test cases pass/ fail on Hackerrank is here.

Try to fix the error, give up - the design has another flaw,
test case:
djjcddjggbiigjhfghehhbgdigjicafgjcehhfgifadihiajgciagicdahcbajjbhifjiaajigdgdfhdiijjgaiejgegbbiigida
i=50, s[i] = 'g', the design let 'g' skip, but
i=52, s[i] = 'i', 'i' has to be added to the output, no more skip.

<-  Julia, think about stack, use some data structure to do reverse work <- such a great workout! Release all my stress and headache, and be humble!

5:12 pm, statistics: Another 3 hours, total: 9+ hours 

Follow up 

May 3, 2017

HackerRank: string algorithm - Reverse Shuffle Merge (I) - First step: Failed twice

March 31, 2016

  Problem statement is here.

 Introduction

 The algorithm is in advanced category. 8:17 am - 10:08 am. Document 2 hours work as a hacker, Julia. First time, Julia thinks that hacker is a good name!

 Practice Talk

Start from 8:19 am, 9:18, tried twice, passed one test case, failed others with wrong answer;  then, need to pay attention to reverse string word.

Spent more than 20 minutes to think, but could not figure out the solution. Have to stop here. Write down the analysis first. Come back later.

The naive solution is to count string in each char in "abc...z", and then, half of count will construct a new string.

For example, if the string counting: a2b2c2
then, the string A is one of strings {abc, bac, cba, bac, aca, cab}

Of course, "abc" is the smallest one in lexicographical order, but the possible string formats:
  abc***
  *abc**
  **abc*
  ***abc

Or, go through each possible string - find the minimum one, smart way to compare with previous one, keep the smallest one.

Assuming that the string is matching.

Got the idea. Linear solution.  From 8:19 am - 8:45 am, more than 20 minutes to come out the idea.

9:00 am -
Two functions - one function is to count the number to determine that count for each char is even. Another step is to go over the string, take substring(i, 3).

20 minutes to write a code, a bug to fix: wrong answer
Need to make sure that substring count matching count first, otherwise, skip it! 
  
9:15 am, bug is not fixed; and then, notice that the string has to be reversed! 

10:16 am, still not fixed. Julia, this is a greedy algorithm, why is the greedy part? You missed merge part in the construction merge(reverse(A), shuffle(A)). So, you have to redesign the algorithm.

Conclusion

1. Design algorithm - advanced - know why it is advanced, examine the idea and see if you can make it first; Otherwise, waste time to write code

Two hours, failed two tries! A new hacker is getting her valuable lesson using 2 hours.

Here is the C# code.

Follow up 

Blog review on May 3, 2017