dadakhalandhar
BAN USER- 0of 0 votes
AnswersWhat is the issue with this Producer Consumer Problem. Can you fix it.
- dadakhalandhar in Indiapublic class ProducerConsumerProb { public static void main(String[] args) { Container container = new Container(); Turn turn = Turn.PRODUCER; Producer p = new Producer(container, turn); Consumer c = new Consumer(container, turn); Thread pro = new Thread(p); Thread con = new Thread(c); pro.start(); con.start(); } public static class Producer implements Runnable{ Container container; Turn turn; public Producer(Container integer,Turn turn) { this.container = integer; this.turn = turn; } @Override public void run() { for(int i=0;i<10;i++){ Turn temp = null; while(true){ synchronized (turn) { temp = turn; } if(temp == Turn.PRODUCER){ break; } } synchronized (turn) { container.setI(i); turn = Turn.CONSUMER; } } } } public static class Consumer implements Runnable{ Container container; Turn turn; public Consumer(Container integer,Turn turn) { this.container = integer; this.turn = turn; } @Override public void run() { for(int i=0;i<10;i++){ Turn temp = null; while(true){ synchronized (turn) { temp = turn; } if(temp == Turn.CONSUMER){ break; } } synchronized (turn) { System.out.println(container.getI()); turn = Turn.PRODUCER; } } } } public static class Container{ Integer i = new Integer(0); public int getI() { return i; } public void setI(int i) { this.i = i; } } enum Turn{ PRODUCER,CONSUMER; } }
| Report Duplicate | Flag | PURGE
Infinera Java Developer Java
The following code is for hourly basis. And can be easily extended.
Check the items list on every 100 milliseconds to clean the older data.
To simplify the code names are used instead of product ids. But can be easily extended.
import java.util.SortedSet;
import java.util.TreeSet;
public class FindTrending {
private SortedSet<Item> items = new TreeSet<>();
public static void main(String[] args) throws InterruptedException {
FindTrending findTrending = new FindTrending();
RemoveAction removeAction = findTrending.new RemoveAction(findTrending.items);
Thread subThread = new Thread(removeAction);
subThread.start();
for(int i=0;i<100;i++){
findTrending.addItem("test"+i);
Thread.sleep(500);
synchronized (findTrending.items) {
System.out.println(findTrending.items);
}
}
subThread.interrupt();
}
public void addItem(String itemName){
Item item = new Item(itemName);
synchronized (items) {
if(items.contains(item)){
items.remove(item);
}
items.add(item);
}
}
class Item implements Comparable<Item>{
String name;
long time;
public Item(String name) {
this.name = name;
time = System.currentTimeMillis();
}
public Item(String name,long time){
this.name = name;
this.time = time;
}
@Override
public boolean equals(Object obj) {
if(obj instanceof Item){
((Item) obj).name.equalsIgnoreCase(this.name);
}
return false;
}
@Override
public String toString() {
return name;
}
@Override
public int hashCode() {
return name.hashCode();
}
@Override
public int compareTo(Item o) {
if(time-o.time > 0){
return 1;
}else{
return -1;
}
}
}
class RemoveAction implements Runnable{
private SortedSet<Item> items;
public RemoveAction(SortedSet<Item> items) {
this.items = items;
}
@Override
public void run() {
while(true){
synchronized (items) {
long currTime = System.currentTimeMillis();
long diff = currTime - 60*60*1000;
Item temp = new Item("Dummy",diff);
SortedSet<Item> headSet = items.headSet(temp);
headSet.clear();
}
try {
Thread.sleep(100);
} catch (InterruptedException e) {
}
}
}
}
}
1) For sorting, use extenal sorting
2) For finding touples, use modified solution of the problem:
Given an array A[] and a number x, check for pair in A[] with sum as x - ( Fro GeeksforGeeks)
Where it is not a single array but two arrays. The arrays contain partial data one from the begninig and one from the end of the data. Say for example we have the data as follows
1 3 4 5 6 7 8 9 10 11 14 16 ........
....................................
....................................
99999999994 100000000000
And supposed we want sum of 100000000001 and we can read only four elements. We read first two elements A0 = [1,3] and A1 = [99999999994, 100000000000] into the memory.
intialize l = 0 and r = 1
A0[0] + A1[1] = 1+100000000000 = 100000000001, a hit and do l++, r--
A0[1] + A1[0] = 3 + 99999999994 = 99999999999, a miss and 99999999999<100000000001 so increament l++
But l crossed A0 boundary. So read next check form the begining [4,5] and set l=0
Repeat this till we left with only array
If we left with A0 then set r as length(A0)-1 in this case 1. If we left with A1 then set l as 0. Then use the logic l<r
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class FriendZone {
public static void main(String[] args) {
boolean[][] input = {{true,true,false},{true,true,true},{false,true,true}};
System.out.println(find(input));
}
public static int find(boolean[][] input){
int length = input.length;
List<Set> list = new ArrayList<Set>();
int totalNumberOfSets = length;
for(int i=0;i<length;i++){
HashSet<Integer> set = new HashSet<>();
set.add(i);
list.add(set);
}
for(int i=0;i<length;i++){
for(int j=i+1;j<length;j++){
if(input[i][j]){
Set set0 = list.get(i);
Set set1 = list.get(j);
set0.addAll(set1);
set1.clear();
list.set(j, set0);
totalNumberOfSets--;
}
}
}
return totalNumberOfSets;
}
}
A generic where numbers can be any array.
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
public class SetPartitionBasedOnQuery {
public static void main(String[] args) {
int N = 4;
List<int[]> queries = new ArrayList<>();
int[] numbers = new int[N];
for(int i=0;i<N;i++){
numbers[i] = i+1;
}
queries.add(new int[]{1,2});
queries.add(new int[]{1,3});
queries.add(new int[]{2,4});
try {
HashSet<Integer>[] result = partition(numbers, queries);
for (HashSet<Integer> hashSet : result) {
Iterator<Integer> iter = hashSet.iterator();
System.out.println();
while(iter.hasNext()){
System.out.print(iter.next());
}
}
} catch (Exception e) {
e.printStackTrace();
}
}
public static HashSet<Integer>[] partition(int[] numbers,List<int[]> queries) throws Exception{
HashSet<Integer> set0 = new HashSet<>();
HashSet<Integer> set1 = new HashSet<>();
for (int i:numbers) {
set0.add(i);
}
for (int[] query:queries) {
if(set0.contains(query[0])){
set0.remove(query[1]);
set1.add(query[1]);
}else if(set0.contains(query[1])){
set0.remove(query[0]);
set1.add(query[0]);
}else{
throw new Exception("Data inconsitent");
}
}
return new HashSet[]{set0,set1};
}
}
g
import java.util.ArrayList;
import java.util.List;
public class RemoveUnbalancedParenthesis {
public static void main(String[] args) {
String input = "i7difdk(ds()))98ijdskjf(89lk)8w(((()))))";
System.out.println(removeUnbalancedParenthesis(input));
}
private static class PosAndLfRt{
int pos;
int ltRt;
private PosAndLfRt(int pos, int ltRt){
this.pos = pos;
this.ltRt = ltRt;
}
}
public static String removeUnbalancedParenthesis(String input){
StringBuilder str = new StringBuilder(input);
List<PosAndLfRt> parenthesis = new ArrayList<>();
for(int i=0;i<str.length();i++){
char charecter = str.charAt(i);
if(charecter == '('){
parenthesis.add(new PosAndLfRt(i,1));
}else if(charecter == ')'){
parenthesis.add(new PosAndLfRt(i,-1));
}
}
int track = 0;
List<Integer> posToRemove = new ArrayList<>();
for (PosAndLfRt posAndLfRt : parenthesis) {
track += posAndLfRt.ltRt;
if(track<0){
posToRemove.add(posAndLfRt.pos);
track++;
}
}
int posToRmvLen = posToRemove.size();
for (int i = posToRmvLen-1;i>=0;i--) {
str.deleteCharAt(posToRemove.get(i));
}
return str.toString();
}
}
public static int NumberOfMaxOccurences(int[] input, int k) {
int flippedZeroCount = 0;
int maxLengthFound = 0;
int maxCount = 0;
int leftPos = 0;
int rightPos = 0;
if(input.length == 0){
return 0;
}
if(input.length == 1){
if(flippedZeroCount == 0){
return input[0]==1?1:0;
}
if(flippedZeroCount == 1){
return input[0]==1?0:1;
}
}
while(rightPos<input.length){
if(input[rightPos] == 0 ){
flippedZeroCount++;
}
if(flippedZeroCount == k){
while(rightPos<input.length-1 && input[rightPos+1] == 1){
rightPos++;
}
if(rightPos-leftPos+1 > maxLengthFound){
maxLengthFound = rightPos-leftPos + 1;
maxCount = 1;
}else if(rightPos-leftPos + 1 == maxLengthFound){
maxCount++;
}
}
if(input[leftPos++] == 0 ){
flippedZeroCount--;
}
rightPos++;
}
return maxCount;
}
This is one of the quick solution. Assuming only characters appear in the board be A-Z
import java.util.ArrayList;
import java.util.Hashtable;
public class CheckBoard {
public static void main(String[] args) {
CheckBoard checkBoard = new CheckBoard();
String word = "ABCCED";
checkBoard.checkIfExists(getBoard(), word);
word = "SEE";
checkBoard.checkIfExists(getBoard(), word);
word = "ABCB";
checkBoard.checkIfExists(getBoard(), word);
}
private static char[][] getBoard(){
char[][] board = {{'A','B','C','E'},
{'S','F','C','S'},
{'A','D','E','E'}
};
return board;
}
private void checkIfExists(char[][] board, String word) {
if (isWordExists(word, constructLists(board, 3, 4))) {
System.out.println("Exists");
} else {
System.out.println("Does not exists");
}
}
private boolean isWordExists(String word, Hashtable<Integer, ArrayList<Position>> hashtable) {
if(word == null){
return true;
}
ArrayList<Position> list = hashtable.get(word.charAt(0)-'A');
if(list == null){
return false;
}
for (Position position : list) {
position.traversed = true;
if(isSubWordExists(word.substring(1),hashtable,position)){
return true;
}
position.traversed = false;
}
return false;
}
private boolean isSubWordExists(String substring, Hashtable<Integer, ArrayList<Position>> hashtable,
Position position) {
if(substring.equals("")){
return true;
}
ArrayList<Position> list = hashtable.get(substring.charAt(0)-'A');
if(list == null){
return false;
}
if(substring.length() == 1){
for (Position neghPos : list) {
if(neghPos.traversed == true){
continue;
}
if(position.x == neghPos.x){
if(Math.abs(position.y-neghPos.y) == 1){
return true;
}
}else if(position.y == neghPos.y){
if(Math.abs(position.x-neghPos.x) == 1){
return true;
}
}
}
return false;
}else{
for (Position neghPos : list) {
neghPos.traversed = true;
if(isSubWordExists(substring.substring(1), hashtable, neghPos)){
return true;
}
neghPos.traversed = false;
}
}
return false;
}
public Hashtable<Integer, ArrayList<Position>> constructLists(char[][] board, int length, int width){
Hashtable<Integer, ArrayList<Position>> occurancePositions = new Hashtable<Integer,ArrayList<Position>>(26);
for(int i=0;i<length;i++){
for(int j=0;j<width;j++){
ArrayList<Position> list = occurancePositions.get(board[i][j] -'A');
if(list == null){
list = new ArrayList<Position>();
occurancePositions.put(board[i][j] -'A', list);
}
list.add(new Position(i, j));
}
}
return occurancePositions;
}
class Position{
int x;
int y;
boolean traversed;
public Position(int x,int y) {
this.x = x;
this.y = y;
traversed = false;
}
}
}
public void findMissingLetters(String input){
boolean[] present = new boolean[26];
input = input.toLowerCase();
for(int i=0;i<input.length();i++){
char c = input.charAt(i);
if(c>='a' && c<='z'){
present[c-'a'] = true;
}
}
for(int i=0;i<26;i++){
if(!present[i]){
System.out.print((char)(i+'a') + " ");
}
}
}
Sample code
public class BiasedProb {
public static void main(String[] args) {
BiasedProb biased = new BiasedProb();
double prob = 0.67;
int count = 1000000;
int appear = 0;
for(int i=0;i<1000000;i++){
if(biased.biased(prob)){
appear++;
}
}
System.out.println(((double)appear)/count);
}
public boolean biased(double prob){
double randVal = Math.random();
return randVal<prob;
}
}
Node class
package binaryTree;
public class Node<T> {
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node<T> getLeft() {
return left;
}
public void setLeft(Node<T> left) {
this.left = left;
}
public Node<T> getRight() {
return right;
}
public void setRight(Node<T> right) {
this.right = right;
}
private T data;
private Node<T> left;
private Node<T> right;
}
package binaryTree;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Tree<T> {
Node<T> root;
public Tree(){
}
public Node<T> getRoot(){
return root;
}
public void setRoot(T data){
root = new Node<T>();
root.setData(data);
}
public void addLeftChild(T par, T chld){
Node<T> parNode = getNode(par);
if(parNode != null){
Node<T> leftNode = parNode.getLeft();
if(leftNode == null){
leftNode = new Node<T>();
parNode.setLeft(leftNode);
}
leftNode.setData(chld);
}
}
public void addRightChild(T par, T chld){
Node<T> parNode = getNode(par);
if(parNode != null){
Node<T> rightNode = parNode.getRight();
if(rightNode == null){
rightNode = new Node<T>();
parNode.setRight(rightNode);
}
rightNode.setData(chld);
}
}
public Node<T> getNode(T data){
return getNode(getRoot(), data);
}
public Node<T> getNode(Node<T> node, T data){
if(node != null){
if(node.getData().equals(data)){
return node;
}
Node<T> leftNodeResult = getNode(node.getLeft(),data);
if(leftNodeResult != null){
return leftNodeResult;
}
Node<T> rightNodeResult = getNode(node.getRight(),data);
if(rightNodeResult != null){
return rightNodeResult;
}
}
return null;
}
public void inOrder(Node<T> node,List<T> list){
if(node != null){
if(node.getLeft() != null){
inOrder(node.getLeft(),list);
}
list.add(node.getData());
if(node.getRight() != null){
inOrder(node.getRight(),list);
}
}
}
public List<T> inOrder(){
List<T> list = new ArrayList<T>();
inOrder(root,list);
return list;
}
public boolean isSameInorder(Tree<T> other){
Iterator<T> thisListIter = inOrder().iterator();
Iterator<T> otherListIter = other.inOrder().iterator();
while(thisListIter.hasNext() && otherListIter.hasNext()){
if (thisListIter.next() != otherListIter.next()){
return false;
}
}
if(thisListIter.hasNext() || otherListIter.hasNext()){
return false;
}
return true;
}
}
Test code
package binaryTree;
public class SameInorder {
public static void main(String[] args){
Tree<String> t1 = new Tree<String>();
t1.setRoot("B");
t1.addLeftChild("B", "A");
t1.addRightChild("B", "C");
Tree<String> t3 = new Tree<String>();
t3.setRoot("A");
t3.addRightChild("A", "B");
t3.addRightChild("B", "C");
System.out.println(t1.isSameInorder(t3));
}
}
The bottom half is also covered in the following code
void diagPrint(int** a,int N)
{
int i,j,k;
for(k=0;k<N;k++)
{
i = 0;
j = k;
while(j>=0)
{
printf("%d ",a[i*N+j]);
i++,j--;
}
printf("\n");
}
for(k=N-1;k>0;k--)
{
i = N-k;
j = N-1;
while(i<N)
{
printf("%d ",a[i*N+j]);
j--,i++;
}
printf("\n");
}
}
@zammer. what is the key value pair you considered.
- dadakhalandhar May 16, 2013@Hariharan. Do you mean
say initial value of var be var_ini
P1 copies var to reg_p1 (swap to P2)
P2 copies var to reg_p2 (swap to P1)
The copy instruction of P1 already got executed (here does not matter)
P1 increments reg_p1
stores it in var
does the following 3 steps 98 times
load var to reg_p1
P1 increments reg_p1
stores it in var
So the value is in var is var_ini + 99 (swap to P2)
The copy instruction of P2 already got executed
P2 increments reg_p2
stores it in var
So the value is in var is var_ini + 1 (swap to P1)
P1 comes and loads var to reg_p1
reg_p1 is now var_ini+1 (swap to P2)
Now P2 comes and does the following 3 steps 99 times
load var to reg_p2
increments reg_p2
stores it in var
Now P2 completed its turn, and P1 will get executed
The copy instruction of P1 already got executed and reg_p1 is now var_int+1
P1 increments reg_p1
stores it in var
now the var is var_ini+2
Now P1 also completed its turn.
And the final value of var is var_ini+2
I agree with abcd. It is o(n) the least possible complexity (since it is required to know each and every element). And it is inplace algorithm. And the code is
void arrange(int a[],int n)
{
int i=0;
int j = n-1;
while(i<j)
{
while(a[i] == 0) i++;
while(a[j] != 0) j--;
if(i<j)
swap(a,i,j);
}
}
A vary good explanation is given in 'Geeks for Geeks'. Since posting links are not allowed here, I am just coping from there and pasting here.
-----------------------------------------------------------------------------------
Mutex vs Semaphore
April 12, 2011
What are the differences between Mutex vs Semaphore? When to use mutex and when to use semaphore?
Concrete understanding of Operating System concepts is required to design/develop smart applications. Our objective is to educate the reader on these concepts and learn from other expert geeks.
As per operating system terminology, the mutex and semaphore are kernel resources that provide synchronization services (also called as synchronization primitives). Why do we need such synchronization primitives? Won’t be only one sufficient? To answer these questions, we need to understand few keywords. Please read the posts on atomicity and critical section. We will illustrate with examples to understand these concepts well, rather than following usual OS textual description.
The producer-consumer problem:
Note that the content is generalized explanation. Practical details will vary from implementation.
Consider the standard producer-consumer problem. Assume, we have a buffer of 4096 byte length. A producer thread will collect the data and writes it to the buffer. A consumer thread will process the collected data from the buffer. Objective is, both the threads should not run at the same time.
Using Mutex:
A mutex provides mutual exclusion, either producer or consumer can have the key (mutex) and proceed with their work. As long as the buffer is filled by producer, the consumer needs to wait, and vice versa.
At any point of time, only one thread can work with the entire buffer. The concept can be generalized using semaphore.
Using Semaphore:
A semaphore is a generalized mutex. In lieu of single buffer, we can split the 4 KB buffer into four 1 KB buffers (identical resources). A semaphore can be associated with these four buffers. The consumer and producer can work on different buffers at the same time.
Misconception:
There is an ambiguity between binary semaphore and mutex. We might have come across that a mutex is binary semaphore. But they are not! The purpose of mutex and semaphore are different. May be, due to similarity in their implementation a mutex would be referred as binary semaphore.
Strictly speaking, a mutex is locking mechanism used to synchronize access to a resource. Only one task (can be a thread or process based on OS abstraction) can acquire the mutex. It means there will be ownership associated with mutex, and only the owner can release the lock (mutex).
Semaphore is signaling mechanism (“I am done, you can carry on” kind of signal). For example, if you are listening songs (assume it as one task) on your mobile and at the same time your friend called you, an interrupt will be triggered upon which an interrupt service routine (ISR) will signal the call processing task to wakeup.
General Questions:
1. Can a thread acquire more than one lock (Mutex)?
Yes, it is possible that a thread will be in need of more than one resource, hence the locks. If any lock is not available the thread will wait (block) on the lock.
2. Can a mutex be locked more than once?
A mutex is a lock. Only one state (locked/unlocked) is associated with it. However, a recursive mutex can be locked more than once (POSIX complaint systems), in which a count is associated with it, yet retains only one state (locked/unlocked). The programmer must unlock the mutex as many number times as it was locked.
3. What will happen if a non-recursive mutex is locked more than once.
Deadlock. If a thread which had already locked a mutex, tries to lock the mutex again, it will enter into the waiting list of that mutex, which results in deadlock. It is because no other thread can unlock the mutex. An operating system implementer can exercise care in identifying the owner of mutex and return if it is already locked by same thread to prevent deadlocks.
4. Are binary semaphore and mutex same?
No. We will suggest to treat them separately, as it was explained signalling vs locking mechanisms. But a binary semaphore may experience the same critical issues (e.g. priority inversion) associated with mutex. We will cover these later article.
A programmer can prefer mutex rather than creating a semaphore with count 1.
5. What is a mutex and critical section?
Some operating systems use the same word critical section in the API. Usually a mutex is costly operation due to protection protocols associated with it. At last, the objective of mutex is atomic access. There are other ways to achieve atomic access like disabling interrupts which can be much faster but ruins responsiveness. The alternate API makes use of disabling interrupts.
6. What are events?
The semantics of mutex, semaphore, event, critical section, etc… are same. All are synchronization primitives. Based on their cost in using them they are different. We should consult the OS documentation for exact details.
7. Can we acquire mutex/semaphore in an Interrupt Service Routine?
An ISR will run asynchronously in the context of current running thread. It is not recommended to query (blocking call) the availability of synchronization primitives in an ISR. The ISR are meant be short, the call to mutex/semaphore may block the current running thread. However, an ISR can signal a semaphore or unlock a mutex.
8. What we mean by “thread blocking on mutex/semaphore” when they are not available?
Every synchronization primitive will have waiting list associated with it. When the resource is not available, the requesting thread will be moved from the running list of processor to the waiting list of the synchronization primitive. When the resource is available, the higher priority thread on the waiting list will get resource (more precisely, it depends on the scheduling policies).
9. Is it necessary that a thread must block always when resource is not available?
Not necessarily. If the design is sure ‘what has to be done when resource is not available‘, the thread can take up that work (a different code branch). To support application requirements the OS provides non-blocking API.
For example POSIX pthread_mutex_trylock() API. When the mutex is not available the function will return immediately where as the API pthread_mutex_lock() will block the thread till resource is available.
Simple and efficient idea.
We can use min heap for maintaining the k-largest elements (x^2+y^2 values) for reducing the space complexity.
The function 'findNextLargest' will do the job
node* findElement(node* r,int val)
{
if(!r)
return NULL;
if(r->data == val)
return r;
if(r->data < val)
return findElement(r->right,val);
else
return findElement(r->left,val);
}
node* findMin(node* s)
{
while(s->left)
s = s->left;
return s;
}
int findNextLargest(node* r,int val)
{
if(!r || !r->right)
{
cout<<"No such element"<<endl;
return ERROR_CONST;
}
node* s = findElement(r,val);
if(s->right != NULL)
{
node* t = findMin(s->right);
return t->data;
}
while(s != r)
s = s->parent;
if(s==r)
return ERROR_CONST;
return s->data;
}
Let us assume that the array is initially sorted in ascending order.
And rotation be moving the elements in the clock-wise direction (one element shift is one rotation)
int rotation(int r[],int size)
{
int low = 0;
int high = size-1;
int middle = (low+high)/2;
while(middle>low)
{
if(r[middle]<r[high])
high = middle;
else
low = middle;
middle = (high+low)/2;
}
return middle+1;
}
I don't know php.
- dadakhalandhar May 14, 2013There are several variations.
1) as 'champion' said, create array of given data structure and use open addressing
2) use array of pointers to given data structure and use separate chaining. (in this case we have to insert a pointer to the data structure within the structure)
Deciding hash function depends on the content of the data structure.
for 1st method we need to have collision resolving techniques like linear probing, quadratic probing. (for more details read Data structures and algorithms by Mark Allen Weiss). And as 'champion' said when the array is full we need to increase the size and do rehashing.
Why can't we use MaxHeap, where the second largest element will be one of the roots' immediate child.
- dadakhalandhar May 14, 2013The following code finds minimum distance between the strings. I think this can be used for the likeliness. The lesser the value the more likely being swapped. If it is zero then the strings both are same, highest likeliness.
The code also takes care of case difference, by converting the strings to lower case.
class testString:public string
{
public:
testString():string(){}
testString(string& s):string(s){}
testString(char *s):string(s){}
int difference(testString& s)
{
int diff = 0;
int pos = 0;
int i;
if(length() == s.length())
{
for(i=0;i<length();i++)
diff += (abs(at(i)-s.at(i))?1:0);
return diff;
}
if(length()>s.length())
{
int* diffArr = new int[length()-s.length()+1];
int j;
for(j=0;j<length()-s.length()+1;j++)
{
diff = 0;
for(i=0;i<s.length();i++)
diff += (abs(at(i+j)-s.at(i))?1:0);
diffArr[j] = diff;
}
diff = s.length();
for(j=0;j<length()-s.length()+1;j++)
{
if(diff>diffArr[j])
diff = diffArr[j];
}
diff = length()-s.length()+diff;
return diff;
}
if(length()<s.length())
{
int* diffArr = new int[-length()+s.length()+1];
int j;
for(j=0;j<-length()+s.length()+1;j++)
{
diff = 0;
for(i=0;i<length();i++)
diff += (abs(at(i+j)-s.at(i))?1:0);
diffArr[j] = diff;
}
diff = length();
for(j=0;j<(int)(-length()+s.length()+1);j++)
{
if(diff>diffArr[j])
diff = diffArr[j];
}
diff = -length()+s.length()+diff;
return diff;
}
}
};
void dist(testString& s,testString &t)
{
int i;
for(i=0;i<s.length();i++)
{
if(s.at(i) >= 'A' && s.at(i) <= 'Z')
s.at(i) = s.at(i)+'a'-'A';
}
for(i=0;i<t.length();i++)
{
if(t.at(i) >= 'A' && t.at(i) <= 'Z')
t.at(i) = t.at(i)+'a'-'A';
}
cout<<"input\t"<<s<<"\t"<<t<<endl;
cout<<s.difference(t)<<endl;
}
If we are interested in the final result, then the we can achieve the result without conversion. The code is given below
#include <stdio.h>
#include <stdlib.h>
int main()
{
int a[] = {7,3,5,3,9};
int i;
// Instead of adding 1 separately, set carry initially
int carry = 1;
int size = sizeof(a)/sizeof(a[0]);
int* result = (int*)malloc((size+1)*sizeof(int));
for(i=size-1;i>=0;i--)
{
result[i+1] = (a[i]+carry)%10;
carry = (a[i]+carry)/10;
}
result[0] = carry;
for(i=0;i<size+1;i++)
printf("%d",result[i]);
printf("\n");
return 0;
}
If we are interested in the final result, then the we can achieve the result without conversion. The code is given below
#include <stdio.h>
#include <stdlib.h>
int main()
{
int a[] = {7,3,5,3,9};
int i;
// Instead of adding 1 separately, set carry initially
int carry = 1;
int size = sizeof(a)/sizeof(a[0]);
int* result = (int*)malloc((size+1)*sizeof(int));
for(i=size-1;i>=0;i--)
{
result[i+1] = (a[i]+carry)%10;
carry = (a[i]+carry)/10;
}
result[0] = carry;
for(i=0;i<size+1;i++)
printf("%d",result[i]);
printf("\n");
return 0;
}
The following algorithm will work
1) Using start and slow pointer to detect the loop.
2) Using temporary variable pointing to the meet point. Another variable traversing through loop and comparing with the temporary variable, find the number of elements in the loop (say k).
3)Now use two pointers first pointing to start of the linked list and second pointing to the k+1 th node, move the pointers. When they meet then that will be the starting point of the loop. So the number of nodes traversed by first node + k, is the total number of nodes in the list.
@Nueman. The following is not always happening.
Now,increment one pointer to point to next node. and the other pointer to start of linked list. Now increment both the pointers until they meet.The meeting point is starting node of cycle.
@codePredator. nice idea
- dadakhalandhar May 12, 2013Sort the array.
1) If all are positive numbers then take largest 3 numbers.
2) If some of them are negative the see which of the following is grater
i. three largest positive numbers
ii. two smallest numbers (negative extreme) and one positive largest number
@alex. got it
- dadakhalandhar May 12, 2013@aka. Sorry aka I am not getting you. Are you talking about the possibility or the consequences.
- dadakhalandhar May 11, 2013@alex: Hi alex, we need to do word reversal, not string reversal.
- dadakhalandhar May 11, 2013@aka. you mean to say the following
struct genericStr g;
void insert(void* pa)
{
g.data = pa;
}
void generic()
{
int i = 5;
char c = 'c';
float f = 5.5;
insert(&i);
printf("data is %d\n",*((int *)(g.data)));
insert(&f);
printf("data is %f\n",*((float *)(g.data)));
insert(&c);
printf("data is %c\n",*((char *)(g.data)));
}
I think the following will work
int IsSumForOdd(int* a,int n,int counter,int sum)
{
if(a[n] == 0)
return 1;
if(sum == 0)
if (counter%2 == 0)
return 1;
else
return 0;
if(sum<0)
return 0;
if(n==0)
return 0;
if(sum<a[n-1])
return doSearch(a,n-1,counter,sum);
return doSearch(a,n-1,counter+1,sum-a[n-1])||doSearch(a,n-1,counter,sum);
}
Let us consider the least common ancestor of D and G be F. And corresponding sub tree be
F
/ \
B G
/ \ / \
A D I C
Do preorder traversal of left sub-tree of F. while pushing the elements into stack while entering the sub-sub-tree and poping while leaving. When we find D, count the number of entries in the stack. This will give the distance between the left element to the common ancestor.
Similarly we can do for right element.
struct genericStr
{
void* data;
struct genericStr* next;
};
void generic()
{
int i = 5;
char c = 'c';
float f = 5.5;
struct genericStr g;
g.data = &i;
printf("data is %d\n",*((int *)(g.data)));
g.data = &f;
printf("data is %f\n",*((float *)(g.data)));
g.data = &c;
printf("data is %c\n",*((char *)(g.data)));
}
void reverse(char* sta,char* end)
{
while(sta<=end)
{
char c = *sta;
*sta = *end;
*end = c;
sta++;
end--;
}
}
void reverseWords()
{
char str[MAX_LEN];
printf("Enter the string: ");
fgets(str,MAX_LEN,stdin);
char *sta,*end;
int len = strlen(str);
sta = str;
end = str+strlen(str)-2;
*(end+1) = '\0';
reverse(sta,end);
sta = strtok(str," ");
while(1)
{
end = sta+strlen(sta)-1;
reverse(sta,end);
sta = strtok(NULL," ");
if(sta == NULL)
break;
}
for(int i=0;i<len;i++)
printf("%c",str[i]);
printf("\n");
}
@dn: For doing what sam said, tree need not be binary search tree because
1) For finding common ancestor tree need not be BST
2) After find the common ancestor we can use stack for finding the distances beteen the common ancestor and each of the node and add them.
#include<stdio.h>
#include<stdlib.h>
struct node
{
int val;
struct node *left;
struct node *right;
};
void verAdd(struct node* r,int* a,int k)
{
if(r == NULL)
return;
a[k]+=r->val;
verAdd(r->left,a,k-1);
verAdd(r->right,a,k+1);
}
int main()
{
// Tree construction
// k spread of the tree one direction .
int* a = (int*)malloc(sizeof(int)*(2*k+1));
for(int i=0;i<2*k+1;i++)
a[i] = 0;
verAdd(r,a,k);
for(int i=0;i<k;i++)
printf("%d - %d \n",i,a[i]);
}
Subtract the the distance from the petrol to the next one form the bunk capacity
we get a new array. If the sum of the new array is >=0, then only the tour is possible.
If the condition is satisfied, then apply the 'Maximum sub-array problem'. Starting position of the sub-array is a starting position of the tour.
I think the termination condition should be
while(start<end)
and initially we need to do
end--;
Is it max heap or min heap
- dadakhalandhar May 03, 2013Dear Monty,
I didn't understand the following part of the code
double w1=(targetprob/containerprob);
double remainingprob=(targetprob-containerprob*(int)w1)*containerprob;
double w2=((double)remainingprob*b/(double)(1.0-remainingprob));
return max((int)(ceil(w1)+(w2)), min);
1
- dadakhalandhar May 01, 2013int large(int d,int s)
{
return d+((d-s)*((d-s)>>(sizeof(int)*8-1)));
}
int findLar(int a[],int size)
{
int lar = a[0];
int i;
for(i=1;i<size;i++)
lar = large(a[i],lar);
return lar;
}
int main()
{
int arr[] = {1,3,64,4,45,6,4};
printf("Large - %d\n",findLar(arr,sizeof(arr)/sizeof(int)));
return 0;
}
Will be always true.
main is address (which is always non zero) and i (here) is non zero. Or on them will be always true.
This following part of the code is used to free the elements of the linked list.
temp1=head->getNext();
while(temp1!=NULL)
{
free(head);
head=temp1;
temp1=head->getNext();
}
But It won't delete the last element from the list.
Say the liked list has only one element, then
temp1 is null and so head won't get deleted.
It is total number of elements in the 2d array
- dadakhalandhar February 20, 2013Very nice. I think it is better than O(n). In any case we are checking at most (m+n-1) number of elements we are checking, where m is number of rows and n is number of columns. Please correct me, if I am wrong
- dadakhalandhar February 19, 2013Can you expalin in more ditail, please
- dadakhalandhar February 12, 2013
@dan:
- dadakhalandhar May 30, 2022I think it is 3^n - [3^(n - 3)] *6. Could you explain why (n-2) required.