Find first occurrence of a string in another

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. If found, then go ahead and look for other matches character...

Read More

Row consisting max continuous chain of 1’s in an n * n grid

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, 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 0In the example above, row 4 has the maximum continuous chain of ONEs. Solution: One’s first guess would be to crawl through each row, finding...

Read More

Convert a Number (unknown base) to a Base 10 Number

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. This a number if stated as, 254, it can be assumed that the number system consists of digits 0, 1, 2, 3,...

Read More

Majority element in the array

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 O/P : 4 I/P : 3 3 4 2 4 4 2 4 O/P : NONE METHOD 1 (Basic) The basic solution is to have two loops and keep track of maximum count for all different elements....

Read More

encodeURIComponent and decodeURIComponent in Java

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...

Read More

atoi() in Java

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.trim().length() == 0) { throw...

Read More

In-Place Character Array Compression

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...

Read More

itoa() in Java

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. The other point to note which most of the folks miss is to check for negative numbers....

Read More

Trie Operations Complexity

Now that we've seen the basic operations on how to work with a TRIE, we shall now see the space and time complexities in order to get a real feel of how good a TRIE data structure is. Lets take the two important operations INSERT and SEARCH to measure the complexity. INSERT operation first. Lets always take into account the worst case timing first and later convince ourselves of the practical timings. For every Node in the TRIE we had something called as Collection where the Collection can be either a Set or a List. If we choose Set, the...

Read More

Trie : Searching in Trie

In the previous section we saw how to insert string into TRIE. In this section, we shall see how to perform a search in the TRIE when a string or key is passed. Consider the following TRIE as usual. The search alogirthm involves the following steps For each character in the string, see if there is a child node with that character as the content. If that character does not exist, return false If that character exist, repeat step 1. Do the...

Read More

Trie : Inserting in Trie

In this section we shall see how the insert() method on the TRIE data structure works. We shall take a specific case and analyze it with pictorial representation. Before we begin, assume we already have an existing TRIE as shown below. Lets see the steps on how to insert a word "bate". Any insertion would ideally be following the below algorithm. If the input string length is zero, then set the marker for the root node to be true. If the...

Read More

Implementing the TRIE ADT in java

We already saw the Node structure of the TRIE ADT had a content (char), a marker (boolean) and collection of child nodes (Collection of Node). It now has one more method called as subNode(char). This method takes a character as argument would return the child node of that character type should that be present. Node.java package com.vaani.ds.trie; import java.util.Collection; import java.util.LinkedList; /** * @author kc */ public class Node { char content; boolean marker; Collection<Node> child; public Node(char...

Read More

Trie ADT

TRIE is an interesting data-structure used mainly for manipulating with Words in a language. This word is got from the word retrieve. TRIE (pronounced as 'try') has a wide variety of applications in Spell checking Data compression Computational biology Routing table for IP addresses Storing/Querying XML documents etc., We shall see how to construct a basic TRIE data structure in Java. The main abstract methods of the TRIE ADT are, public void...

Read More

Four People on a Rickety Bridge

Problem :  Four people need to cross a rickety bridge at night. Unfortunately, they have only one torch and the bridge is too dangerous to cross without one. The bridge is only strong enough to support two people at a time. Not all people take the same time to cross the bridge. Times for each person:  1 min, 2 mins, 7 mins and 10 mins. What is the shortest time needed for all four of them to cross the bridge?   Solution :  The...

Read More

Globe Walker

Problem : How many points are there on the globe where, by walking one mile south, then one mile east and then one mile north, you would reach the place where you started? Solution :  The trivial answer to this question is one point, namely, the North Pole. But if you think that answer should suffice, you might want to think again! Let’s think this through methodically. If we consider the southern hemisphere, there is a ring...

Read More

Trains and Birds

Problem : A train leaves City X for City Y at 15 mph. At the very same time, a train leaves City Y for City X at 20 mph on the same track. At the same moment, a bird leaves the City X train station and flies towards the City Y train station at 25 mph. When the bird reaches the train from City Y, it immediately reverses direction. It then continues to fly at the same speed towards the train from City X, when it reverses its direction again,...

Read More