Friday, November 21, 2014

Foldable Binary Trees - Given a binary tree, find out if the tree can be folded or not.

Problem

Given a binary tree, find out if the tree can be folded or not.
A tree can be folded if left and right subtrees of the tree are structure wise mirror image of each other. An empty tree is considered as foldable.

Examples


Consider the below trees:
(a) and (b) can be folded.
(c) and (d) cannot be folded.

(a)
       10
     /    \
    7      15
     \    /
      9  11

(b)
        10
       /  \
      7    15
     /      \
    9       11

(c)
        10
       /  \
      7   15
     /    /
    5   11

(d)

         10
       /   \
      7     15
    /  \    /
   9   10  12

Solution


Method 1 (Change Left subtree to its Mirror and compare it with Right subtree)
Algorithm: isFoldable(root)
1) If tree is empty, then return true.
2) Convert the left subtree to its mirror image
    mirror(root->left); /* See this post */
3) Check if the structure of left subtree and right subtree is same
   and store the result.
    res = isStructSame(root->left, root->right); /*isStructSame()
        recursively compares structures of two subtrees and returns
        true if structures are same */
4) Revert the changes made in step (2) to get the original tree.
    mirror(root->left);
5) Return result res stored in step 2. 


Method 2 - Using recursion
here is the pseudocode:

boolean mirrorEquals(BTree left, BTree right) {
  if (left == null || right == null) 
             return left == null && right == null;
  return left.value == right.value && mirrorEquals(left.left, right.right) && mirrorEquals(left.right, right.left);
}

Method 3 - Iteratively

bool isMirrorItselfIteratively(BinaryTreeNode *root) 
{
    /// use single queue
    if(!root) return true;
    queue<BinaryTreeNode> q;
    q.push(root.left);
    q.push(root.right);
    BinaryTreeNode l, r;
    while(!q.empty()) {
        l = q.front();
        q.pop();
        r = q.front();
        q.pop();
        if(l==NULL && r==NULL) continue;
        if(l==NULL || r==NULL || l.data!=r.data) return false;
        q.push(l.left);
        q.push(r.right);
        q.push(l.right);
        q.push(r.left);
    }

    return true;
}


Thanks.

References 

Saturday, October 18, 2014

Given a node in binary tree - Check if left and right subtree are mirror of each other

Problem

A binary tree is a mirror image of itself if its left and right subtrees are identical mirror images i.e., the binary tree is symmetrical. This is best explained with a few examples.


Example


  1
 / \
2   2
TRUE
   1
  / \
 2   2
  \
   3
FALSE
     1
   /   \
  2     2
 / \   / \
4   3 3   4
TRUE
       1
     /   \
    2     2 
   / \   / \
  3   4 3   4
FALSE
       1
     /   \
    2     2
   /       \
  3         3
TRUE

Solution

Method 1 - Recursiion mirrorEquals(BTree left , BTree right)
Basically compare the left subtree and inverted right subtree, drawing an imaginary line of inversion across root.
boolean mirrorEquals(BTree left, BTree right) {
  if (left == null || right == null) return left == null && right == null;
  return left.value == right.value 
         && mirrorEquals(left.left, right.right) 
   && mirrorEquals(left.right, right.left);
}

Method 2 - Iterative solution using queue
Insert 2 elements at a time and then pop and compare the values, and continue to do with the children.


bool isMirrorItselfIteratively(BTree root) 
{
    /// use single queue and initial push
    if(!root) return true;
    queue<btree> q;
    q.push(root.left);
    q.push(root.right);
 
    BTree l, r;
    while(!q.empty()) {
        l = q.front();
        q.pop();
        r = q.front();
        q.pop();
        if(l==NULL && r==NULL) continue;
        if(l==NULL || r==NULL ) return false;
  if(l.data!=r.data) return false;
  //not the push ordering
        q.push(l.left);
        q.push(r.right);
        q.push(l.right);
        q.push(r.left);
    }

    return true;
}

References 

Friday, October 17, 2014

Queue ADT

Definition :-
A queue is a collection of same type of entities, which ensures that all entities in collection will have a sequential storage structure that permits access only at the two ends of the sequence.  We refer to the ends of the sequence as the front and rear.  The first element in queue have the position as front and value or pointer or front changes according to the solution of the given problem. Rear is the terminal position of the queue, this can be the position of the last element or last point of the queue. A queue inserts new elements at the rear and removes elements from the front of the sequence, to maintain the sequential storage structure.  You will note that a queue removes elements in the same order in which they were stored, and hence a queue provides FIFO (first-in / first-out), or FCFS (first-come, first-served), ordering.


Example :-  Consider that you and your family went zoo. First you have to buy a ticket, so you or one of member of your group have to join the line for ticket counter. every person in that line will get the ticket in same sequence, in which they join that line. So this is one of the common example of queue.
 

Advanced Data Structure of Queue:- 

Advanced data structure involve the following steps:
  • how to define a data structure type,
  • create a data structure to implement the function performed by or associated to the new type
  • implement the above two in any programming language.
There are many operations which we can perform with a queue to solve any problem. Basic operations or function of queue are as follows:
  • queue() creates a new queue that is empty. It needs no parameters and returns an empty queue.
  • enqueue(item) adds a new item to the rear of the queue. It needs the item and returns nothing.
  • dequeue() removes the front item from the queue. It needs no parameters and returns the item. The queue is modified.
  • isEmpty() tests to see whether the queue is empty. It needs no parameters and returns a boolean value.
  • size() returns the number of items in the queue. It needs no parameters and returns an integer.

Tuesday, September 23, 2014

Maximum number of chickens you cannot order

Problem

There is a non vegetarian restaurant which sells chicken in orders of 6, 9 and 20.

Calculate the maximum number of chicken pieces you cannot order from that restaurant ?

Solution

43

If you analyze, then you will find that all the 6 numbers divisible by 3 can be ordered. Why? Because you can break them own as the sum of 6 and 9.
Now after 26, all the numbers that are divisible by 3 if subtracted by 40 can be obtained.
After 46, all the numbers will fit into one of the above categories and thus all such numbers can be obtained. But 43 will be last number that will not fall into one of the above categories.
44 = 20 + 6 * 4, 45 = 6 * 6 + 9





Wednesday, July 30, 2014

Union and Intersection of two unsorted Linked Lists

Problem

Given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. Order of elments in output lists doesn’t matter.

Example

Input:
   List1: 10->15->4->20
   lsit2:  8->4->2->10
Output:
   Intersection List: 4->10
   Union List: 2->8->20->4->15->10

Solution

Method 1 - Simple
Following are simple algorithms to get union and intersection lists respectively.
Intersection (list1, list2)
Initialize result list as NULL. Traverse list1 and look for its each element in list2, if the element is present in list2, then add the element to result.
Union (list1, list2):
Initialize result list as NULL. Traverse list1 and add all of its elements to the result.
Traverse list2. If an element of list2 is already present in result then do not insert it to result, otherwise insert.
This method assumes that there are no duplicates in the given lists.
Java code:
bool isPresent (Node head, int data)
{
    Node t = head;
    while (t != NULL)
    {
        if (t.data == data)
            return true;
        t = t.next;
    }
    return false;
}   
 
 
// Function to get union of two linked lists head1 and head2 /
Node getUnion (Node head1, Node head2)
{
    Node result = NULL;
    Node t1 = head1, t2 = head2;
 
    // Insert all elements of list1 to the result list
    while (t1 != NULL)
    {
        push(&result, t1.data);
        t1 = t1.next;
    }
 
    // Insert those elements of list2 which are not present in result list
    while (t2 != NULL)
    {
        if (!isPresent(result, t2.data))
            push(&result, t2.data);
        t2 = t2.next;
    }
 
    return result;
}
 
// Function to get intersection of two linked lists head1 and head2 
Node getIntersection (Node head1, Node head2)
{
    Node result = NULL;
    Node t1 = head1;
 
    // Traverse list1 and search each element of it in list2. If the element
    // is present in list 2, then insert the element to result
    while (t1 != NULL)
    {
        if (isPresent(head2, t1.data))
            push (&result, t1.data);
        t1 = t1.next;
    }
 
    return result;
}
 
// A utility function to insert a node at the begining of a linked list/
void push (Node headRef, int newData)
{
    // allocate node /
    Node newNode = new Node();
 
    // put in the data /
    newNode.data = newData;
 
    // link the old list off the new node /
    newNode.next = (headRef);
 
    // move the head to point to the new node /
    (headRef) = newNode;
}

Time Complexity: O(mn) for both union and intersection operations.
Here m is the number of elements in first list and n is the number of elements in second list.

Method 2 - Use Merge Sort
In this method, algorithms for Union and Intersection are very similar. First we sort the given lists, then we traverse the sorted lists to get union and intersection.
Following are the steps to be followed to get union and intersection lists.
1) Sort the first Linked List using merge sort. This step takes O(mLogm) time. Refer this post for details of this step.
2) Sort the second Linked List using merge sort. This step takes O(nLogn) time. Refer this post for details of this step.
3) Linearly scan both sorted lists to get the union and intersection. This step takes O(m + n) time. This step can be implemented using the same algorithm as sorted arrays algorithm discussed here.
Time complexity of this method is O(mLogm + nLogn) which is better than method 1′s time complexity.

Method 3 (Use Hashing)
Union (list1, list2)
Initialize the result list as NULL and create an empty hash table. Traverse both lists one by one, for each element being visited, look the element in hash table. If the element is not present, then insert the element to result list. If the element is present, then ignore it.
Intersection (list1, list2)
Initialize the result list as NULL and create an empty hash table. Traverse list1. For each element being visited in list1, insert the element in hash table. Traverse list2, for each element being visited in list2, look the element in hash table. If the element is present, then insert the element to result list. If the element is not present, then ignore it.
Both of the above methods assume that there are no duplicates.
Time complexity of this method depends on the hashing technique used and the distribution of elements in input lists. In practical, this approach may turn out to be better than above 2 methods.



