For example, if the input string is “00100101”, then there are three substrings “1001”, “100101” and “101”.
Ans
a) Count the number of 1’s. Let the count of 1’s be m.
b) Return m(m-1)/2
Monthly Archives: December 2014
Apti
1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
What is the next line?
Answer
LZ algorithm
Next line is pairs (count, digit) for sequence of digits in previous line.
3 1 2 2 1 1
How to check if an instance of 8 puzzle is solvable
It is not possible to solve an instance of 8 puzzle if number of inversions is odd in the input state.
What is inversion?
A pair of tiles form an inversion if the the values on tiles are in reverse order of their appearance in goal state. For example, the following instance of 8 puzzle has two inversions, (8, 6) and (8, 7).
1 2 3 4 _ 5 8 6 7
CODE
int getInvCount(int arr[])
{
int inv_count = 0;
for (int i = 0; i < 9 - 1; i++)
for (int j = i+1; j < 9; j++)
// Value 0 is used for empty space
if (arr[j] && arr[i] && arr[i] > arr[j])
inv_count++;
return inv_count;
}
bool isSolvable(int puzzle[3][3])
{
// Count inversions in given 8 puzzle
int invCount = getInvCount((int *)puzzle);
// return true if inversion count is even.
return (invCount%2 == 0);
}
string to int
str = '1234'
str - '0' = [1 2 3 4]
When you use arithmetic operators with strings, strings is cast as doubles, which converts a string to ascii values,
Thus, subtraction will work just fine, though addition will give weird results
minimal sum of two integers that are made of the digits contained in the array
Given the array of digits (0 is also allowed), what is the minimal sum of two integers that are made of the digits contained in the array.
For example, array: 1 2 7 8 9. The min sum (129 + 78) should be 207
For example, array: 1 2 7 8 9. The min sum (129 + 78) should be 207
ANSWER
Sort the array. The largest numbers should be in the least significant positions, so build up your two integers by alternating from the two arrays.
E.g. 1 3 5 7 8 9 => 1 and 3, then 15 and 37, then 158 and 379. 0 is a special case, if not allowed to use that as a leading digit then have to use it as the second digit.
Try adding two numbers, you would find all that matters is the order of magnitude of a digit and not which of the two numbers that a digit belongs. (e.g. 178+29 = 128+79 = 179+28 = 129+78)
Collections in Java
Iterator interface
| Iterator interface provides the facility of iterating the elements in forward direction only. |
Methods of Iterator interface
There are only three methods in the Iterator interface. They are:
- public boolean hasNext() it returns true if iterator has more elements.
- public object next() it returns the element and moves the cursor pointer to the next element.
- public void remove() it removes the last elements returned by the iterator. It is rarely used.
Nuts & Bolts Problem (Lock & Key problem)
Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts. Match nuts and bolts efficiently.
Constraint: Comparison of a nut to another nut or a bolt to another bolt is not allowed. It means nut can only be compared with bolt and bolt can only be compared with nut to see which one is bigger/smaller.
Other way of asking this problem is, given a box with locks and keys where one lock can be opened by one key in the box. We need to match the pair.
Logic
- first performs a partition by picking last element of bolts array as pivot,
- rearrange the array of nuts and returns the partition index ‘i’ such that all nuts smaller than nuts[i] are on the left side and all nuts greater than nuts[i] are on the right side.
- Next using the nuts[i] we can partition the array of bolts. This operation also makes nuts and bolts array nicely partitioned.
- Now we apply this partitioning recursively on the left and right sub-array of nuts and bolts.
As we apply partitioning on nuts and bolts both so the total time complexity will be Θ(2*nlogn) = Θ(nlogn) on average.
CODE
private static void matchPairs(char[] nuts, char[] bolts, int low, int high) { if (low < high) { // Choose last character of bolts array for nuts partition. int pivot = partition(nuts, low, high, bolts[high]); // Now using the partition of nuts choose that for bolts partition(bolts, low, high, nuts[pivot]); // Recur for [low...pivot-1] & [pivot+1...high] for nuts and bolts array. matchPairs(nuts, bolts, low, pivot-1); matchPairs(nuts, bolts, pivot+1, high); } }Given an array A[] and a number x, check for pair in A[] with sum as x
hasArrayTwoCandidates (A[], ar_size, sum)
1) Sort the array in non-decreasing order.
2) Initialize two index variables to find the candidate elements in the sorted array.
(a) Initialize first to the leftmost index: l = 0
(b) Initialize second the rightmost index: r = ar_size-1
3) Loop while l < r.
(a) If (A[l] + A[r] == sum) then return 1
(b) Else if( A[l] + A[r] < sum ) then l++
(c) Else r--
4) No candidates in whole array - return 0
Search in a row wise and column wise sorted matrix
Given an n x n matrix, where every row and column is sorted in increasing order. Given a number x, how to decide whether this x is in the matrix. The designed algorithm should have linear time complexity.
1) Start with top right element
2) Loop: compare this element e with x
i) if they are equal then return its position
ii) e < x then move it to down (if out of bound of matrix then break return false)
iii) e > x then move it to left (if out of bound of matrix then break return false)
3) repeat the i), ii) and iii) till you find element or returned false
HashMap
If you're only interested in the keys, you can iterate through the keySet() of the map:
Map<String, Object> map = ...;
for (String key : map.keySet()) {
// ...
}
If you only need the values, use values():
for (Object value : map.values()) {
// ...
}
Finally, if you want both the key and value, use entrySet():
for (Map.Entry<String, Object> entry : map.entrySet()) {
String key = entry.getKey();
Object value = entry.getValue();
// ...
}
Learn By Coding 