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 / ...

Read More

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...

Read More

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...

Read More

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....

Read More

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...

Read More

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]...

Read More

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,...

Read More

Algorithm Interview Questions - Set 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. Intersection of n sets without using a hash table. Implement a LRU(Least Recently Used) cache Implement a function to compute cubic root what is the time complexity? 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. Given a matrix of numbers in which some may be zero. If a cell contains a zero, set all the...

Read More

Design Questions - Set 1

Design a game of chess Given an ebay site model., you have to deal with auctioning of a particular item. Design the billing & auctioning system of the same. OOPs design of a file system Class diagram of a system to implement Blackjack Class diagram of a parking lot 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 Which Data structure is used in window search…??  http://www.careercup.com/question?id=12688668 Design...

Read More

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

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/finding-the-maximum-distance-between-increasing-elements-in-an-array/. 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:...

Read More

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...

Read More

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...

Read More

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...

Read More

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...

Read More

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...

Read More

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...

Read More

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' ...

Read More

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....

Read More