References

Union and Intersection of two sorted arrays

Problem

Find  Union and Intersection of two sorted arrays

Example

For example, if the input arrays are:
arr1[] = {1, 3, 4, 5, 7}
arr2[] = {2, 3, 5, 6}
Then your program should print Union as {1, 2, 3, 4, 5, 6, 7} and Intersection as {3, 5}.


Solution

Algorithm Union(arr1[], arr2[]):
For union of two arrays, follow the following merge procedure.
1) Use two index variables i and j, initial values i = 0, j = 0
2) If arr1[i] is smaller than arr2[j] then print arr1[i] and increment i.
3) If arr1[i] is greater than arr2[j] then print arr2[j] and increment j.
4) If both are same then print any of them and increment both i and j.
5) Print remaining elements of the larger array.
#include<stdio.h>
#include<stdio.h>
int printUnion(int arr1[], int arr2[], int m, int n)
{
  int i = 0, j = 0;
  while(i < m && j < n)
  {
    if(arr1[i] < arr2[j])
      printf(" %d ", arr1[i++]);
    else if(arr2[j] < arr1[i])
      printf(" %d ", arr2[j++]);
    else
    {
      printf(" %d ", arr2[j++]);
      i++;
    }
  }
 
  // Print remaining elements of the larger array
  while(i < m)
   printf(" %d ", arr1[i++]);
  while(j < n)
   printf(" %d ", arr2[j++]);
}

Time Complexity: O(m+n)
Algorithm Intersection(arr1[], arr2[]):
For Intersection of two arrays, print the element only if the element is present in both arrays.
1) Use two index variables i and j, initial values i = 0, j = 0
2) If arr1[i] is smaller than arr2[j] then increment i.
3) If arr1[i] is greater than arr2[j] then increment j.
4) If both are same then print any of them and increment both i and j.
#include<stdio.h>
int printIntersection(int arr1[], int arr2[], int m, int n)
{
  int i = 0, j = 0;
  while(i < m && j < n)
  {
    if(arr1[i] < arr2[j])
      i++;
    else if(arr2[j] < arr1[i])
      j++;
    else // if arr1[i] == arr2[j]
    {
      printf(" %d ", arr2[j++]);
      i++;
    }
  }
}

Time Complexity: O(m+n)

References

Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1?

Problem

Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1?

Solution

Method 1 - Using hashset on str2 and boolean array or hashset on str2
Break down the problem into two tasks.

i) Finding the non-unique i.e. repeating elements in str 1. Hashing can be used for this purpose.

ii) Finding if all the characters hashed in the first string are available in the second string. You can use a bool flag array for this purpose

Java code
public static Set<String> getNonUniqueChar(String str1, String str2){
 HashMap<Character, Integer> visit = new HashMap<Character, Integer>(); // find the non-unique characters
    HashSet<Character> visit2 = new HashSet<Character>(); // put the st1 chars into to hashset
    for (int i=0; str2.length; i++) {
  char c = str2.charAt(i);
  if(visit.containsKey(c)){
   Integer charCount = visit.get(c);
   visit.put(c,charCount++);
  }else
   visit.put(c,1);//initially char count is 1
 }
         
    for (i=0; i < str1.length; i++){
  char c = str1.charAt(i);
        if(!visit2.contains(c))
   str1.put(c);
 }
 //get all the elements where count is greater than 1
 List<String> nonUniqueCharsinS2 = new ArrayList<String>();
 for(Character c : visit.keys()) {
  if(visit.get(c) > 1)
   nonUniqueCharsinS2.add(c);
 }
 
 //iterate on s1 set to get all the elements
 Set<String> answer = new HashSet<String>();
    for (Character c : nonUniqueCharsinS2 )
         if(visit2.contains(c))
   answer.add(c);
     
  return answer;
}

Time complexity - O(n)
Space complexity - O(n)

Algorithm Interview Questions - Set 1

  1. A period of time where users login and logout, given a sets of login and logout time pairs, write a function that can show the number of users online at any given time.
  2. Intersection of n sets without using a hash table.
  3. Implement a LRU(Least Recently Used) cache
  4. Implement a function to compute cubic root
    what is the time complexity?
  5. Given a matrix with 1′s and 0′s, find the number of groups of 1′s. A group is defined by horiz/vertically adjacent 1′s.
  6. Given a matrix of numbers in which some may be zero. If a cell contains a zero, set all the cells in the corresponding column and row to zero.
  7. You are given a set of numbers 0 – n. Given a k, print all subsets of size k. Give the time complexity of the algorithm.
  8. Given an unsorted array of integers, find a 3-element subset that sums to zero..Complexity…?
  9. Multiply two big integers which don’t fit into an built-in integer type. How would you represent big numbers as a data structure? Write the function to multiply two big integers.
  10. Implement atof function. eg., +3.5e-2, .03e1, 1e1, 0.0
  11. How to implement Sqrt(double k) efficiently?   OR   Compute the square root of a number down to a certain precision.
    ie sqrt(num, precision) returns a number that is in-between sqrt(num) – precision and sqrt(num) + precision.
  12. How to implement multiple inheritance in Java
  13. Given set of coins and each coin has its unique probability to be head up, say double[] probs stores the probability values for all coins, print out all different cases and accordingly probability.
  14. Find the min and max in an array. Now do it in less than 2n comparisons. (they were looking for the solution that finds both max and min in about 3/2 n comparisons).
  15. FInd the maximum sum of a sub-sequence from an positive integer array where any two numbers of sub-sequence are not adjacent to each other in the original sequence. E.g 1 2 3 4 5 6 –> 2 4 6
  16. Given an array of integers, now we want to erase all 0′s (can be other value), and we want the result array condensed, meaning no empty cell in the array.
  17. given a list of words with a same size and a big string that contains one of the permutation of all the words combined(say p), find the startindex of the string p in the big string
  18. Reverse a Linked list (Recursively/Non recursively)
  19. Write the actual code to parse a regular expression including “*”, which stands for 0 or more characters, “+”, which stands for 1 or more characters, and “.”, which stands for 1 exact character.
  20. print out all prime numbers in a given string. abc2134kd31 -> 2, 13, 3, 3
  21. search needle in haystack problem. Make it more robust.
  22. Implement a function rotateArray(vector arr, int r) which rotates the array by r places. Eg 1 2 3 4 5 on being rotated by 2 gives 4 5 1 2 3.
  23. Implement a function string balanceParanthesis(string s); which given a string s consisting of some parenthesis returns a string s1 in which parenthesis are balanced and differences between s and s1 are minimum.
    Eg – “(ab(xy)u)2)” -> “(ab(xy)u)2″
    “)))(((” -> “”
  24. All Possible balanced parenthesis problem
  25. How will you design TinyUrl?
  26. How will you design facebook newsfeed. Focus was on a design which could handle the huge number of status updates and display them on each of the user’s friend’s wall.
  27. Implement a function
    char* readLine();
    which returns single lines from a buffer. To read the buffer, you can makes use of a function
    int read(char* buf, int len)
    which fills buf with upto len chars and returns the actual number of chars filled in. Function readLine can be called as many times as desired. If there is no valid data or newline terminated string available, it must block. In order to block, it can use read function which in turn will block when it doesn’t have anything to fill the buf.
  28. Find Kth smallest element in a BST.
  29. Implement a queue data structure given only stacks. What is the time complexity of enqueuing and dequeuing operations?
  30. Given a Binary Search Tree, iterate over the elements without using recursion.
  31. Given a set of non-overlapping integer ranges (1,3) (5,8), etc., and an input integer, what is the best way to organize the data and allow for quick search based on the input, etc.
  32. Given a telephone number, find all the permutations of the letters assuming 1=abc, 2=def, etc.
  33. Print a singly-linked list backwards, in constant space and linear time.
  34. Convert a binary search tree to a sorted, circular, doubly-linked list, in place (using the tree nodes as the new list nodes).
  35. Given a set of words, group them into sets of anagrams.
  36. Given a string, remove all the duplicate characters (not necessarily consecutive)
  37. Write a function to tell if two line segments intersect or not.
  38. Find an algorithm to find the largest sum subarray in an array of integers. (Better than O(n^2) ).
  39. Write a function that computes log2() using sqrt().
  40. Given a list of n objects, write a function that outputs the minimum set of numbers that sum to at least K. FOLLOW UP: can you beat O(n ln n)?
  41. Write a function to prettify Json objects
  42. Given sorted arrays of length n and 2n with n elements each, merge first array into second array.
  43. You are given intervals of contiguous integers, like [1, 10), [15, 25), [40, 50), which are non-overlapping and of a fixed size.
    Design a data structure to store these intervals and have the operations of insert, delete, and find functions
  44. Design a system to detect typos and provide suggestions to users.  Design and implement an algorithm that would correct typos: for example, if an extra letter is added, what would you do?
  45. Find the n-th smallest element in a binary tree.
  46. Print a binary tree in infix order. Recursive and iterative.
  47. Design the Facebook Credit system which is a application where users can buy/trade virtual currency and can use the virtual currency to purchase Facebook services, like paid apps.What's the advantage of the design?How would the total credit points of a user be calculated based on my design?
  48. Write a code to convert an ASCII representation of a positive integer to it's numeric value.
  49. Write a function to take two arbitrarily long numbers in the form of Strings and multiply them, returning another String with the product.
  50. Given a binary tree, write a function to find the length of the longest path in the tree.
  51. Write a function to take a BST and a value k as input and have it print the kth smallest element in the BST.
  52. Find the minimum depth of binary search tree.. http://www.glassdoor.com/Interview/Find-the-minimum-depth-of-binary-search-tree-QTN_127018.htm
  53. Print a binary search tree. Each level on a new line.
  54. Implement the div operator without using / or %
  55. You are trying to rob houses on a street. Each house has some +ve amount of cash. Your goal is to rob houses such that you maximize the total robbed amount. The constraint is once you rob a house you cannot rob a house adjascent to that house.
  56. Given a matrix print it clockwise from the first element to the very inner element.
  57. Given an array of integers and size find 3 integers that sum to zero.
  58. You are going to take some numbers as an input from a file. You need to witer a program to find longest increasing sequence. You should process it as soon as you are taking an input. After finishing the last input immediately you should be able to tell the sequence.
    Input: 1 5 3 4 6 4
    Output: 3 4 6
  59. A file contains 10 billions of Strings and need to find duplicate Strings. You have N number of systems available. How will you find duplicates?
  60. Given a set of integers, print out all its subsets.
  61. Code a program to check if a given string is matching a given regular expression
  62. Each key on the telephone represents a list of letters. Given a telephone number, please write a program to output all the possible strings the telephone number represents.
  63. write a function to check if a graph was bipartite.
  64. Given two binary trees, return true if they have same elements (irrespective of tree structure)
  65. Given a string, remove all chars from the string that are present in say another string called filter.
  66. Given two events, each with a start and end time, implement a boolean check to see if they overlap.
  67. Print out all combinations of k numbers out of 1...N
    e.g. when k = 2, n = 4
    Print out 12, 13, 14, 23, 24, 34
  68. runtime complexity of binary search and the average num of guesses it takes to find a number between 1 to 1000.  Given the numbers 1 to 1000, what is the minimum numbers guesses needed to find a specific number if you are given the hint "higher" or "lower" for each guess you make.
  69. Advantage of B Trees - Used in databases for indexing. Adv. Less number of memory lookups because of less hierarchy. Large fanout.
  70. Given a set of inputs in a log file: log:
    example:
    1,2
    1,1
    2,1
    3,1
    1,2

    out:
    1,2
    2,1
    3,1

    The output should be all the unique numbers and the count associated with them.
  71. Given an array, print the largest subarray that has elements in an increasing order
  72. How do you find sequences of consequtive integers in a list that add to a particular number.
  73. Given a score S, and individual points p1,p2,...,pn. give all combinations of p that add up to s.
  74. Given a large string (haystack), find a substring (needle) on it.
  75. Given a list of strings, for each string, find if it has an anagram in the list.
  76. Function to compute the number of ways to climb a flight of n steps. Taking 1, 2, or 3 steps at a time. Do it in Linear time and constant space. n = 3.
    1 1 1
    1 2
    2 1
    3
    Ans = 4
  77. Interweave a linked list. Do it in Linear time and constant space. Input: A->B->C->D->E
    Output: A->E->B->D->C
  78. Given a dictionary based simple password, create all possible (special character) passwords based on a provided mapping. Input: face
    Map: {a -> @, 4, A}
    Output: f@ce, f4ce, fAce
  79. Get numeric number out of a roman string, linear time
    Given: mapping I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000
    Input/Output:
    II = 2, III = 3, IV = 4
    VI, VII, VIII
    IX = 9
    XL = 40,
    XLIX = 49
  80. Merge 'k' sorted arrays, each array may have max 'n' elements
  81. how does hash map implementation looks like
  82. Implement strstr in C
  83. Write some pseudo code to raise a number to a power.
  84. Given an array of integers, find the maximum number that can be reached by summing the best possible consecutive subsequence of the array.
  85. Design a linked list operation that takes a singly-linked list (only forward ptrs, no backward ptrs) as input and reverses the list.
  86. Given a 1TB file of serialized 4 byte integers, and 2GB of ram, sort the integers into a resulting 1TB file. My interviewer was very collaborative in entertaining various solution ideas until we came up with a combo that would work performantly and reduce the number of passes over the 1TB file and intermediate files.
  87. Write a list class where the only data structure available is a stack
  88. Determine the 10 most frequent words given a terabyte of strings.
  89. Use basic arithmetic operations (+-*/) to implement sqrt function.
  90. Print out all the permutations of a string
  91. Write a function that prints out all subsets of a given set of numbers.
  92. Write a function that takes in two binary strings and returns their sum (also a binary string).
  93. Write a function that finds the minimum and maximum values within an unsorted array using divide-and-conquer.
  94. Generate a new array from an array of numbers. Start from the beginning. Put the number of some number first, and then that number.
    For example, from array 1, 1, 2, 3, 3, 1
    You should get 2, 1, 1, 2, 2, 3, 1, 1
    Write a program to solve this problem.
  95. given the utitlies getFriend(User u) and areFriends(User u1, User u2), write the function which takes as parameter the array of users and return a bool saying if you can divide the users in 2 groups s.t. if u1 and u2 both belong to a certain group, they are not friends.
  96. remove duplicates in a string.
  97. Given a file with 3-letter words, print all 3x3 with each row, column and diagonal being one of the words from given file.
  98. Find the center of graph(vertex, that is connected with every other vertex, but edges are directed to the center of graph).
  99. Given n+1 buckets with n of them with ball inside and move(a,b) function, that moves ball from bucket a to bucket b. Each ball has a different number from [1,n] on it. Move balls, so each bucket has a ball with matching number in it.
  100. Implement a power function to raise a double to an int power, including negative powers.
  101. Given a String containing java-script assets, write a parser which will output the String with proper indentation.
  102. Given a certain state of an Othelo game board, location on the board, a certain piece to place on the given location, update the board and make the required validations
  103. Given a collection of words, return a collection of anagrams found in the
    given collection
  104. Output a single linked list in reverse, in linear time and constant space, and recursively
  105. Pascal’s Triangle – print a row
  106. Given a function for a fair coin, write a function for a biased coin that returns heads 1/n times (n is a param).

Design Questions - Set 1

  1. Design a game of chess
  2. Given an ebay site model., you have to deal with auctioning of a particular item. Design the billing & auctioning system of the same.
  3. OOPs design of a file system
  4. Class diagram of a system to implement Blackjack
  5. Class diagram of a parking lot
  6. design a furniture module, a furniture could be a couch,  chair, etc. each furniture could contain multiple materials, wood, steel, etc. http://www.careercup.com/question?id=12989661
  7. Which Data structure is used in window search…??  http://www.careercup.com/question?id=12688668
  8. Design elevator system    http://www.careercup.com/question?id=12598663
  9. OOPs design of a file system     http://www.careercup.com/question?id=12598664
  10. mplement LRU cache .  http://www.careercup.com/question?id=12674664
  11. Design a Architecture of Online Movie Booking System . Find the possible issues and Idea to Resolve them. How do you optimize the Performance against all these issues.  http://www.careercup.com/question?id=12533687
  12. Design an online movie booking system
  13. Design and Implement Boggle game for n x n  http://www.careercup.com/question?id=12427668
  14. A news paper agency wants an application through which customers can select the news paper & magzenes they need on daily basis (ex day1 -> he need paper1 ,paper2, magjene1, day2 -> none , day3 – paper4 ) etc.. how registration and billing will be done, Provide a high & low level diagrams for it. which are the classes needed for the same.
  15. Two chess players want to play chess online with each other using facebook. Which are the classes you need for it and what are the APIs needed for the same. How one user will inform other once he made a move from his side .(Client server architecture .) . How a client will reduce the unwanted number of hits to server 2) once user1 has made a move how user2 will be informed quickly. 3) how the chess board position will be propagated from user1 to user2 with least amount of data . 4) Tell the security measures to make this game efficient (asked what is BUT and how to solve it) .
  16. How will you implement file search facility in windows, so that you will save the search and indexes for future references. Provide the design & tell the classes needed for the same.  http://www.careercup.com/question?id=12419685
  17. Give data structures for the following problems in making an employee management system:
    1) given a manager give all the employees he manages ( one to many relationship)
    2) represent organizational structure of the company  http://www.careercup.com/question?id=12375725
  18. Consider a cloak room. It has 3 compartments, small, medium, large
    1 medium = 2 small
    1 large = 2 medium = 4 small Design such a system, ensuring maximum capacity optimization of the compartments. Also, make the required number of moves (in-btw compartments) as minimum as possible.
    Write class, functions. Wht functions will u expose. What token will you return back to the user.  http://www.careercup.com/question?id=12493669

Tuesday, July 29, 2014

Given an array arr[], find the maximum j – i such that arr[j] > arr[i]

Problem

Given an array arr[], find the maximum j – i such that arr[j] > arr[i].

Example

  Input: {34, 8, 10, 3, 2, 80, 30, 33, 1}
  Output: 6  (j = 7, i = 1)

  Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}
  Output: 8 ( j = 8, i = 0)

  Input:  {1, 2, 3, 4, 5, 6}
  Output: 5  (j = 5, i = 0)

  Input:  {6, 5, 4, 3, 2, 1}
  Output: -1 

Solution

Method 1 (Simple but Inefficient)
Run two loops. In the outer loop, pick elements one by one from left. In the inner loop, compare the picked element with the elements starting from right side. Stop the inner loop when you see an element greater than the picked element and keep updating the maximum j-i so far.

code
int maxIndexDiff(int arr[], int n)
{
    int maxDiff = -1;
    int i, j;

    for (i = 0; i < n; ++i)
    {
        for (j = n-1; j > i; --j)
        {
            if(arr[j] > arr[i] && maxDiff < (j - i))
                maxDiff = j - i;
        }
    }

    return maxDiff;
}

Time Complexity: O(n^2)

Method 2 (Efficient)
To solve this problem, we need to get two optimum indexes of arr[]: left index i and right index j. For an element arr[i], we do not need to consider arr[i] for left index if there is an element smaller than arr[i] on left side of arr[i]. Similarly, if there is a greater element on right side of arr[j] then we do not need to consider this j for right index.
So we construct two auxiliary arrays LMin[] and RMax[] such that LMin[i] holds the smallest element on left side of arr[i] including arr[i], and RMax[j] holds the greatest element on right side of arr[j] including arr[j]. After constructing these two auxiliary arrays, we traverse both of these arrays from left to right. While traversing LMin[] and RMa[] if we see that LMin[i] is greater than RMax[j], then we must move ahead in LMin[] (or do i++) because all elements on left of LMin[i] are greater than or equal to LMin[i]. Otherwise we must move ahead in RMax[j] to look for a greater j – i value.

