# Binary Trees

Binary Tree – Recursion

Recursion

• Recursion is the strategy for solving problems where a method calls itself.

• Approach
– If the problem is straightforward, solve it directly (base case – the last step to

stop the recursion).

– Else (recursive step)

1. Simplify the problem into smaller problems.
2. Solve the simpler problems using the same algorithm.
3. Combine the solutions of the smaller problems that solve the general problem.

• Given an array of [2, 3, 4, 5, 6, 7], implement a recursive method add(int[] a) that calculates the sum of all integers in the array.

return add_helper(a, 0); //Need a helper method to access each //element

}
private int add_helper(int[] a, int index) {

if (index == a.length – 1) return a[index]; //Base case

else return a[index] + add_helper(a, ++index); //Recursive step }

Binary Tree

• Definition: Binary Tree is a data structure that has a root node and each node in the tree has at most two subtrees, which are referred to the left child and right child.

• Example:

Binary Tree Traversal

• Breadth-first traversal (BFS) visits node according to how far away from the root.

• Depth-first traversal (DFS) visits nodes as far ahead as possible before backing up. There are three types of DFS for binary trees:

• Preorder traversal visits a node, then its left child, then its right child.
• Inorder traversal visits a node’s left child, then the node itself, then its right

child.
• Postorder traversal visits a node’s left child, then its right child, then itself.

Binary Tree Traversal Example

Binary Tree Traversal Example

Breadth-first: 4, 3, 6, 5, 7
Preorder: 4, 3, 6, 5, 7
Inorder: 3, 4, 5, 6, 7
Postorder: 3, 5, 7, 6, 4

Which one of these is breadth-first traversal?

A. 1,2,3,4,5,6,7,8,9 B. 5,2,6,1,4,8,3,7,9 C. 1,3,4,2,7,9,8,6,5 D. 5,3,2,4,3,6,8,7,9

Which one of these is breadth-first traversal?

A. 1,2,3,4,5,6,7,8,9

B. 5,2,6,1,4,8,3,7,9

C. 1,3,4,2,7,9,8,6,5 D. 5,3,2,4,3,6,8,7,9

Which one of these is postorder traversal?

A. 1,3,4,2,7,9,8,6,5 B. 5,2,6,1,4,8,3,7,9 C. 1,2,3,4,5,6,7,8,9 D. 5,3,2,4,3,6,8,7,9

Which one of these is postorder traversal?

A. 1,3,4,2,7,9,8,6,5

B. 5,2,6,1,4,8,3,7,9 C. 1,2,3,4,5,6,7,8,9 D. 5,3,2,4,3,6,8,7,9

Which one of these is inorder traversal?

A. 1,2,3,4,5,6,7,8,9 B. 5,2,6,1,4,8,3,7,9 C. 1,3,4,2,7,9,8,6,5 D. 5,3,2,4,3,6,8,7,9

Which one of these is inorder traversal?

A. 1,2,3,4,5,6,7,8,9

B. 5,2,6,1,4,8,3,7,9 C. 1,3,4,2,7,9,8,6,5 D. 5,3,2,4,3,6,8,7,9

Which one of these is preorder traversal?

A. 1,3,4,2,7,9,8,6,5 B. 5,2,6,1,4,8,3,7,9 C. 1,2,3,4,5,6,7,8,9 D. 5,3,2,4,3,6,8,7,9

Which one of these is preorder traversal?

A. 1,3,4,2,7,9,8,6,5

B. 5,2,1,4,3,6,8,7,9

C. 1,2,3,4,5,6,7,8,9 D. 5,3,2,4,3,6,8,7,9

Tree Construction Algorithm

1. Get the root from the pre (post) order traversal.
2. Locate the root in the inorder traversal.
3. Determine the sizes of your left and right subtrees from the inorder traversal, and obtain the inorder traversal of the left and right subtrees.
4. Compute the split index of your pre (post) order traversal to get the left and right preorder traversal of your left and right subtrees.
5. Create the root node and solve recursively for its left and right subtrees.

Binary Tree

Exercise 1: Implement findMaxSum() method that find the maximum sum of all paths (each path has their own sum and find max sum of those sums). For example, the path 1->2->5 makes the max sum of 8 and 8 is the result.

int findMaxSum(Node n) { }

Binary Tree

Exercise 1: Implement findMaxSum() method that find the maximum sum of all paths (each path has their own sum and find max sum of those sums). For example, the path 1->2->5 makes sum of 8; 1->2>4 makes sum of 7; and 1->3 makes sum of 4. Therefore, 8 is the result.

int findMaxSum(Node n) {
if (n == null) return 0;

else {
int sumleft = findMaxSum(n.left);

} }

int sumright = findMaxSum(n.right);
if (sumleft > sumright) return n.data + sumleft; else return n.data + sumright;

Binary Tree

• Exercise 2: Implement mirror() method that replaces the current binary tree with its own mirror version.

void mirror(Node n) { }

Binary Tree

• Exercise 2: Implement mirror() method that replaces the current binary tree with its own mirror version.

void mirror(Node n) { if (n != null) {

mirror(n.left); mirror(n.right); Node temp = n.right; n.right = n.left;
n.left = temp;

} }

# Mobile Microservices

Let me start by stating that Microservices is NOT a pattern but rather a distinctive method of developing software systems which is becoming more and more popular as people realize the advantages of it Vs developing a Monolithic systems.

I’ve adopted and been developing & evolving this type of architecture for mobile applications and decided to share knowledge..

The core of microservices architecture is :

Smart endpoints that process info and apply logic, and dumb pipes through which the info flows.

Before we dive in to the microservices lets go through some foundational, mobile oriented paradigms.

### Message-driven

Message driven architecture ( i.e. reactive ) is one of the most important paradigms one needs to understand when developing any mobile app. Most important rule of any mobile app is User Experience. A responsive system ensures quick reaction to any user requests or actions which is driven by asynchronous behavior and timely messages deliveries among objects in the system.

Lets take an example from real life:

Task in hand : Brew a pot of coffee

• Impediments :
• You’re out of cream and sugar.

Reactive, message driven approach:

• Begin to brew a pot of coffee.
• Go to the store while the coffee is brewing.
• Return home.
• Drink coffee immediately.
• Enjoy life.

Monolithic approach:

• Go to the store.
• Return home.
• Start brewing a pot of coffee.
• Impatiently watch the pot of coffee as it brews.
• Experience caffeine withdrawal.
• Crash.

As you can clearly see, the second approach take double the time resulting in a very poor user experience.

A message-driven application may be event-driven, actor-based, or a combination of the two.

Event-driven system is based on events which are monitored by zero or more observers. This is different than imperative programming because the caller doesn’t need to block waiting for a response from the invoked routine. Events are being broadcasts and absorbed by whoever is willing to listen.

Consider the following diagram describing the event – driven architecture

Actor-based concurrency is an extension of the Event-driven system, where messages are directed to a recipient, which happens to be an actor. Messages may cross thread boundaries or be passed to another actor’s mailbox on a different physical server. This enables elasticity — scaling out on demand — as actors can be distributed across the network, yet still communicate with each other as they are all sharing the same bus.

The main difference between messages and events is that messages are directed while events happen. Messages have a clear destination while events may be observed by zero or more (0-N) observers.

Example of the Message driven implementation can be found at the following git repo:

Event Driven mobile foundation

#### Actor-based concurrency

Actor-based applications revolve around asynchronous message passing between multiple actors.

An actor is a construct with the following properties:

• An observer for receiving messages.
• The actor’s logic, which relies on pattern matching to determine how to handle each type of message it receives.
• Isolated state — rather than shared state — for storing context between requests.

Actors pass messages back and forth, or to themselves. An actor can pass a message to itself in order to finish processing a long-running request after it services other messages in its queue first. A huge benefit of actor-based concurrency is that in addition to the benefits gained by an event-driven architecture, scaling computation out across network boundaries is even easier, and callback-hell is avoided because messages are directed to actors. This is a powerful concept that makes it easy to build hyper-scalable applications that are also easy to design, build, and maintain. You only need to think about how messages flow between actors.

Another major benefit of an actor-based architecture is the loose coupling of components. The caller doesn’t block a thread waiting for a response, therefore the caller can quickly move onto other work. The invoked routine, encapsulated by an actor, only needs to call the caller back if necessary.

More to come…..

# Behavior Over Time -> BOT

Developing Pic2Pseak Process

This is a “close to home” project that should ( hopefully ) give voice to children that have trouble with their speech.

It started as a simple Picture sequence app with intention to help kids, at some point I realized that by implementing even a basic learning algorithm that will study kids behavior over time ( BOT heretofore ) the this app transforms from a simple helper app to an app that will improve quality of life.

After doing research I’ve narrowed down to 2 methodologies : FSM ( Finite State Machine ) and Behavior Trees…

To be continued….

# Facebook -What to expect when you are expecting…

Featured

### Me – Software Engineer with 15 years of experience in anything from AT&T / C++ to iOs development ( last 8 years ). Had my own startup, worked with Kardashians on their mobile app, married + 2 and a dog, mortgage and everything around it.

One sunny / cloudy April day, I got an email and later a phone call from Facebook ( Yes, the last company I ever thought I would be a part of, yeah, I have Facebook account and use it sometimes and I have done some Facebook integrations here and there but nothing serious or deep )

Well, one April morning I took a call from a very nice person at Facebook who explained to me what are they doing, who are they looking for, what is their hiring process and what are my options to work on if and when I get accepted. She also tested me on 5 questions about Obj-C which I got 4 out of 5 correctly which got me into the next round ( 3 total ).

10 minutes after we’ve finished our phone conversation I got an email from her with the process of hiring and what I should be preparing for as well as resources for learning the material.

What to expect on the day:

The interview will be approximately 45min long.
Be prepared for technical questions involving coding algorithms and data structures, design patterns in Objective-C, runtime complexity and iOS API’s.
It may also help to review core CS concepts as well as subjects pertaining to the scale of our environment.
For coding questions, you will be asked to produce clean, compilable, efficient code in a reasonable amount of time.

Think out loud if you are working through a solution you are presented with as the engineer will want to know how you approach and troubleshoot problems.
If the interviewer gives you hints to improve your code, take them and run with them.  It is good to adjust and work through the problems with the interviewer to show your thought process and problem solving ability.
The engineer will also want to ascertain your level of interest in the role. Have some questions prepared, for example, what is involved in the role, day to day tasks, what is the most exciting project they have worked on in Facebook etc.
Be able to articulate a deep, thorough understanding of iOS memory management, ARC, etc.
Some Topics & things to Consider:

Data Structures: Arrays and lists (critical), Binary trees (critical), Hash tables (critical), Stacks and queues (critical), Graphs (critical), Trie (nice to have), Heap (nice to have), Set (nice to have), Red-black trees (nice to have).
Algorithms/CS Concepts: Search (iterator, binary, hash – all critical), Sort (merge, quick, bucket – all critical), Graph traversals (BFS, DFS – all critical), Complexity and big O notation (critical), Recursion (critical), Randomized quicksort (nice to have), Heap sort (nice to have), Radix sort (nice to have), Spanning tree and minimum cut (nice to have).
Objective-C Knowledge: Look through Mike Ash’s blog and NSHipster. Additionally, make sure you can explain memory management (different types), usage of different Foundation collections, threading and Thread safety.
Don’t worry about rote memorization such as runtimes or API/native calls. It’s always good to know how to figure out approximate runtimes on the fly but the code you write is more important.
Generally avoid solutions that would have lots of edge cases or huge if/elseif/… blocks. Most coding interview questions at most places are designed with semi-elegant solutions so try to identify patterns. Deciding between iteration and recursion is always an important step.
You may be asked in the interview to explain a technically challenging problem you have worked on in the past. Think about and explain how the problem was technically challenging.

• What to Expect During the Recruiting Process

• How to Crush Your Coding Interview

• Facebook Mobile Engineer blog post on his process

• Algorithm Tutorials

• Glassdoor Interview Questions
A few coding samples:

• Cracking the Coding Interview

• Big O Cheat Sheet

• Career Cup

• Code Chef

• Project Euler

• Geeks for Geeks

• Facebook on iOS: Inside the “Big Blue App”

• Timed releases for mobile apps

• Get that job at Facebook

• Engineering notes

15 minutes after our phone call while reading all the material she sent, I came to realize just how much preparation will I have to do if I want to get anywhere near the second interview.

Before I spend time / money and energy I wanted to see what’s all the fuss was about so I went and watched Building Paper video ( an hour and a half long ). That was the first time EVER I’ve gotten through tech video without getting up from my chair, this was by far illuminating, innovating, inspiring and all other fancy words that I could think of at that moment. in hour and a half I learned about 5 brand new to me open source libraries for iOs, I learned that people in Facebook can move from any team to any team even if you spent your whole life doing backend, you can get into Mobile UI team and vice versa.

So, about half way through a video, I hit a pause button and wrote the following email back to the Facebook recruiter:

thank you so much for all the information, that was literally a “Red Bull” of conversations / interviews and I’m very excited about this opportunity!
I would like to take time to prepare by taking Gayle’s classes and going over all the material that you’ve sent me.
Would that be ok if I gave you my availability dates for the next interview round after I’ve done my “homework”?

Facebook policy allows scheduling interviews anywhere between 2 days and 2 months so I figured it should give me some time to get ready.

Next thing I’ve done is :

And so the preparations begin…

As I started going over the basics, I gradually ended up doing some basic math, remembering what log(n) means, what is Big-O, and what the hell is “Red-Black Trees” ( I know, I wasn’t even aware of such trees.

I’ll try to state ALL the resources that I’ve found useful in my prep in this post.

• Trie ( not a typo ) “thanks” to Edward Fredkin
• Basic Illustration I found to be VERY useful
• Big-O ( big what now?! )
• Divide and conquer algorithms usually have a log n component to the running time. This comes from the repeated halving of the input.In the case of binary search, every iteration you throw away half of the input. It should be noted that in Big-O notation, log is log base

Basically it’s a fancy way of saying that any search algorithm that splits by half every search iteration will have a time complexity of O(log n)

Example ( obj-c) :

AKA Fibonacci series
-(int) fibo:(int)n{
if(n<= 1){
return 1;
}
return [self fibo:n-1] + [self fibo:n-1];
}

What would be the runtime complexity here?
Obvious ( to some people ) answer would be O(n²) = WRONG

lets plant a tree, shall we...

few things here...
a) we do not go down the tree from both leaves simultaneously,
rather we go down on one branch-> then go back up and then go
down the second branch.
b) the bigger the input number N the deeper the tree is.
Which brings us to the time complexity ( the Big-O ).
we are going to run as many as the number of nodes in the tree
which we can set as 'A'. Each level doubles the number of
leaves ( nodes ) on the branch => 2ª => O(2ª) is the runtime
of the fibonacci series.
• Basically – any search algorithm that divides

• #### Upper and lower bounds on the complexity of problems

T(n) = Upper bound. For example assume the following algorithm, T(n) = 7n2 + 15n + 40, in big O notation one would write T(n) = O(n2) because by definition in Big-O notation we hide constant factors and smaller terms such as O(7n) becomes O(n).

## Data Structure and other animals…

• Graphs – A graph is a structure consisting of a set of arrays (also called dimensions) $\{v_1, v_2,\dots,v_n\}$ and a set of edges $\{e_1, e_2,\dots,e_m\}$
• Graphs memory optimization take O(n2) space.
• Graphs search time complexity is also O(n2)
• Graphs types are :
• Directed  – UniDirectional, connecting 2 vertices ( nodes ) where the flow direction travels only one way.

• Undirected – well, the exact opposite of “Directed” , flow travels both ways between each vertical ( node )

• Question : given a set of n nodes and m edges where the graph was represented by an adjacency list, why insertVertex would take O(1) and deleteVertex would take O(m).
• Solution: It takes O(1) time to append a node to a linked list. And it takes O(n) time to delete an item.a) Why insertVertex is O(1)?Inserting a vertex is just appending a node to a linked list (O(1)) or 2 if the graph is undirected.b) Why deleteVertex is O(m)?Deleting a vertex means:1) Delete a linked list (O(1))2) In the worst case you will have to remove the vertex from all the linked lists: O(m). It’s O(m) cause the number of nodes in all the linked lists is m, or 2*m if the graph is undirected.
• Following up on that question I had to look up terms “adjacency list” & “adjacency matrix”.
• Adjacency list – is a collection of unordered lists used to represent a finite graph.

