OpenText interview question
1.Implement queue using two stack (famous interview question)
2.find the anagrams maximum count {"aab", "baa","aba","abc"} that he was asking me to order of n. I have suggested different algo like Trie ,wordMap ,etc but he asked me to algo in o(n) ,i don't think so possible .if somebody know in o(n) share the code with me.
3.given array {10,20,12,10,18,2} etc find the sum of two element 20.
4.find the given no in binary tree ---my answer is level order traversal ..but he doesn't understand he want different solution.
5.continous data stream find the given word ...i have suggested maximum heap implementation and trie
Interview Answers
if Interviewer doesn't know the things they should use laptop or prepare some cheat sheet to understand the other approach.
For 5 th question u have to use filter from stream API ---java 8 feature
For question 2---below solution time O(1)
import java.io.*;
import java.util.*;
public class CountAnagrams{
final static int MAX_CHAR = 256
// Function to find if two strings are equal
static boolean isCountZero(int[] count)
{
for (int i = 0; i < MAX_CHAR; i++)
if (count[i] != 0)
return false;
return true;
}
static int countAnagrams(String text, String word)
{
int N = text.length();
int n = word.length();
// Check for first window. The idea is to
// use single count array to match counts
int[] count = new int[MAX_CHAR];
for (int i = 0; i < n; i++)
count[word.charAt(i)]++;
for (int i = 0; i < n; i++)
count[text.charAt(i)]--;
// If first window itself is anagram
int res = 0;
if (isCountZero(count))
res++;
for (int i = n; i < N; i++) {
// Add last character of current
// window
count[text.charAt(i)]--;
// Remove first character of previous
// window.
count[text.charAt(i - n)]++;
// If count array is 0, we found an
// anagram.
if (isCountZero(count))
res++;
}
return res;
}
// Driver code
public static void main(String args[])
{
String text = "forxxorfxdofr";
String word = "for";
System.out.print(countAnagrams(text, word));
}
}