Here is the java code
int maxIndexDiff(int arr[], int n)
{
    int maxDiff;
    int i, j;
 
    int[] LMin = new int[n];
    int[] RMax = new int[n];
 
   // Construct LMin[] such that LMin[i] stores the minimum value
   //    from (arr[0], arr[1], ... arr[i]) 
    LMin[0] = arr[0];
    for (i = 1; i < n; ++i)
        LMin[i] = Math.min(arr[i], LMin[i-1]);
 
    // Construct RMax[] such that RMax[j] stores the maximum value
    //   from (arr[j], arr[j+1], ..arr[n-1]) 
    RMax[n-1] = arr[n-1];
    for (j = n-2; j >= 0; --j)
        RMax[j] = Math.max(arr[j], RMax[j+1]);
 
    // Traverse both arrays from left to right to find optimum j - i
     //   This process is similar to merge() of MergeSort 
    i = 0, j = 0, maxDiff = -1;
    while (j < n && i < n)
    {
        if (LMin[i] < RMax[j])
        {
            maxDiff = max(maxDiff, j-i);
            j = j + 1;
        }
        else
            i = i+1;
    }
 
    return maxDiff;
}

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

Examples of running method 2

Example 1
Input Array         :  [7, 3, 9, 2, 1, 11, 0]
LMin                :  [7, 3, 3, 2, 1, 1 , 0]
IndexOfLeftMinimum  :  [0, 1, 1, 3, 4,  4, 6]

RMax                :  [11,11,11,11,11,11, 0]
IndexOfRightMaximum :  [5, 5, 5, 5, 5,  5, 6]
Distance Array      :  [5, 4, 4, 3, 1,  1, 0]

Maximum value in distance array = 5
Corresponding i (from IndexOfLeftMinimum array)  = 0
Corresponding j (from IndexOfRightMaximum array) = 5
Solution: i=0, j=5

Example 2:

Input Array         :  [0, 1, 2, 3, 4]
IndexOfLeftMinimum  :  [0, 0, 0, 0, 0]
IndexOfRightMaximum :  [4, 4, 4, 4, 4]

Maximum value in distance array = 4
Corresponding i (from IndexOfLeftMinimum array)  = 0
Corresponding j (from IndexOfRightMaximum array) = 4
Solution: i=0, j=4


Example 3:
Input Array         :  [4, 3, 2, 1, 0]
IndexOfLeftMinimum  :  [0, 1, 2, 3, 4]
IndexOfRightMaximum :  [0, 1, 2, 3, 4]

Maximum value in distance array = 0
Corresponding i (from IndexOfLeftMinimum array)  = None
Corresponding j (from IndexOfRightMaximum array) = None
Solution: No such pair


Source -  geeksforgeeks

Sunday, July 27, 2014

Filters in Linux/Unix

A filter is a program that reads a single input stream, transforms it in some way, and writes the result to a single output stream, as shown in Figure 1, below. By default, the output stream (called standard output or just stdout) is connected to the terminal window that the program is running in, and the input stream (standard input, or just stdin) is connected to the keyboard, though in practice filters are rarely used to process data typed in manually at the keyboard.

(diagram from http://www.tuxradar.com/content/exploring-filters-and-pipes#null )

Filters with Pipes
Command lines which use a filter will include a pipes to connect it to the stdout of one process and the stdin of another process.
For example, the command line below takes the output of "who" and sorts it. The sorted output is then passed to the lp command for printing. In this example, sort is a filter.



     who  |  sort  | lp

Both filters and pipes demonstrate a basic UNIX principle: Expect the output of every program to become the input of another, yet unknown, program to combine simple tools to perform complex tasks.

References

Unix Interview Questions - Set 4

What is $*?
Its mainly used for showing up all params. This show all parameter values passed in shell script

What does $# stand for?
# will return the number of parameters that are passed as the command-line arguments.

What does $? Return? $?
It will return exit status of command .0 if command gets successfully executed ,non-zero if command failed.

What are Different types of shells?
sh :
the oldest shell
csh : C shell
ksh : Korn Shell
bash : bourne again shell

How do you read arguments in a shell program – $1, $2?
Shell script accepts parameters in following format…
$1 would be the first command line argument, $2 the second, and so on
$0 is the name of the script or function If your script has more than 9 params then accept in following way…
${12} : 12th param
${18} : 18th param

What are the different kinds of loops available in shell script?
for, if, while, case

What is the difference between a shell variable that is exported and the one that is not exported?
The Shell variable which is exported would available to all the programs outside the Shell also. And the shell variable which is not exported, would available for that shell or for the shell program only, in which the variable is declared. Export LANG=C
will make the variable LANG the global variable, put it into the global environment. All other processes can use it.

LANG=C
will change the value only in the current script.     If you have a string “one two three”, which shell command would you use to extract the strings? echo $string | cut -d” ” -f1
echo $string | cut -d” ” -f2
echo $string | cut -d” ” -f3

How will you list only the empty lines in a file (using grep)?
grep “^$” filename.txt

How would you get the character positions 10-20 from a text file?
cat filename.txt | cut -c 10-20 or cut -c10-20



How would you replace the n character in a file with some xyz?
sed ‘s/n/xyz/g’ filename > new_filename

We can replace n characters by using the following command:
1,$s/./xyz/g
where 1 shows that the search string will start searching patterns from first line of the file.
           ‘.’ for any character.
            g for global replacemet.

What is the difference between a ‘thread’ and a ‘process’?
A process is a collection of virtual memory space, code, data, and system resources. A thread is code that is to be serially executed within a process. A processor executes threads, not processes, so each application has at least one process, and a process always has at least one thread of execution, known as the primary thread. A process can have multiple threads in addition to the primary thread Thread – is stream of executable code within process. They are light weight process. All thread with in a process  share process instruction,code & data segment,open file descriptor,signal handler,userID and GroupID. Thread has its own set of register including program counter,stack pointer

What is this line in the shell script do ?#!/bin/ksh?
To invoke the shell indirectly this line is added as the first line in the file.This particular line invokes korn shell
What is use of “cut” command? Give some examples. Cut – Utility used to cut/Strip out the required data/text from the source. Cut can be used in three modes,   Stripping by Character      cut -c 1-3   Striping by Byte length      cut -b -1-72 Stripping by delimiter and fields.      cut -d “|” -f1 Where    -d “|” -> Delimiter used in input text to separate columns -f1 -> Field/Column number   While processing huge input files, Cut’s performance is far better than awk

References

Finding IP Address from hostname in Windows Linux and Unix

IP Address from hostname in Windows and Linux
How many times in a day you have a hostname and you want to know the IP address? Host name to IP address and IP address to hostname conversion is one of frequent thing which we need to do for many things when dealing with networking command in unix. For one command we need IP address for other we need hostname even from bash script some time we require hostname and some time we look for IP address. networking commands are not as popular as find command or grep command but they are equally important and if you working in Windows or UNIX environment you must learn them and they should also be included in any list of Unix commands for beginners. By the way In this hostname to IP address tutorial I will show you how to get IP address from hostname or computer-name in Unix or Linux and how to get hostname if you have IP address. If you are looking a way to do it via Java program then you can also see my post how to find IP address of localhost in Java.


Finding IP address from hostname in UNIX and Linux

If you are working in UNIX network and have lots of machine in LAN (Local Area network),  many times you want to know IP address of computers from hostname. Here are top 4 ways of getting IP address from hostname in Linux or UNIX machine 1) IP address using hostname command in Unix/Linux ~/hostname -i This is the easiest way of finding IP address of your computer but limitation is that sometime this option may or may not available in your UNIX machine e.g. I hardly find this command on Solaris and IBM AIX machines but they are mostly available on Linux Servers. also limitation of hostname is that you can not find IP address of any other machine. It's like finding IP address of localhost. 2) IP address using ping command in UNIX or Linux stock_trader@system:~/test ping trading_system Pinging trading_system.com [192.24.112.23] with 32 bytes of data: Reply from 192.24.112.23: bytes=32 time<1ms ttl="128</span"> Reply from 192.24.112.23: bytes=32 time<1ms ttl="128</span"> Reply from 192.24.112.23: bytes=32 time<1ms ttl="128</span"> ping is  another simplest way of finding IP address of localhost or any other host in network, if you know the hostname or computer-name just ping and it will display IP address associated with it. Normally pint command is used to check if a host is alive and connected with network. In above example IP address associated with trading_system is "192.24.112.23". Disadvantage of using ping command is that you can not convert IP address back to hostname. 3) IP address using nslookup command in UNIX or Linux
stock_trader@system:~/test nslookup trading_system Name:    trading_system.com Address:  192.24.112.23 nslookup is my favorite command for getting IP address form hostname, its very powerful and also available in many UNIX operating system e.g. Linux , Solaris, IBM AIX, Ubuntu or BSD. Another advantage of  nslookup command is that , we can get either from hostname to IP address or from IP address to hostname. It can also be used to find IP address of your own host or any other machine in the network. In above example of nslookup we have displayed IP address associated with trading_system. If you want to find hostname form IP address you can just provide IP address instead of hostname 4) How to find IP address using ifconfig command ifconfig is another networking utility in UNIX or Linux which can be used to find IP address of your UNIX machine. ifconfig shows lot of information so I just grep on inet to find the IP address in below example, IP address associate with "trading_system.com" is "192.24.112.23". trading_system.com $ /sbin/ifconfig -a | grep inet inet 192.24.112.23 netmask ffffff00 broadcast 192.24.112.255

IP Address from hostname in Windows Linux and Unix

How to find IP address of your computer in Windows

