Rotate Matrix by One


http://www.cnblogs.com/yrbbest/p/5165084.html
记得有道Amazon的OA题目,好像是给定一个矩阵,让把矩阵的每个元素向右shift一个位置。这道题之前没有好好自习想过。今天正好刷到了rotate matrix,所以正好一块想了。 
思路是类似LeetCode Spiral Matrix:
  1. 假设矩阵为方阵
  2. 设置top, left, bot, right四个边界变量,然后从最外圈到最内圈一圈一圈的shift。
  3. 设定一个count,当count < total elements in matrix的时候进行shift
  4. 在每一圈开始的时候记录下来matrix[top][left],然后开始shift
    1. 从top到bot
    2. 从left到right
    3. 从bot到top
    4. 从right到left
      1. 在最后一条边的结果尝试更新新的matrix[top][left],这时候的top为旧的,而left已经更新过一次了, 我们要分为两种情况考虑
        1. count != totalElements - 1, 这时候我们要:
          1. matrix[top][left] 更新为tmp
          2. count++
          3. top++
          4. 进入下一圈
        2. 否则 count == totalElements - 1,也要分为两种情况
          1. totalElements为奇数,我们不改变matrix[top][left]
          2. totalElements为偶数,这时我们依然要更新一次matrix[top][left] = tmp
        3. 然后count++结束循环返回结果
  5. 假如给定矩阵不为方阵,则我们还要加入更多判断,比如剩下最后一行或者最后一列的时候不更新之类的。最后一行或者最后一列可以由bot - top 或者 right - left分别求出
Time Complexity - O(mn),Space Complexity - O(1),  in place。
    public void rotateMatrixByOne(int[][] matrix) {
        if (matrix == null || matrix[0] == null) {
            return;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, top = 0, right = n - 1, bot = m - 1;
        int count = 0;
        int totalElements = m * n;
        
        while (count < totalElements) {            
            int tmp = matrix[top][left];            
            if (count < totalElements) {
                for (int i = top; i < bot; i++) {
                    matrix[i][left] = matrix[i + 1][left];
                    count++;
                }
                left++;
            }
            if (count < totalElements) {
                for (int i = left - 1; i < right; i++) {
                    matrix[bot][i] = matrix[bot][i + 1];
                    count++;
                }
                bot--;
            }
            if (count < totalElements) {
                for (int i = bot + 1; i > top; i--) {
                    matrix[i][right] = matrix[i - 1][right];
                    count++;
                }
                right--;
            }
            if (count < totalElements) {
                for (int i = right + 1; i > left; i--) {
                    matrix[top][i] = matrix[top][i - 1];
                    count++;
                }
                if (count != totalElements - 1) {
                    matrix[top][left] = tmp;
                } else if (totalElements % 2 == 0) {
                    matrix[top][left] = tmp;
                }
                count++;
                top++;
            }            
        }        
    }

Frobenius coin problem - GeeksforGeeks


Frobenius coin problem - GeeksforGeeks
Given two coins of denominations "X" and "Y" respectively, find the largest amount that cannot be obtained using these two coins (assuming infinite supply of coins) followed by the total number of such non obtainable amounts, if no such value exists print "NA".

Input : X=2, Y=5  
Output: Largest amount = 3
        Total count  = 2
We cannot represent 1 and 3 from infinite supply
of given two coins. The largest among these 2 is 3.
We can represent all other amounts for example 13
can be represented 2*4 + 5.

Input : X=5, Y=10
Output: NA
There are infinite number of amounts that cannot
be represented by these two coins.
One important observation is, if GCD of X and Y is not one, then all values that can be formed by given two coins are multiples of GCD. For example if X = 4 and Y = 6. Then all values are multiple of 2. So all values that are not multiple of 2, cannot be formed by X and Y. Thus there exist infinitely many values that cannot be formed by 4 and 6, and our answer becomes “NA”.
This general problem for n coins is known as classic Forbenius coin problem.
When the number of coins is two, there is 
explicit formula if GCD is not 1. The formula
is:
  Largest amount A = (X * Y) - (X + Y)
  Total amount = (X -1) * (Y - 1) /2 
 
Hence, we can now easily answer the above question by following the below steps:
  1. Calculate GCD of X and Y
  2. If GCD is 1 then required largest amount is (X*Y)-(X+Y) and total count is (X-1)*(Y-1)/2
  3. Else print “NA”
int gcd(int a, int b)
{
    int c;
    while (a != 0)
    {
        c = a;
        a = b%a;
        b = c;
    }
    return b;
}
 
// Function to print the desired output
void forbenius(int X,int Y)
{
    // Solution doesn't exist if GCD is
    // not 1
    if (gcd(X,Y) != 1)
    {
        cout << "NA\n";
        return;
    }
 
    // Else apply the formula
    int A = (X*Y)-(X+Y);
    int N = (X-1)*(Y-1)/2;
 
    cout << "Largest Amount = " << A << endl;
    cout << "Total Count = " << N << endl;
}
Read full article from Frobenius coin problem - GeeksforGeeks

Comb Sort - GeeksforGeeks


Comb Sort - GeeksforGeeks
Comb Sort is mainly an improvement over Bubble Sort. Bubble sort always compares adjacent values. So allinversions are removed one by one. Comb Sort improves on Bubble Sort by using gap of size more than 1. The gap starts with a large value and shrinks by a factor of 1.3 in every iteration until it reaches the value 1. Thus Comb Sort removes more than one inversion counts with one swap and performs better than Bublle Sort.
The basic idea is to eliminate turtles, or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously.Rabbits, large values around the beginning of the list, do not pose a problem in bubble sort.
In bubble sort, when any two elements are compared, they always have a gap (distance from each other) of 1. The basic idea of comb sort is that the gap can be much more than 1 (Shell sort is also based on this idea, but it is a modification of insertion sort rather than bubble sort).
In other words, the inner loop of bubble sort, which does the actual swap, is modified such that gap between swapped elements goes down (for each iteration of outer loop) in steps of shrink factor. i.e. [ input size / shrink factor, input size / shrink factor^2, input size / shrink factor^3, ...., 1 ]. Unlike in bubble sort, where the gap is constant i.e. 1.
// To find gap between elements
int getNextGap(int gap)
{
    // Shrink gap by Shrink factor
    gap = (gap*10)/13;
 
    if (gap < 1)
        return 1;
    return gap;
}
 
// Function to sort a[0..n-1] using Comb Sort
void combSort(int a[], int n)
{
    // Initialize gap
    int gap = n;
 
    // Initialize swapped as true to make sure that
    // loop runs
    int swapped = true;
 
    // Keep running while gap is more than 1 and last
    // iteration caused a swap
    while (gap != 1 || swapped == true)
    {
        // Find next gap
        gap = getNextGap(gap);
 
        // Initialize swapped as false so that we can
        // check if swap happened or not
        swapped = false;
 
        // Compare all elements with current gap
        for (int i=0; i<n-gap; i++)
        {
            if (a[i] > a[i+gap])
            {
                swap(a[i], a[i+gap]);
                swapped = true;
            }
        }
    }
}

Read full article from Comb Sort - GeeksforGeeks

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts