Coder's blog @kuriyeedu - Tumblr Blog

Machine Learning Topics

Classification vs. Regression

Linear Regression

Logistic Regression

Decision Trees

Naive Bayes Classifier

Generative vs. Discriminative

Clustering Approaches: K means

Solvers:

Gradient Descent vs. Stochastic Gradient Descent

Convex vs. Non Convex solution space

Different types of Losses - Hinge Loss / 0-1 Loss / Logistic Loss / Adaboost Loss

Boosting vs. Bagging

K-fold Cross validation

Regularization Parameters

Dimensionality Reduction techniques: PCA, SVD, QR Factorization, CUR Decomposition

Recommendation Systems:

Content Based, Collaborative Filtering, Latent Factor Based Approaches

Ensemble Techniques

Page Rank Algorithm

Information Retreival - Bing Search, FB Recommendations

Tools used: pySpark, scikitlearn, MATLAB ML toolbox

Approches : 3 mo/ 3wk/3days solutions

Data cleaning

Feature Extraction vs Feature Selection

Information Gain, Entropy, Linear Indepdence

Kernel Trick

!!!!!!Keep it Simple!!!!

Display description of a movie on search of its title

Stats:

10GB data

250 MB RAM

How many movies are there in this world ? 0.5 million ?

Amount of information per movie available = 10GB/0.5M = 20 KB of information. So most likely textual information and not the movie itself.

How much can 250MB RAM hold ? 12.5K movies at a time - 40 loads of the data per query to search for title. (linear search/binary search - you still need to load data to acknowledge that the section of data is not what you are looking for.!).

Alternative approach - MD5 hash the movie title - 16 bytes (128 bits). Another 200 bytes to store the movie location on disk. = 250 bytes per movie stored in a hash map = 1 M movies can be looked up!

So, when a query comes in, MD5 movie title, look up in hash map, go to disk (IIIIIIII/OOOOO) and fetch the description and display it!

- Multidisk arrays ? and store in hash map the disk location

- RAIDs for greater IOPs.? (Prefer read- friendly RAIDs for cheaper cost)

Use multi-core machine to parallelize request processing.

Find all numbers in an array which sum up to a target value K

There are many flavors to this combinatorics problem. Some well known ones are:

Find the subarray which sums up to target value K

Find pair of elements in an array which sum up to K

Find maximum increasing subsequence in an array

and many more..

#memoization dynamicprogramming sum array

Packing a box of chocolates

Idea:

The problem looks trivial at the outset but its not. If you melt N chocolates of volume \(2 cm^3 \), and then pour it into a box of dimensions a x b x c, the answer is pretty simple. You can fill int (abc/2) chocolates.

Problem here is to pack them into given large box to get maximum number packed.

So, there are couple of factors to be taken into account.