Surprisingly some of above example of finding IP address from hostname will work is windows ditto. You can use ping and nslookup in exactly same way as shown above. Even hostname command is available in windows command prompt but I doubt about options "hostname -i". Another change is in command  ifconfig , instead of  ifconfig windows uses  ipconfig  command to find out the IP address of your computer in windows.
1) How of use ipconfig command in windows to find IP address Here is an example of using ipconfig command in windows to find out IP address of our computer: C:\Documents and Settings\stock_trader>ipconfig Windows IP Configuration Ethernet adapter Local Area Connection:
        Connection-specific DNS Suffix  . : trading_system.com         IP Address. . . . . . . . . . . . : 192.24.112.23         Subnet Mask . . . . . . . . . . . : 255.255.255.0         Default Gateway . . . . . . . . . : 192.24.112.254

How to find external IP address of your network or computer

All above example will show your internal IP address if you are inside a LAN. If you have connected with internet and want to know your external IP address assigned by your service provider there are lots of website which will let you know your IP address e.g.  ipchicken.com just logging into this site and it will show you your IP address and location. If you have an IP address and wanted to know about location you can also get it from internet.
That’s it from me on these nice little tips of converting IP address to hostname and than back from hostname to IP address. Let me know if you have some other ways to find IP address and hostname of local machine and remote machine.
Read more: http://javarevisited.blogspot.com/2011/09/find-hostname-from-ip-address-to.html#ixzz304c6ZOcV

INODE in Linux/Unix

INode contains the metadata about the files in the *nix systems.

Inode Basics

An Inode number points to an Inode. An Inode is a data structure that stores the following information about a file :
  • Size of file
  • Device ID
  • User ID of the file
  • Group ID of the file
  • The file mode information and access privileges for owner, group and others
  • File protection flags
  • The timestamps for file creation, modification etc
  • link counter to determine the number of hard links
  • Pointers to the blocks storing file’s contents
Please note that the above list is not exhaustive.
Also, the name of the file is not stored in Inodes (We will come to it later). When a file is created inside a directory then the file-name and Inode number are assigned to file i.e. directory maps file name to inode number.

The user might think that the directory contains the complete file and all the extra information related to it but this might not be the case always. So we see that a directory associates a file name with its Inode number.
When a user tries to access the file or any information related to the file then he/she uses the file name to do so but internally the file-name is first mapped with its Inode number stored in a table. Then through that Inode number the corresponding Inode is accessed. There is a table (Inode table) where this mapping of Inode numbers with the respective Inodes is provided.

Why no file-name in Inode information?

As pointed out earlier, there is no entry for file name in the Inode, rather the file name is kept as a separate entry parallel to Inode number. The reason for separating out file name from the other information related to same file is for maintaining hard-links to files. This means that once all the other information is separated out from the file name then we can have various file names which point to same Inode.
For example :
$ touch a

$ ln a a1

$ ls -al
drwxr-xr-x 48 himanshu himanshu 4096 2012-01-14 16:30 .
drwxr-xr-x 3 root root 4096 2011-03-12 06:24 ..
-rw-r--r-- 2 himanshu family 0 2012-01-14 16:29 a
-rw-r--r-- 2 himanshu family 0 2012-01-14 16:29 a1
In the above output, we created a file ‘a’ and then created a hard link a1. Now when the command ‘ls -al’ is run, we can see the details of both ‘a’ and ‘a1′. We see that both the files are indistinguishable. Look at the second entry in the output. This entry specifies number of hard links to the file. In this case the entry has value ’2′ for both the files.
Note that Hard links cannot be created on different file systems and also they cannot be created for directories.

When are Inodes created?

As we all now know that Inode is a data structure that contains information of a file. Since data structures occupy storage then an obvious question arises about when the Inodes are created in a system? Well, space for Inodes is allocated when the operating system or a new file system is installed and when it does its initial structuring. So this way we can see that in a file system, maximum number of Inodes and hence maximum number of files are set.
Now, the above concept brings up another interesting fact. A file system can run out of space in two ways :
  • No space for adding new data is left
  • All the Inodes are consumed.
Well, the first way is pretty obvious but we need to look at the second way. Yes, its possible that a case arises where we have free storage space but still we cannot add any new data in file system because all the Inodes are consumed. This may happen in a case where file system contains very large number of very small sized files. This will consume all the Inodes and though there would be free space from a Hard-disk-drive point of view but from file system point of view no Inode available to store any new file.
The above use-case is possible but less encountered because on a typical system the average file size is more than 2KB which makes it more prone to running out of hard disk space first. But, nevertheless there exists an algorithm which is used to create number of Inodes in a file system. This algorithm takes into consideration the size of the file system and average file size. The user can tweak the number of Inodes while creating the file system.


Commands to access Inode numbers

Following are some commands to access the Inode numbers for files :

1) Ls -i Command

As we explained earlier in our Unix LS Command: 15 Practical Examples article, the flag -i is used to print the Inode number for each file.
$ ls -i
1448240 a 1441807 Desktop 1447344 mydata 1441813 Pictures 1442737 testfile 1448145 worm
1448240 a1 1441811 Documents 1442707 my_ls 1442445 practice 1442739 test.py
1447139 alpha 1441808 Downloads 1447278 my_ls_alpha.c 1441810 Public 1447099 Unsaved Document 1
1447478 article_function_pointer.txt 1575132 google 1447274 my_ls.c 1441809 Templates 1441814 Videos
1442390 chmodOctal.txt 1441812 Music 1442363 output.log 1448800 testdisk.log 1575133 vlc
See that the Inode number for ‘a’ and ‘a1′ are same as we created ‘a1′ as hard link.

2) Df -i Command

df -i command displays the inode information of the file system.
$ df -i
Filesystem            Inodes   IUsed   IFree IUse% Mounted on
/dev/sda1            1875968  293264 1582704   16% /
none                  210613     764  209849    1% /dev
none                  213415       9  213406    1% /dev/shm
none                  213415      63  213352    1% /var/run
none                  213415       1  213414    1% /var/lock
/dev/sda2            7643136  156663 7486473    3% /home
The flag -i is used for displaying Inode information.

3) Stat Command

Stat command is used to display file statistics that also displays inode number of a file
$ stat a
File: `a'
Size: 0 Blocks: 0 IO Block: 4096 regular empty file
Device: 805h/2053d Inode: 1448240 Links: 2
Access: (0644/-rw-r--r--) Uid: ( 1000/himanshu) Gid: ( 1001/ family)
Access: 2012-01-14 16:30:04.871719357 +0530
Modify: 2012-01-14 16:29:50.918267873 +0530
Change: 2012-01-14 16:30:03.858251514 +0530

Example Usage Scenario of an Inode number

  1. Suppose there exist a file name with some special character in it. For example:  ”ab*
  2. Try to remove it normally using rm command, you will not be able to remove it.
  3. However using the inode number of this file you can remove it.
Lets see these steps in this example :
1) Check if the file exists:
$ ls -i
1448240 a 1447274 my_ls.c
1448240 a1 1442363 output.log
1448239 "ab* 1441813 Pictures
1447139 alpha
So we have a file with name “ab* in this directory
2) Try to remove it normally:
$ rm "ab*
> ^C
$ rm "ab*
> ^C
$
See that I tried couple of times to remove the file but could not.
3) Remove the file using Inode number:
As we discussed earlier in our find command examples article, you can search for a file using inode number and delete it.
$ find . -inum 1448239 -exec rm -i {} \;
rm: remove regular empty file `./"ab*'? y
$ ls -i
1448240 a 1447274 my_ls.c
1448240 a1 1442363 output.log
1447139 alpha 1441813 Pictures
So we used the find command specifying the Inode number of the file we need to delete. The file got deleted. Though we could have deleted the file otherwise also by using the command rm \”ab* instead of using the complicated find command example above but still I used it to demonstrate one of the use of Inode numbers for users.


Resources

15 practical examples of Linux find command - Part 2

A while back we reviewed 15 practical find command examples (Part I). Find command can do lot more than just searching for files based on name.

In this article (Part 2), let us discuss 15 advanced examples of find command including — finding files based on the time it is accessed, modified or changed, finding files comparatively, performing operation on found files etc.,

Ramesh Natarajan: That is my sweet little daughter in that picture. She was very happy to spot the sea lion in the California Long Beach Aquarium.

Find Files Based on Access / Modification / Change Time

You can find files based on following three file time attribute.
  1. Access time of the file. Access time gets updated when the file accessed.
  2. Modification time of the file. Modification time gets updated when the file content modified.
  3. Change time of the file. Change time gets updated when the inode data changes.

In the following examples, the difference between the min option and the time option is the argument.
  • min argument treats its argument as minutes. For example, min 60 = 60 minutes (1 hour).
  • time argument treats its argument as 24 hours. For example, time 2 = 2*24 hours (2 days).
  • While doing the 24 hours calculation, the fractional parts are ignored so 25 hours is taken as 24 hours, and 47 hours is also taken as 24 hours, only 48 hours is taken as 48 hours. To get more clarity refer the -atime section of the find command man page.

Example 1: Find files whose content got updated within last 1 hour

To find the files based up on the content modification time, the option -mmin, and -mtime is used. Following is the definition of mmin and mtime from man page.
  • -mmin n File’s data was last modified n minutes ago.
  • -mtime n File’s data was last modified n*24 hours ago.

Following example will find files in the current directory and sub-directories, whose content got updated within last 1 hour (60 minutes)
 find . -mmin -60

In the same way, following example finds all the files (under root file system /) that got updated within the last 24 hours (1 day).
 find / -mtime -1

Example 2: Find files which got accessed before 1 hour

To find the files based up on the file access time, the option -amin, and -atime is used. Following is the definition of amin and atime from find man page.
  • -amin n File was last accessed n minutes ago
  • -atime n File was last accessed n*24 hours ago

Following example will find files in the current directory and sub-directories, which got accessed within last 1 hour (60 minutes)
 find -amin -60

