Double Linked List Structure
Posted on December 31, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
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.
[Read More]First non repeating element in the array
Posted on December 31, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
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.
[Read More]Find anagrams in the array of Strings
Posted on December 31, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
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).
[Read More]Gold bar with 7 segments
Posted on December 30, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
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.
[Read More]Implementing a strstr() / indexOf function
Posted on December 30, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
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.
[Read More]Combination of all the possible characters in the string
Posted on December 30, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
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.
[Read More]Concatenate N strings with good optimization
Posted on December 30, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
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.
[Read More]Check if Tree is a Balanced Tree
Posted on December 29, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
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){ if(root==null){ return true; //tree is empty } else{ int lh = root.
[Read More]Some Stack Question
Posted on December 29, 2011
(Last modified on August 7, 2020)
| 5 minutes
| Kinshuk Chandra
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)
[Read More]Implement 3 stacks in 1 array
Posted on December 29, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
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 3, we will use [2n/3, n) Here is the code :
[Read More]