Kapil
BAN USER
boolean isDivisible(String input, int n) {
int remainder = 0;
int size = input.length();
for(int index = size-1; index >=0; index--) {
if(input.charAt(index) == '1') {
remainder = (2*remainder + 1) %n;
} else {
remainder = (2*remainder) %n;
}
}
if(remainder%n==0) {
return true;
} else {
return false;
}
}
Step 1 :- First we create the trie and add the index value of word at the end of the word.
Step 2 :- search in the trie for the given words and if we found those words we also get the location of all the word where these word are present in the file.
Step 3:- we will put then in a single list of both the occurrence location of words and apply the below algorithm.
void function() {
List<Point> xPoints = new ArrayList<Point>();
List<Point> yPoints = new ArrayList<Point>();
xPoints.add(new Point("firstWord", 32));
xPoints.add(new Point("firstWord", 54));
yPoints.add(new Point("secondWord", 38));
yPoints.add(new Point("secondWord", 67));
Comparator<Point> myComparator = new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
return o1.value - o2.value;
}
};
List<Point> listOfPoints = new ArrayList<Point>();
listOfPoints.addAll(xPoints);
listOfPoints.addAll(yPoints);
Collections.sort(listOfPoints, myComparator);
Point xPoint = null;
Point yPoint = null;
int minValue = Integer.MAX_VALUE;
for (Point point : listOfPoints) {
if (point.type == "firstWord") {
if (null != yPoint) {
if (minValue > (point.value - yPoint.value)) {
minValue = point.value - yPoint.value;
}
}
xPoint = point;
} else if (point.type == "secondWord") {
if (null != xPoint) {
if (minValue > (point.value - xPoint.value)) {
minValue = point.value - xPoint.value;
}
}
yPoint = point;
}
}
System.out.println("Data Value "+minValue);
}
// Time Complexity O(n)
static Node constructTree(int[] pre, int size) {
Node root = new Node(pre[0]);
Stack<Node> stack = new Stack<Node>();
stack.push(root);
for (int index = 1; index < size; index++) {
Node temp = null;
while (!stack.isEmpty() && pre[index] > stack.peek().data) {
temp = stack.pop();
}
if (null != temp) {
temp.right = new Node(pre[index]);
stack.push(temp.right);
} else {
temp = stack.peek();
temp.left = new Node(pre[index]);
stack.push(temp.left);
}
}
return root;
}
Time Complexity is O(n) where n is the length of input string.
static boolean isDivisible(String input) {
int noOfOnesAtOddPlace = 0;
for(int index=0; index < input.length(); index++) {
if(index%2 == 0 && input.charAt(index) == '1') {
noOfOnesAtOddPlace--;
} else if(index%2 != 0 && input.charAt(index) == '1') {
noOfOnesAtOddPlace++;
}
}
return (noOfOnesAtOddPlace%3==0);
}
Simple Java implementation of LRU cache :-
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
int capacity;
public LRUCacheImplementationUsingLinkedHashMap(int capacity) {
super(capacity + 1, 1.0f, true);
this.capacity = capacity;
}
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return (size() > capacity);
}
}
Points need to consider to solve the problem of slow server.
1. We need to check the load on the server.
2. We need to check if any process is taking 100% cpu or not.
3. we need to check the permSize and heap Size on the server.
These are some of the steps i will consider if sever is slow.
In This mapping will also play a important role like As rsumanKumar mentioned that we need the entities like Topic, Message, User and Manager so mapping should be like Topic to Message have one to many mapping, Message to user have one to one mapping and user to Manager have many to one mapping.
- Kapil July 27, 2017int maximumPeopleInARoom(int[] entryTimeArray, int[] exitTimeArray) {
Arrays.sort(entryTimeArray);
Arrays.sort(exitTimeArray);
int maxCount = 0, count = 0;
int entryIndex = 0;
int exitIndex = 0;
while (entryIndex < entryTimeArray.length && exitIndex < exitTimeArray.length) {
if (entryTimeArray[entryIndex] < exitTimeArray[exitIndex]) {
count++;
entryIndex++;
} else if (entryTimeArray[entryIndex] > exitTimeArray[exitIndex]) {
count--;
exitIndex++;
} else {
exitIndex++;
entryIndex++;
}
if(maxCount < count) {
maxCount = count;
}
}
return maxCount;
}
boolean distance(Node root, Integer height, int n1, int n2) {
if(null == root || n1 == n2) {
height = 0;
return false;
}
if(root.data == n1 || root.data == n2) {
height = 0;
return true;
}
Integer leftHeight = 0, rightHeight = 0;
boolean left = distance(root.left, leftHeight, n1, n2);
boolean right = distance(root.right, rightHeight, n1, n2);
if(left && right) {
System.out.println("Diameter "+leftHeight+rightHeight+1);
return true;
} else if(left || right) {
height = (left ? leftHeight+1 : 0);
height = (right ? rightHeight +1 : 0);
return true;
}
return false;
}
// Java Solution
// Time Complexity O(n) and Space Complexity is O(1)
static int getMaximumSumSubArray(int[] arr) {
int size = arr.length;
int max_so_far = 0;
int max_end_here = 0;
for (int index = 0; index < size; index++) {
if (max_end_here + arr[index] < 0) {
max_end_here = 0;
} else {
max_end_here += arr[index];
if (max_so_far < max_end_here) {
max_so_far = max_end_here;
}
}
}
return max_so_far;
}
// Time Complexity O(n)
// Space Complexity O(n)
public class OverlappingProblem {
static class Interval {
int start;
int end;
public Interval() {
this.start = 0;
this.end = 0;
}
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
}
static ArrayList<Interval> getOverlapingInterval(List<Interval> intervals) {
ArrayList<Interval> results = new ArrayList<Interval>();
Collections.sort(intervals, new MyComparator());
int start = intervals.get(0).start;
int end = intervals.get(0).end;
for (int index = 0; index <= intervals.size(); index++) {
if (index == 0) {
start = intervals.get(index).start;
end = intervals.get(index).end;
} else if (index != intervals.size()) {
if (intervals.get(index).start <= end) {
end = (intervals.get(index).end > end) ? intervals.get(index).end : end;
} else {
results.add(new Interval(start, end));
start = intervals.get(index).start;
end = intervals.get(index).end;
}
} else {
results.add(new Interval(start, end));
}
}
return results;
}
public static void main(String args[]) {
List<Interval> listOfIntervals = new ArrayList<Interval>();
listOfIntervals.add(new Interval(1,3));
listOfIntervals.add(new Interval(2,6));
listOfIntervals.add(new Interval(8, 12));
listOfIntervals.add(new Interval(10, 18));
List<Interval> results = getOverlapingInterval(listOfIntervals);
for(Interval result : results) {
System.out.println(result.start+" "+result.end);
}
}
static class MyComparator implements Comparator<Interval> {
@Override
public int compare(Interval a, Interval b) {
int first = a.start - b.start;
return (first == 0) ? (a.end - b.end) : first;
}
}
}
int[] function(int[] a, int[] b) {
int aSize = a.length;
int bSize = b.length;
int aIndex = aSize;
int bIndex = bSize;
for(int index = aSize-1; index >=0 ; index--) {
if(bIndex == 0) {
break;
} else if(aIndex == 0) {
a[index] = b[bIndex-1];
bIndex--;
} else if(a[aIndex-1] > b[bIndex-1]) {
a[index] = a[aIndex-1];
aIndex--;
} else {
a[index] = b[bIndex-1];
bIndex--;
}
}
return a;
}
// Time Complexity O(nLogn)
static class Node {
int sum;
int index;
public Node(int sum, int index) {
this.sum = sum;
this.index = index;
}
public int getSum() {
return sum;
}
public void setSum(int sum) {
this.sum = sum;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
}
static class PrefixSumcomparator implements Comparator<Node> {
@Override
public int compare(Node o1, Node o2) {
return (o1.getSum() <= o2.getSum()) ? -1 : 1;
}
}
static void printPairWithMinimumsum(int[] input) {
int size = input.length;
Node[] prefixSum = new Node[size];
for (int index = 0; index < size; index++) {
int sum = input[index];
if (index > 0) {
sum += prefixSum[index - 1].getSum();
}
Node node = new Node(sum, index);
prefixSum[index] = node;
}
Arrays.sort(prefixSum, new PrefixSumcomparator());
int globalSum = Math.abs(prefixSum[0].getSum()), start = 0, end = prefixSum[0].getIndex();
for(int index=1; index < size; index++) {
int minSum = (prefixSum[index].getSum() - prefixSum[index-1].getSum());
if(Math.abs(prefixSum[index].getSum()) < globalSum) {
globalSum = Math.abs(prefixSum[index].getSum());
start = 0;
end = index;
} else if (minSum < globalSum) {
globalSum = minSum;
if (prefixSum[index - 1].getIndex() < prefixSum[index].getIndex()) {
end = prefixSum[index].getIndex();
start = prefixSum[index - 1].getIndex();
} else {
start = prefixSum[index].getIndex();
end = prefixSum[index - 1].getIndex();
}
}
}
System.out.println("start "+start+" end "+end+" sum "+globalSum);
}
Integer[] findIntegers(int[] arr) {
int avg = 0;
for(int index = 0; index < arr.length; index++) {
avg+=arr[index];
}
avg /= arr.length;
ArrayList<Integer> integerArray = new ArrayList<Integer>();
for(int index=0; index < arr.length; index++ ) {
if(arr[index] > avg) {
integerArray.add(arr[index]);
}
}
return ArrayUtils.toPrimitive((Integer[])integerArray.toArray());
}
Big-endian and little-endian are terms that describe the order in which a sequence of bytes are stored in computer memory. Big-endian is an order in which the "big end" (most significant value in the sequence) is stored first (at the lowest storage address). Little-endian is an order in which the "little end" (least significant value in the sequence) is stored first. For example, in a big-endian computer, the two bytes required for the hexadecimal number 4F52 would be stored as 4F52 in storage (if 4F is stored at storage address 1000, for example, 52 will be at address 1001). In a little-endian system, it would be stored as 524F (52 at address 1000, 4F at 1001).
using lscpu command in linux we can get the about our system bytes order.
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 58
Stepping: 9
CPU MHz: 1200.000
BogoMIPS: 4789.59
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 3072K
NUMA node0 CPU(s): 0-3
// n should be positive
int fibonacci(int n) {
int[] fibonacciArray = new int[n + 1];
fibonacciArray[0] = 0;
fibonacciArray[1] = 1;
for (int index = 2; index <= n; index++) {
fibonacciArray[index] = fibonacciArray[index - 1] + fibonacciArray[index - 2];
}
return fibonacciArray[n];
}
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
// Time Complexity O(n)
Node getElement(Node head, int n) {
Node first = head, second = head;
int count = 0;
while(null != first && count < n) {
first = first.next;
count++;
}
if(count != n) {
return first;
}
while(null != first) {
first = first.next;
second = second.next;
}
return second;
}
// Time Complexity is O(n) and space complexity is (n)
void findDuplicates(int[] arr) {
Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
Set<Integer> duplicates = new HashSet<Integer>();
for (int index = 0; index < arr.length; index++) {
if (null != hashMap.get(arr[index])) {
duplicates.add(arr[index]);
} else {
hashMap.put(arr[index], 1);
}
}
for (Integer duplicate : duplicates) {
System.out.println(duplicate);
}
}
// Java Implementation
// Time Complexity is O(n) where n is the length of string and space complexity is O(1)
void printMaximumOccuringCharacter(String str) {
Map<Integer, Entry> occurrenceMap = new HashMap<Integer, Entry>();
int maximumOccuringCharacter = 0;
for (int index = 0; index < str.length(); index++) {
int character = str.charAt(index);
if (null != occurrenceMap.get(character)) {
occurrenceMap.get(character).setCount(occurrenceMap.get(character).getCount() + 1);
} else {
occurrenceMap.put(character, new Entry(1, index));
}
if (character != maximumOccuringCharacter) {
Entry entry = occurrenceMap.get(maximumOccuringCharacter);
if (null == entry || occurrenceMap.get(character).getCount() > entry.getCount()) {
maximumOccuringCharacter = character;
} else if (occurrenceMap.get(character).getCount() == entry.getCount()) {
if (occurrenceMap.get(character).getStartingIndex() < entry.getStartingIndex()) {
maximumOccuringCharacter = character;
}
}
}
}
System.out.println("Maximum Occuring Character is " + ( char ) maximumOccuringCharacter);
}
// Java Implementation
// Algorithm of this code is Brandy code.
// Time complexity is O(n) and space is O(n)
private class Node {
int data;
Node next, other;
Node(int data) {
this.data = data;
this.next = this.other = null;
}
}
Node copyLinkedList(Node head) {
if (null == head) {
return null;
}
Node current = head;
while (null != current) {
Node temp = new Node(current.data);
temp.next = current.next;
current.next = temp;
current = temp.next;
}
current = head;
Node copiedList = head.next;
while(null != current) {
Node temp = current.next;
temp.other = current.other.next;
current.next = temp.next;
current = current.next;
temp = current.next;
}
return copiedList;
}
A struct is a value type so it is stored on the stack, but class is a reference type so it is stored in a heap.A structure can't support inheritance and polymorphism, but class support both. By default struct are public in nature but class are private in nature.
Padding :- In order to align the memory one or more empty bytes (addresses) are inserted between memory addresses. which are allocated for other structure member while memory allocation.This concept is called structure padding.
int function(int number) {
StringBuilder str = new StringBuilder(String.valueOf(number));
for (int i = str.length() - 1; i > 0; i--) {
if (Integer.valueOf(str.charAt(i) - '0') > Integer.valueOf(str.charAt(i - 1) - '0')) {
int index = str.length() - 1;
while (index > (i - 1)) {
if (Integer.valueOf(str.charAt(index) - '0') > Integer.valueOf(str
.charAt(i - 1) - '0')) {
break;
}
index--;
}
char temp = str.charAt(i - 1);
str.replace(i - 1, i, String.valueOf(str.charAt(index)));
str.replace(index, index + 1, String.valueOf(temp));
int j = str.length() - 1;
while (j > i) {
temp = str.charAt(j);
str.replace(j, j + 1, String.valueOf(str.charAt(i)));
str.replace(i, i + 1, String.valueOf(temp));
i++;
j--;
}
break;
}
}
return Integer.valueOf(str.toString());
}
public class TicTacToeGame {
private static final int SIZE = 3;
private char[][] matrix;
private boolean player = true;
private boolean flag = false;
public TicTacToeGame() {
matrix = new char[SIZE][SIZE];
for (int row = 0; row < SIZE; row++) {
for (int col = 0; col < SIZE; col++) {
matrix[row][col] = '-';
}
}
}
public void play(int row, int column) {
if ('-' == matrix[row][column] && !flag) {
matrix[row][column] = (player ? 'x' : '0');
player = !player;
if (checkWin()) {
System.out.println((player ? "First " : "Second") + " Player win");
printMatrix();
flag = true;
}
return;
}
if (flag) {
System.out.println((player ? "First " : "Second") + " Player winned ");
}
System.out.println("invalid move");
return;
}
private char move() {
return (player ? 'x' : '0');
}
private boolean checkWin() {
return (checkWinConditionInRow() || checkWinConditionInColumn() || checkWinConditionInDiagonal());
}
private boolean checkWinConditionInRow() {
for (int row = 0; row < SIZE; row++) {
boolean isValid = true;
for (int col = 0; col < SIZE; col++) {
if (matrix[row][col] != move()) {
isValid = false;
break;
}
}
if (isValid) {
return true;
}
}
return false;
}
private boolean checkWinConditionInColumn() {
for (int col = 0; col < SIZE; col++) {
boolean isValid = true;
for (int row = 0; row < SIZE; row++) {
if (matrix[row][col] != move()) {
isValid = false;
break;
}
}
if (isValid) {
return true;
}
}
return false;
}
private boolean checkWinConditionInDiagonal() {
return ((matrix[0][0] == move() && matrix[1][1] == move() && matrix[2][2] == move()) || (matrix[0][2] == move()
&& matrix[1][1] == move() && matrix[2][0] == move()));
}
private void printMatrix() {
for (int row = 0; row < SIZE; row++) {
for (int col = 0; col < SIZE; col++) {
System.out.print(matrix[row][col] + " ");
}
System.out.println();
}
}
public static void main(String args[]) {
TicTacToeGame ticTacToeGame = new TicTacToeGame();
ticTacToeGame.play(0, 0);
ticTacToeGame.play(1, 1);
ticTacToeGame.play(0, 1);
ticTacToeGame.play(1, 2);
ticTacToeGame.play(0, 2);
ticTacToeGame.play(2, 0);
}
}
// TimeComplexity O(N) where no is the no of nodes
class Node {
Integer nodeId;
Integer parentNodeId;
public Integer getNodeId() {
return nodeId;
}
public void setNodeId(Integer nodeId) {
this.nodeId = nodeId;
}
public Integer getParentNodeId() {
return parentNodeId;
}
public void setParentNodeId(Integer parentNodeId) {
this.parentNodeId = parentNodeId;
}
}
class TreeNode {
Integer nodeId;
List<TreeNode> childs;
TreeNode(Integer id) {
this.nodeId = id;
childs = new ArrayList<TreeNode>();
}
public Integer getNodeId() {
return nodeId;
}
public void setNodeId(Integer nodeId) {
this.nodeId = nodeId;
}
public List<TreeNode> getChilds() {
return childs;
}
public void setChilds(List<TreeNode> childs) {
this.childs = childs;
}
}
TreeNode createTree(List<Node> listOfNode) {
Map<Integer, List<Node>> parentChildRelationShipMap = new HashMap<Integer, List<Node>>();
Map<Integer, Node> nodeIdMap = new HashMap<Integer, TestClass.Node>();
Integer rootId = null;
for (Node node : listOfNode) {
Integer parentId = node.getParentNodeId();
Integer nodeId = node.getNodeId();
if (null != parentChildRelationShipMap.get(nodeId)) {
nodeIdMap.put(nodeId, node);
if (null != parentChildRelationShipMap.get(parentId)) {
parentChildRelationShipMap.get(parentId).add(node);
} else {
ArrayList<Node> nodeList = new ArrayList<Node>();
nodeList.add(node);
parentChildRelationShipMap.put(parentId, nodeList);
}
} else {
parentChildRelationShipMap.put(nodeId, new ArrayList<Node>());
nodeIdMap.put(nodeId, node);
}
if(null == parentId) {
rootId = nodeId;
}
}
return createTreeUtils(parentChildRelationShipMap, rootId);
}
TreeNode createTreeUtils(Map<Integer, List<Node>> parentChildRelationShipMap, Integer nodeId) {
List<TreeNode> childList = new ArrayList<TreeNode>();
for (Node node : parentChildRelationShipMap.get(nodeId)) {
childList.add(createTreeUtils(parentChildRelationShipMap, node.getNodeId()));
}
TreeNode node = new TreeNode(nodeId);
node.setChilds(childList);
return node;
}
// No of multiplication (n-1) where n is the size of matrix and time complexity is O(n) and space complexity is O(1)
void function(int[] arr) {
int multiply = 1;
for(int index=0; index<arr.length; index++) {
multiply*=arr[index];
}
for(int index=0; index < arr.length; index++) {
System.out.print(multiply/arr[index] + " ");
}
}
void pascalTriangle(int level) {
if(level > 0) {
pascalTriangle(level-1);
int number = 1;
for(int index=0; index<level;index++) {
if(index==0 || index == level-1) {
System.out.print("1 ");
} else {
number = number*(level-index)/index;
System.out.print(number+" ");
}
}
System.out.println();
}
}
// This will solution assumes that the str2 contains all the unique tokens
String function(String str1, String str2) {
StringTokenizer stringTokenizer = new StringTokenizer(str2);
while (stringTokenizer.hasMoreTokens()) {
str1 = str1.replaceFirst(stringTokenizer.nextToken()+" ", "");
}
return str1;
}
Java Implementation Time Complexity (O(nLogn))
void function(int[] arr, int size) {
Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();
for (int index = 0; index < size; index++) {
Integer elementFrquency = frequencyMap.get(arr[index]);
if (null != elementFrquency) {
elementFrquency += 1;
} else {
elementFrquency = 1;
}
frequencyMap.put(arr[index], elementFrquency);
}
List<Map.Entry<Integer, Integer>> frequencyMapElementList = new LinkedList<Map.Entry<Integer, Integer>>(
frequencyMap.entrySet());
Collections.sort(frequencyMapElementList, new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
int compare = o1.getKey().compareTo(o2.getKey());
if (compare == 0) {
return o1.getValue().compareTo(o2.getValue());
}
return compare;
}
});
for(Map.Entry<Integer,Integer> entry : frequencyMapElementList) {
for(int index=0; index<entry.getValue(); index++) {
System.out.print(entry.getKey()+" ");
}
}
}
Implementation in Java.
void function(int[] arr, int k) {
int size = arr.length;
// list is used to print the pairs
Map<Integer, List<Integer>> hashMap = new HashMap<Integer, List<Integer>>();
int currentSum = 0;
for (int index = 0; index < size; index++) {
currentSum += arr[index];
List<Integer> list = hashMap.get(currentSum % k);
if (null != list) {
list.add(index);
} else {
list = new ArrayList<Integer>();
list.add(index);
}
hashMap.put(currentSum % k, list);
}
int noOfSubArray = 0;
for(Map.Entry<Integer, List<Integer>> entry : hashMap.entrySet()) {
Integer key = entry.getKey();
Integer listSize = entry.getValue().size();
if(key == 0) {
noOfSubArray += (listSize*(listSize+1))/2;
} else {
noOfSubArray += (listSize*(listSize-1))/2;
}
}
System.out.println("No of subArray in O(k+n) time complexity "+noOfSubArray);
}
1. employee ( id, name, email, password, manager_id, role_id)
2. role (id, name, city_name)
3. attendance( id, employee_id, swap_in_time, swap_out_time, date).
for employee :-
select at.swap_in_time, at.swap_out_time from attendance at inner join employee emp on emp.id = at.employee_id where emp.email = "abc@example.com" and at.date = now();
- Kapil November 01, 2017static void sortedArray(int[] arr, int k) { int size = arr.length; PriorityQueue<Integer> queue = new PriorityQueue<Integer>(); for(int i=0; i<k; i++) { queue.add(arr[i]); } int m =0; int n = k; while(!queue.isEmpty()){ Integer value = queue.poll(); arr[m++] = value; if(n < size) { queue.add(arr[n++]); } } System.out.println(" "+Arrays.toString(arr)); }