Monthly Archives: June 2016

Pass data from UITableViewCell to UIViewController

http://stackoverflow.com/questions/9005052/recipes-to-pass-data-from-uitableviewcell-to-uitableviewcontroller

Solution: Use custom delegate

UIViewController

MyViewController.h

MyViewController.m

Custom table cell and Protocol

MyTableViewCell.h

MyTableViewCell.m

azure permissions

When you are in Active Directory, it will tell you what kind of Role you have:

Global admin
Billing admin
Service admin
User

MY_ROLE-Global_Admin

EPAM_ROLE-USER

I have found that apps created by Global admin can access the GRAPH API. For example, a user from the Tenant’s Active Directory signs in, and then hits the Graph API to access their user data such as first name, last name, address, email…etc.

data-received

If you are a Global Admin, and set up the app, users of this app will have permissions to view their own data.

If you are NOT a Global admin, any app you set, will not have permissions to access Graph API.

VIPER Part 1 – Dependencies, Root Wireframe, AppDelegate, ViewController

demo for xCode 7.3

This tutorial shows how to hook up an AppDelegate, Dependencies object, a Root wireframe, and a standalone ViewController in a VIPER design pattern.

AppDelegate.h

Standard AppDelegate with the window property.

AppDelegate.m

AppDelegate allocates a Dependencies object. That dependencies object will then install a RootViewController onto the Window object.

Dependencies

The dependencies component has a property wireframe. This wireframe is what carries the logic of showing which ViewController. The ViewControllers are simply instantiated and used by the wireframe.

AppDependencies.h

The installRootViewControllerIntoWindow method simply passes along the window object, and let’s other wireframes (or itself) set view controllers on the window

AppDependencies.m

We simply instantiate a ViewController, and then passes it along into the RootWireFrame object so it can do its logic of showing which controller in the window

Wireframe carries logic of showing ViewControllers/Views

RootWireFrame.h

RootWireFrame.m

Using protocols to have components talk to each other in iOS Design Pattern

https://www.objc.io/issues/13-architecture/viper/

Protocol is a one to one relationship where a receiving object implements a delegate protocol. A sending object uses it and sends messages (assuming that those methods are implemented) since the receiver promised to comply to the protocol.

First, the Interactor protocol!

The interactor is the middle man between data and the presenter. It has a protocol that says

1) there is an input property from the presenter that forces Interactor to implement findUpcomingItems ( to find upcoming certain (decided by presenter) items or data.

2) there is an output property pointing to presenter that forces Presenter to implement foundUpcomingItems:.

InteractorIO.h

present_interact

Presenter.h

Presenter.m

Using the interactor property to force the Interactor component to implement required method(s)

The interactor property is connected to the Interactor component. Our interactor property (which conforms to InteractorInput), promises that this Interactor component will have the method findUpcomingItems implemented. Thus, say when we want to update the view, we tell the interactor component (through our id interactor property) to call the findUpcomingItems method.

In other words, Interactor can retrieve data for us because it talks to the DB Manager/Entities, thus, we (the Presenter) have an interactor property to the Interactor object so that we can call required Protocol methods to find certain data for us by forcing the Interactor component to implement findUpcomingItems:

Presenter component implements promised required protocol methods

Presenter conforms to InteractorOutput because we promise to implement a method foundUpcomingItems: which means we’ll take care of
the data returned by the Interactor.

The Interactor will point a output property to the Presenter. Thus, the output says Presenter must implement foundUpcomingItems:.

Interactor.h

The Presenter object works with the UIViews/UIViewControllers to display data, thus, we point an output property to
the Presenter object in order to force it to implement foundUpcomingItems:(NSArray*).

The method gets gets the found data
in Presenter, and thus, can have the UIViews/UIViewControllers display it.

Interactor.m

Interactor conforms to InteractorInput, which means we promise to implement a method called findUpcomingItems.
This is be requested by the Presenter/Views throug Presenter’s interactor property.

Hooking it all up

Interview Exercise – Earliest Index of array, where the subarray contains all unique elements of the array

Time: 2 hours

Try to solve the following exercise in O(n) worst-case time complexity and O(n) worst-case space complexity – giving a more complex solution is also acceptable, but not so valuable.
Also, try not to rely on library functions, unless they don’t increase complexity.
Please test your solution – correctness is important.

You get a non-empty zero-indexed array parameter A that contains N integers. Return S, the earliest index of that array where the sub-array A[0..S] contains all unique elements of the array.
For example, the solution for the following 5−element array A:
A[0] = 3
A[1] = 3
A[2] = 2
A[3] = 0
A[4] = 2
is 3, because sub-array [ A[0], A[1], A[2], A[3] ] equal to [3, 3, 2, 0], contains all values that occur in array A.