In the same way, following example finds all the files (under root file system /) that got accessed within the last 24 hours (1 day).
 find / -atime -1

Example 3: Find files which got changed exactly before 1 hour

To find the files based up on the file inode change time, the option -cmin, and -ctime is used. Following is the definition of cmin and ctime from find man page.
  • -cmin n File’s status was last changed n minutes ago.
  • -ctime n File’s status was last changed n*24 hours ago.

Following example will find files in the current directory and sub-directories, which changed within last 1 hour (60 minutes)
 find . -cmin -60

In the same way, following example finds all the files (under root file system /) that got changed within the last 24 hours (1 day).
 find / -ctime -1

Example 4: Restricting the find output only to files. (Display only files as find command results)

The above find command’s will also show the directories because directories gets accessed when the file inside it gets accessed. But if you want only the files to be displayed then give -type f in the find command as

The following find command displays files that are accessed in the last 30 minutes.
 find /etc/sysconfig -amin -30
.
./console
./network-scripts
./i18n
./rhn
./rhn/clientCaps.d
./networking
./networking/profiles
./networking/profiles/default
./networking/profiles/default/resolv.conf
./networking/profiles/default/hosts
./networking/devices
./apm-scripts
[Note: The above output contains both files and directories]

 find /etc/sysconfig -amin -30 -type f
./i18n
./networking/profiles/default/resolv.conf
./networking/profiles/default/hosts
[Note: The above output contains only files]

Example 5: Restricting the search only to unhidden files. (Do not display hidden files in find output)

When we don’t want the hidden files to be listed in the find output, we can use the following regex.
The below find displays the files which are modified in the last 15 minutes. And it lists only the unhidden files. i.e hidden files that starts with a . (period) are not displayed in the find output.
 find . -mmin -15 \( ! -regex ".*/\..*" \)

Finding Files Comparatively Using Find Command

Human mind can remember things better by reference such as, i want to find files which i edited after editing the file “test”. You can find files by referring to the other files modification as like the following.

Example 6: Find files which are modified after modification of a particular FILE

Syntax: find -newer FILE

Following example displays all the files which are modified after the /etc/passwd files was modified. This is helpful, if you want to track all the activities you’ve done after adding a new user.
 find -newer /etc/passwd

Example 7: Find files which are accessed after modification of a specific FILE

Syntax: find -anewer FILE

Following example displays all the files which are accessed after modifying /etc/hosts. If you remember adding an entry to the /etc/hosts and would like to see all the files that you’ve accessed since then, use the following command.
 find -anewer /etc/hosts

Example 8: Find files whose status got changed after the modification of a specific FILE.

Syntax: find -cnewer FILE

Following example displays all the files whose status got changed after modifying the /etc/fstab. If you remember adding a mount point in the /etc/fstab and would like to know all the files who status got changed since then, use the following command.
find -cnewer /etc/fstab

Perform Any Operation on Files Found From Find Command

We have looked at many different ways of finding files using find command in this article and also in our previous article. If you are not familiar in finding files in different ways, i strongly recommend you to read the part 1.

This section explains about how to do different operation on the files from the find command. i.e how to manipulate the files returned by the find command output.

We can specify any operation on the files found from find command.
find  -exec  \;

The OPERATION can be anything such as:
  • rm command to remove the files found by find command.
  • mv command to rename the files found.
  • ls -l command to get details of the find command output files.
  • md5sum on find command output files
  • wc command to count the total number of words on find command output files.
  • Execute any Unix shell command on find command output files.
  • or Execute your own custom shell script / command on find command output files.

Example 9: ls -l in find command output. Long list the files which are edited within the last 1 hour.

 find -mmin -60
./cron
./secure

 find -mmin -60 -exec ls -l {} \;
-rw-------  1 root root 1028 Jun 21 15:01 ./cron
-rw-------  1 root root 831752 Jun 21 15:42 ./secure

Example 10: Searching Only in the Current Filesystem

System administrators would want to search in the root file system, but not in the other mounted partitions. When you have multiple partitions mounted, and if you want to search in /. You can do the following.

Following command will search for *.log files starting from /. i.e If you have multiple partitions mounted under / (root), the following command will search all those mounted partitions.
 find / -name "*.log"

This will search for the file only in the current file system. Following is the xdev definition from find man page:
  • -xdev Don’t descend directories on other filesystems.

Following command will search for *.log files starting from / (root) and only in the current file system. i.e If you have multiple partitions mounted under / (root), the following command will NOT search all those mounted partitions.
 find / -xdev -name "*.log"

Example 11: Using more than one { } in same command

Manual says only one instance of the {} is possible. But you can use more than one {} in the same command as shown below.
 find -name "*.txt" cp {} {}.bkup \;

Using this {} in the same command is possible but using it in different command it is not possible, say you want to rename the files as following, which will not give the expected result.
find -name "*.txt" -exec mv {} `basename {} .htm`.html \;

Example 12: Using { } in more than one instance.

You can simulate it by writing a shell script as shown below.
 mv "$1" "`basename "$1" .htm`.html"

These double quotes are to handle spaces in file name. And then call that shell script from the find command as shown below.
find -name "*.html" -exec ./mv.sh '{}' \;
So for any reason if you want the same file name to be used more than once then writing the simple shell script and passing the file names as argument is the simplest way to do it.

Example 13: Redirecting errors to /dev/null

Redirecting the errors is not a good practice. An experienced user understands the importance of getting the error printed on terminal and fix it.

Particularly in find command redirecting the errors is not a good practice. But if you don’t want to see the errors and would like to redirect it to null do it as shown below.
find -name "*.txt" 2>>/dev/null

Sometimes this may be helpful. For example, if you are trying to find all the *.conf file under / (root) from your account, you may get lot of “Permission denied” error message as shown below.
$ find / -name "*.conf"
/sbin/generate-modprobe.conf
find: /tmp/orbit-root: Permission denied
find: /tmp/ssh-gccBMp5019: Permission denied
find: /tmp/keyring-5iqiGo: Permission denied
find: /var/log/httpd: Permission denied
find: /var/log/ppp: Permission denied
/boot/grub/grub.conf
find: /var/log/audit: Permission denied
find: /var/log/squid: Permission denied
find: /var/log/samba: Permission denied
find: /var/cache/alchemist/printconf.rpm/wm: Permission denied
[Note: There are two valid *.conf files burned in the "Permission denied" messages]

So, if you want to just view the real output of the find command and not the “Permission denied” error message you can redirect the error message to /dev/null as shown below.
$ find / -name "*.conf" 2>>/dev/null
/sbin/generate-modprobe.conf
/boot/grub/grub.conf
[Note: All the "Permission denied" messages are not displayed]

Example 14: Substitute space with underscore in the file name.

Audio files you download from internet mostly come with the spaces in it. But having space in the file name is not so good for Linux kind of systems. You can use the find and rename command combination as shown below to rename the files, by substituting the space with underscore.

The following replaces space in all the *.mp3 files with _
$ find . -type f -iname “*.mp3″ -exec rename “s/ /_/g” {} \;

Example 15: Executing two find commands at the same time

As shown in the examples of the find command in its manual page, the following is the syntax which can be used to execute two commands in single traversal.

The following find command example, traverse the filesystem just once, listing setuid files and directories into /root/suid.txt and large files into /root/big.txt.
 find /    \( -perm -4000 -fprintf /root/suid.txt '%m %u %p\n' \) , \
 \( -size +100M -fprintf /root/big.txt '%-10s %p\n' \)

References

15 practical examples of Linux find command - Part 1

In this article, let us review 15 practical examples of Linux find command that will be very useful to both newbies and experts.


First, create the following sample empty files under your home directory to try some of the find command examples mentioned below.
 vim create_sample_files.sh
touch MybashProgram.sh
touch mycprogram.c
touch MyCProgram.c
touch Program.c

mkdir backup
cd backup

touch MybashProgram.sh
touch mycprogram.c
touch MyCProgram.c
touch Program.c

 chmod +x create_sample_files.sh

 ./create_sample_files.sh

 ls -R
.:
backup                  MybashProgram.sh  MyCProgram.c
create_sample_files.sh  mycprogram.c      Program.c

./backup:
MybashProgram.sh  mycprogram.c  MyCProgram.c  Program.c

1. Find Files Using Name

This is a basic usage of the find command. This example finds all files with name — MyCProgram.c in the current directory and all its sub-directories.
 find -name "MyCProgram.c"
./backup/MyCProgram.c
./MyCProgram.c

2. Find Files Using Name and Ignoring Case

This is a basic usage of the find command. This example finds all files with name — MyCProgram.c (ignoring the case) in the current directory and all its sub-directories.
 find -iname "MyCProgram.c"
./mycprogram.c
./backup/mycprogram.c
./backup/MyCProgram.c
./MyCProgram.c

3. Limit Search To Specific Directory Level Using mindepth and maxdepth

Find the passwd file under all sub-directories starting from root directory.
 find / -name passwd
./usr/share/doc/nss_ldap-253/pam.d/passwd
./usr/bin/passwd
./etc/pam.d/passwd
./etc/passwd

Find the passwd file under root and one level down. (i.e root — level 1, and one sub-directory — level 2)
 find -maxdepth 2 -name passwd
./etc/passwd

Find the passwd file under root and two levels down. (i.e root — level 1, and two sub-directories — level 2 and 3 )
 find / -maxdepth 3 -name passwd
./usr/bin/passwd
./etc/pam.d/passwd
./etc/passwd

Find the password file between sub-directory level 2 and 4.
 find -mindepth 3 -maxdepth 5 -name passwd
./usr/bin/passwd
./etc/pam.d/passwd

4. Executing Commands on the Files Found by the Find Command.

In the example below, the find command calculates the md5sum of all the files with the name MyCProgram.c (ignoring case). {} is replaced by the current file name.
 find -iname "MyCProgram.c" -exec md5sum {} \;
