Minimax (Minmax) Search
Posted on December 18, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Minimax (sometimes minmax) is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case (maximum loss) scenario. Alternatively, it can be thought of as maximizing the minimum gain (maximin). Originally formulated for two-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision making in the presence of uncertainty.
[Read More]Find an element in matrix in which rows and columns are sorted
Posted on December 18, 2011
(Last modified on August 7, 2020)
| 5 minutes
| Kinshuk Chandra
Problem
Given a matrix in which each row and each column is sorted, write a method to find an element in it.
Example
1 4 7 13 2 5 9 15 3 6 10 16 Solution
Here we can have 2 cases -
Case when array is sorted such that last element of nth row is less than first element of n+1 th row Generic case - simply put rows and columns CASE 1 - If last element of each row is less than first element of next row
[Read More]Find first occurrence of a string in another
Posted on October 9, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem: Typical question for indexOf operation. Given two strings s1 and s2, find the first index of s2 in s1 in an efficient manner.
Solution: The problem has very typical solution, starting with each character in the source string start looking if the string being searched for, exists or not. However, the implementations may differ on the way they optimize. One good approach is to first look for the starting character of the string being searched for, in the string being searched.
[Read More]Row consisting max continuous chain of 1’s in an n * n grid
Posted on October 9, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem: Given an n * n grid consisting of only ZEROs and ONEs, such that if in a row a ZERO is present all elements to the right of it will be ZEROs. Thus, a row can start with ONEs and end in only ZEROs, there cannot be a mix and match. You need to find the row with maximum ONEs in a given row. For example in the grid below,
[Read More]Convert a Number (unknown base) to a Base 10 Number
Posted on October 9, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem Given an integer, write a program that converts the given number to a number (in base 10). The base of the given number is unknown.
Solution The problem statement states that the base of the given number is unknown. Thus to proceed one must need to assume a base for the number. It is practically safe to assume that the digit with the maximum value in the number denotes the maximum that can be accounted in the unknown base.
[Read More]Majority element in the array
Posted on October 9, 2011
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Majority Element: A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).
Problem: Given an array consisting of N integers, find the number with the maximum occurrences, i.e. majority element, given the assumption that the number occurs more than N/2 times in the array.
Example
I/P : 3 3 4 2 4 4 2 4 4
[Read More]encodeURIComponent and decodeURIComponent in Java
Posted on October 9, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
A very common task when working with Webservices, is to encode/decode specific URI components, and for there is no direct API in Java for the same, it gets a difficult. Below is the code piece that I have been using for quite some time now.
public static final String ALLOWED\_CHARS = "abcdefghijklmnopqrstuvwxyz"+ “ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-_.!~*'()";
public static String encodeURIComponent(String input) {
if(StringUtils.isEmpty(input)) {
return input;
}
int l = input.length();
StringBuilder o = new StringBuilder(l * 3);
[Read More]atoi() in Java
Posted on October 9, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem: Write a function to convert an ASCII string to integer, similar to atoi() function of C++.
Solution: The solution is too simple, it’s simple checks for erroneous inputs that makes writing such a function fun.
public class AsciiToInteger { public static void main(String\[\] args) { AsciiToInteger instance \= new AsciiToInteger(); int x \= instance.atoi("-683"); System.out.println("Conversion is: " + x); } private int atoi(String number) { // check for NULL or empty if(number \=\= null || number.
[Read More]In-Place Character Array Compression
Posted on October 9, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem: Given a character stream as an array, compress the characters in place appending the number of continuous characters by the numerical value and then the character. The array is terminated by a 0x00 character.
Solution: Another classic interview problem which tests multiple skills in a single problem, namely,
Conversion from integer to ascii - the number returned is a integral value which needs to be converted to ascii and then put in place in stream Skills with pointers (not the real pointers) when operating on an array The following JAVA code illustrates how to work up the given problem.
[Read More]itoa() in Java
Posted on October 9, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem: Write a function to convert an integer value to its ASCII equivalent and return as a character array, similar to itoa() function of C++.
Solution: The solution may seem tricky at first because the array is constructed left-to-right, whereas the number is read right-to-left. The easiest approach is to construct an array with digits from right-to-left and then reverse the array itself. The result being the number representation in character array.
[Read More]