Sibendu Dey
BAN USERPreparing For Google!!
Store the position of '(' in another stack.The position should be the length of the output string at that point. If '(' needs to be printed in the output string, then we can get the entry position in the output string from the stackPos.
package careercup.questions.google;
import java.util.Scanner;
import java.util.Stack;
/**
* Created by sibendu on 26/6/17.
*/
public class BalanceStringParanthesis {
public static void main( String args[]) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
System.out.print(balanceParanthesis(str).toString());
}
private static StringBuilder balanceParanthesis(String str) {
Stack<Character> stack = new Stack<>();
Stack<Integer> stackPos = new Stack<>();
StringBuilder output = new StringBuilder("");
for ( int i = 0 ; i < str.length() ; i++) {
char curr = str.charAt(i);
switch (curr) {
case '(' : stack.push('(');
stackPos.push(output.length());
break;
case ')' :
if ( stack.size() != 0) {
char ch = stack.pop();
int pos = stackPos.pop();
output.insert(pos , ch);
output.append(')');
}
break;
default:
output.append(curr);
}
}
return output;
}
}
package hashmaps.careercup.facebook;
import trees.Node;
import trees.TreeTraversals;
import java.util.Scanner;
/**
* Created by Sibendu Dey on 6/5/17.
*/
public class TernaryToBinary {
public static void main( String args[]) {
Scanner sc = new Scanner(System.in);
String ternaryExpression = sc.next();
Node root = constructTree(ternaryExpression);
// Takes care of displaying the tree in-order fashion
TreeTraversals.inOrderStringDisplay(root);
}
private static Node constructTree(String ternaryExpression) {
return constructTreeTernary(ternaryExpression);
}
private static Node constructTreeTernary(String ternaryExpression) {
int questionIndex = ternaryExpression.indexOf('?');
Node node = null;
if ( questionIndex == -1)
node = new Node(ternaryExpression);
else
node = new Node(ternaryExpression.substring(0 , questionIndex));
// It means this is a leaf node. No need for further recursive operation
if ( questionIndex == -1)
return node;
// This indices takes care of dividing the strings into two parts for recursive operations.
int firstExpressionStartIndex = questionIndex + 1;
int secondExpressionStartIndex = ternaryExpression.lastIndexOf(':');
node.setleftNode(constructTreeTernary(ternaryExpression.substring(firstExpressionStartIndex , secondExpressionStartIndex )));
node.setRightNode(constructTreeTernary(ternaryExpression.substring(secondExpressionStartIndex + 1)));
return node;
}
}
package hashmaps.careercup.amazon;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.*;
/**
* Created by Sibendu Dey on 4/25/2017.
*/
class Employee {
String id;
Date lastLogin;
int consecutiveDays;
static final int SECONDS_IN_DAY = 24*60*60*1000;
public Employee(String id, Date date) {
this.id = id;
lastLogin = date;
}
public void incrementConsecutiveDays(Date date) {
if ( consecutiveDays == 3)
return;
if ( (date.getTime() - lastLogin.getTime()) <= SECONDS_IN_DAY) {
consecutiveDays++;
}
else {
consecutiveDays = 1;
}
lastLogin = date;
}
public boolean isConsecutive() {
return consecutiveDays == 3 ? true : false;
}
}
public class ConsecutiveLogin {
public static void main( String args[]) {
Scanner sc = new Scanner(System.in);
int input = sc.nextInt();
sc.nextLine();
HashMap<String , Employee> list = new HashMap<>();
for ( int i = 0 ; i < input ; i++) {
SimpleDateFormat sdf = new SimpleDateFormat("dd/MM/yyyy");
try {
String line = sc.nextLine();
System.out.println(line);
String values[] = line.split("/t");
String dateValue = values[0];
Date date = sdf.parse(dateValue);
String employeeID = values[1];
Employee employee = null;
if ( list.containsKey(employeeID)) {
employee = list.get(employeeID);
employee.incrementConsecutiveDays(date);
}
else {
employee = new Employee(employeeID, date);
list.put(employeeID , employee);
employee.incrementConsecutiveDays(date);
}
} catch (ParseException e) {
e.printStackTrace();
}
}
findEmployeeWithConsecutiveLogin(list);
}
private static void findEmployeeWithConsecutiveLogin(HashMap<String, Employee> list) {
for (Map.Entry<String , Employee > entry : list.entrySet()) {
Employee employee = entry.getValue();
if ( employee.isConsecutive()) {
System.out.println( entry.getKey());
}
}
}
}
import java.util.*;
/**
* Created by Sibendu on 4/24/2017.
*/
class TrieNode {
String value;
HashMap<String, TrieNode> trieNodes;
int count;
TrieNode(String value) {
this.value = value;
trieNodes = new HashMap<>();
}
public void addTrieNode(String trieNodeValue) {
if (trieNodes == null)
trieNodes = new HashMap<>();
trieNodes.put(value+trieNodeValue , new TrieNode(value+trieNodeValue));
}
public HashMap<String , TrieNode> getTrieNodes() {
return trieNodes;
}
public boolean isLeaf() {
return trieNodes != null && trieNodes.size() > 0 ? false : true;
}
}
public class Device {
private static Scanner sc = new Scanner(System.in);
public static void main(String args[]) {
TrieNode head = new TrieNode("//");
int inputs = sc.nextInt();
sc.nextLine();
for ( int i = 0 ; i < inputs ; i++) {
String input = sc.nextLine();
parseInputs( head , input);
}
findCount(head);
}
private static void findCount(TrieNode head) {
for ( Map.Entry<String , TrieNode> node : head.getTrieNodes().entrySet()) {
System.out.println( node.getKey() + "=" + node.getValue().count);
findCount(node.getValue());
}
}
private static void parseInputs(TrieNode head, String input) {
head.count++;
for ( String str : input.split("/")) {
if ( !head.getTrieNodes().containsKey(head.value + str + "/")) {
head.getTrieNodes().put(head.value + str + "/" , new TrieNode( head.value + str + "/"));
}
head = head.getTrieNodes().get(head.value + str + "/");
head.count++;
}
}
}
@Rajendra: Can you please explain the code?
- Sibendu Dey April 24, 2017If the numbers are sorted:
public class MissingNumber {
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[] = {22, 23 ,24 , 25 , 26 , 27 , 28 , 29 , 31 , 32 , 33 , 34};
System.out.println(binarySearch ( arr , 0 , arr.length - 1 , arr.length - 1));
}
private static int binarySearch(int[] arr , int start , int end , int lastIndex) {
// TODO Auto-generated method stub
if ( start > end)
return -1;
int mid = ( start + end ) / 2;
if ( mid-1 >=0 && arr[mid]-1 != arr[mid-1] ) {
return arr[mid] - 1;
}
else if ( mid+1 <= lastIndex && arr[mid+1] != arr[mid] + 1) {
return arr[mid]+1;
}
else {
if ( arr[mid] - arr[0] == mid - 0) {
return binarySearch(arr , mid+1, end, lastIndex);
}
else {
return binarySearch ( arr , start , mid - 1 , lastIndex);
}
}
}
}
Merge sort -in place(in-place Heap sort can be considered too O(nlogn) ) should do with binary search but yes time complexity will increase.
If API usage is allowed, why not use Arrays.sort function followed by binary search? But O(n log n) is not guaranteed as stated in the javadocs.
Java implementation:
import java.util.ArrayList;
public class InsertWhitespaces {
static ArrayList<String> dictionary = new ArrayList<String>();
public static void main(String[] args) {
// TODO Auto-generated method stub
dictionary.add("he");
dictionary.add("herew");
dictionary.add("we");
dictionary.add("go");
String str = "herewwego";
insertWhitespaces(str , 0 , str.length());
}
private static void insertWhitespaces(String str, int start, int end) {
// TODO Auto-generated method stub
if ( start == end) {
System.out.println(str);
return;
}
for ( int i = start+1 ; i <= end ; i++) {
if ( dictionary.contains(str.substring(start , i ))) {
insertWhitespaces( str.substring(0, start) + str.substring(start , i) + " " + str.substring(i , end), i+1, end+1);
}
}
}
}
TimeComplexity O(mn)
public class WordsCounting {
public static void main(String[] args) {
String words[] = new String[] { "Do" , "run"};
int row = 2 , col = 9;
System.out.println(countWords( words , row , col));
}
private static int countWords(String[] words, int row, int col) {
// TODO Auto-generated method stub
int wordCount = 0;
int rowIterator = 0;
int wordIterator = 0;
int remainingCol;
while ( rowIterator < row ) {
remainingCol = col;
while ( remainingCol > 0 && words[wordIterator].length() <= remainingCol) {
wordCount++;
// update remainingCol , takes wordspacing into account
remainingCol = remainingCol - words[wordIterator].length() - 1;
wordIterator++;
if (wordIterator == words.length)
wordIterator = 0;
}
// IF the word length in any case doesn't fit in the column , increment the wordIterator
if ( words[wordIterator].length() > col) {
wordIterator++;
if (wordIterator == words.length)
wordIterator = 0;
}
//else do a row increment
else {
rowIterator++;
}
}
return wordCount;
}
}
Traversing the matrix in spiral form and storing the elements in stack should do if extra space is allowed.
import java.util.Stack;
public class AntiSpiralMatrixDisplay {
public static void main(String args[]) {
int arr[][] = new int[][]{ {1,2,3}, {4,5,6} , {7,8,9}};
int MAX_ROW = 2;
int MAX_COL = 2;
Stack<Integer> stack = new Stack<Integer>();
for ( int i = 0, j = 0 ; i <= MAX_ROW && j <= MAX_COL; i++ , j++ , MAX_ROW-- , MAX_COL-- ){
int l,k;
l=i;k=j;
for ( ; k <= MAX_COL ; k++)
stack.push(arr[l][k]);
for ( l = i+1 , k = MAX_COL ; l <= MAX_ROW ; l++)
stack.push(arr[l][k]);
for ( l = MAX_ROW , k = MAX_COL - 1 ; k >= j ; k-- )
stack.push(arr[l][k]);
for ( l = MAX_ROW - 1 , k = j ; l > i ; l--)
stack.push(arr[l][k]);
}
printAntiSpiralMatrix(stack);
}
private static void printAntiSpiralMatrix(Stack<Integer> stack ) {
// TODO Auto-generated method stub
while (!stack.empty())
System.out.print(stack.pop()+ " ");
}
}
References : geeksforgeeks
package stacks;
import java.util.Stack;
public class Evaluation {
static Stack<Character> ops = new Stack<Character>();
static Stack<Integer> numbers = new Stack<Integer>();
public static void main(String[] args) {
// TODO Auto-generated method stub
String expression = "19+12/4-((4-7)*3/1)";
char[] tokens = expression.toCharArray();
for ( int i = 0 ; i < tokens.length ; i++){
if ( tokens[i] >= '0' && tokens[i] <='9') {
StringBuffer number = new StringBuffer();
while ( i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9') {
number.append(tokens[i++]);
}
System.out.println("Number added:" + number);
i--;
numbers.push(Integer.decode(number.toString()));
}
else if (tokens[i] == '(')
ops.push(tokens[i]);
else if (tokens[i] == ')') {
while ( ops.peek() != '(' ) {
numbers.push(performOp(ops.pop() , numbers.pop() , numbers.pop()));
System.out.println("Number added:" + numbers.peek());
}
ops.pop();
}
else if ( tokens[i] == '+' || tokens[i] == '-' || tokens[i] == '*' || tokens[i] == '/') {
while (!ops.isEmpty() && hasPrecedence( tokens[i] , ops.peek())) {
numbers.push(performOp(ops.pop() , numbers.pop() , numbers.pop()));
System.out.println("Number added:" + numbers.peek());
}
ops.push(tokens[i]);
System.out.println("Operator added" + ops.peek());
}
}
while (!ops.isEmpty()){
numbers.push(performOp(ops.pop() , numbers.pop() , numbers.pop()));
}
System.out.println("Result of expression:" + numbers.pop());
}
private static boolean hasPrecedence(char c, Character peek) {
// TODO Auto-generated method stub
if ( peek == '(' || peek == ')')
return false;
else if ( (c == '*' || c== '/' ) && (peek == '+' || peek == '-') )
return false;
return true;
}
private static int performOp(char pop, Integer num1, Integer num2) {
// TODO Auto-generated method stub
if ( pop == '+') {
Integer value = num1 + num2;
return value;
}
else if ( pop == '-') {
Integer value = num2 - num1;
return value;
}
else if ( pop == '*') {
Integer value = num1 * num2;
return value;
}
else {
System.out.println(num2 + " " + num1);
Integer value = num2 / num1;
return value;
}
}
}
Running time should be O(nlogk) as O(nlogk) + O(n) ~ O(nlogk) of the above code
- Sibendu Dey July 02, 2016Time period/Lcm of N runners.Basically the answer should be 2 for the example provided
- Sibendu Dey June 29, 2016Basic things first. How can we store data inside a queue in a parallel way.Since we can only store it one at a time.
- Sibendu Dey June 15, 2016public class JumbledNumbers {
public static void main(String args[]) {
String number = "2222134";
//int i = -1 % 10;
printJumbledNumbers(number);
}
private static void printJumbledNumbers(String number) {
// TODO Auto-generated method stub
for ( int i = 1 ; i <= 9 ; i++){
String str = "";
str= str + i;
printJumbedNumbersUtil(str , number);
}
}
private static void printJumbedNumbersUtil(String str, String number) {
// TODO Auto-generated method stub
if ( Long.valueOf(str) <= Long.valueOf(number) ) {
System.out.println(str);
String incrementStr = str;
int nextDigitIncrement = Integer.valueOf(str.substring(str.length() - 1 , str.length() )) + 1;
if ( nextDigitIncrement != 10) {
incrementStr = incrementStr + nextDigitIncrement;
printJumbedNumbersUtil(incrementStr , number);
}
String decrementStr = str;
int nextDigitDecrement = Integer.valueOf(str.substring(str.length() - 1)) - 1;
if (nextDigitDecrement != -1) {
decrementStr = decrementStr + nextDigitDecrement;
printJumbedNumbersUtil(decrementStr , number);
}
}
else {
return;
}
}
}
perform a BFS? Turn the enemy paths into friendly paths and take note of number of magic potions. The minimum potion path is the result.
- Sibendu Dey June 15, 2016Can be done pretty easily in O(n) time using spiral traversal of matrix. Any O(log n ) ideas?
- Sibendu Dey June 14, 2016public class PeakElement {
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[] = { 10, 25, 15, 35, 36, 37 };
System.out.println(findPeakElement(arr, 0, arr.length - 1));
}
private static int findPeakElement(int[] arr, int start, int end) {
// TODO Auto-generated method stub
int mid = (start + end) / 2;
if ((mid == 0 || arr[mid] > arr[mid - 1])
&& (mid == arr.length - 1 || arr[mid] > arr[mid + 1])) {
return arr[mid];
} else if (mid > 0 && (arr[mid] < arr[mid + 1])) {
return findPeakElement(arr, mid + 1, arr.length - 1);
} else {
return findPeakElement(arr, 0, mid - 1);
}
}
}
Reference - geeksforgeeks
package designQs;
import java.util.Date;
import java.util.HashMap;
public class CareerCupDropBox {
static Integer ID = 0;
static HashMap< Date , Integer> hitMap = new HashMap<Date , Integer >();
public static void main(String[] args) {
// TODO Auto-generated method stub
}
public static void recordHit() {
//ID++;
hitMap.put(new Date(), ++ID);
}
public static int getCount(){
Date date = new Date();
return ID - hitMap.get(new Date( date.getTime() - 300000)) ;
}
}
One thing to be considered is the synchronized use of static variable ID is important
- Sibendu Dey April 27, 2016How about using a hashmap and then searching for a key (keys will be the words) based on the content of the stream after every character is received?
- Sibendu Dey April 17, 2016P(a intersection b)=p(a)+p(b)-p(a union b)
Am i correct regarding this case?
@vgeek:We can find a subset and then apply kadane algo from the index after the index where the previous subset ends..Suppose in an array a subset matching a sum lies in 1...5..We can again apply kadane algorithm from 6th index and find for any other possible subset that matches the sum.
- Sibendu Dey July 28, 2013@vgeek:Don't you think applying kadane's algo will be simpler to apply on this??What's your thought?
- Sibendu Dey July 28, 2013Do we need to find a subset whose sum matches at most K/2 or the total number of subsets ??
please clarify everyone??
@DJ:well seems like its not specified there.though this is one possible solution if the number of notes are unlimited..:-)
- Sibendu Dey July 28, 2013Can be changed to DP :-)
- Sibendu Dey July 27, 2013Take the tail node of linked list as the pivot..traverse from the beginning.If the node traversed is lesser than the tail node leave it in its place if the node is greater than the tail add to the end of the list..recursively call the linked list with nodes to the left side of the pivot and to the right side of the pivot.
- Sibendu Dey July 27, 2013Good copy and paste from geeksforgeeks.. :-)
- Sibendu Dey July 27, 2013@abhishek:can you please explain it in an elaborate manner?
- Sibendu Dey July 27, 2013Here is a geeksforgeeks solution:-)
.geeksforgeeks.org/dynamic-programming-set-7-coin-change/
awesome man..+1
- Sibendu Dey July 27, 2013the worst complexity seems to be o(m*n)
- Sibendu Dey July 26, 2013C++ implementation time complexity o(n) and space o(1)
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
int findPoint(int arr[],int size) {
int leftSum=arr[0];
int rightSum=arr[size-1];
int leftIndex=0;
int rightIndex=size-1;
while(true ) {
if(leftSum>rightSum) {
rightSum=rightSum+arr[--rightIndex];
if(leftSum==rightSum) {
return rightIndex-1;
}
}
else {
leftSum=leftSum+arr[++leftIndex];
if(leftSum==rightSum) {
return leftIndex+1;
}
}
}
return leftIndex;
}
int main() {
int arr[]={1,3,2,5,4,6,7,8};
int point=findPoint(arr,sizeof(arr)/sizeof(arr[0]));
std::cout<<point;
return 0;
}
i guess O(m+n) is better than O(n*logm)
- Sibendu Dey July 26, 2013I think it can be solved in 0(logm+logn) time with extra space of o(m) + o(n).
We need to apply a modified binary search in this problem both rowwise and columnwise.
Posting the solution soon.
Implementation of Kadane's algorithm
#include<iostream>
#include<stdio.h>
using namespace std;
void printSubArray(int arr[],int start,int end) {
for(int i=start;i<=end;i++) {
cout<<arr[i]<<" ";
}
return;
}
void kadaneAlgo(int arr[],int size) {
int maxIndex;
int startIndex=0;
int maxStartIndex;
int currSum=0;
int max=arr[0];
for(int i=0;i<size;i++) {
currSum=currSum+arr[i];
if(currSum<=0) {
currSum=0;
startIndex=i+1;
}
else {
if(currSum>max) {
max=currSum;
maxIndex=i;
maxStartIndex=startIndex;
}
}
}
printSubArray(arr,maxStartIndex,maxIndex);
}
int main() {
int arr[]={-2, 11, -4, 13, -5, -2};
kadaneAlgo(arr,sizeof(arr)/sizeof(arr[0]));
return 0;
}
@logicfinder:Can u please give an example?
- Sibendu Dey July 20, 2013Will post code solution if the solution seems correct to others..
- Sibendu Dey July 19, 2013Build a array from the traversal of binary tree.Swap the elements present at index 2^i to 2^(i+1)-1 where i is odd.Then construct the tree from the queue.
- Sibendu Dey July 19, 2013@Ayahuasca:Yes ofcourse me too
- Sibendu Dey July 19, 2013I think we need a comment for @P3A about this issue.The example which he gave clearly brings out a debate on the "distinct" issue.He might have said in the example:The solution is player 1 and player 2 or Player 1 and player 3,but he did'nt.That clearly brings some doubt.
- Sibendu Dey July 19, 2013@Anonymous:Counter example:How about this?
3 6 5
111100
000011
111110
According to your solution Player 1 and player 2 will be the answer
But the solution player 3 gives us an minimum solution.
If the value of K can take any value ,then the place of 1's doesn't matter,we can apply DP to solve it.But if the value of K need to be less than N,then it matters.
- Sibendu Dey July 19, 2013Can anyone say that the value of K need to be necessarily lesser than N or it can take any value ?
- Sibendu Dey July 19, 2013Just a change required,you dont need to find the subarray,you need to find a minimum length subsequence that matches the sum.
- Sibendu Dey July 19, 2013I think we just need to find the key is in an increasing pattern or decreasing pattern and then apply binary search on it.
- Sibendu Dey July 18, 2013By the way im confused whether by k we mean distinct followers or a follower following two players is counted as 2 in the context of k
- Sibendu Dey July 18, 2013well i thought about it but the distinct followers thing puzzled me out.I don't think it may be applied here.Correct me if iam wrong.
- Sibendu Dey July 18, 2013Well good solution @vgeek.I was doing the same but was somewhere stuck around the point about dealing a case where LCA was among the two nodes.
- Sibendu Dey July 18, 2013
Repjoyceclark, Graphics Programmer at Denmin Group
I am Joyce, a highly talented and passionate writer expert in storytelling. Outside of my writing profession, I’ve hobbies ...
RepI am Susan From Wasilla USA. and my strong interest in yoga and reading historical books. I have a large ...
RepSpent 2001-2004 selling UFOs for the government. Have some experience with Internet Marketing Services New York. Set new standards for ...
- Sibendu Dey June 10, 2018