d41d8cd98f00b204e9800998ecf8427e  ./mycprogram.c
d41d8cd98f00b204e9800998ecf8427e  ./backup/mycprogram.c
d41d8cd98f00b204e9800998ecf8427e  ./backup/MyCProgram.c
d41d8cd98f00b204e9800998ecf8427e  ./MyCProgram.c

5. Inverting the match.

Shows the files or directories whose name are not MyCProgram.c .Since the maxdepth is 1, this will look only under current directory.
 find -maxdepth 1 -not -iname "MyCProgram.c"
.
./MybashProgram.sh
./create_sample_files.sh
./backup
./Program.c

6. Finding Files by its inode Number.

Every file has an unique inode number, using that we can identify that file. Create two files with similar name. i.e one file with a space at the end.
 touch "test-file-name"

 touch "test-file-name "
[Note: There is a space at the end]

 ls -1 test*
test-file-name
test-file-name

From the ls output, you cannot identify which file has the space at the end. Using option -i, you can view the inode number of the file, which will be different for these two files.
 ls -i1 test*
16187429 test-file-name
16187430 test-file-name

You can specify inode number on a find command as shown below. In this example, find command renames a file using the inode number.
 find -inum 16187430 -exec mv {} new-test-file-name \;

 ls -i1 *test*
16187430 new-test-file-name
16187429 test-file-name

You can use this technique when you want to do some operation with the files which are named poorly as shown in the example below. For example, the file with name — file?.txt has a special character in it. If you try to execute “rm file?.txt”, all the following three files will get removed. So, follow the steps below to delete only the “file?.txt” file.
 ls
file1.txt  file2.txt  file?.txt

Find the inode numbers of each file.
 ls -i1
804178 file1.txt
804179 file2.txt
804180 file?.txt

Use the inode number to remove the file that had special character in it as shown below.
 find -inum 804180 -exec rm {} \;

 ls
file1.txt  file2.txt
[Note: The file with name "file?.txt" is now removed]

7. Find file based on the File-Permissions

Following operations are possible.
  • Find files that match exact permission
  • Check whether the given permission matches, irrespective of other permission bits
  • Search by giving octal / symbolic representation

For this example, let us assume that the directory contains the following files. Please note that the file-permissions on these files are different.
 ls -l
total 0
-rwxrwxrwx 1 root root 0 2009-02-19 20:31 all_for_all
-rw-r--r-- 1 root root 0 2009-02-19 20:30 everybody_read
---------- 1 root root 0 2009-02-19 20:31 no_for_all
-rw------- 1 root root 0 2009-02-19 20:29 ordinary_file
-rw-r----- 1 root root 0 2009-02-19 20:27 others_can_also_read
----r----- 1 root root 0 2009-02-19 20:27 others_can_only_read

Find files which has read permission to group. Use the following command to find all files that are readable by the world in your home directory, irrespective of other permissions for that file.
 find . -perm -g=r -type f -exec ls -l {} \;
-rw-r--r-- 1 root root 0 2009-02-19 20:30 ./everybody_read
-rwxrwxrwx 1 root root 0 2009-02-19 20:31 ./all_for_all
----r----- 1 root root 0 2009-02-19 20:27 ./others_can_only_read
-rw-r----- 1 root root 0 2009-02-19 20:27 ./others_can_also_read

Find files which has read permission only to group.
 find . -perm g=r -type f -exec ls -l {} \;
----r----- 1 root root 0 2009-02-19 20:27 ./others_can_only_read

Find files which has read permission only to group [ search by octal ]
 find . -perm 040 -type f -exec ls -l {} \;
----r----- 1 root root 0 2009-02-19 20:27 ./others_can_only_read

8. Find all empty files (zero byte file) in your home directory and its subdirectory

Most files of the following command output will be lock-files and place holders created by other applications.
 find ~ -empty

List all the empty files only in your home directory.
 find . -maxdepth 1 -empty

List only the non-hidden empty files only in the current directory.
 find . -maxdepth 1 -empty -not -name ".*"

9. Finding the Top 5 Big Files

The following command will display the top 5 largest file in the current directory and its subdirectory. This may take a while to execute depending on the total number of files the command has to process.
 find . -type f -exec ls -s {} \; | sort -n -r | head -5

10. Finding the Top 5 Small Files

Technique is same as finding the bigger files, but the only difference the sort is ascending order.
 find . -type f -exec ls -s {} \; | sort -n  | head -5

In the above command, most probably you will get to see only the ZERO byte files ( empty files ). So, you can use the following command to list the smaller files other than the ZERO byte files.
 find . -not -empty -type f -exec ls -s {} \; | sort -n  | head -5

11. Find Files Based on file-type using option -type

Find only the socket files.
 find . -type s

Find all directories
 find . -type d

Find only the normal files
 find . -type f

Find all the hidden files
 find . -type f -name ".*"

Find all the hidden directories
 find -type d -name ".*"

12. Find files by comparing with the modification time of other file.

Show files which are modified after the specified file. The following find command displays all the files that are created/modified after ordinary_file.
 ls -lrt
total 0
-rw-r----- 1 root root 0 2009-02-19 20:27 others_can_also_read
----r----- 1 root root 0 2009-02-19 20:27 others_can_only_read
-rw------- 1 root root 0 2009-02-19 20:29 ordinary_file
-rw-r--r-- 1 root root 0 2009-02-19 20:30 everybody_read
-rwxrwxrwx 1 root root 0 2009-02-19 20:31 all_for_all
---------- 1 root root 0 2009-02-19 20:31 no_for_all

 find -newer ordinary_file
.
./everybody_read
./all_for_all
./no_for_all

13. Find Files by Size

Using the -size option you can find files by size.

Find files bigger than the given size
 find ~ -size +100M

Find files smaller than the given size
 find ~ -size -100M

Find files that matches the exact given size
 find ~ -size 100M

Note: – means less than the give size, + means more than the given size, and no symbol means exact given size.

14. Create Alias for Frequent Find Operations

If you find some thing as pretty useful, then you can make it as an alias. And execute it whenever you want.

Remove the files named a.out frequently.
 alias rmao="find . -iname a.out -exec rm {} \;"
 rmao

Remove the core files generated by c program.
 alias rmc="find . -iname core -exec rm {} \;"
 rmc

15. Remove big archive files using find command

The following command removes *.zip files that are over 100M.
 find / -type f -name *.zip -size +100M -exec rm -i {} \;"
Remove all *.tar file that are over 100M using the alias rm100m (Remove 100M). Use the similar concepts and create alias like rm1g, rm2g, rm5g to remove file size greater than 1G, 2G and 5G respectively.
 alias rm100m="find / -type f -name *.tar -size +100M -exec rm -i {} \;"
 alias rm1g="find / -type f -name *.tar -size +1G -exec rm -i {} \;"
 alias rm2g="find / -type f -name *.tar -size +2G -exec rm -i {} \;"
 alias rm5g="find / -type f -name *.tar -size +5G -exec rm -i {} \;"

 rm100m
 rm1g
 rm2g
 rm5g

Here are more usage of find - part 2.

References

stat command in Linux/Unix - Identifying file attributes

Question: How do I find out all the available file attributes. i.e I would like to know more about a file or directory than what the ls -l command displays.
Answer: Everything in Unix is treated as files. This includes devices, directories and sockets — all of these are files. Stat command displays file or filesystem status as explained in this article.

File Stat – Display Information About File

For example, to find out more information about 101hacks.txt file, execute the stat command as shown below.
$ stat 101hacks.txt
  File: `/home/sathiyamoorthy/101hacks.txt'
  Size: 854        Blocks: 8          IO Block: 4096   regular file
Device: 801h/2049d Inode: 1058122     Links: 1
Access: (0600/-rw-------)  Uid: ( 1000/ sathiya)   Gid: ( 1000/ sathiya)
Access: 2009-06-28 19:29:57.000000000 +0530
Modify: 2009-06-28 19:29:57.000000000 +0530
Change: 2009-06-28 19:29:57.000000000 +0530

Details of Linux Stat Command Output

  • File: `/home/sathiyamoorthy/101hacks.txt’ – Absolute path name of the file.
  • Size: 854 – File size in bytes.
  • Blocks: 8 – Total number of blocks used by this file.
  • IO Block: 4096 – IO block size for this file.
  • regular file – Indicates the file type. This indicates that this is a regular file. Following are available file types.
    • regular file. ( ex: all normal files ).
    • directory. ( ex: directories ).
    • socket. ( ex: sockets ).
    • symbolic link. ( ex: symbolic links. )
    • block special file ( ex: hard disk ).
    • character special file. ( ex: terminal device file ).
  • Device: 801h/2049d  – Device number in hex and device number in decimal
  • Inode: 1058122 – Inode number is a unique number for each file which is used for the internal maintenance by the file system.
  • Links: 1 – Number of links to the file
  • Access: (0600/-rw——-): Access specifier displayed in both octal and character format. Let us see explanation about both the format.
  • Uid: ( 1000/ sathiya) – File owner’s user id and user name are displayed.
  • Gid: ( 1000/ sathiya) – File owner’s group id and group name are displayed.
  • Access: 2009-06-28 19:29:57.000000000 +0530 – Last access time of the file.
  • Modify: 2009-06-28 19:29:57.000000000 +0530 – Last modification time of the file.
  • Change: 2009-06-28 19:29:57.000000000 +0530 – Last change time of the inode data of that file.

Dir Stat – Display Information About Directory

