Dev
BAN USER- 0of 0 votes
AnswersDesign a data cache.
- Dev in United States
Given two arrays which represent numbers. Write a function to add them.| Report Duplicate | Flag | PURGE
Google Software Engineer in Test - 1of 1 vote
AnswersGiven a set of non overlapping intervals
- Dev in United States
Example 1 :(1,4) (6,10) (14, 19) and another interval (13, 17) merge them as (1,4) (6,10) (13,19)
Example 2: (1,5) (6, 15) (20, 21) (23, 26) (27, 30) (35, 40)
New interval (14, 33)
Output should be
(1,5) (6, 33) (35, 40)
This is because the new interval overlaps with (6, 15) (20, 21) (23, 26) (27, 30)| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Algorithm
I did it when I coded on the paper, but forgot here... there is an interesting way to achieve that if you see, I added that to the code.
Thanks for pointing it out.
Here is the list of test cases I used in the interview
null(null string)
""(Empty String)
-
Integer.MAX_VALUE
Integer.MIN_VALUE
123,234,677
-100
100
02324
12345.9812
12a3
public long stringToInt(String s) throws Exception
{
if(s == null)
throw new Exception("Null values for entered input");
else
{
int isNegative = 1;
if(s.charAt(0) == '-')
{
s.substring(1);
isNegative = -1;
}
if(s.length() == 0)
throw new Exception("Unrecognized string");
else
{
long result = 0;
for(int i = 0; i < s.length(); i++)
{
int value = s.charAt(i) - '0';
if(value < 0 || value > 9)
throw new Exception("Unrecognized string");
result = result * 10;
if(result > Integer.MAX_VALUE - value)
throw new Exception("Integer Overflow");
result += value;
}
return isNegative * result;
}
}
}
Step 1. 5 people can sit around a circular table in 4! ways
Step2. Consider these two poeple as one unit so 3 people + 1 Couple can sit around a round table in 3! ways
Step3. But the couple can exchange seats in 2 ways. MH or HM
So the total probability is 2. 3! / 4! = 1/2 = 50% chance
Returns the whole list of common substrings in the given two strings...
public Set<String> getLCS(String s1, String s2)
{
if(s1 == null || s2 == null)
return null;
int len1 = s1.length(), len2 = s2.length();
int[][] array = new int[len1 + 1][len2 + 1];
int longest = 0;
Set<String> substrings = new TreeSet<String>();
for(int i = 0; i < len1; i++)
{
for(int j = 0; j < len2; j++)
{
if(s1.charAt(i) == s2.charAt(j))
{
int v = array[i][j] + 1;
array[i + 1][j + 1] = v;
if(v > longest)
{
longest = v;
}
if( v == longest)
{
substrings.add(s1.substring(i - v + 1, i + 1));
}
}
}
}
return substrings;
}
There is a paper on this, if you are interested you can read
- But the basic idea is to construct only the K heaps at a time, and find k largest sums from these heaps using a heap selection algorithm.
- Then all the heaps are deleted except the last one. And this last one is used to generate the next set of K heaps.
- Repeat the above two steps till you find out all the k sets.
Node leastCommonAncestor(Node root, Node left, Node right)
{
if(root == null || p == null || q == null)
return null;
if(p == root || q == root)
return root;
Node left = LCA(root.left, p, q);
Node right = LCA(root.right, p, q);
if(left != null && right != null) return root;
else
return left != null ? left : right;
}
Using Two Stacks is the answer
public static void printZigZag(BTNode root, boolean leftToRight)
{
Stack<BTNode> currentStack, nextStack;
currentStack = new Stack<BTNode>();
nextStack = new Stack<BTNode>();
if(root == null)
return;
currentStack.push(root);
while(!currentStack.isEmpty())
{
BTNode node = currentStack.pop();
System.out.println(node.data);
if(leftToRight)
{
if(node.right != null)
nextStack.push(node.right);
if(node.left != null)
nextStack.push(node.left);
}
else
{
if(node.left != null)
nextStack.push(node.left);
if(node.right != null)
nextStack.push(node.right);
}
if(currentStack.isEmpty())
{
leftToRight = !leftToRight;
Stack<BTNode> temp;
temp = currentStack;
currentStack = nextStack;
nextStack = temp;
}
}
}
First Non Repeating Character:-
Stores the sequence in a Queue and hashmap to store the count.
If you want the last non repeating character replace the Queue with a Stack :)
public Character firstNonRepeating(String s)
{
char[] strChars = s.toCharArray();
HashMap<Character, Integer> charMap = new HashMap<Character, Integer>();
Queue<Character> strQueue = new LinkedList<Character>();
for(int i = 0; i < strChars.length; i++)
{
if(charMap.containsKey(strChars[i]))
{
charMap.put(strChars[i], charMap.get(strChars[i]) + 1);
}
else
{
charMap.put(strChars[i], 1);
strQueue.add(strChars[i]);
}
}
while(!strQueue.isEmpty())
{
char firstUnique = strQueue.poll();
if(charMap.get(firstUnique) == 1)
{
return firstUnique;
}
}
return null;
}
Works with all the test cases that were provided in the comments, code is in JAVA
public int nextHigherWithSameDigits(int number)
{
char[] digits = String.valueOf(number).toCharArray();
int length = digits.length;
int i;
for(i = length - 1; i > 0; i--)
{
if(digits[i-1] < digits[i])
{
break;
}
}
if(i > 0)
{
char minChar = digits[length -1];
int position = length - 1;;
for(int k = length - 2; k >= i; k--)
{
if(minChar > digits[k] || minChar < digits[i-1])
{
minChar = digits[k];
position = k;
}
}
char temp = digits[position];
digits[position] = digits[i-1];
digits[i-1] = temp;
char[] subDigits = new char[digits.length - i];
int j = 0;
for(int index = i; index < length; index++)
{
subDigits[j++] = digits[index];
}
Arrays.sort(subDigits);
j = 0;
for(int index = i; index < length; index++)
{
digits[index] = subDigits[j++];
}
number = Integer.parseInt(new String(digits));
}
return number;
}
Instead of storing the values straight away create an object with something like
class Data
{
int number;
int maxValue;
}
Queue<Data> q = new LinkedList<Data>();
Every time you store your values, store it as this Data object
so
enqueue(int value)
{
Data data = new Data();
data.number = value;
if(data.maxValue < value)
data.maxValue = value;
}
What this does is it stores the findMax at each point of the data insertion, so you can access the maximum data at each point looking at the top of the queue.
I believe we have to do a Radix Sort O(n) after the elements are deleted,and also compare the absolute values instead of comparing them directly that way we delete large negative numbers also.
I tired this and it worked. But did not use the Radix Sort in my code, went with a more easy O(n log n) sorting algorithm and here is the code, if anyone is interested
public int findSmallestPositiveMissing(int[] array)
{
int left = 0;
int right = array.length - 1;
while(left < right)
{
if(Math.abs(array[left]) > array.length)
{
int temp = array[left];
array[left] = array[right];
array[right] = temp;
right--;
}
left++;
}
Arrays.sort(array);
for(int i = 1; i < array[right]; i++)
{
if(Arrays.binarySearch(array, i) < 0)
{
return i;
}
}
return array[right] + 1;
}
Here is the code for the algorithm I discussed:-
private static BTNode closestLookup(BTNode node, double data)
{
double currDiff = Integer.MAX_VALUE, prevDiff = Integer.MAX_VALUE;
BTNode closest = null;
while(node != null)
{
currDiff = node.data - data;
if(Math.abs(currDiff) < prevDiff)
{
prevDiff = Math.abs(currDiff);
closest = node;
}
if(node.data == data)
{
break;
}
else
{
if(data < node.data)
{
node = node.left;
}
else
{
node = node.right;
}
}
}
return closest;
}
1. Keep two variables currDiff = Integer.MAX_VALUE and prevDiff = Integer.MAX_VALUE
2. Do BST,
but at each node do currDiff = node.value - key
if(Math.abs(currDiff) < prevDiff)
{
prevDiff = Math.abs(currDiff);
closest = node.value;
}
At the end return closest;
If the value is zero it is going to find that element, if not the closest one.
- Interfaces are used for writing extensible code, when you modify an implementation of an interface, you ensure that this change will not effect the system because only the implementation has changed but not the contract, so when you really need to modify the implementations without really affecting how the application uses it, you use interfaces.
- And usually it is a good practice to write interfaces because they also help you in Mocking and unit testing of your code.
- It is also a good practice to ensure that you set the implementations of interfaces in your application using setter methods because that ensures more ways to mock your objects and helps in loose coupling.
Repemilinarula, Dev Lead at ABC TECH SUPPORT
Hi, i've been spotting for about 4 years.Teamwork: works well as a member of a team, pitches in ...
Added more info to the question, hope it helps.
- Dev March 12, 2012