Write a function
function solution($A);
that, given a zero-indexed non-empty array A consisting of N integers, returns this S index.
For example, if we call solution(A) with the above array, it should return 3.

You can assume that:
· N is an integer within the range [1..1,000,000];
· each element of array A is an integer within the range [0..N−1].

//whiteboard logic
15:20 – 16:03

//coding in up in C++
16:03 – 17:29

1st try, O(n^2)

Further thoughts

We can first use a merge sort O ( n log n ) to sort the original array.
After sorting it,you do a O ( n ) run through to build your unique array.

Then, you can build your unique array with O ( n log n ).

AVL tree

ref – https://github.com/redmacdev1988/avl-binary-tree

height and balance

The height of a node is the maximum number of vertices from itself to a leaf.
Thus, a leaf has a height of 0.

If the leaf has a parent node, the parent node’s height would be 1.

The balance factor of a node is the height of the left subtree minus the height of the right subtree.

  • If the result is > 0, the left subtree is larger
  • If the result is < 0, the right subtree is larger

In our example, we use absolute value as we don’t care which side is larger. We simply want to see what the balance factor is.

simple example

We have a root node 5, and its left node of value 2.

We calculate from the leaf. 2 is a leaf, so its height is 0. And in turn, balance factor is 0.
The left and right of a leaf is always null, thus, we don’t add 1.

At 5, the height is calculated as height of the subtree + 1. Thus, we get 1 for left subtree. And obviously 0 for right subtree. The height is the max of those 2 numbers. We get 1. The balance is the difference in the height of the left and right subtree, which is 1.

In the next example, it is the same, but simply flipped. The leaf has height of 0 because there is no left or right subtrees. Thus, its balance is also 0.
The root node 8’s left subtree is null, so its height is defaulted to 0.
Its right subtree exists so we add 1 to right subtree height (0), which results to 1.

Our balance is abs value of (left height – right height), which is abs(0-1) = 1.

In the last example, 50 is the root. Its left subtree is 10, which has height of 0, balance of 0.
Its right subtree is 80 which has height of 0, balance of 0.

Thus, at 50, its left height is 0 + 1. right height is 0 + 1, thus, max of left and right height is 1.
Its balance is therefore abs(1 – 1) = 0

code for height and balance

The code shows, if we’re at a subtree that is null, we don’t add 1. If there exists a subtree, we add 1 to the height of that subtree in order to get our current height.

We do this for both left and right.

The balance is simply the difference between the heights.

more examples

When to balance a tree

we want to balance a tree whenever its node’s balance is 2 or larger. If so, we call the correctBalanceness for that node.

A node can be corrected in 4 difference situations. In this particular tutorial, we test for the heaviness of the node to see whether its left or right subtree has more node. Actually, not using absolute in calculating the balance should let you know whether its left or right heavy. If the result is positive, its left heavy. If negative, its right heavy. But for sake of practicing recursion, let’s just say we need to implement a function to test for heaviness of a node.

Its basically recursively calling getHeight and then comparing those heights. If left subtree is taller, we return LEFT_HEAVY. If right subtree is taller, we return RIGHT_HEAVY.

When height is same, just compare count

If those heights are the same, then we compare which subtree has more count. If the left subtree has more nodes, we return LEFT_HEAVY.
If the right subtree has more nodes, we return RIGHT_HEAVY.

where counting a node in a subtree is:

Once we get the heaviness of a node, we then calculate the heaviness of its left and right.

1. if we get left heavy, left heavy, then the nodes have a “/” left spear pattern

We give two examples. One example is if there are no subtrees to worry about. The other example is if there’s a subtree. The key is to remember to take the right subtree of the left child, or the left subtree of the right child.

2. If we have right heavy, right heavy, then the nodes have “\” right spear pattern

If we do not have anything hanging left from the anchor node, we can do a straightforward rotation. But if we have a subtree hanging left off of anchor, we need to move that subtree to the right side of toMove node. Then the anchor’s left can safely attach to toMove.

Remember, toMove should always take left subtree of the right child, or right subtree of the left child.

3. if we have right heavy, and left heavy, then its a “>” right arrow pattern

4. if we get left heavy, right heavy, then the nodes have a”<" left arrow pattern

Correcting Balance at Node

We have a utility correctBalanceness function for a certain when a that node’s balance is 2 or more. We simply apply the rules from above to it to make it so that this node has a balance of 1 or less. It rotates and manipulates subtrees.

This utility correctBalancesness function is then used by balanceNode.

balanceNode does 2 things:

1) update height and balance for the current node.
2) checks to see if the balance >= 2. If so, it corrects the balance by manipulating its subtree.

Insertion with Balance

The insertion public function insertAndBalanceis called first. It uses utility function traverseInsertion in order to find a leaf position to insert the new node.

Once inserted, since we are at the very bottom of the tree, we recurse up and run balanceNode on every node. The reason for this is that once a node is inserted, it may create imbalance in the tree.

