Algo#50: Find k element pairs out of given array which adds to SUM

Find k element pairs out of given array which adds to SUM

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#49: Sort the input character array based on the given dictionary order.

Sort the input character array based on the given dictionary order.

E.G. If input word is “SHEEP“, sorting will make it as “EEHPS“.

But in the given dictionary, E may not be at first. As per the dictionary in given problem, if P is first, S followed and E later and finally H.

Then sorted array should be “PSEEH“.

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#48: Find minimum window length which accommodate all given character.

Given problem is purely string manipulation problem. Here we have to find minimum window length which accommodate all given character for second string.

E.g. Given string ABBACBAA, and if we want to find minimum window length which can accommodate "AAA", it will be 5 (index 3 to 7). "CCC" should return MAX length as no window in original string can accommodate "CCC".

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#47: Word search in matrix of N*N

Word search can be solved with backtracking method.

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#46: Determine growing direction of stack.

Note down the address of a local variable. Call another function with a local variable declared in it and check the address of that local variable and compare both.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#45: Find middle node from given singly linked list using recursion.

We can find middle node from given linked list in one look of singly linked list using recursion (Ignoring stack removal access).

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#44: Modify linked list to put nodes alternate from begin & end

To modify linked list to put nodes alternate from begin & end, we will use recursion. So we can access nodes in forward and reverse direction simultaneously. And we don't need to go back and forth to access nodes from begin and end.

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#43: Write basic function to implement atoi - Alpha to Integer

Function atoi is used to convert alphabetical string to integer. We can parse given string one character at a time, and convert it to integer. To make conversion fast enough, we can use bits manipulation for faster calculation.

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#42: Multiply by 7

Multiply given number by 7 without using * operator. What we can do is, multiply given number by 8 and then subtract given number from result. Now problem reduce to multiply by 8 rather than 7. But we know to multiply any number with power of 2, we can use shift operator. 

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#41: Free given binary tree.

Given problem of freeing data structure checks whether you know in & out of given data structure or not. You can verify memory leaks using Valgrind.

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#40: Union Find Data Structure in C

Union Find Data Structure is useful to reduce time complexity in many problems e.g. Kruskal’s algorithm. 

Following is implementation of above data structure in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#39: Trim spaces from given string

Trim spaces from given string, can be asked in 2 ways. Removing all spaces from given string is easy to do than trimming only initial & end spaces.

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#38: Print range of numbers without loop

To print range of numbers without using loop, we can use our usual recursion concept again.

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#37: Calculate x^y in less time complexity than O(y)

Brute force way to calculate power of any number is to multiply given x number, power y times. But recursion can drastically reduce time complexity.

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#36: String passing from function

Many times we need to pass string from one function to other. There are different ways to do it. Each way has some method of allocating memory either in stack or heap. We need to be aware of allocation method when we use particular way.

Following is implementation of above concept in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#35: Check whether given number is power of two

To check whether given number is power of two, is problem of doing bits manipulation.

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#34: Find GCD of two numbers.

To find Greatest Common Divisor - GCD , we can use well known Euclidean algorithm.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#33: Using existing library functions.

This problem seems different from others. But many times in interview, you can expect this type of question of using existing library function.

Given teams score and number of times they won. We have to sort team based on these. If there is tie on score, sort them using number of times they won.

We can do this easily with qsort rather than starting from scratch.

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#32: Generate spiral matrix or helical matrix.

It seems very easy problem of just printing 2D matrix in some format. But it includes many corner cases which needs to be taken care of. Such problems can test your coding practice.

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#31: Find nth node in inorder traversal.

Given problem of finding nth node in in-order traversal can be easily done if we keep count of nde visited while doing in-order traversal. We will do keep this counter as static rather than global. Though taking static variable are also not encouraged in general because of parallel programming. But as of now in our case it will do.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#30: Iterative implementation of Post-order, Pre-order & In-order traversal of given binary tree

We mostly use recursive function whenever we are asked traversal of binary tree. But what if you have to do it iterative. All recursion function can be converted to iterative with more or less effort.

Here we will see Post-order, Pre-order & In-order traversal of given binary tree using iterative method.

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#29: Check whether given number's bit representation is palindrome or not.

To find whether anything is palindrome or not,easiest method is to reverse it and check whether it is same as original. We will follow same approach for checking whether given number's bit representation is palindrome or not.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#28: Help frog to cross river.

Lets say there is a river that is η meters wide. At every meter from the starting shore, there may or may not be a stone enough for frog to sit. Now a frog needs to cross the river. However the frog has the limitation that if it has just jumped x meters, then it can take next jump only of size  x-1, x or x+1 meters. First jump can be of only 1 meter when starting from shore.

Assume frog can see all stone from this shore to opposite shore. Can frog determine whether it can make it to the other end or not.

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#27: Count number of 1's in given number

Brute force method to count number of 1's in given number is to iterate through each bit and check if it is 1, then increment counter. But it will take 32 checks (assuming 32 bit number).

Can we do better? Is there any way by which we don't need to check all bits? What if we iterate as many times as numbers of 1's. To achieve it, we have to remove 1 from number at each iteration, then only at last when no one is remaining in number, we can stop.

Manipulation of bits in number is only solution to reduce iteration. By doing x-1, we can eliminate last 1 from given number but it will introduce tailing 1's in number. But those should be not an issue for us. Because we have AND weapon to get rid of all tail 1's.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#26: Binary Search In Unbounded Array

Binary Search in Unbounded array.

Following is simple algorithm for above problem.

Step 1: Locate lower and upper bound using jump at every 2^k location
Step 2: Do binary search within located bounds.

Following is implementation of above algorithm in c++ language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#25: Find kth smallest from given 2 sorted array.

Finding kth smallest element from given 2 sorted array is not big deal if we are allowed to do it in O(K) or O(N+M). But what if you are asked to do it less than that. Can we use binary search technique to reduce complexity as given array are sorted !!

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#24: Find min and max from given array.

Given problem of finding min and max from given array seems to be very trivial problem. But what if you are asked to do it in less than 2N-3 comparisons!

Following is simple algorithm for above problem.

Step 1: Partition given array in 2 parts.
        1.1: Compare 2 element pairs for all elements.
        1.2: Put min out of this 2 elements in list-1 and max out of this 2 elements in list-2.
Step 2: Find min & max from partial lists.
        2.1: Find running min from list-1.
        2.2: Find running max from list-2.

Though at first look, given algorithm seems to have other 2N space for storing partial list with 3N/2 -1 comparisons to find min & max. But making twist during implementation can make above algorithm to run in O(1) space complexity and 3N/2+3 comparisons only.
.

Following is implementation of above algorithm in c language with twist to reduce space complexity.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#23 Search given key in BST, if not present return next higher value than key which is present

Search given key in BST, if not present return next higher value than key which is present.

If we think just for a while, we will come to know that it is nothing but modified search in BST only. We have to maintain node when ever we are taking left turn in BST. Thats it. Done. Why it will work like this? Because if we are going right side, it means our key is grater than value at current node. So we don't need that value which is less than our key.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#22: Swap nibbles of number.

Nibbles are nothing but chunk of 4 bits in simple language.

To swap nibbles in given number, we have to extract 4-bits chunk from number and depending on system, we have to shift them accordingly.

Following is implementation of above algorithm in c language for 8-bit system ( Imaginary ).

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#21: Give next higher boundary number.

To give next higher boundary of number, is used when allocating memory to structure, so that access to its members are fast.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#20: Tail command implementation

Tail command is used for extracting last n lines from file. This is very common question that we can expect  in any IT interview. To implement tail command we will use queue data structure. 

Following is simple algorithm for tail command implementation with n as parameter (number of last lines to read).

Step 1: Read line from file, and store it into queue.
Step 2: If number of lines in queue exceeds parameter n, then we can delete one line from front. Because we only need to keep n lines in queue.
Step 3: When file reading ends, we have n lines in queue.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#19: Convert given number in different endian system than your system.

There are mainly two types of system based on endianness available to us.
1) Big endian
2) Little endian

To convert one number other endianness system, we have to change order of all bytes.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#18: Add two numbers without using plus(+) operator.

There are many ways to do one thing. Given problem very well follows it. This kind of problems will test how much comfortable you are with concepts as well as language. Because both will improve your skills to solve problem in more than one way.

There is no single algorithm for such tricks. Practice makes (wo)man perfect.

Following is implementation of some of the tricks in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#17: Check whether array is sorted or not using recursion

This program basically test your recursion skills. So what should be our approach when questions like this comes.

When we are solving any problem with recursion, we have to identify datum which we are going to process in one iteration of recursion. Here in our case, we will process one element of array at a time, it means remaining n-1 element should be process by recursion.

Following is simple recursive algorithm for Checking array for sorted property using recursion.
Step 1: If we are having only one element, then by default it is sorted. Success.
Step 2: Otherwise, relationship between first and second element. first element <= second element. If not then failure, else go to step 3.
Step 3: Get success or failure indicator for remaining array of n-1 element using recursion.If remaining array comes out to be sorted, then whole array is sorted.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#16: Solve 8-Queen Problem.

8-Queen problem ask us to set 8 queen on board such that they don't attack each other by any direction. We must be knowing that queen can move row wise, column wise and in both diagonals also.

First thing we need here is, way to check whether we can put chosen queen at particular location or not. We can put queen only if satisfy following criteria.
1. It should be unique in its row.
2. It should be unique in its column.
3. It should be unique in its both diagonals.

Lets say we made some function called Check() which tell whether current queen have any conflicts with previous queens that we have set. Now we are ready to take up our back tracking algorithm.

Following is simple algorithm for finding 8-Queen Problem.

Step 1: If we have filled all rows of board than we are done.
Step 2: Otherwise try all possible columns for current queen and check if it has any conflicts with any previous queen, if not then set remaining queens.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#15: Sudoku solver

To solve given Sudoku of any level, by back tracking method, we have to try each possible combinations until it gets solved. We have to take care about given filled numbers which we can not modified while doing back track.

First thing we need here is, way to check whether we can put chosen number at particular location or not. We can put number only if satisfy following criteria.
1. It should be unique in its row.
2. It should be unique in its column.
3. It should be unique in its region (3 * 3) box.

Lets say we made some function called isValid() which tell check above constraint for our move. Now we are ready to take up our back tracking algorithm.

Following is simple recursive algorithm for Solving given Sudoku.

Step 1: If we have filled all position without violation of any constraint, then we are done.
Step 2: If current location (filling row by row, left to right) is fixed location, we can not modified it, go ahead and fill remaining location recursively.
Step 3: Try every element from 1 to 9 one by one and check if remaining Sudoku can be solved recursively. If we are out of all nine numbers, and Sudoku doesn't yet solved then Sudoku is unsolvable.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#14: Set specified bits range in number.

Set specified bits range in number.

Following is simple algorithm for setting bits range in given number.

Step 1: Make mask for start index to end index.
        1.1: First step to make mask is, set 1 in each position from 0 to end index, call it mask-1.
        1.2: Then same way, set 1 in each position from 0 to start index, call  it mask-2.
        1.3: XOR mask-1 and mask-2, which will give us our desired mask having 1 set from start to end index.
Step 2: Do OR operation between given number and mask.

Following is implementation of above algorithm in c language in 1 line.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#13: Cyclic right shift of bits in number

Manipulation of bits are very crucial if you can apply it properly in your computing because it is one of the fastest technique for computing.

Following is simple algorithm for finding Cyclic Right Shift of bits in given number by S bits.

Step 1: Take right S bits of number, and shift it right by R-S positions, where R is number of total bits in given number, call it Partial-1.
Step 2: Take left R-S bits of number, and shift it left by S positions, call it Partial-2.
Step 3: Do OR operation between Partial-1 and Partial-2.

Following is implementation of above algorithm in c language in one line.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#12: Binary Search Technique with Duplicates - Find Last Occurrence Index

Binary search technique is very well known for its fast search result provided given array is sorted.

Following is simple iterative algorithm for Binary Search (Last Occurrence) in Sorted Array With Duplicates.
Step 1: Set l(left) at start index of array.
Step 2: Set r(right) at end index of array.
Step 3: Set left-border at start index of array.
Step 4: Set right-border at end index of array.
Step 5: Repeat following until r>=l
        5.1: Initialize mid using current left and right index (l+(r-l)/2).
      5.2: If element at mid index is target element and element at after mid index is different than target element, then return mid index as successful binary search.
        5.3: Otherwise if element at mid index is greater or equal to target element, then replace r = mid -1
        5.4: Otherwise if element at mid index is less than target element, then replace l = mid +1
Step 6: If you reach here, element you are searching for is not found.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.