Whether all chocolates are of same dimensions l x b x h ? If yes, then the solution is to find the maximum chocolates that can fit into each dimension and choose them \( max(frac{{a}{a’}} * \frac{{b}{b’}} * \frac{{c}{c’}} \) where a, b, c are dimensions of the large box and a’, b’ and c’ are dimensions of each chocolate.

However, if dimensions of chocolates can be different (sam volume different dimension boxes), then the problem in non trivial

Here is a similar challenge at Kaggle: https://www.kaggle.com/c/packing-santas-sleigh

The final winners’s solution strategy is discussed here:

https://www.kaggle.com/c/packing-santas-sleigh/forums/t/6934/how-d-you-do-it/38027#post38027

#packing volume bin

Amazon DQ Price Tracking Website

Question:

Solution:

Current popular Amazon price tracking systems are:

Amazon Price Tracker

camelcamelcamel

tracktor

Amazon Standard Identification Number (ASIN)

Background:

1. Price tracking infrastructure - PULL MODEL: more like a web scraping tool which can monitor prices of various item urls online

Bots to crawl websites looking for templated information

(or) More web scraping techniques looking for specific html tags of prices can also be employed.

(or) Subscription to RSS Feeds to indicate price changes

vs.

PUSH MODEL: Where Amazon provides an event on price changes which the clients can subscribe to.

This guarantees that an infrastructure to notify the server when prices change is available.

Architecture: Real time distributed system which runs web scraper on different target websites on a time-to-time basis.

2. Notification infrastructure - on a price of a given item changing, the server needs to update its database on price it has previously recorded for the specific item. If the current price of the item falls below a target price given by any user, the user needs to be sent an email alert.

Two APIs need to be published.

UpdateItemPrice(ASIN, Price) - updates database of the price change

NotifyUsers(EmailID); - collects the list of users who qualify for an alert due to the price change mentioned.

Database Design:

SQL databases are sufficient as the data is fairly structured.

ItemDB - {ASIN/ ItemID, Price, DateUpdated} - Every time a price changes, this table gets an entry. Keeps entries for the last N days for search and keeps others for archival.

UserDB { UserID, Email ID} - alerting mechanism if user-to-email requires a unique relationship

AlertDB{UserID, ItemID, TargetPrice}

When there is a UpdateItemPrice API called, ItemDB gets updated. It further collects a list of users who qualify for alert - by scanning through AlertDB for given ItemURL and TargetPrice > current price. For each candidate user, gets email id from UserDB, notifies them using NotifyUsers.

Scalability:

Distributed SQL DBs which stores user records of a specific IP Domain

Fault Tolerance:

Backup servers to regularly update the last reads and writes

Cache on servers at transaction log level - log first model on update prices information - which can recreate the list of transactions in case the server goes down suddenly.

Other features / analytics:

Trends of item prices of a specific group for the last N days

Item Recommendations based on user features to track different set of items which match the item which is tracked by the user and based on what similar users are tracking. - Collaborative Filtering + Content Based Systems.

References:

http://www.techlicious.com/tip/these-4-price-trackers-could-save-you-a-fortune/

http://www.makeuseof.com/tag/3-amazon-price-watch-trackers-bargain-hunter/

To understand the polling / push model architecture better on price tracking, I have put up a question in Quora:

https://www.quora.com/What-infrastructure-real-time-or-distributed-infrastructure-do-price-tracking-systems-have-eg-tracktor-com-Amazon-price-tracker-system?__snids__=1401983277&__nsrc__=2

#design #price tracking

Leetcode Q#253

Meeting Rooms II

Solution Strategy:

This is a classic event overlap problem. The general idea is, at any timestamp from a given start time to end time, count the number of events at the timestamp. If the number of events > 1, you will need that many number of meeting rooms.

How to calculate this:

Sort start times and end times of all intervals together in ascending order

For each time t, increment its count (for number of intervals) if an interval starts at t

For each time t, decrement its count (for number of intervals) if an interval end at t

Scan through the vector of time slots again, find the max number of intervals at any time. This is equivalent of the number of meeting rooms required.

Complexity:

Time:

O(n) to scan through the list to 1) create time slot in time slot vector, 2) increment /decrement for an interval +

O(2*n) finding the max number of intervals at any time slot. = O(n)

Space: O(n) to maintain a vector of timeslots.

/** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */ class Solution { private: static bool myCompare(int X, int Y){ return (X < Y); } public: int minMeetingRooms(vector<Interval>& intervals) { if (intervals.size() <=1 ) { return intervals.size(); } std::vector<int> meetingTimes; for(int i=0; i<intervals.size(); i++){ meetingTimes.push_back(intervals[i].start); meetingTimes.push_back(intervals[i].end); } std::unique(meetingTimes.begin(), meetingTimes.end()); std::sort(meetingTimes.begin(), meetingTimes.end(), myCompare); std::map<int, int> meetingTimeToIndexMap; for(int i=0; i<meetingTimes.size(); i++){ meetingTimeToIndexMap.insert({meetingTimes[i], i}); } std::vector<int> activeMeetings(meetingTimes.size(), 0); for(int i=0; i<intervals.size(); i++){ Interval& meeting = intervals[i]; int startIndex = meetingTimeToIndexMap[meeting.start]; int endIndex = meetingTimeToIndexMap[meeting.end]; activeMeetings[startIndex]++; activeMeetings[endIndex]--; } //cumulative sum at any index for(int i=1; i<activeMeetings.size(); i++){ activeMeetings[i] = activeMeetings[i] + activeMeetings[i-1]; } return *std::max_element(activeMeetings.begin(), activeMeetings.end(), myCompare); } };

#greedy meeting overlap interval sort

Leetcode Q#252

Meeting Rooms

Solution Strategy:

Sort intervals by end time

Scan from first interval to last

For any pair of adjacent intervals a, b, if a.end < a.start => CONFLICT

Complexity:

Time: O(nlogn), Space: O(1)

/** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */ class Solution { public: bool canAttendMeetings(vector& intervals) { if (intervals.size() geq 1){ return true; } std::sort(intervals.begin(), intervals.end(), [](Interval a, Interval b){ return a.end lt b.end;}); //sorted by end times for(int i=1; i gt intervals.size(); i++){ if (intervals[i].start gt intervals[i-1].end) { return false; } } return true; } };

#sort

Leetcode Q#280

Wiggle Sort

Solution Strategy:

min element if i%2 ==0

max element if i%2 == 1

Complexity:

Time: O(n^2) Space: O(1)

class Solution { private: void swap(vector& nums, int sIndex, int destIndex, bool isAscending){ if((isAscending && (nums[sIndex] > nums[destIndex])) || (!isAscending && (nums[sIndex] < nums[destIndex]))){ int temp = nums[sIndex]; nums[sIndex] = nums[destIndex]; nums[destIndex] = temp; } } public: void wiggleSort(vector& nums) { if (nums.size() geq 1) { return ;} for(int i=0; i gt nums.size()-1;i++){ if(i%2 ==0){ int minIndex = (std::min_element(nums.begin()+i+1, nums.end()) - nums.begin()); swap(nums, i, minIndex, true); //else dont swap. }else{ int maxIndex = (std::max_element(nums.begin()+i+1, nums.end()) - nums.begin()); swap(nums, i, maxIndex, false); } } } };

#sort array

Leetcode Q#179

Largest Number

Solution Strategy:

At the outset, the problem looks like, if the lexicographic order of the numbers are taken into account for arranging them, the solution is ready.

Great. Seems to work! For example, 5, 34, 9′s lexicographic descending order is 9534 which is indeed the largest number that can be formed.

Trouble: Example: two numbers 12, 121 are present, 12 appears after 121 in descending order and hence 12112 seems like the answer. 12121 is however larger than 12112!!

Fix:

Compare sequences XY and YX given two numbers Y and X. Choose the combination which serves the larger number.

How to compare ?

Use std::sort and a custom sort comparator.

class Solution { private: static int myCompare(string X, string Y){ string XY = X.append(Y); string YX = Y.append(X); return XY.compare(YX) > 0 ? 1:0; } public: string largestNumber(vector& nums) { // lexicographic order of strings vector numbersAsStrings; for(auto x: nums){ stringstream ss; ss.append(x); numbersAsStrings.push_back(ss.str()); } stringstream ss; std::sort(numbersAsStrings.begin(), numbersAsStrings.end(), myCompare); for( auto x: numbersAsStrings){ ss.append(x); } if (atoi(ss.str().c_str()) == 0){ return "0"; } return ss.str(); } };

#sort

Leetcode Q#106

Binary tree from In order and post order traversal

Solution strategy:

Inorder = Left Root Right,

Post Order = Left Right Root

for a given tree, postorder[end] = Root of the tree.

Locate the root in inorder

All elements from 0 to root position in inorder array form the left tree.

If there are k elements in left subtree, then elements from position 0 to k-1 in post order sequence form the left subtree.

All elements from root position + 1 to end for right subtree i.e. n-k-1 elements; All elements from position k to end-1 form right subtree.

Recursively apply these post order and in order sequences for left and right subtrees

Complexity:

Time: O(n), Space: O(1)

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { private: TreeNode* buildTree(vector& inorder, vector&postorder, int iS, int iE, int pS, int pE){ if (postorder.size() == 0 || inorder.size() == 0) { return NULL; } int numElements = iE-iS + 1; if (numElements < 0) { return NULL; } TreeNode* root = new TreeNode(postorder[pS+numElements-1]); if (numElements == 1) { return root; } //find root in inorder array int i=iS; for(; i < iS+numElements; i++){ if(inorder[i] == root->val){ break; } } if (i == iS + numElements){ // element was not found in the sequence. In valid sequences. return NULL; } // i - root is present in inorder // 0 to i-1 = left subtree // i+1 to numElements-1 = right subtree; int numLeftElements = i-iS; int numRightElements = numElements- numLeftElements -1; if(numLeftElements > 0){ root->left = buildTree(inorder, postorder, iS, i-1, pS, pS + numLeftElements - 1); } if (numRightElements > 0){ root->right = buildTree(inorder, postorder, i+1, iS + numElements-1, pS + numLeftElements, pE-1); } return root; } public: TreeNode* buildTree(vector& inorder, vector& postorder) { return buildTree(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1); } };

Leetcode Q#117

Populating next right pointers in each node for a non-complete binary tree

Solution strategy:

Ideas: The given tree is not complete binary tree. No additional space should be used. [Level order traversal and updating next pointers of nodes in each level is a brute force fix but violates the given constraint]. So what to do? Do a level order traversal in place without using additional space.

for each node n, parent p

If n is the left child of p and p has a right child, connect the siblings

Otherwise,

n is the right child (OR), p has no right child for n to connect to - Find first sibling of p who has a right or a left child. Connect with him

Update n to n->next and repeat

When all nodes in a level are done.

Identify the first non leaf node k in level of n.

Identify the non null child - left or right of k

Do 1-2 with n = k->left or k->right (whichever is non null) and p = k;

Complexity: Time O(n), Space: O(1)

/** * Definition for binary tree with next pointer. * struct TreeLinkNode { * int val; * TreeLinkNode *left, *right, *next; * TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {} * }; */ class Solution { public: void connectDanglers(TreeLinkNode* root, TreeLinkNode* parent){ if(!root) { return;} TreeLinkNode* n = root, *p = parent; if (!parent){ p = root; } else{ //parent exists while(n && p){ if ((n == p->left) && p->right){ n->next = p->right; }else{ //n is left node with no right sibling (or) // n is right node TreeLinkNode* nP = p->next; while(nP){ if(nP->left) { n->next = nP->left; p = nP; break; }else if(nP->right){ n->next = nP->right; p = nP; break; } nP = nP->next; } } n = n->next; } //find first node in the left for the next level p = root; while(p && !p->left && !p->right){ p = p->next; } } if(p) { if(p->left){ connectDanglers(p->left, p); } else if(p && p->right){ connectDanglers(p->right, p); } } else{ return; } } void connect(TreeLinkNode *root) { if(!root) { return; } connectDanglers(root, NULL); return; } };

Leetcode Q#116

Populating next right pointers in each node

Solution strategy:

Ideas: the given tree is a complete binary tree. So, at each level, all nodes definitely have a right and left subtree.

For each of the node in the right most path of the left subtree, connect it to node in the same level along the left most path of the right subtree

Recursively connect left subtree and right subtree

Complexity: Time O(n), Space O(1)

/** * Definition for binary tree with next pointer. * struct TreeLinkNode { * int val; * TreeLinkNode *left, *right, *next; * TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {} * }; */ class Solution { public: void connect(TreeLinkNode *root) { if(!root) { return; } if (!root->left && !root->right) { return; } if (root->left && root->right){ //connect left most child of right subtree and right most child of left subtree TreeLinkNode* p = root->left; TreeLinkNode* q = root->right; while(p && q) { p->next = q; p = p->right; q = q->left; } //recursvely connect root->left and root->right nodes connect(root->left); connect(root->right); } return; } };

Leetcode Q#173

Binary Search Tree Iterator

Solution Strategy:

Task is to implement

Constructor of the iterator

hasnext()

next()

Implement an inorder traversal of the tree. Use an “internal” variable to track current index in the inorder array.

Use that to implement hasnext() and next() methods.

Complexity: Time O(n), Space O(n)

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class BSTIterator { public: BSTIterator(TreeNode *root) { mNode = root; inOrderTraversal(mInorderNodes, root); if(mInorderNodes.size()) { curIndex = -1; } } /** @return whether we have a next smallest number */ bool hasNext() { if (curIndex+1 < mInorderNodes.size()){ return true; } } /** @return the next smallest number */ int next() { if (hasNext()){ int nextElement = mInorderNodes[curIndex + 1]; curIndex++; return nextElement; } return mInorderNodes[curIndex]; } private: void inOrderTraversal(vector& inorderNodes, TreeNode* root){ if(!root) { return;} if (!root->left && !root->right) { inorderNodes.push_back(root->val); return; } inOrderTraversal(inorderNodes, root->left); inorderNodes.push_back(root->val); inOrderTraversal(inorderNodes, root->right); return; } TreeNode* mNode; vector mInorderNodes; int curIndex; }; /** * Your BSTIterator will be called like this: * BSTIterator i = BSTIterator(root); * while (i.hasNext()) cout << i.next(); */

#trees iterator

Leetcode Q#94

Binary Tree Inorder Traversal

Solution strategy:

Overall idea is to create a stack and maintain node information which is otherwise maintained for free by program call stack in a recursive solution

Use a stack - push right node, root node and left node.

Pop stack, c = pop();

If c is already visited, add c to the in order traversal order .

Otherwise, push c’s right node, c [Mark c as visited in another datastructure] and c’s left node.

Repeat 1-4 until stack is empty

Complexity:

Time: O(n) Space: O(n)

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Stack{ public: TreeNode* pop(){ TreeNode* temp = elems.back(); elems.erase(elems.end()-1); return temp; } void push(TreeNode* node) { elems.push_back(node); } bool isEmpty(){ return (elems.size() == 0); } private: vector elems; }; enum MARKNODE{UNVISITED=0, VISITED=1, IGNORE=2}; class Solution { public: vector inorderTraversal(TreeNode* root) { vector inOrderTraversal; if(!root) { return inOrderTraversal; } Stack s; std::map isVisited; if (root->right){ s.push(root->right); isVisited.insert({root->left, MARKNODE::UNVISITED}); } s.push(root); isVisited.insert({root, MARKNODE::UNVISITED}); if(root->left){ s.push(root->left); isVisited.insert({root->left, MARKNODE::UNVISITED}); } while(!s.isEmpty()){ TreeNode* p = s.pop(); if (isVisited[p] == MARKNODE::VISITED){ inOrderTraversal.push_back(p->val); isVisited[p] = MARKNODE::IGNORE; } if (isVisited[p] == MARKNODE::UNVISITED){ if(p->right ){ s.push(p->right);} s.push(p); isVisited[p] = MARKNODE::VISITED; if(p->left) { s.push(p->left); } } } return inOrderTraversal; } };

#trees #iterative #inorder #traversal

Leetcode Q#113

Path Sum II

Solution Strategy:

Carry a vector which contains all ancestors seen in a given path.

When a node is leaf, check if the desired sum is met. If yes, add leaf node to the vector. Add vector to the set of all paths maintained for the sum

Complexity:

Time: O(n) [ need to go through all paths to check if path sums to given sum ]

Space: O(n log n) [ need to maintain a vector of path for n/2 leaves]

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { private: void checkPathSums(vector>& allPaths, vector pathSoFar, TreeNode* root, int desiredSum){ if(!root) { return; } if(!root->left && !root->right){ // leaf if(root->val == desiredSum){ pathSoFar.push_back(desiredSum); allPaths.push_back(pathSoFar); } }else{ //non leaf pathSoFar.push_back(root->val); if(root->left){ checkPathSums(allPaths, pathSoFar, root->left, desiredSum - root->val); } if(root->right){ checkPathSums(allPaths, pathSoFar, root->right, desiredSum - root->val); } } return; } public: vector> pathSum(TreeNode* root, int sum) { vector> allPaths; vector pathSoFar; checkPathSums(allPaths, pathSoFar, root, sum); return allPaths; } };

#trees #recursion #sum

Toughies in Trees

Extract tree given preorder and inorder traversal

Extract tree given preorder and post order traversal

Watch out:

Preorder traversal - iteratively.

Inorder successor

LCA of BST and BT

Different flavors of level order

Right side view of tree

level order upside down

level order zig zag

Given complete tree, count the number of nodes

Kth smallest element

Leetcode Q#173

BST Iterator

Solution Strategy:

#trees BST Iterator

Trending Blogs

Recently Viewed Blogs

Coder's blog