We basically repeat:
1) check for imbalance. Fix if need be.
2) Then go up to its parent.

…all the way up to the root.

As shown here, we basically recursively go down and find a spot at a leaf somewhere to insert our node. Once we have inserted our new node at the base case, we recurse back up, and then do a balance/height check at that node. This ensures that our insertion gets accounted for. We do this all the way up to the root. That way, from the root all the way down to the leaf, this path of nodes have all the updated height and balance, as well as the rotation itself.

After all the insertAndBalance recursive functions have popped, we need to run update balance and height for the whole tree. Because even though we have successfully fixed balanced the tree after the insertion, it only applies from the root down to the newly inserted node. Only that area is balanced and fixed. The other nodes that were untouched (usually at the opposite side of the tree) needs their height and balance be updated.

Thus at the end of the insertAndBalance we do:

where updateBalanceAndHeightValuesForTree uses utility function balanceIt to recursively traverse the whole tree and update all height and balance values:

Removal of Node

Removal of Node is straightforward. We use public function remove and it uses utility traverseRemove function. travereRemove traverses the tree until it gets to the node with the value you want to remove.

When we find the node we’re looking for, it will look at 4 situations:

1) no children, simply delete and remove the current node
2) only the left child exist, so we return the node’s left subtree to be attached. remove the node
3) only the right child exist, so we return the node’s right subtree to be attached. remove the node.

4) both child exist.

This is the key in deletion. In this particular case, we want to return the leftmost of the right subtree or rightmost of the left subtree.
In our example, we return the leftmost of the rightsubtree.

Binary Search Tree

http://code.runnable.com/VUTjJDME6nRv_HOe/delete-node-from-bst-for-c%2B%2B

demo download xCode 7.3 (c++)

Adding to Tree Concept

Traverse until you hit a leaf. Then, Re-point at the leaf

Finding from Tree Concept

Traverse if data does not match. If at leaf, return NULL.

1) we need the node back, hence, we return our traversals.
2) When we find our target node, we return a new Node with that value. That return will return traverse back.
3) If nothing is found then we return NULL.

Running Time

Average Time

Access: O(log(n))
Search: O(log(n))
Insertion: O(log(n))
Deletion: O(log(n))

Worst Time (due to unbalanced tree that deteriorates to a linear tree

Access: O(n)
Search: O(n)
Insertion: O(n)
Deletion: O(n)

The Node – building block of the Binary Search Tree

First we must create the building block of the tree. It is an object with a data container, a left pointer, and right pointer. Each pointer denotes a leaf.

You can initialize this object by value, and set both leafs to NULL.
Or you can pass in data to set everything.

Creating a BST tree

First we create the BST class. The key thing here is to add a private member for the root Node. This is the starting point of all tree manipulations.
Then we add the void addNode(Node * root, int newVal) for adding data algorithm.

Adding Nodes O(log n)

We start at the root node, and check the value of it with the incoming new value.

If the new value is larger than the root, then:

1) If the right node exist, we move down the right side of the tree via recursion.
2) If the right node is NULL, we create a new Node, and point it to the right node.

If the new value is smaller or equal than the root, then:

1) If the left node exist, we move down the left side of the tree via recursion.
2) If the left node is NULL, we create a new Node, and point it to the left node.

http://stackoverflow.com/questions/9456937/when-to-use-preorder-postorder-and-inorder-binary-search-tree-traversal-strate

Depth First Search – Pre order (left side)

print
recursion left
recursion right

If you know you need to explore the roots before inspecting any leaves, you pick pre-order because you will encounter all the roots before all of the leaves.

Depth First Search – Post order (right side)

recursion left
recursion right
print

If you know you need to explore all the leaves before any nodes, you select post-order because you don’t waste any time inspecting roots in search for leaves.

Depth First Search – In order (bottom side)

recursion left
print
recursion right

If you know that the tree has an inherent sequence in the nodes, and you want to flatten the tree back into its original sequence, than an in-order traversal should be used. The tree would be flattened in the same way it was created. A pre-order or post-order traversal might not unwind the tree back into the sequence which was used to create it.

Search for a value O(log n)

Search a value in the binary tree is the fastest. The time is O(log n).

If the node is not NULL, we recursively go down the tree according to if the “to get” value is larger or smaller. Then when we hit a node value that matches, we just return the current node.

Deletion O(log n)

Deletion is O(log n + k).

Delete All Nodes

The idea behind deleting all the nodes is a thorough recursion through the left and right.

We delete in 2 situations:

1) delete the node if it has no children
2) delete the node after left and right recursion.

given that if a root is NULL, we just return.
If a node has one child (and the other is NULL), then the NULL leaf just returns.
We recurse down the child.

BST.cpp

Testing it all