Algorithm Questions - Series 1
String/List Algorithm Questions
String
Q. Reverse a C-Style String
Q. Replace all spaces in a string with '%20' [C, C++]
Construct the new string backwards - from back to front.
Q. Find the First Non-repeated Character
Q. Deletes characters from a string. Use the prototype string removeChars( string str, string remove );
Q. Convert String to Integer
Q. Convert Integer to String
Q. Reverse the order of the words in a string
S. Reverse the whole string then iterate it to reverse each word.
Q. You are given a string like "aaaabbbcc", do an in place conversion which write frequency of each character (which come continuously) with that character. If character repeats only once, don't write '1'.
Q. You have a string "RGBBGBGR". Eliminate the pairs (two same chars adjacent to each other) recursively:
void removePair(char[] input)
{
int len = input.length;
int i, j = 0;
for (i=1; i <= len; i++)
{
while ((input[i] == input[j]) && (j >= 0)) //Cancel pairs
{ i++; j--; }
input[++j] = input[i];
}
}
Q. Remove the duplicate characters in a string without using any additional buffer [C,C++].
1. Same technique as before, use an int to express whether the char has appeared before.
S2.
for (int i = 1; i < len; ++i) {
int j;
for (j = 0; j < tail; ++j)
{if (str[i] == str[j]) break;}
if (j == tail) {
str[tail] = str[i];
++tail;
}
}
Q. Find all the characters, which are present in the character array given. The order of character should remain intact.
Q. Decide if two strings are anagrams [变位词] or not.
S. Check if the two strings have identical counts for each unique char.
1. Use an int array letters [256] to count number of each char in the first string s.
2. Iterate each char in the second string t:
If char ch doesn't exist in s, return false, else decrease the number of letters[ch] by one.
3. At last, check whether all values in letters is 0, if not return false else return true.
Q. Check if s2 is a rotation of s1 using isSubstring?
Check if length(s1) == length(s2). If not, return false
Else, concatenate s1 with itself and see whether s2 is substring of the result
Q. Determine if a string has all unique characters without using any additional buffer.
Save space usage by using an int as bit vector to express whether the char has appeared before.
public static boolean isUniqueChars(String str)
{
int checker = 0;
for (int i = 0; i < str.length(); ++i)
{
int val = str.charAt(i);
if ((checker & (1 << val)) > 0) return false;
checker |= (1 << val);
}
return true;
}
Q. Prints all possible ordering of the characters in a string. Treat each character in the input string as a distinct character, even if it is repeated. – Dynamic programming
Q. Combinations of a String
Print all possible combinations of the characters in a string. Two combinations that differ only in ordering of their characters are the same combination.
Array
Q. Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees in place? [TODO]
Q. Find minimum and maximum in an unsorted array in minimum number of comparisons.
Pick 2 elements at a time 1) compare the larger element with max find till now, 2) compare the smaller elements with min find till now and 3) update accordingly. – Time complexity O(3n/2).
Q1. A sorted array has been rotated, how to find the minimum element?
For a particular point, if LEFT < RIGHT, then the range does not contain the reset, if LEFT > RIGHT, then it does.
Q2. How to find an element?
Q. There is an m x n grid. One can only move either down or right at any point in time. Calculate how many possible unique paths are there and print all paths.
Paths[i][j] = paths[i][j-1] + paths[i-1][j]
Q. Find triplets in an integer array A[] which satisfy following condition:a[i]^2 + a[j]^2 = a[k]^2
Q. There is an integer array consisting positive and negative integers. Find maximum positive difference S defined as: S = a[i] - a[j] where i>j and S > 0
void MaxDiff(int in[], int sz, int &start, int &end) {
int min = 0;
int maxDiff = 0;
start = end = 0;
for (int i = 0; i < sz; i++) {
if (in[i] < in[min]) min = i;
int diff = in[i] - in[min];
if (diff > maxDiff) { start = min; end = i; maxDiff = diff; }
}
}
Q. You have an array containing only '0's and '1's. Sort this array in minimum time.
while(j>i){
if(array[i] == 0){
i++; continue;
}
while(array[--j] == 1);
if(j>i) SWAP(array[i],array[j]);
}
Lo := 1; Mid := 1; Hi := N;
while Mid <= Hi do
Invariant: a[1..Lo-1]=0 and a[Lo..Mid-1]=1 and a[Hi+1..N]=2; a[Mid..Hi] are unknown.
case a[Mid] in
0: swap a[Lo] and a[Mid]; Lo++; Mid++
1: Mid++
2: swap a[Mid] and a[Hi]; Hi--
Sort array A[], then initialize 2 pointers, one points to the head, another to the end. add elements the head and end point to, if the sum is equal with the number, return, if greater than the number, decrease end pointer by 1, else increase start by 1.
Q. There is an integer array consisting positive numbers only. Find maximum possible sum of elements such that there are no 2 consecutive elements present in the sum.
S(i) = MAX {S(i-1), S(i-2) + T(i) }
S(-1) = 0,S(0) = T(0);
sum2 = 0;
sum = sum1 = array[0];
for(i=1; i<len; i++)
{
sum = MAX(sum2 + array[i], sum1);
sum2 = sum1;
sum1 = sum;
}
Q. Print all valid parenthesis Sequences for a given number of pairs of parenthesis. -Dynamic programming
void printbracket(char[] out, int level, int open, int close)
{
if (level == 2 *n)
{ System.out.print(out); return; }
out[level] = '(';
if ((open + 1) <= n && open >= close)
{ printbracket(out, level + 1, open + 1, close); }
out[level] = ')';
if ((close + 1) <= n && open >= close)
{ printbracket(out, level + 1, open, close + 1); }
}
Q. An array contains integers, every integer occurs 3 times, one integer appears only once. Find out that integer. [TODO]
Basically, it makes use of the fact that x^x = 0. So all paired elements get XOR'd and vanish leaving the lonely element.
Since XOR operation is associative, commutative. It does not matter in what fashion elements appear in array, we still get the answer.
Linked List
Q. Remove duplicates from an unsorted linked list.
Maintain 2 pointers, "current" does a normal iteration, while "runner" iterates through all prior nodes to check for dups. whenever found one match, remove current node and break the loop - as there would be only one dup node before.
Q. Find the nth to last element of a singly linked list.
1. At first p1 points to the head, iterate to make p2 point to the nth node.
2. Check for p2->next == null, if yes return value of p1, otherwise increment p1 and p2.
Q. Only give a pointer to one node, delete it from a single linked list.
Copy the data from the next node into this node and then delete the next node.
This problem can not be solved if the node to be deleted is the last node in the linked list.
Q. Swap adjacent element in a link list
Q. You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
LinkedListNode addLists(LinkedListNode l1, LinkedListNode l2, int carry) {
if (l1 == null && l2 == null) { return null; }
LinkedListNode result = new LinkedListNode(carry, null, null);
int value = carry;
if (l1 != null) { value += l1.data; }
if (l2 != null) { value += l2.data; }
result.data = value % 10;
LinkedListNode more = addLists(l1 == null ? null : l1.next, l2 == null ? null : l2.next, value > 10 ? 1 : 1);
result.setNext(more);
return result;
}
Q. Decide whether a linked list has a loop if yes, return node at the beginning of the loop.
1. Find meeting point by moving two pointers, n1 with speed 1 and n2 with speed 2, they will end up meeting if the linked list has a loop.
2. Move n1 to Head. Keep n2 at Meeting Point. Each is k steps from the Loop Start. If they move at the same pace, they must meet at Loop Start.
Resources