You can use the same command to display the information about a directory as shown below.
$ stat /home/ramesh
File: `/home/ramesh'
Size: 4096 Blocks: 8 IO Block: 4096 directory
Device: 803h/2051d Inode: 5521409 Links: 7
Access: (0755/drwxr-xr-x) Uid: ( 401/ramesh) Gid: ( 401/ramesh)
Access: 2009-01-01 12:17:42.000000000 -0800
Modify: 2009-01-01 12:07:33.000000000 -0800
Change: 2009-01-09 12:07:33.000000000 -0800

Details of File Permission:

File Permission In Octal Format

This information about the file is displayed in the Access field when you execute stat command. Following are the values for read, write and execute permission in Unix.
  • Value Meaning
  • 4 Read Permission
  • 2 Write Permission
  • 1 Execute Permission

File Permission In Character Format

This information about the file is displayed in the Access field when you execute stat command.
  • File Type: First bit of the field mentions the type of the file.
  • User Permission: 2nd, 3rd and 4th character specifies the read, write and execute permission of the user.
  • Group Permission: 5th, 6th and 7th character specifies the read, write and execute permission of the group.
  • Others Permission: 8th, 9th and 10th character specifies the read, write and execute permission of the others.

Display Information About File System

You can also use stat command to display the file system information as shown below.
$ stat -f /
  File: "/"
    ID: 0        Namelen: 255     Type: ext2/ext3
Blocks: Total: 2579457    Free: 1991450    Available: 1860421    Size: 4096
Inodes: Total: 1310720    Free: 1215875

References

Saturday, July 26, 2014

15 Practical use of ls in Linux/Unix

1. Open Last Edited File Using ls -t

To open the last edited file in the current directory use the combination of ls, head and vi commands as shown below.
ls -t sorts the file by modification time, showing the last edited file first. head -1 picks up this first file.
$ vi first-long-file.txt
$ vi second-long-file.txt
$ vi `ls -t | head -1`
Note: This will open the last file you edited (i.e second-long-file.txt)

2. Display One File Per Line Using ls -1

To show single entry per line, use -1 option as shown below.
$ ls -1
bin
boot
cdrom
dev
etc
home
initrd
initrd.img
lib

3. Display All Information About Files/Directories Using ls -l

To show long listing information about the file/directory.
$ ls -l
-rw-r----- 1 ramesh team-dev 9275204 Jun 13 15:27 mthesaur.txt.gz
  • 1st Character – File Type: First character specifies the type of the file.
    In the example above the hyphen (-) in the 1st character indicates that this is a normal file. Following are the possible file type options in the 1st character of the ls -l output.
    • Field Explanation
    • - normal file
    • d directory
    • s socket file
    • l link file
  • Field 1 – File Permissions: Next 9 character specifies the files permission. Each 3 characters refers to the read, write, execute permissions for user, group and world In this example, -rw-r—– indicates read-write permission for user, read permission for group, and no permission for others.
  • Field 2 – Number of links: Second field specifies the number of links for that file. In this example, 1 indicates only one link to this file.
  • Field 3 – Owner: Third field specifies owner of the file. In this example, this file is owned by username ‘ramesh’.
  • Field 4 – Group: Fourth field specifies the group of the file. In this example, this file belongs to ”team-dev’ group.
  • Field 5 – Size: Fifth field specifies the size of file. In this example, ’9275204′ indicates the file size.
  • Field 6 – Last modified date & time: Sixth field specifies the date and time of the last modification of the file. In this example, ‘Jun 13 15:27′ specifies the last modification time of the file.
  • Field 7 – File name: The last field is the name of the file. In this example, the file name is mthesaur.txt.gz.

4. Display File Size in Human Readable Format Using ls -lh

Use ls -lh (h stands for human readable form), to display file size in easy to read format. i.e M for MB, K for KB, G for GB.
$ ls -l
-rw-r----- 1 ramesh team-dev 9275204 Jun 12 15:27 arch-linux.txt.gz*

$ ls -lh
-rw-r----- 1 ramesh team-dev 8.9M Jun 12 15:27 arch-linux.txt.gz

5. Display Directory Information Using ls -ld

When you use “ls -l” you will get the details of directories content. But if you want the details of directory then you can use -d option as., For example, if you use ls -l /etc will display all the files under etc directory. But, if you want to display the information about the /etc/ directory, use -ld option as shown below.
$ ls -l /etc
total 3344
-rw-r--r--   1 root root   15276 Oct  5  2004 a2ps.cfg
-rw-r--r--   1 root root    2562 Oct  5  2004 a2ps-site.cfg
drwxr-xr-x   4 root root    4096 Feb  2  2007 acpi
-rw-r--r--   1 root root      48 Feb  8  2008 adjtime
drwxr-xr-x   4 root root    4096 Feb  2  2007 alchemist
$ ls -ld /etc
drwxr-xr-x 21 root root 4096 Jun 15 07:02 /etc

6. Order Files Based on Last Modified Time Using ls -lt

To sort the file names displayed in the order of last modification time use the -t option. You will be finding it handy to use it in combination with -l option.
$ ls -lt
total 76
drwxrwxrwt  14 root root  4096 Jun 22 07:36 tmp
drwxr-xr-x 121 root root  4096 Jun 22 07:05 etc
drwxr-xr-x  13 root root 13780 Jun 22 07:04 dev
drwxr-xr-x  13 root root  4096 Jun 20 23:12 root
drwxr-xr-x  12 root root  4096 Jun 18 08:31 home
drwxr-xr-x   2 root root  4096 May 17 21:21 sbin
lrwxrwxrwx   1 root root    11 May 17 20:29 cdrom -> media/cdrom
drwx------   2 root root 16384 May 17 20:29 lost+found
drwxr-xr-x  15 root root  4096 Jul  2  2008 var

7. Order Files Based on Last Modified Time (In Reverse Order) Using ls -ltr

To sort the file names in the last modification time in reverse order. This will be showing the last edited file in the last line which will be handy when the listing goes beyond a page. This is my default ls usage. Anytime I do ls, I always use ls -ltr as I find this very convenient.
$ ls -ltr

total 76
drwxr-xr-x  15 root root  4096 Jul  2  2008 var
drwx------   2 root root 16384 May 17 20:29 lost+found
lrwxrwxrwx   1 root root    11 May 17 20:29 cdrom -> media/cdrom
drwxr-xr-x   2 root root  4096 May 17 21:21 sbin
drwxr-xr-x  12 root root  4096 Jun 18 08:31 home
drwxr-xr-x  13 root root  4096 Jun 20 23:12 root
drwxr-xr-x  13 root root 13780 Jun 22 07:04 dev
drwxr-xr-x 121 root root  4096 Jun 22 07:05 etc
drwxrwxrwt  14 root root  4096 Jun 22 07:36 tmp

8. Display Hidden Files Using ls -a (or) ls -A

To show all the hidden files in the directory, use ‘-a option’. Hidden files in Unix starts with ‘.’ in its file name.
$ ls -a
[rnatarajan@asp-dev ~]$ ls -a
.                             Debian-Info.txt
..                            CentOS-Info.txt
.bash_history                 Fedora-Info.txt
.bash_logout                  .lftp
.bash_profile                 libiconv-1.11.tar.tar
.bashrc                       libssh2-0.12-1.2.el4.rf.i386.rpm
It will show all the files including the ‘.’ (current directory) and ‘..’ (parent directory). To show the hidden files, but not the ‘.’ (current directory) and ‘..’ (parent directory), use option -A.
$ ls -A
Debian-Info.txt               Fedora-Info.txt
CentOS-Info.txt               Red-Hat-Info.txt
.bash_history                 SUSE-Info.txt
.bash_logout                  .lftp
.bash_profile                 libiconv-1.11.tar.tar
.bashrc                       libssh2-0.12-1.2.el4.rf.i386.rpm

Note: . and .. are not displayed here

9. Display Files Recursively Using ls -R

$ ls  /etc/sysconfig/networking
devices  profiles

$ ls  -R /etc/sysconfig/networking
/etc/sysconfig/networking:
devices  profiles

/etc/sysconfig/networking/devices:

/etc/sysconfig/networking/profiles:
default

/etc/sysconfig/networking/profiles/default:
To show all the files recursively, use -R option. When you do this from /, it shows all the unhidden files in the whole file system recursively.

10. Display File Inode Number Using ls -i

Sometimes you may want to know the inone number of a file for internal maintenance. Use -i option as shown below to display inone number. Using inode number you can remove files that has special characters in it’s name as explained in the example#6 of the find command article.
$ ls -i /etc/xinetd.d/
279694 chargen      279724 cups-lpd  279697 daytime-udp
279695 chargen-udp  279696 daytime   279698 echo

11. Hide Control Characters Using ls -q

To print question mark instead of the non graphics control characters use the -q option.
ls -q

12. Display File UID and GID Using ls -n

Lists the output like -l, but shows the uid and gid in numeric format instead of names.
$ ls -l ~/.bash_profile
-rw-r--r--  1 ramesh ramesh 909 Feb  8 11:48 /home/ramesh/.bash_profile
$ ls -n ~/.bash_profile
-rw-r--r--  1 511 511 909 Feb  8 11:48 /home/ramesh/.bash_profile

Note: This display 511 for uid and 511 for gid

13. Visual Classification of Files With Special Characters Using ls -F

Instead of doing the ‘ls -l’ and then the checking for the first character to determine the type of file. You can use -F which classifies the file with different special character for different kind of files.
$ ls -F
Desktop/  Documents/  Ubuntu-App@  firstfile  Music/  Public/  Templates/
Thus in the above output,
  • / – directory.
  • nothing – normal file.
  • @ – link file.
  • * – Executable file

14. Visual Classification of Files With Colors Using ls -F

Recognizing the file type by the color in which it gets displayed is an another kind in classification of file. In the above output directories get displayed in blue, soft links get displayed in green, and ordinary files gets displayed in default color.
$ ls --color=auto
Desktop  Documents Examples firstfile Music  Pictures  Public  Templates  Videos

15. Useful ls Command Aliases

You can take some required ls options in the above, and make it as aliases. We suggest the following.
  • Long list the file with size in human understandable form.
    alias ll="ls -lh"
  • Classify the file type by appending special characters.
    alias lv="ls -F"
  • Classify the file type by both color and special character.
    alias ls="ls -F --color=auto"

References