BFS (Breadth first search ) OR Level Order Traversal on tree

Algorithm Starting at some arbitrarily chosen vertex s (s stands for start vertex) , we mark v so that we know we've visited it, process v, and  then visit i.e. mark the vertex as visited and process all of v's neighbors.  Now that we've visited and processed all of v's neighbors,  we need to visit and process all of v's neighbors neighbors Example So consider the tree:       1    /    \   2      3  /   \   /   ...

Read More

Check if 2 strings are rotated versions of each other

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/rotate-string-problem/. Problem : Given two string s1 and s2 how will you check if s1 is a rotated version of s2 ? OR Assume you have a method isSubstring() which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring.ie: 'waterbottle' is a rotation of 'erbottlewat' Example s1...

Read More

Syntax highlighter for blogs

Read the tutorial he...

Read More

Escape all % characters in a string; % is the escape character

Example : Input : India has GDP of 10% in 2009 Output : Input has GDP of 10%% in 2009 It is usually not be possible to do this in-place since the original unescaped string may not have enough space in the array to store the additional escape characters. But if we create a new array, O(n) algo is possible, though space complexity will increase. String escapePercent(String input) { StringBuilder sb = new StringBuilder(); char[] str = input.toCharArray(); for (int i = 0; i < input.length(); i++) { if (str[i] == ‘%’) sb.append(‘%’); ...

Read More

Remove whitespace from a string in-place, in linear time

void removeWhitespace(char* str) { int current = 0; int ahead = 0; while (str[ahead] != '\0') { while (str[ahead] == ' ') ahead++; str[current] = str[ahead]; current++; ahead++; } ...

Read More

Implementing strcpy

char *strcpy ( char *dest, const char *src ); strcpy is short for string copy, which means it copies the entire contents of src into dest. The contents of dest after strcpy will be exactly the same as src such that strcmp ( dest, src ) will return 0. size_t strlen ( const char *s );strlen will return the length of a string, minus the termating character ('\0'). The size_t is nothing to worry about. Just treat it as an integer that cannot be negative, which it is....

Read More

Implementing strcat

char *strcat ( char *dest, const char *src );strcat is short for string concatenate, which means to add to the end, or append. It adds the second string to the first string. It returns a pointer to the concatenated string. Beware this function, it assumes that dest is large enough to hold the entire contents of src as well as its own contents....

Read More

Implementing strcmp

int strcmp ( const char *s1, const char *s2 );strcmp will accept two strings. It will return an integer. This integer will either be: Negative if s1 is less than s2. Zero if s1 and s2 are equal. Positive if s1 is greater than s2.Strcmp is case sensitive. Strcmp also passes the address of the character array to the function to allow it to be accessed....

Read More

Double Linked List Structure

If you wish to traverse a list both forwards and backwards efficiently, or if you wish, given a list element, to determine the preceding and following elements quickly, then the doubly-linked list comes in handy. A list element contains the data plus pointers to the next and previous list items as shown in the picture below. Of course we need a pointer to some link in the doubly-linked list to access list elements. It is convenient for doubly-linked...

Read More

First non repeating element in the array

Question: Write an algorithm to find the first non-repeated character in a string. For example, the first non-repeated character in the string ‘abcdab’ is ‘c’. Answer: Seems trivial enough right? If a character is repeated, we should be able to search the string to determine if that character appears again. So if we go about doing this for every character in the string, our worst case run time would O(n^2). Here is some code to show this logic. char returnFirstNonRepeatedChar( char * str ) { int i, repeated = 0; int len = strlen(str); ...

Read More

Find anagrams in the array of Strings

Question: You are given an array of strings and you are asked to display all the anagrams within the array. For those who don’t know, two words are anagrams if they contain the same characters. We have already discussed how to check if 2 strings are anagrams here. Answer: The brute force solution would be to take each string and compare it to every other string in the array one character at a time ( O(n^4) solution, assuming there are n strings with maximum n characters each). This will surely give you the answer but almost certainly not the...

Read More

Gold bar with 7 segments

Problem: You’ve got someone working for you for seven days and a gold bar to pay them. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker? Solution: Break the 7 piece gold bar to make a piece of 1 segment size and the other of 2 segments size.( the remaining 4 segments intact) i.e 7=...

Read More

Implementing a strstr() / indexOf function

strstr() find the substring index into the larger string and returns the index of first occurrence. Below is the code implementation in java. However note that strstr() equivalent in java is indexOf() which do the same thing. public static int strStr(String large, String possibleSubStr){ for(int i = 0; i < large.length(); i++ ) { for(int j = 0; j < possibleSubStr.length() && i+j < large.length(); j++ ) { if(possibleSubStr.charAt(j) != large.charAt(i+j)) { break; } else if...

Read More

Combination of all the possible characters in the string

Question: Write an algorithm to print all possible combinations of characters in a string. Note : By combination it means number of different strings possible taking 1 or 2 ...or n characters from string, so we dont have to worry about various character permutation. So for beta, when you get eta, you don't have to get its anagrams like ate, tae etc. For a string of length n, there are nCn + nCn-1 + ... + nC1 combinations. For string abc, there are 1 + 3 + 3 = 7 combinations. nC1 - a, b, c nC2 - ab, bc, ca nC3 - abc Answer: Any thoughts?...

Read More

Concatenate N strings with good optimization

You have n strings with their lengths. You are given an add(string s1,string s2) which would concatenate the string s2 with s1 and return s3. Optimize the cost of concatenation of all these strings into one big string. Eg: 1,3,2 are the lengths of given strings. 1+3=4 4+2=6 total cost=10 Optimize this total cost? So here goes the algo: Make a min heap out of the elements given. Pop the smallest and the second smallest, add them and again insert that back to the heap. Finally you will get the minimum cost OR you can sort the array on the basis...

Read More

Check if Tree is a Balanced Tree

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/balanced-binary-tree-problem/. Problem Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one Solution Method 1 - Difference of height at each node should not be greater than 1 Here is the code : public boolean isBalanced(Node root){ ...

Read More

Some Stack Question

 1)How do you implement 2 stacks using only one array.Your stack routines should not indicate an overflow unless every slot in the array is used? Solution:given an Array,start the first stack S1 from left end and other stack S2 from the right end.while S1 gets grows towards right ,S2 grows towards left. (By the way we can implement n stacks in 1 array, eg. of 3 stacks in 1 array is given in question 3 below) 2)Propose a data structure which supports the stack Push and Pop operations and a third operation FindMin,which returns the smallest...

Read More

Implement 3 stacks in 1 array

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/implement-3-stacks-in-1-array/. Problem - Implement 3 stacks in 1 array Solutions Method 1 - Create 3 stacks with fixed max size Divide the array in three equal parts and allow the individual stack to grow in that limited space (note: "[" means inclusive, while "(" means exclusive of the end point). for stack 1, we will use [0, n/3) for stack 2, we will use [n/3, 2n/3) for stack...

Read More

Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.

You can implement a stack with O(1) pop(), push() and get_min(): just store the current minimum together with each element. So, for example, the stack [4,2,5,1] (1 on top) becomes [(4,4), (2,2), (5,2), (1,1)]. See here for the full implementation. Then you can use two stacks to implement the queue. Push to one stack, pop from another one; if the second stack is empty during the pop, move all elements from the first stack to the second one. To find the minimum element of the queue, look at the smallest two elements of the individual min-stacks,...

Read More

Find the minimum element in the rotated sorted sorted array

Question : Find the minimum element in the rotated sorted array. So for example we have sorted array as  - 2,3,6,12, 15, 18. Now suppose the array is rotated k times ( we don't know k), such that array becomes 15, 18,2,3,6,12 Answer - The answer to this lies on the fact that if we can find the point on inflection and things will be simple. So if we can have 2 sub arrays A and B, // always restrict the search to the unsorted // sub-array. The min is always there. public static int findMin(int[] a, int start, int end){ int mid =...

Read More

Search an element in the sorted rotated array

Question: Implement a search function for a sorted rotated array. Duplicates are allowed. Returning any one of the duplicates is acceptable. So for example we have sorted array as  - 2,3,6,12, 15, 18. Now suppose the array is rotated k times ( we don't know k), such that array becomes 15, 18,2,3,6,12 Answer: We can do a binary search with some modified checks. So lets take arr as array, start be start of the array, end be arr.length-1 and x be the number to find. Pseudocode:  Find the middle of array Select the sorted...

Read More

Reverse a String using bits

Question: Reverse a string in C using as little additional memory as possible. Answer: The first solution needs the size of a char and size of two integers, all of which will be allocated from the stack. This solution is the most commonly accepted “good” solution. Here is the code. Method 1 - Normal Reversal of String void reverseString(char* str) { int i, j; char temp; i=j=temp=0; j=strlen(str)-1; for (i=0; i<j; i++, j--) { temp=str[i]; str[i]=str[j]; str[j]=temp; } } Method 2 - Using...

Read More

Pick a Random Byte

Problem:  You have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal. Solution:  Since we can only store one byte at a time, we have to be able to work with the bytes as they come in. We can’t store everything, count the number of bytes...

Read More