randomCoder1988
BAN USER- 0of 2 votes
AnswersAdd a third dimension of time to a hashmap , so ur hashmap will look something like this - HashMap<K, t, V> where t is a float value. Implement the get and put methods to this map. The get method should be something like - map.get(K,t) which should give us the value. If t does not exists then map should return the closest t' such that t' is smaller than t. For example, if map contains (K,1,V1) and (K,2,V2) and the user does a get(k,1.5) then the output should be v1 as 1 is the next smallest number to 1.5
- randomCoder1988 in United States for Mobile| Report Duplicate | Flag | PURGE
Uber Software Engineer - 0of 0 votes
AnswerDesign a ride sharing application
- randomCoder1988 in United States| Report Duplicate | Flag | PURGE
Uber Software Engineer
My take on this, I assume all words are of same length which is given in the question as k and contain characters from 1 to 256 in ASCII
1. Iterate over the array going through each word. - O(n)
2. For each word make a bitmap using the character set from ASCII - O(k)
3. Store the bitmap created as the key of a HashMap. (If you want, you can store the index of the word as value)
4. While iterating over the next elements , if you find the calculated bit map as a key, then you have found a pair.
Creating the bit map for each word will be O(k) operation and pushing and getting from the HasMap will be O(1) so the total time complexity will come to O(nk).
its a singly linked list in the question
- randomCoder1988 April 26, 2015Java solution --> The main idea is that if we find the next node of the current node, then the next of the last children of current node should be the first next children found. the while loop for next takes care of this. Please comment if you find any issues -
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.LinkedList;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
Node node = new Node(20);
node.left = new Node(9);
node.right = new Node(49);
node.left.right = new Node(12);
node.left.left = new Node(5);
//node.left.right.right = new Node(15);
node.right.right = new Node(52);
node.right.left = new Node(23);
// node.right.right.left = new Node(50);
print(makeLink(node));
}
public static void print(Node node){
if(node == null) return;
System.out.println("node.data " + node.data + " node.next " + node.next + "->");
print(node.left);
print(node.right);
}
public static Node makeLink(Node root){
Queue<Node> q = new LinkedList<Node>();
q.add(root);
while(!q.isEmpty()){
Node node = q.remove();
System.out.println("node data " + node.data);
Node tmp = node.next;
if(tmp != null){
if(node.right == null && node.left != null){
while(tmp != null){
if(tmp.left!=null){
node.left.next = tmp.left;
break;
}else if(tmp.right != null){
node.left.next = tmp.right;
break;
}else {
tmp = tmp.next;
}
}
} else if(node.right != null){
while(tmp != null){
if(tmp.left!=null){
node.right.next = tmp.left;
break;
}else if(tmp.right != null){
node.right.next = tmp.right;
break;
}else {
tmp = tmp.next;
}
}
}
}
if(node.left != null && node.right != null){
node.left.next = node.right;
q.add(node.left);
q.add(node.right);
} else if(node.left != null){
q.add(node.left);
} else if(node.right != null){
q.add(node.right);
}
}
return root;
}
}
class Node{
int data;
Node left;
Node right;
Node next;
public Node(int data){
this.data = data;
}
}
This gives the correct output but can be made neater, will appreciate if someone can help fix the number of recursive calls made -
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
static Set<String> resultStrings = new HashSet<String>();
public static void main (String[] args) throws java.lang.Exception
{
System.out.println(permuteSetOfString("fox", "red", "super"));
}
public static Set<String> permuteSetOfString(String a, String b, String c){
char first = a.charAt(0);
if(a.length() > 1){
permuteSetOfString(a.substring(1),b,c);
}
char second = b.charAt(0);
if(b.length() > 1){
permuteSetOfString(a,b.substring(1),c);
}
char third = c.charAt(0);
if(c.length() > 1){
permuteSetOfString(a,b,c.substring(1));
}
String result = first + "" + second + "" + third + "";
resultStrings.add(result);
return resultStrings;
}
}
O(n) time and space complexity
- randomCoder1988 April 09, 2015/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
Map<String, String> map = new HashMap<String, String>();
map.put("A", "C");
map.put("B", "C");
map.put("C", "F");
map.put("D", "E");
map.put("E", "F");
map.put("F", "F");
System.out.println(getEmployees(map));
}
public static Map<String, Integer> getEmployees(Map<String, String> map){
Map<String, Integer> resultMap = new TreeMap<String, Integer>();
Iterator<String> it = map.keySet().iterator();
while(it.hasNext()){
String key = it.next();
String value = map.get(key);
if(key != value){
if(!resultMap.containsKey(value)){
resultMap.put(value, 1);
}else{
resultMap.put(value, resultMap.get(value) + 1);
}
if(resultMap.containsKey(key)){
//if key already has some count, we can add those to the value's count
resultMap.put(value, resultMap.get(value) + resultMap.get(key));
}
}
}
Iterator<String> it1 = map.keySet().iterator();
// to add the remaining employees whom no one reports to
while(it1.hasNext()){
String key = it1.next();
if(!resultMap.containsKey(key)){
resultMap.put(key, 0);
}
}
return resultMap;
}
}
If spaces can be considered to mark end and start for words --
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
System.out.println("reverse of i am will - " + reverseWords("i am will"));
}
public static String reverseWords(String str){
String newString = "";
String arr[] = str.split(" ");
for(int i = arr.length-1; i >= 0; i--){
newString = newString + " " + arr[i];
}
return newString;
}
}
we don't need to append another copy of the list to apply binarySearch. Look at my code in the answers.
- randomCoder1988 April 08, 2015/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int arr[] = {4,5,6,1,2,3};
System.out.println(modifiedBinarySearch(arr, 5, 0, arr.length -1 ));
System.out.println(modifiedBinarySearch(arr, 2, 0, arr.length -1 ));
System.out.println(modifiedBinarySearch(arr, -1, 0, arr.length -1 ));
}
public static boolean modifiedBinarySearch(int arr[], int val, int low, int high){
if(low > high)
return false;
int mid = (low + high) / 2;
if(arr[mid] == val)
return true;
else{
if(arr[low]<arr[mid] && val < arr[mid] && val > arr[low]){
return modifiedBinarySearch(arr, val, low, mid);
}else{
return modifiedBinarySearch(arr, val, mid+1, high);
}
}
}
}
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
TwoSumImpl obj = new TwoSumImpl();
obj.store(1);
obj.store(-2);
obj.store(3);
obj.store(6);
System.out.println("test val " + 4 + " result " + obj.test(4));
System.out.println("test val " + -1 + " result " + obj.test(-1));
System.out.println("test val " + 9 + " result " + obj.test(9));
System.out.println("test val " + 10 + " result " + obj.test(10));
System.out.println("test val " + 5 + " result " + obj.test(5));
System.out.println("test val " + 0 + " result " + obj.test(0));
}
}
interface TwoSum {
/**
* Stores @param input in an internal data structure.
*/
void store(int input);
/**
* Returns true if there is any pair of numbers in the internal data structure which
* have sum @param val, and false otherwise.
* For example, if the numbers 1, -2, 3, and 6 had been stored,
* the method should return true for 4, -1, and 9, but false for 10, 5, and 0
*/
boolean test(int val);
}
class TwoSumImpl implements TwoSum{
ArrayList<Integer> list = new ArrayList<Integer>();
public void store(int input){
list.add(input);
}
public boolean test(int val){
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(Integer input: list){
map.put(input, 1);
}
for(Integer input: list){
if(map.containsKey(val - input))
return true;
}
return false;
}
}
*. makes no sense in a practical pattern matching scenario
- randomCoder1988 April 08, 2015Java solution to recursively check for each character in the pattern and string.
- randomCoder1988 April 08, 2015/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
System.out.println("Match " + stringMatching("abcddd", "abcd*"));
System.out.println("Match " + stringMatching("ccca", "c*a"));
System.out.println("Match " + stringMatching("ab", ".*"));
System.out.println("Match " + stringMatching("abcdefg", "a*c..f*"));
}
public static boolean stringMatching(String string, String pattern){
System.out.println("String " + string + " pattern " + pattern);
if(pattern == null || pattern.length() == 0 || (pattern.equals("*") && string!=null) || (pattern.equals(".") && string.length() == 1) || pattern.equals(string)){
return true;
}
char firstOfPattern = pattern.charAt(0);
char[] strArray = string.toCharArray();
if(firstOfPattern!='*' && firstOfPattern != '.'){
if(firstOfPattern == strArray[0]){
return stringMatching(string.substring(1), pattern.substring(1));
}
else{
return false;
}
}
else if(firstOfPattern == '.'){
return stringMatching(string.substring(1), pattern.substring(1));
}
else if(firstOfPattern == '*' && pattern.length()>1){
char secondOfPattern = pattern.charAt(1);
int i = 0;
while(strArray[i] != secondOfPattern){
i++;
}
if(i >= strArray.length)
return false;
else{
return stringMatching(string.substring(i+1), pattern.substring(2));
}
}
return false;
}
}
This will work only for words with all unique characters. My bad.
- randomCoder1988 May 18, 2015