Example of graph usage ( Facebook of course what else… )

This social network is a graph. The names are the vertices of the graph. (If you’re talking about just one of the vertices, it’s a vertex.) Each line is an edge, connecting two vertices. We denote an edge connecting vertices u and v by the pair (u,v). Because the “know each other” relationship goes both ways, this graph is undirected. An undirected edge (u,v) is the same as (v,u) (Directed graphs, in which relationships between vertices don’t necessarily go both ways. ) In an undirected graph, an edge between two vertices, such as the edge between Audrey and Gayle, is incident on the two vertices, and we say that the vertices connected by an edge are adjacent orneighbors. The number of edges incident on a vertex is the degree of the vertex. ( source – Khan Academy )

### iOs related

• Assign, weak, strong, unsafe_unretained etc….
• Strong reference (which you will use in most cases) means that you want to “own” the object you are referencing with this property/variable. The compiler will take care that any object that you assign to this property will not be destroyed as long as you point to it with a strong reference. Only once you set the property to nil will the object get destroyed (unless one or more other objects also hold a strong reference to it).

Weak reference you signify that you don’t want to have control over the object’s lifetime. The object you are referencing weakly only lives on because at least one other object holds a strong reference to it. Once that is no longer the case, the object gets destroyed and your weak property will automatically get set to nil. The most frequent use cases of weak references in iOS are:

1. delegate properties, which are often referenced weakly to avoid retain cycles, and
2. subviews/controls of a view controller’s main view because those views are already strongly held by the main view.

atomic vs. nonatomic refers to the thread safety of the getter and setter methods that the compiler synthesizes for the property.

Atomic (the default) tells the compiler to make the accessor methods thread-safe (by adding a lock before an ivar is accessed).

Nonatomic does the opposite. The advantage of nonatomic is slightly higher performance.

On iOS, Apple uses nonatomic for almost all their properties so the general advice is for you to do the same

• Ok, listened for 2 hours for Gayle Mcdowell talking about how to prepare for Facebook interview. She had a lot of good pointers and raised a few questions:
• I for one, take time to develop any algorithm or to solve the problem, why they expect me to do so in under 10 minutes?
• After 15 years of software engineering, I went over the material she was presenting and I figured I used about 5% of it to develop real life solutions, systems, applications etc…
• Here is the Power Point from the lecture about Facebook for you to decide guys

Ok, Facebook or not, a week and a half later I can definitely say that I’m smarter than I used to be a week ago which only comes to show how much work one needs to be doing to stay no top of things without letting the “experience” to get in the way. I still have long way to go but at least I’m there and hopefully regardless if this Facebook position happens or not I’ll make sure from now on to keep going back to basics and practicing practicing practicing!

I’m going to publish a list of puzzles that I’m solving at least once a day which are programming language agnostic and are good practice for any level of software engineer.

Gayle Laakmann McDowell’s

Cracking the Coding Interview Challenges is now available to all at the following link:

#Get Cracking