nitinguptaiit
BAN USER- 1of 3 votes
AnswersQuestion: Can you break the given string into words, provided by a given hashmap of frequency of word as <word: n>
- nitinguptaiit in United States
Example:
HashMap -> {"abc":3, "ab":2, "abca":1}
String: abcabcabcabca
output: Yes; [ abc, abc, abc , abca ]
Example:
HashMap -> {"abc":3, "ab":2}
String: abcabab
output: No
Example:
HashMap -> {"abc":3, "ab":2, "abca":1}
String: abcx
output: No| Report Duplicate | Flag | PURGE
Facebook Algorithm - 1of 1 vote
AnswersGiven array of integer, count number of distinct sub array such that it has at most k odd elements and two sub array differ if only when they have at least one member differ.
Example:
{3, 2, 3, 4}, k = 1;
output; 7
[ [3], [2], [4], [3,2], [2,3], [2,3,4],[3,4] ]; Note we did not count [3,2,3] since it has more than k odd elements.
Example 2:
{6, 3, 5, 8}, k = 1;
[ [6], [3], [5], [8] , [6,3], [5,8] ] = 6
We did not count [3,5] as it has > k odd elements
Example 2:
{2, 2, 5, 6, 9, 2, 11, 9, 2, 11, 12}
There are these many arrays ;
[2], [2] , [5], [6], [9] , [2], [11], [9], [2], [11], [12]
[2, 2] , [2, 5] , [5, 6] , [6, 9] , [9, 2] , [2, 11] , [11, 9] , [11, 12] , [2, 2, 5] , [2, 5, 6] , [5, 6, 9] , [6, 9, 2] , [9, 2, 11] , [2, 11, 9] , [11, 9, 2] , [2, 11, 12] , [2, 2, 5, 6] , [2, 5, 6, 9] , [5, 6, 9, 2] , [6, 9, 2, 11] , [9, 2, 11, 9] , [2, 11, 9, 2] , [11, 9, 2, 11] , [9, 2, 11, 12] , [2, 2, 5, 6, 9] , [2, 5, 6, 9, 2] , [5, 6, 9, 2, 11] , [6, 9, 2, 11, 9] , [9, 2, 11, 9, 2] , [2, 11, 9, 2, 11] , [11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2] , [2, 5, 6, 9, 2, 11] , [5, 6, 9, 2, 11, 9] , [6, 9, 2, 11, 9, 2] , [9, 2, 11, 9, 2, 11] , [2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11] , [2, 5, 6, 9, 2, 11, 9] , [5, 6, 9, 2, 11, 9, 2] , [6, 9, 2, 11, 9, 2, 11] , [9, 2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11, 9] , [2, 5, 6, 9, 2, 11, 9, 2] , [5, 6, 9, 2, 11, 9, 2, 11] , [6, 9, 2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11, 9, 2] , [2, 5, 6, 9, 2, 11, 9, 2, 11] , [5, 6, 9, 2, 11, 9, 2, 11, 12] , [2, 2, 5, 6, 9, 2, 11, 9, 2, 11] , [2, 5, 6, 9, 2, 11, 9, 2, 11, 12]
But only 18 get qualified as there are duplicates like [9, 2, 11] etc.
Qualified arrays are
[2] , [5], [6], [9] , [11], [12] , [2, 2] , [2, 5] , [5, 6] , [6, 9] , [9, 2] , [2, 11] , [11, 12] , [2, 2, 5] , [2, 5, 6] , [6, 9, 2] , [2, 11, 12] , [2, 2, 5, 6]
MY finding so far;
we can use sliding window technique, such that we start counting all sub array of len = 1 to n such that each sub array are different and have at most k odd elements
Here is the code, that i've written for this approach O(n^2)static int subArraysBrute(int arr[], int k) { int count = 0; Set<Integer> set = new HashSet<>(); //Count single length for (int i = 0; i < arr.length; i++) { count += set.contains(arr[i]) ? 0 : 1; set.add(arr[i]); } int len = 2; int odd; Set<List<Integer>> setArray = new HashSet<>(); while (len < arr.length) { setArray.clear(); for (int i = 0; i < arr.length - len + 1; i++) { int j = i + len - 1; odd = 0; List<Integer> ar = new ArrayList<>(); for (int x = i; x <= j; x++) { if (arr[x] % 2 != 0) odd++; ar.add(arr[x]); } if (!setArray.contains(ar)) { if (odd <= k) { count++; System.out.print(ar + " , "); } } setArray.add(ar); } len++; } return count; }
Other findings;
- nitinguptaiit in United States
1. We can't sort the array, as they will ruin the subarray property
2. We can't use simple sliding technique as they will mis so many sub arrays ( moving from left to right window) - I've tried this, this fails like any thing;
Probably, in second idea (sliding window), can be improve further such that once we counted sub arrays, we can run one more time and count those sub array which are left out.| Report Duplicate | Flag | PURGE
Uber SDE-2 Algorithm - 0of 0 votes
AnswersCount number of possible rhythm in a poem.
- nitinguptaiit in India
Explanation:
Twinkle, twinkle, little star, [ A ]
How I wonder what you are! [A]
Up above the world so high, [B]
Like a diamond in the sky. [B]
In the above poem, we see the first two line ( ending with "star" and "are" ) is in the rhythm that's why they are given as character "A" and similarly last two lines (ending with "high" and "sky" ] s in the rhythm that's why they are given as character "B".
Questions: Given "n" number of lines in a poem, Count number of possible rhythm in a poem.
P.S. output should be in lexicographical order only
Example:
n=1
only one possible "A"
Answer: A, count =1
n=2 [ possible chars are A,B]
AA
AB
BA <- This is not possible as it collide with AB. How? Look at the pattern
AB says first line has different rhythm and second line has different rhythm then first line.
Similarly BA is also shows the same ; first line has different rhythm and second line has different rhythm then first line.
Hence discard
n=2
AA
AB , count=2
n=3 [ possible chars are A,B, C]
AAA
AAB
ABA
ABB
ABC, count=5
Look we can't have AAC as it collide with AAB (first two are same and last is different in both)
Similarly other BCA/ BAC etc we'll discard them because of collide and lexicographical ordering.
n=4, there will be 15 [ we need to print all of them too ]
My Finding;
1. I found out that, this is just a bell number ( see the pattern 1,2,5,15.... )
2. I found, this is Dynamic programming question, we can generate the next n+1 from n; How
n=2 has
AA
AB
n=3
Take AA; there are three possiblilties to append a character is A,B,C
But since the last character is A; so lexicographically A and B can be appended at the most, since appending C could conflict with B.
AA(A)
AA(B)
Take AB; there are three possibilities to append a character is A,B,C
But since the last character is B; which is lexicographically smaller than A, so lexicographically A, B,C can be appended easily,
AB(A)
AB(B)
AB(C) <- this is possible since its not colliding with any thing
So ans; 5
AA(A)
AA(B)
AB(A)
AB(B)
AB(C)
Now lets try n=4 [ now its become complicated ;A,B,C,D]
Take AAA; possibilty A,B, not possible C/D conflict with B
AAA(A)
AAA(B)
Take AAB, Possibility is A, B C but what about D; is it possible ? Yes/No
AAB(A)
AAB(B)
AAB(C)
AAB(D) <- it collide with last C so discard ;
Hence with AAB
AAB(A)
AAB(B)
AAB(C)
Take ;
ABA(A)
ABA(B)
ABA(C)
ABA(D) Not possible ; collide with C
If you observe there is a pattern with last character to first character from right to left;
Solution: Brute force is obvious solution; and generating number is also fine since you can use Bell number [ i was not able to come up with this solution though, found later]
Any one can help me over here?| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm
Here is the solution using trie
public class PairOfPalindrome {
static class ResultHelper {
public int index1, index2;
public ResultHelper(int index1, int index2) {
this.index1 = index1;
this.index2 = index2;
}
@Override
public String toString() {
return "{" +
"index1=" + index1 +
", index2=" + index2 +
'}';
}
}
static class TrieNode {
public boolean isLeaf = false;
public Map<Character, TrieNode> children = new HashMap<>();
public List<Integer> palindromsWithinString = new ArrayList<>();
public int idOfThisString = -1;
}
static class Trie {
TrieNode root;
void insert(String toInsert, int myId) {
if (root == null)
root = new TrieNode();
TrieNode pCrawl = root;
for (int i = toInsert.length() - 1; i >= 0; i--) {
char currentChar = toInsert.charAt(i);
if (!pCrawl.children.containsKey(currentChar))
pCrawl.children.put(currentChar, new TrieNode());
if (isPalindrome(toInsert, 0, i))
pCrawl.palindromsWithinString.add(myId);
pCrawl = pCrawl.children.get(currentChar);
}
pCrawl.isLeaf = true;
pCrawl.idOfThisString = myId;
}
private boolean isPalindrome(String toInsert, int from, int to) {
while (from < to && toInsert.charAt(from) == toInsert.charAt(to)) {
from++;
to--;
}
if (from == to)
return true;
return false;
}
public List<ResultHelper> search(String toSearch, int myId) {
List<ResultHelper> resultHelpers = new ArrayList<>();
if (search(toSearch, myId, resultHelpers))
return resultHelpers;
else
return Collections.EMPTY_LIST;
}
private boolean search(String toSearch, int myId, List<ResultHelper> resultHelpers) {
if (null == root)
return false;
TrieNode pCrawl = root;
for (int i = 0; i < toSearch.length(); i++) {
char currentChar = toSearch.charAt(i);
if (!pCrawl.children.containsKey(currentChar))
return false;
pCrawl = pCrawl.children.get(currentChar);
if (pCrawl.idOfThisString >= 0 && pCrawl.idOfThisString != myId
&& isPalindrome(toSearch, i, toSearch.length() - 1)) {
resultHelpers.add(new ResultHelper(myId, pCrawl.idOfThisString));
}
}
for (int rem : pCrawl.palindromsWithinString) {
resultHelpers.add(new ResultHelper(myId, rem));
}
return true;
}
}
public static void main(String args[]) {
String[] list = {"abc", "xyxcba", "geekst", "or", "keeg", "bc"};
Trie trie = new Trie();
for (int i = 0; i < list.length; i++)
trie.insert(list[i], i);
for (int i = 0; i < list.length; i++) {
List<ResultHelper> result = trie.search(list[i], i);
if (!result.isEmpty())
System.out.println(result);
}
}
}
test
This is very easy to understand; and has performance boost if one of the list size is >>> then other
- nitinguptaiit April 02, 2019public class InterleavedList {
static class Helper {
public int listIndex = 0;
public int selfIndex = 0;
public Helper(int listIndex) {
this.listIndex = listIndex;
}
@Override
public String toString() {
return "{" +
"listIndex=" + listIndex +
", selfIndex=" + selfIndex +
'}';
}
}
public static void main(String args[]) {
List<List<Integer>> input = new ArrayList<>();
List<Integer> one = new ArrayList<>();
one.add(1);
one.add(2);
one.add(3);
List<Integer> two = new ArrayList<>();
two.add(9);
two.add(0);
List<Integer> three = new ArrayList<>();
three.add(5);
List<Integer> four = new ArrayList<>();
four.add(-4);
four.add(-5);
four.add(-2);
four.add(-3);
four.add(-1);
input.add(one);
input.add(two);
input.add(three);
input.add(four);
System.out.println(interleavedList(input));
}
private static List<Helper> getIndexList(int totalLists) {
List<Helper> helpers = new ArrayList<>(totalLists);
for (int i = 0; i < totalLists; i++) {
helpers.add(new Helper(i));
}
return helpers;
}
private static List<Integer> interleavedList(List<List<Integer>> input) {
int totalLists = input.size();
//We use this list to iterate over input
List<Helper> helpers = getIndexList(totalLists);
int x = totalLists;
List<Integer> result = new ArrayList<>();
//We remove all the helper once their corresponding list exhaust
while (true) {
ListIterator<Helper> listIterator = helpers.listIterator();
while (listIterator.hasNext()) {
Helper h = listIterator.next();
//get the inner list by listIndex
List<Integer> inner = input.get(h.listIndex);
if (h.selfIndex < inner.size()) {
result.add(inner.get(h.selfIndex++));
} else {
//If all element traversed, remove it for next iteration
listIterator.remove();
}
}
if (helpers.isEmpty())
break;
}
return result;
}
}
Check my comment below to generate Hash. That will solve ur doubt
- nitinguptaiit April 01, 2019This is typical example of hashing with user defined Hash function.
Just generate a hash based on index and then count distinct string by Hash.
static String encodeString(char[] str) {
// hashEven stores the count of even indexed character
// for each string hashOdd stores the count of odd
// indexed characters for each string
int hashEven[] = new int[MAX_CHAR];
int hashOdd[] = new int[MAX_CHAR];
// creating hash for each string
for (int i = 0; i < str.length; i++) {
char c = str[i];
if ((i & 1) != 0) // If index of current character is odd
hashOdd[c-'a']++;
else
hashEven[c-'a']++;
}
// For every character from 'a' to 'z', we store its
// count at even position followed by a separator,
// followed by count at odd position.
String encoding = "";
for (int i = 0; i < MAX_CHAR; i++) {
encoding += (hashEven[i]);
encoding += ('-');
encoding += (hashOdd[i]);
encoding += ('-');
}
return encoding;
}
A hash function.
Just iterate and convert to hash, put in set if not present then increase count otherwise skip
Here is the Most simplest, very easy to extend up to any numbers (trillion...or any thing u wish).
This take advantage, how we read the number from left to right, here i just port how we read the number in code;
package Java;
import java.text.DecimalFormat;
/**
* Author: Nitin Gupta(nitin.gupta@walmart.com)
* Date: 15/03/19
* Description:
*/
public class ConvertNumberToWords {
private static final String[] tensNames = {
"",
" ten",
" twenty",
" thirty",
" forty",
" fifty",
" sixty",
" seventy",
" eighty",
" ninety"
};
private static final String[] numNames = {
"",
" one",
" two",
" three",
" four",
" five",
" six",
" seven",
" eight",
" nine",
" ten",
" eleven",
" twelve",
" thirteen",
" fourteen",
" fifteen",
" sixteen",
" seventeen",
" eighteen",
" nineteen"
};
private static String convertLessThanOneThousand(int number) {
String soFar;
if (number % 100 < 20) {
soFar = numNames[number % 100];
number /= 100;
} else {
soFar = numNames[number % 10];
number /= 10;
soFar = tensNames[number % 10] + soFar;
number /= 10;
}
if (number == 0) return soFar;
return numNames[number] + " hundred" + soFar;
}
private static String convertLessThanOneThousandWithAnd(int number) {
String soFar;
if (number % 100 < 20) {
soFar = numNames[number % 100];
number /= 100;
} else {
soFar = numNames[number % 10];
number /= 10;
soFar = tensNames[number % 10] + soFar;
number /= 10;
}
if (number == 0) return soFar;
if (!soFar.isEmpty())
return numNames[number] + " hundred and " + soFar;
return numNames[number] + " hundred" + soFar;
}
public static String convert(long number, boolean withoutAnd) {
// 0 to 999 999 999 999
if (number == 0) {
return "zero";
}
// pad with "0"
String mask = "000000000000";
DecimalFormat df = new DecimalFormat(mask);
String snumber = df.format(number);
// XXXnnnnnnnnn
int billions = Integer.parseInt(snumber.substring(0, 3));
// nnnXXXnnnnnn
int millions = Integer.parseInt(snumber.substring(3, 6));
// nnnnnnXXXnnn
int hundredThousands = Integer.parseInt(snumber.substring(6, 9));
// nnnnnnnnnXXX
int thousands = Integer.parseInt(snumber.substring(9, 12));
String tradBillions;
switch (billions) {
case 0:
tradBillions = "";
break;
default:
tradBillions = convertLessThanOneThousand(billions)
+ " billion ";
}
String result = tradBillions;
String tradMillions;
switch (millions) {
case 0:
tradMillions = "";
break;
default:
tradMillions = convertLessThanOneThousand(millions)
+ " million ";
}
result = result + tradMillions;
String tradHundredThousands;
switch (hundredThousands) {
case 0:
tradHundredThousands = "";
break;
case 1:
tradHundredThousands = "one thousand ";
break;
default:
tradHundredThousands = convertLessThanOneThousand(hundredThousands)
+ " thousand ";
}
result = result + tradHundredThousands;
String tradThousand;
if (!withoutAnd)
tradThousand = convertLessThanOneThousandWithAnd(thousands);
else
tradThousand = convertLessThanOneThousand(thousands);
result = result + tradThousand;
// remove extra spaces!
return result.replaceAll("^\\s+", "").replaceAll("\\b\\s{2,}\\b", " ");
}
static String convert(float number) {
String temp = String.valueOf(number);
String v[] = temp.split("\\.");
String left = convert(Long.parseLong(v[0]), true);
String right = convert(Long.parseLong(v[1]), true);
return left + " and " + right;
}
/**
* testing
*
* @param args
*/
public static void main(String[] args) {
System.out.println("*** " + convert(334.32f ));
// System.out.println("*** " + convert(0, true));
// System.out.println("*** " + convert(1, true));
// System.out.println("*** " + convert(16, true));
// System.out.println("*** " + convert(100, true));
// System.out.println("*** " + convert(118, true));
// System.out.println("*** " + convert(200, true));
// System.out.println("*** " + convert(219, true));
// System.out.println("*** " + convert(800, true));
// System.out.println("*** " + convert(801, true));
// System.out.println("*** " + convert(1316, true));
// System.out.println("*** " + convert(1000000, true));
// System.out.println("*** " + convert(2000000, true));
// System.out.println("*** " + convert(3000200, true));
// System.out.println("*** " + convert(700000, true));
// System.out.println("*** " + convert(9000000, true));
// System.out.println("*** " + convert(9001000, true));
// System.out.println("*** " + convert(123456789, true));
// System.out.println("*** " + convert(2147483647, true));
// System.out.println("*** " + convert(3000000010L, true));
/*
*** zero
*** one
*** sixteen
*** one hundred
*** one hundred eighteen
*** two hundred
*** two hundred nineteen
*** eight hundred
*** eight hundred one
*** one thousand three hundred sixteen
*** one million
*** two millions
*** three millions two hundred
*** seven hundred thousand
*** nine millions
*** nine millions one thousand
*** one hundred twenty three millions four hundred
** fifty six thousand seven hundred eighty nine
*** two billion one hundred forty seven millions
** four hundred eighty three thousand six hundred forty seven
*** three billion ten
**/
}
}
Take the hint form this solution;
package facebook;
import java.util.*;
/**
* Author: Nitin Gupta(nitin.gupta@walmart.com)
* Date: 01/04/19
* Description:
*/
public class ContactCleaner {
static class Contact {
String userName;
Set<String> contacts;
boolean isVisited = false;
int index = -1;
public Contact(String name, Set<String> set, int index) {
userName = name;
contacts = new HashSet<>(set);
this.index = index;
}
@Override
public String toString() {
return String.valueOf(index);
}
}
public static void main(String args[]) {
String [][]contacts = {{"John", "john@gmail.com", "john@fb.com"},
{"Dan", "dan@gmail.com", "+1234567"},
{"john123", "5412312", "john123@skype.com"},
{"john1985", "5412312", "john@fb.com"},
{"john19856", "john123@skype.com", "john@fb1.com"},
{"Dan2", "dan123@gmail.com", "+1234567"},{"Dan3", "dan@gmail.com", "+123456712312"},
{"Sandy", "sandy@gmail.com", "+123456712"},{"sandy4", "sandy@fb.com", "sandy@gmail.com"}};
List<Contact> contactList = buildContactList(contacts);
List<Set<Contact>> result = buildContactGraph(contactList);
System.out.println(result);
}
private static List<Set<Contact>> buildContactGraph(List<Contact> contactList) {
Map<String, List<Contact>> map = buildContactMap(contactList);
List<Set<Contact>> result = new ArrayList<>();
for (List<Contact> contacts : map.values()) {
Set<Contact> uniques = null;
for (Contact con : contacts) {
if (!con.isVisited) {
uniques = dfs(map, con, new HashSet<>());
}
}
if (uniques != null)
result.add(uniques);
}
return result;
}
private static Set<Contact> dfs(Map<String, List<Contact>> map, Contact con, Set<Contact> uniques) {
if (!con.isVisited) {
con.isVisited = true;
uniques.add(con);
for (String s : con.contacts) {
List<Contact> contactList = map.get(s);
for (Contact c : contactList) {
if (!c.isVisited) {
dfs(map, c, uniques);
}
}
}
}
return uniques;
}
private static Map<String, List<Contact>> buildContactMap(List<Contact> contactList) {
Map<String, List<Contact>> map = new HashMap<>();
for (Contact cont : contactList) {
for (String c : cont.contacts) {
if (map.containsKey(c)) {
map.get(c).add(cont);
} else {
List<Contact> list = new ArrayList<>();
list.add(cont);
map.put(c, list);
}
}
}
return map;
}
private static List<Contact> buildContactList(String[][] contacts) {
List<Contact> contactList = new LinkedList<>();
for (int i = 0; i < contacts.length; i++) {
Set<String> conts = new HashSet<>();
for (int j = 1; j < contacts[0].length; j++) {
conts.add(contacts[i][j]);
}
contactList.add(new Contact(contacts[i][0], conts, i));
}
return contactList;
}
}
This print duplicate together, to make this question
1. Just keep email id in contacts ( instead phone etc)
2. once found the result, print only those who set size is 1
Check my solution below
- nitinguptaiit March 31, 2019BTW these are the famous problem,
there are two variation;
1. Forward depth sum [ the current question ]
2. Reverse depth sum
Here is the simple way ;
public interface NestedInteger
{
/** @return true if this LinkedInt.NestedInteger holds a single integer, rather than a nested list */
boolean isInteger();
/** @return the single integer that this LinkedInt.NestedInteger holds, if it holds a single integer
* Return null if this LinkedInt.NestedInteger holds a nested list */
Integer getInteger();
/** @return the nested list that this LinkedInt.NestedInteger holds, if it holds a nested list
* Return null if this LinkedInt.NestedInteger holds a single integer */
List<NestedInteger> getList();
}
public int getDepth(List<NestedInteger> input, int depth) {
int myDepth = depth;
if (input.size() == 1 && input.get(0).isInteger())
return myDepth;
for (NestedInteger nst : input) {
if (!nst.isInteger()) {
int d = getDepth(nst.getList(), depth + 1);
myDepth = Math.max(d, myDepth);
}
}
return myDepth;
}
@Override
public int reversDepthSum(List<NestedInteger> input) {
int myDeptht = getDepth(input, 1);
return reverseDepthSum(input, 1, myDeptht);
}
private int reverseDepthSum(List<NestedInteger> input, int depth, int myDepth) {
int sum = 0;
for (NestedInteger nst : input) {
// System.out.println(nst);
if (!nst.isInteger()) {
sum += reverseDepthSum(nst.getList(), depth + 1, myDepth);
} else {
sum += (myDepth - depth + 1) * nst.getInteger();
}
}
return sum;
}
@Override
public int forwardDepthSum(List<NestedInteger> input) {
return forwardDepthSum(input, 1);
}
private int forwardDepthSum(List<NestedInteger> input, int depth) {
int sum = 0;
for (NestedInteger nst : input) {
if (nst.isInteger()) {
sum += depth * nst.getInteger();
} else
sum += forwardDepthSum(nst.getList(), depth + 1);
}
return sum;
}
public class Main {
public static void main(String[] ar) {
IDepthSum depthSum = new DepthSum();
List<NestedInteger> sample1 = Arrays.asList(
new NestedIntegerValues(new NestedIntegerValue(1), new NestedIntegerValue(1)),
new NestedIntegerValue(2),
new NestedIntegerValues(new NestedIntegerValue(1), new NestedIntegerValue(1)));
List<NestedInteger> sample2 = Arrays.asList(
new NestedIntegerValue(1),
new NestedIntegerValues(new NestedIntegerValue(4), new NestedIntegerValues(new NestedIntegerValue(6))));
System.out.println(sample1);
System.out.println("depth: " + depthSum.getDepth(sample1, 1));
System.out.println(sample2);
System.out.println("depth: " + depthSum.getDepth(sample2, 1));
System.out.println("Reverse depth sum");
System.out.println(depthSum.reversDepthSum(sample1));
System.out.println(depthSum.reversDepthSum(sample2));
System.out.println("Forward depth sum");
System.out.println(depthSum.forwardDepthSum(sample1));
System.out.println(depthSum.forwardDepthSum(sample2));
}
}
Why Everyone writing so complex code; here is very simple
package Java;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
/**
* Author: Nitin Gupta(nitin.gupta@walmart.com)
* Date: 31/03/19
* Description:
*/
public class MergeSortedListOfInterval {
static class Interval {
public int start, end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Interval interval = (Interval) o;
return start == interval.start &&
end == interval.end;
}
@Override
public int hashCode() {
return Objects.hash(start, end);
}
@Override
public String toString() {
return "(" + start + "," + end + ')';
}
}
private static void test(List<Interval> a, List<Interval> b) {
System.out.println();
merge(a, b).stream().forEach(x -> System.out.print(x + "->"));
}
public static void main(String args[]) {
List<Interval> a = new ArrayList<>();
List<Interval> b = new ArrayList<>();
a.add(new Interval(1, 2));
a.add(new Interval(3, 9));
a.add(new Interval(12, 15));
b.add(new Interval(4, 6));
b.add(new Interval(8, 10));
b.add(new Interval(11, 12));
test(a, b);
a.clear();
b.clear();
a.add(new Interval(1, 5));
a.add(new Interval(10, 14));
a.add(new Interval(16, 18));
b.add(new Interval(2, 6));
b.add(new Interval(8, 10));
b.add(new Interval(11, 20));
test(a, b);
a.clear();
b.clear();
/**
* [(1,2),(3,4)]
* [(2,3),(5,6)]
*
* [(1,3)
*/
a.add(new Interval(1, 2));
a.add(new Interval(3, 4));
b.add(new Interval(2, 3));
b.add(new Interval(5, 6));
test(a, b);
}
private static boolean areOverlap(Interval a, Interval b) {
if (a == null || b == null)
return false;
if (a.end < b.start || b.end < a.start)
return false;
return true;
}
private static Interval merge(Interval a, Interval b) {
if (areOverlap(a, b)) {
return new Interval(Math.min(a.start, b.start), Math.max(a.end, b.end));
}
return null;
}
private static List<Interval> merge(List<Interval> a, List<Interval> b) {
if (a == null || a.isEmpty())
return b;
if (b == null || b.isEmpty())
return a;
final LinkedList<Interval> resuList = new LinkedList<>();
int aIndex = 0, bIndex = 0;
int aSize = a.size(), bSize = b.size();
while (aIndex < aSize && bIndex < bSize) {
Interval x = a.get(aIndex);
Interval y = b.get(bIndex);
Interval z = resuList.isEmpty() ? null : resuList.getLast();
Interval finalInterval = null;
if (x.end < y.start) {
mergeUpdate(x, z, resuList);
aIndex++;
} else if (y.end < x.start) {
mergeUpdate(y, z, resuList);
bIndex++;
} else {
aIndex++;
bIndex++;
mergeUpdate(merge(x, y), z, resuList);
}
}
while (aIndex < aSize){
Interval x= a.get(aIndex++);
Interval z = resuList.isEmpty() ? null : resuList.getLast();
mergeUpdate(x, z, resuList);
}
while (bIndex < bSize){
Interval x= b.get(bIndex++);
Interval z = resuList.isEmpty() ? null : resuList.getLast();
mergeUpdate(x, z, resuList);
}
return resuList;
}
private static void mergeUpdate(Interval finalInterval, Interval z, List<Interval> result) {
Interval merged = merge(finalInterval, z);
if (merged != null) {
z.start = merged.start;
z.end = merged.end;
} else {
result.add(finalInterval);
}
}
}
Its simple rotate. Just traverse from back. Find the point by reducing index by k. P
Then reverse from 0 to p and p+1 to n-1
Thrn reverse whole array
We can do all operation in constant time using Hashmap and doubly LL
Node {
T key
T value
}
Map<key,Node>
LinkesList
Keep two variable also
1. Tail this is the tail node of DLL
2. LastAaccess this will tell abt the last access node
1. Set
Insert it to tail of DLL update tail to point last node. If LastAaccess is same as tail then make both same(LastAaccess =tail)
O(1)
2. Get(key)
Go to hash map, get the node if exist and go to that node in DLL return value.
Also update the LastAaccess to this node.
O(1)
3. Delete (key), use map, get the node if exist and remove from both DLL and map
Here if
1. If LastAaccess = key node the update LastAaccess to tail otherwise don't update LastAaccess
A. In case if all LastAaccess, tail and key to delete are same then automatically tail gets update and with inner if condition the last Access gets update
B. If key and tail are same the it won't affect LastAaccess at all
Fetching last node is not constant time operation until list is array list,.... Ur us linked list. So ur solution is o(n^2)
- nitinguptaiit March 31, 2019Its very simple, the code works.
Just put those interval on a line and see. U'll understand
Why every one choosing queue? It's not correct. This ncr problem
- nitinguptaiit February 24, 2019
RepOliviaJBlack, Consultant at Apkudo
I am Olivia from San Diego. I am working as a checker in the Thom McAn Store company. My strong ...
Here is solution using trie
- nitinguptaiit April 03, 2019