Skip to main content

Posts

Big Data

Big Data Analytics Introduction 5 Vs of Big Data Volume Velocity Variety Veracity value Big Data Infrastructure ( Slide P38 ) Reliable Distributed File system Data kept in “chunks” spread across machines Each chunk replicated on different machines.(if machine/disk) failure, recovery seamlessly) Bring computation directly to data Chunk servers also servers as compute servers Societal concerns: privacy, algorithmic black boxes, filter bubble. MapReduce Programming model: A programming model, a parallel, data aware, fault-tolerant implementation mappers:( Slide P11 ) The Map function takes an input element as its argument and produces zero or more key-value pairs. The types of keys and values are each arbitrary. Further, keys are not “keys” in the usual sense; they do not have to be unique. Rather a Map task can produce several key-value pairs with the same key, even from the same element. reducers:( Slide P11 ) The Reduce function’s argument is a p
Recent posts

[Interview]: URLify

[Interview]  URLify: -------------------------------------------------------------------------------------------------------------------------- Question: URLify: Write a method to replace all spaces in a string with ‘%20’, you may assume that the string has sufficient space at the end to hold the additional characters. Example  input: ' mr john smith '  output: ' mr %20john%20smith' --------------------------------------------------------------------------------------------------------------------------   Idea 1:  Start from the back and start replacing until the character is not ' ', and replace the characters in reverse order. Solution 1: public class Solution{ public String replace(char[] str) { boolean flag = false; StringBuffer sb = new StringBuffer(); for (int i = str.length - 1; i >= 0; i--) { if (str[i] != ' ') flag = true; if (flag == true) { if (str[i] == ' ') { s

[Interview] Check Permutation

[Interview] Check Permutation -------------------------------------------------------------------------------------------------------------------------- Question: Given 2 Strings, write a method to decide if one is a permutation of the other. -------------------------------------------------------------------------------------------------------------------------- Idea 1:  count the number of each character in first string and check if the number of each character in the 2nd string is the same as the 1st string. Solution 1: public class Solution{ boolean checker(String str1, String str2) { if (str1.length() != str2.length()) return false; int[] helper = new int[256]; for(int i = 0 ; i<str1.length();i++) { int index = str1.charAt(i); helper[index]++; } for(int i = 0 ; i<str2.length();i++) { int index = str2.charAt(i); helper[index]--; if(helper[index]<0) return false; } return true; } } ---------------------

[Interview] Reverse C-Style String

[Interview] Reverse C/C++ Style String  Question: Write code to reverse a C-Style String. (C-String means that “abcd” is represented as five characters, including the null character.) Solution: public class Solution{ public String reverse(String str) { int p1 = 0; int p2 = str.length() - 1; char temp; char[] c = new char[p2]; c = str.toCharArray(); while (p1 < p2) { temp = c[p1]; c[p1] = c[p2]; c[p2] = temp; p1++; p2--; } return new String(c); } } Complexity Analysis: Time Complexity: \(O(n)\) Space Complexity: \(O(n)\)

[Interview] Check if String has Unique Characters

[Interview] Check if String has Unique Characters Implement an algorithm to determine if a string has all unique characters What if you can not use additional data structure? package com.Array_Strings; /** * @Question: 1-1. Implement an algorithm to determine if a string has all * unique characters What if you can not use additional data * structure? */ public class Ans1_1 { public boolean helper(String str) { boolean[] map = new boolean[256]; for (int i = 0; i < str.length(); i++) { int val = str.charAt(i); if (map[val]) return false; map[val] = true; } return true; } } Complexity Analysis: Time Complexity: \(O(n)\) Space Complexity: \(O(n)\) Here is my Video Explanation

[LeetCode Solution 131]: Palindrome Partitioning

[LeetCode Solution 131]: Palindrome Partitioning ********************************************************************************* Question: Given a string   s , partition   s   such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of   s . For example, given   s   =   "aab" , Return [ ["aa","b"], ["a","a","b"] ] -------------------------------------------------------------------------------------------------- Recursive Method Strategy We are going to use backtracking to solve this problem, the idea is if we find a palindrome  substring, we add it in a temp and go further searching, the idea is as shows in the following picture: Java public class Solution { public List<List<String>> partition(String s) { if (s.length() == 0 || s == null) return null; List<List<String>> res = new ArrayList&

[LeetCode Solution 40]: Combination Sum II

[LeetCode Solution 40]: Combination Sum II ********************************************************************************* Question: Given a collection of candidate numbers ( C ) and a target number ( T ), find all unique combinations in  C  where the candidate numbers sums to  T . Each number in  C  may only be used  once  in the combination. Note: All numbers (including the target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set  [10, 1, 2, 7, 6, 1, 5]  and target, 8 A solution set is:  [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] -------------------------------------------------------------------------------------------------- Approach Recursive Method Strategy The idea is same with the  [LeetCode Solution 39] Combination Sum , using backtracking method, but the only difference is how to get the value that we have to skip that can help us to avoid the duplication. H