Bharat Kumar Arya
BAN USERI am because I am.... a born coder...
1. We will start with a TreeMap to store the incoming order and total quantity sold sorted based on quantity in decreasing order
1.1 if item is already in map just update the quantity
1.2 if item is not there just add it up into the map
2. As the keys of the maps are already sorted based on decreasing quantity order we can just take the key list and get the top ith order item
insertion time (nlogn)
search time (n) (correct me if i am wrong)
Total efficiency : nlogn
#include <iostream>
#include <cstring>
using namespace std;
const int DG = sizeof(unsigned int) * 8;
void resetBit(unsigned int &data, unsigned int bit) {
if (bit < DG) {
data &= ~(1 << (DG - 1 - bit));
}
}
void setBit(unsigned int &data, unsigned int bit) {
if (bit < DG) {
data |= (1 << (DG - 1 - bit));
}
}
unsigned int getBit(unsigned int data, unsigned int bit) {
unsigned int res = 0;
if (bit < DG) {
res = ((data & (1 << (DG - 1 - bit))) == 0) ? 0 : 1;
}
return res;
}
void setIJ(unsigned int data[], int i, int j, const int cols) {
int I = ((i * cols) + j) / DG;
int J = ((i * cols) + j) % DG;
setBit(data[I], J);
}
void resetIJ(unsigned int data[], int i, int j, const int cols) {
int I = ((i * cols) + j) / DG;
int J = ((i * cols) + j) % DG;
resetBit(data[I], J);
}
int getIJ(unsigned int data[], int i, int j, const int cols) {
int I = ((i * cols) + j) / DG;
int J = ((i * cols) + j) % DG;
return getBit(data[I], J);
}
bool findWay(unsigned int data[], int M, int N, int sx, int sy, int ex, int ey) {
bool found = false;
if ((sx == ex) && (sy == ey)) {
found = true;
} else {
if (getIJ(data, sx, sy, N) == 0) {
setIJ(data, sx, sy, N);
if (sy - 1 >= 0) { // left
found = findWay(data, M, N, sx, sy - 1, ex, ey);
}
if (!found && (sx - 1 >= 0)) { // top
found = findWay(data, M, N, sx - 1, sy, ex, ey);
}
if (!found && (sy + 1 < N)) { // right
found = findWay(data, M, N, sx, sy + 1, ex, ey);
}
if (!found && (sx + 1 < M)) { //bottom
found = findWay(data, M, N, sx + 1, sy, ex, ey);
}
} else {
found = false;
}
}
return found;
}
int main() {
int M;
int N;
unsigned int* data;
int input = 0;
cin >> M >> N;
const int size = (M * N - 1) / DG + 1;
data = new unsigned int[size];
memset(data, 0, sizeof(unsigned int) * size);
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
cin >> input;
if (input != 0) {
setIJ(data, i, j, N);
}
}
}
int sx, sy, ex, ey;
cin >> sx >> sy >> ex >> ey;
if (findWay(data, M, N, sx, sy, ex, ey)) {
cout << "true" << endl;
} else {
cout << "false" << endl;
}
return 0;
}
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int DG = sizeof(unsigned int) * 8;
struct Point {
int x, y;
Point(int ix, int iy) {
x = ix;
y = iy;
}
Point() {
x = y = 0;
}
};
void resetBit(unsigned int &data, unsigned int bit) {
if (bit < DG) {
data &= ~(1 << (DG - 1 - bit));
}
}
void setBit(unsigned int &data, unsigned int bit) {
if (bit < DG) {
data |= (1 << (DG - 1 - bit));
}
}
unsigned int getBit(unsigned int data, unsigned int bit) {
unsigned int res = 0;
if (bit < DG) {
res = ((data & (1 << (DG - 1 - bit))) == 0) ? 0 : 1;
}
return res;
}
void setIJ(unsigned int data[], int i, int j, const int cols) {
int I = ((i * cols) + j) / DG;
int J = ((i * cols) + j) % DG;
setBit(data[I], J);
}
void resetIJ(unsigned int data[], int i, int j, const int cols) {
int I = ((i * cols) + j) / DG;
int J = ((i * cols) + j) % DG;
resetBit(data[I], J);
}
int getIJ(unsigned int data[], int i, int j, const int cols) {
int I = ((i * cols) + j) / DG;
int J = ((i * cols) + j) % DG;
return getBit(data[I], J);
}
bool getNeighbors(unsigned int data[], int M, int N, int i, int j, int which) {
bool anyOneSet = false;
switch (which) {
case 0:
if (i - 1 >= 0) {
if (j - 1 >= 0) {
anyOneSet = getIJ(data, i - 1, j - 1, N);
}
}
break;
case 1:
if (i - 1 >= 0) {
anyOneSet = getIJ(data, i - 1, j, N);
}
break;
case 2:
if (i - 1 >= 0) {
if (j + 1 < N) {
anyOneSet = getIJ(data, i - 1, j + 1, N);
}
}
break;
case 3:
if (j + 1 < N) {
anyOneSet = getIJ(data, i, j + 1, N);
}
break;
case 4:
if (i + 1 < M) {
if (j + 1 < N) {
anyOneSet = getIJ(data, i + 1, j + 1, N);
}
}
break;
case 5:
if (i + 1 < M) {
anyOneSet = getIJ(data, i + 1, j, N);
}
break;
case 6:
if (i + 1 < M) {
if (j - 1 >= 0) {
anyOneSet = getIJ(data, i + 1, j - 1, N);
}
}
break;
case 7:
if (j - 1 >= 0) {
anyOneSet = getIJ(data, i, j - 1, N);
}
break;
default:
break;
}
return anyOneSet;
}
void checkForIt(unsigned int data[], int M, int N, int i, int j, vector<Point>& res) {
res.push_back(Point(i, j));
resetIJ(data, i, j, N);
bool neighbor[4];
memset(neighbor, 0, sizeof(neighbor));
if (getNeighbors(data, M, N, i, j, 0)) { // -1, -1
checkForIt(data, M, N, i - 1, j - 1, res);
}
if (getNeighbors(data, M, N, i, j, 1)) { // -1, 0
checkForIt(data, M, N, i - 1, j, res);
}
if (getNeighbors(data, M, N, i, j, 2)) { // -1, 1
checkForIt(data, M, N, i - 1, j + 1, res);
}
if (getNeighbors(data, M, N, i, j, 7)) { // 0, -1
checkForIt(data, M, N, i, j - 1, res);
}
if (getNeighbors(data, M, N, i, j, 3)) { // 0, 1
checkForIt(data, M, N, i, j + 1, res);
}
if (getNeighbors(data, M, N, i, j, 6)) { // 1, -1
checkForIt(data, M, N, i + 1, j - 1, res);
}
if (getNeighbors(data, M, N, i, j, 4)) { // 1, 1
checkForIt(data, M, N, i + 1, j + 1, res);
}
if (getNeighbors(data, M, N, i, j, 5)) { // 1, 0
checkForIt(data, M, N, i + 1, j, res);
}
}
void fillResult(unsigned int data[], const int size, int M, int N, vector<vector<Point>* >& result) {
int move = 0;
while (move < size) {
if (data[move] != 0) {
for (int i = 0; (data[move] != 0) && (i < DG); ++i) {
if (getBit(data[move], i) != 0) {
vector<Point>* res = new vector<Point>();
int total = (move * DG) + i;
checkForIt(data, M, N, total / N, total % N, *res);
++i;
if (res->size() > 0) {
result.push_back(res);
} else {
delete res;
}
}
}
}
++move;
}
}
int main() {
int M;
int N;
unsigned int* data;
int input = 0;
cin >> M >> N;
const int size = (M * N - 1) / DG + 1;
data = new unsigned int[size];
memset(data, 0, sizeof(unsigned int) * size);
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
cin >> input;
if (input != 0) {
setIJ(data, i, j, N);
}
}
}
vector<vector<Point>* > result;
fillResult(data, size, M, N, result);
if (result.size() > 0) {
vector<Point>* set = NULL;
for (size_t i = 0; i < result.size(); ++i) {
set = result[i];
if ((set != NULL) && (set->size() > 0)) {
cout << "{";
for (size_t j = 0; j < set->size(); ++j) {
Point p = set->at(j);
cout << "(" << (p.y + 1) << "," << (p.x + 1) << "),";
}
cout << "}" << endl;
} else {
cout << "Inner set#" << (i + 1) << " is empty" << endl;
}
}
} else {
cout << "Empty!" << endl;
}
return 0;
}
Well! collisions in hashtable can even occurs if two url(s) are different.?
Think of size of 8GB string hashtable?
modprobe reads the modules from /lib/modules/$(uname -r)/modules.dep.bin (or without the .bin suffix if the other file is not available). From the same file, dependencies are loaded.
modprobe accepts the name of a .ko file in /lib/modules/$(uname -r) (e.g. nvidia-current for the file dkms/nvidia-current.ko) and aliases (modules.alias.bin). Builtins (modules.alias.bin) are recognized as well, but since these modules are loaded by default, there is not point in modprobing this kind of modules.
insmod on the other hand accepts paths to files. The module does not have to reside in /lib/modules/$(uname -r), but dependencies are not automatically loaded. This is the lower program used by modprobe to load modules.
do this toss() func 3 times
let XXX is result where X = H, T
ignore case of where all X are H or all are T
now the sequence will be
HHH = 1/8
HHT = 1/8
HTH = 1/8
HTT = 1/8
THH = 1/8
THT = 1/8
TTH = 1/8
TTT = 1/8
all with probability 1/8 now if HHH or TTT comes toss again for 3 times until different event occurs.
take H as 0 and T = 1
so the sequence will be
001= 1
010 = 2
011 = 3
100 = 4
101 = 5
110 = 6
all with equal probability (though we are skipping operations sometimes still)
Yes it is O(1) space as you have to return a different array not the same one, so this much space is needed indeed and O(n) performance
- Bharat Kumar Arya January 14, 2015Please read the following link
wiki dot archlinux dot org/index dot php/kernel_modules
int* sumExcept(int[] arr, int size) {
int* result = new int[size];
int sum = 0;
memset(result, 0, sizeof(int) * size);
sum = arr[0];
for(int i = 1; i < size; ++i) {
result[i] = sum;
sum += arr[i]
}
sum = arr[n-1];
for (int i = size - 2; i >= 0; --i) {
result[i] += sum;
sum += arr[i];
}
return result;
}
public bool isNumber(String s) {
bool signOccured = false;
bool dotOccured = false;
bool started = false;
s = s.trim();
for(char c : s.toCharArray()) {
switch (c) {
case '+', '-':
if (started || signOccured || dotOccured) {
return false;
} else {
signOccured = true;
}
break;
case '0'-'9':
started = true;
break;
case '.':
if (dotOccured) {
return false;
} else {
dotOccured = true;
}
default:
return false;
}
}
return true;
}
import java.util.HashMap;
import java.util.Map;
public class Main {
// for adding new nodes
private static Node headNode = null;
// for LROM
private static Node tailNode = null;
// for check existing messages
private static Map<String, Node> messages = new HashMap<>();
// double linked list node
private static class Node {
private Node prev;
private Node next;
private String message;
public Node(String message) {
next = prev = null;
this.message = message;
}
public Node getPrev() {
return prev;
}
public void setPrev(Node prev) {
this.prev = prev;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public String getMessage() {
return message;
}
}
// add a new message to list
private static void addNode(String msg) {
Node newNode = null;
// first message into list
if (messages.isEmpty()) {
newNode = new Node(msg);
headNode = tailNode = newNode;
messages.put(msg, newNode); // remember message
} else {
// if message already exists
if (messages.containsKey(msg)) {
newNode = messages.get(msg);
// if it is head node we are done otherwise
if (newNode != headNode) {
newNode.getPrev().setNext(newNode.getNext());
if (newNode != tailNode) { // if not tail node set next node
newNode.getNext().setPrev(newNode.getPrev());
} else { // if tail node set it accordingly
tailNode = newNode.getPrev();
tailNode.setNext(null);
}
// make it head node
newNode.setNext(headNode);
headNode.setPrev(newNode);
newNode.setPrev(null);
headNode = newNode;
}
} else { // a new message comes
newNode = new Node(msg);
if (headNode == tailNode) { // if only message in list
headNode = newNode;
headNode.setNext(tailNode);
tailNode.setPrev(headNode);
} else { // set head node only
headNode.setPrev(newNode);
newNode.setNext(headNode);
headNode = newNode;
}
messages.put(msg, newNode); // remember message
}
}
}
public static void main(String[] args) {
addNode("M2");
addNode("M1");
addNode("M3");
addNode("M2");
addNode("M1");
System.out.println("LROM=" + tailNode.getMessage());
}
}
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
List<String> strings = new ArrayList<>();
Map<String, Integer> data = new TreeMap<>((s1, s2) -> s1.compareToIgnoreCase(s2));
strings.add("Good");
strings.add("word");
strings.add("good");
strings.add("woRd");
strings.forEach(s -> {
if (data.containsKey(s)) {
data.put(s, data.get(s) + 1);
} else {
data.put(s, 1);
}
});
data.forEach((k, v) -> System.out.println(k + "=" + v));
}
}
As this is a file then reading 1 character is really make IO consumption too high
better is take a good buffer (especially equal to sector size/or divisible of sector size i.e. multiple of 1024 byte, nowadays 4096 is best) say this as BUFFSIZE
char* buff[BUFFSIZE];
int readLen = 0;
fdr is src file handle open in read mode
fdw is dst file handle open in write mode
divide file size in terms of BUFFSIZE(i.e. sector size) and from seeking to last sector (which will have data maybe less than BUFFSIZE) to first sector
readLen = fread(fdr, buff, BUFFSIZE)
reverseBuff(buff, readLen); //reverses the buffer content upto readLen
fwrite(fdw, buff, readLen);
seek to previous sector (BUFFSIZE)
This is a general idea. Hope it will help
- Bharat Kumar Arya January 11, 2015What I suggest is:
Take a hashmap <src, (pointer, dest)> = city and pointer to node in doubly linked list
Take a doubly linked list with string value of city
Now for each (source, dest.) pair in vector
take source city from vector and try to find in hashmap
if not found
try to find destination city in hashmap
if found
using the pointer value from hashmap prepend this (source, dest) pair to DLL and also update hashmap for source city
if not found create linked pair of nodes (source, dest) and update hashmap with source city
if found
there is some error in input
Finally the head and tail of DLL will be the given source and destination and this DLL can be converted to required vector
Well this type of data structure is really interesting
What I can think of is:
For Insert/Delete(a particular element)/Search: O(1)
Hashmap is the best solution
If want to have max operation as well
We can have Hashmap having hashing algorithm implemented in such a way that takes comparison into account (means greater element will map to greater hash key). (Though empty keys could be a problem but that can be solved using parallelism or other useful data structure for keys management)
Hope it will help!
What I have understood is that your algorithm is correct but there are some mistakes you made as others have already pointed out
1. Syntax error - braces not in pair
2. Compilation error - used reserved keyword new
3. Logical/Typo error - used / for modulo instead of %
4. Performance issue - not used StringBuffer for string concatenation
I wrote the approach below : it works well with this case as well
{ -1, 4, 8, 7, 1, 3, 11, -1, -1, -1 }
| {0}
| {0}
| {0}
| {11 + 0}
| {3 + 0}
| {1 + 11 + 0}
| {7 + 11 + 0}
| {8 + 1 + 11 + 0}
| {4 + 7 + 11 + 0}
| {greater of next two postive number, if second is negative take only of the first}
= {4 + 7 + 11 + 0} = 22
Let me know if there is any issue.
- Bharat Kumar Arya August 07, 20143 5 3 6 3 2 5 6
| {6}
| {5}
| {2 + 6}
| {3 + 6}
| {6 + 2 + 6}
| {3 + 3 + 6}
| {5 + 6 + 2 + 6} = 19
| {3 + 6 + 2 + 6} = 17
* This starts from last to first
* For an element at i check only sum with i + 2, i + 3 (which ever is bigger)
* For a negative number remember the index of last biggest sum, and redirect to that element if queried
* If first number is non-positive it will have biggest sum (index to refer)
* If first number is positive and second is non-positive than first number has biggest sum
* If first and second both are positive biggest sum = max { first sequence sum, second sequence sum}
* Also keep a variable for lowest non-positive number found if first number is non-positive and has biggest sum still 0 or set nothing then print this lowest non-positive number
1. Find out the highest element in 8X8 matrix and find out a 3X3 matrix with lowest variance from that element.
2. Give the second lowest to second player. and let the god decide... :)
this question is quite easy... just to add a counter on their server... :P
- Bharat Kumar Arya September 24, 2012
This solution tries to solve sodoku based of given input. It puts the sudoku in final proccessed state. If given data provided has a solution it will take it to deterministic state..
- Bharat Kumar Arya May 29, 2015