artur.ghandilyan
BAN USERpublic class StringListEncoder {
private static final char SEPARATOR = ' ';
/**
* The key here is that we are putting the string length and separator before every String
* So that we can distinguish always.
*/
public String encodeStringList(final List<String> strings) {
final StringBuffer buffer = new StringBuffer();
for (final String s : strings) {
buffer.append(s.length());
buffer.append(' ');
buffer.append(s);
}
return buffer.toString();
}
public List<String> decodeString(final String value) {
String s = value;
final List<String> decodedList = new ArrayList<>();
int start = 0;
while (!s.isEmpty()) {
/**
* The first SEPARATOR will be the one we put during the serialization
*/
int idx = s.indexOf(SEPARATOR);
int strLen = Integer.parseInt(s.substring(start, idx));
int curStrStart = idx + 1;
int curStrEnd = idx + strLen + 1;
final String currStr = s.substring(curStrStart, curStrEnd);
decodedList.add(currStr);
s = s.substring(curStrEnd);
}
return decodedList;
}
}
public class StringListEncoder {
private static final char SEPARATOR = ' ';
/**
* The key here is that we are putting the string length and separator before every String
* So that we can distinguish always.
*/
public String encodeStringList(final List<String> strings) {
final StringBuffer buffer = new StringBuffer();
for (final String s : strings) {
buffer.append(s.length());
buffer.append(' ');
buffer.append(s);
}
return buffer.toString();
}
public List<String> decodeString(final String value) {
String s = value;
final List<String> decodedList = new ArrayList<>();
int start = 0;
while (!s.isEmpty()) {
/**
* The first SEPARATOR will be the one we put during the serialization
*/
int idx = s.indexOf(SEPARATOR);
int strLen = Integer.parseInt(s.substring(start, idx));
int curStrStart = idx + 1;
int curStrEnd = idx + strLen + 1;
final String currStr = s.substring(curStrStart, curStrEnd);
decodedList.add(currStr);
s = s.substring(curStrEnd);
}
return decodedList;
}
}
This is a wrong solution, what if the one or many original strings have ',' character in them?
- artur.ghandilyan January 15, 2017public class GenerateMatrix {
private int[][] matrix;
private int rowCount;
private int colCount;
final List<Integer> alphabet;
public GenerateMatrix(int n, int m) {
rowCount = n;
colCount = m;
matrix = new int[n][];
for (int i = 0; i < m; ++i) {
matrix[i] = new int[m];
}
alphabet = new ArrayList<>();
alphabet.add(1);
alphabet.add(2);
alphabet.add(3);
alphabet.add(4);
}
public void generate() {
for (int i = 0; i < rowCount; ++i) {
for (int j = 0; j < colCount; ++j) {
matrix[i][j] = generate(i, j);
}
}
}
private int generate(int r, int c) {
Set<Integer> s = new HashSet<>();
s.addAll(alphabet);
int left = leftDisallowed(r, c);
int up = uptDisallowed(r, c);
if (left != -1) {
s.remove(left);
}
if (up != -1 && up != left) {
s.remove(up);
}
int rand = (new Random()).nextInt(s.size());
return (int) s.toArray()[rand];
}
private int leftDisallowed(int i, int j) {
if (i < 2) {
return -1;
}
if (matrix[i - 2][j] == matrix[i - 1][j]) {
return matrix[i - 2][j];
}
return -1;
}
private int uptDisallowed(int i, int j) {
if (j < 2) {
return -1;
}
if (matrix[i][j - 2] == matrix[i][j - 1]) {
return matrix[i][j - 1];
}
return -1;
}
}
/**
* Assuming that sets dont have duplicates as in the Mathematical definition of set.
* @param sets: The input list of the Sets.
* @return Intersection of the sets.
*/
public List<Integer> setIntersection(final List<Set<Integer>> sets) {
final List<Integer> intersection = new ArrayList<>();
if (sets.isEmpty()) {
return intersection;
}
final Map<Integer, Integer> occurance = new HashMap<>();
for (final Set<Integer> s : sets) {
for (final Integer i : s) {
if (occurance.containsKey(i)) {
occurance.put(i, occurance.get(i) + 1);
} else {
occurance.put(i, 1);
}
}
}
for (final Integer key : occurance.keySet()) {
if (occurance.get(key).equals(sets.size())) {
intersection.add(key);
}
}
return intersection;
}
public class Node
{
Node parent;
Node right;
Node left;
};
public class ParentFinder
{
private class DepthAndNode
{
public int depth;
public Node node;
}
Node FindCommonParent(Node n1, Node n2)
{
if (n1 == null || n2 == null)
{
return null;
}
DepthAndNode r1 = GetRoot(n1);
DepthAndNode r2 = GetRoot(n2);
// They dont have common root, so they dont have common parent
if (r1.node != r2.node)
{
return null;
}
// Bring n1 and n2 to the same level
while (r1.depth > r2.depth)
{
r1.node = r1.node.parent;
--r1.depth;
}
// Bring n1 and n2 to the same level
while (r2.depth > r1.depth)
{
r2.node = r2.node.parent;
--r2.depth;
}
while (n1 != n2)
{
n1 = n1.parent;
n2 = n2.parent;
}
return n1;
}
DepthAndNode GetRoot(Node n)
{
DepthAndNode r = new DepthAndNode();
r.depth = 0;
while (n.parent != null)
{
++r.depth;
r.node = n.parent;
n = n.parent;
}
return r;
}
}
In case of n/2 there is no need to check, the a[n/2] is the majority element. In fact if you check that might lead to unwanted results like A = 1, 2, 2, 2, 2, 3, 4.
Here n = 7 and A[n/2] is not equal neither A[0] nor A[n]
int Read(int toRead, char* buf)
{
int readSoFar = 0;
int remaining = toRead;
char* intBuf = new char[4096];
while (remaining)
{
int current = Read4k(intBuf);
if (current == 0)
break;
int bytesToCopy = remaining >= current ? current : remaining;
memccpy(buf + readSoFar, intBuf, bytesToCopy);
readSoFar += bytesToCopy;
remaining -= bytesToCopy;
}
delete[] intBuf;
return readSoFar;
}
public static Employee closestCommonManagerRecur(Employee ceo, Employee firstEmployee, Employee secondEmployee)
{
if (ceo == null || firstEmployee == null || secondEmployee == null)
{
return null;
}
if (ceo.getId() == firstEmployee.getId())
{
return ceo;
}
if (ceo.getId() == secondEmployee.getId())
{
return ceo;
}
HashSet<Employee> em = new HashSet<Employee>();
foreach (var e in ceo.getReports())
{
var m = closestCommonManagerRecur(e, firstEmployee, secondEmployee);
if (m != null)
{
em.Add(m);
}
}
if (em.Count == 0)
{
return null;
}
if (em.Count == 2)
{
return ceo;
}
else
{
return em.ElementAt(0);
}
}
void ConnectNexts(Node* root)
{
if (root == nullptr || (!root->left && !root->right))
{
return;
}
if (root->left)
{
root->left->next = root->right;
}
if (root->next)
{
Node* newNextNode = root->next->left ? root->next->left : root->next->right;
if (root->right)
{
root->right->next = newNextNode;
}
else
{
// At this point root->left should exist
root->right->next = newNextNode;
}
}
ConnectNexts(root->left);
ConnectNexts(root->right);
}
void GenerateValidParenthesis(std::string& s, int open, int close, int n)
{
if (close == n)
{
std::cout << s << std::endl;
}
if (open > close)
{
GenerateValidParenthesis(s + ')', open, close + 1, n);
}
if (open < n)
{
GenerateValidParenthesis(s + '(', open + 1, close, n);
}
}
int max_gain_stock(const std::vector<int>& v)
{
if (v.empty())
{
return 0;
}
int min = v[0];
int max_gain = 0;
for (int i = 1; i < v.size(); ++i)
{
int local = v[i] - min;
if (local > max_gain)
{
max_gain = local;
}
if (v[i] < min)
{
min = v[i];
}
}
return max_gain;
}
void Sort(std::vector<char>& a, std::vector<int>& b)
{
int i = 0;
while (i < b.size())
{
if (b[i] == i)
{
++i;
continue;
}
std::swap(a[b[i]], a[i]);
std::swap(b[i], b[b[i]]);
}
}
void PrintPermutations(char permutation[], char alpha[], int n, int current_len, int expected_len)
{
if (current_len == expected_len)
{
for (int i = 0; i < expected_len; ++i)
{
std::cout << permutation[i];
}
std::cout << std::endl;
return;
}
for (int i = 0; i < n; ++i)
{
permutation[current_len] = alpha[i];
PrintPermutations(permutation, alpha, n, current_len + 1, expected_len);
}
}
}
- artur.ghandilyan April 25, 2017