GekkoGordan
BAN USERI trade, trade and then trade.
I assume the question is for inplace sorting. because if extra memory is allowed then any efficient sort can be used.
Since we don't have direct indexing we cannot access an element directly and for merge sort we would require n additional pointers to each node (doesn't matter if it's by recursion). So we cannot use merge sort because it would require O(n) space. Maybe insertion sort is the best in for linked list, any suggestions?
@Kishore: some minor modifications. use a array of size 256. and count the number of occurrences for each character in string B.
Ex: A[abcc] B[back], then the answer shud be false. if you use bit array this would be true so use a normal array
sry didnt read question completely. tulley's solution shud work
- GekkoGordan February 22, 2011This should generate the same number. try coding and see. you need a different seed everytime.
better to use system time to seed
given an image, you want to find a square of size k that gives maximum size.
Convolve with a square filter of size k all 1's.
@Nohsib: post code on ideone.com or make an account so that you can edit your code
Posting code again and again with little changes is "bad for environment"
from stackoverflow
int NumberOfSetBits(int i)
{
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return ((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
If two linked lists meet then they should end at the same NULL node (or last node). Traverse both lists and if they both end at the same NULL node (or if the last node is same for both), they meet
- GekkoGordan February 22, 2011@Anonymous: its better to use std::list rather than creating your own double linked list. that gives you a lot of advantages and is a good practice too.
- GekkoGordan February 21, 201110 digits (non repeated digits): Does that mean using all 0-9 digits.
So basically find a number which is a perfect square that contains all digits without repetitions?
So why not just check all squares of numbers from sqrt(1023456789) to sqrt(9876543210)
i.e. check if squares of numbers from 31991 to 99380 contain any repetitions.
it should be 24531
- GekkoGordan February 17, 2011...
- GekkoGordan February 15, 2011Okay I don't undestand, what exactly r u trying to do? pseudo code/ algorithm please.
Also demonstrate on this example 9 8 7 6 5 9 8 7 5 5 6 5 with k=3. if possible
@Sathya: good solution
- GekkoGordan February 15, 2011complexity not better than O(n*n). why not just move each element which has the same compelxity
- GekkoGordan February 15, 2011This is not better than maintaining a heap, in fact much worser
- GekkoGordan February 15, 2011For all the folks who think the answer posted with the question is right: IT IS PLAIN WRONG.
As Tulley pointed out it should be "if((num) && (!(num & num-1))"
But looking at blueskin's solution: counting number of bits and if equals to 1 or break counting when greater than 1 is the best solution because counting bits is faster than applying bit operations between two integers
ya.. but you would need a special datatype or a BIG integer to store the product. Normal datatypes in (atleast C++) wont work with factorials greater than 171 (double in C++)
- GekkoGordan February 08, 2011keep a priority queue of size 10.
for every point P, if distance(P,(0,0)) is less than the min(priorityQueue) then insert in the queue
Complexity: O(nlog10)
space ; O(10) --> O(1)
Ya....good trick. you are using recursion for storing additional data.
- GekkoGordan February 08, 2011How about k-d tree
Building a k-d tree: O(n log 2 n)
Insertion; O(logn)
Searching closest point: O(sqrt(n))
stackoverflow.com/questions/190232/can-a-recursive-function-be-inline
- GekkoGordan February 08, 2011Hey sss,
One thing it doesn't matter SDE or SDET, if you think its a job that you would be interested in then take it.
From my experience, it doesn't matter it is MSFT or AMZN or GOOG etc... (unless you just graduated and looking for a job), if you think that the team is smart and the problems that you work on are interesting to you then go for it. But in general, there's a high chance that you would be offered SDET if you are an SDET in future
//Copy next node to current node and delete next node;
deleteNode(Node* currNode){
if(currNode!=NULL && currNode->next!=NULL){
currNode->data = currNode->next->data;
Node* tmpNode;
tmpNode = currNode->next;
currNode->next = currNode->next->next;
delete tmpNode;
}else{
delete currNode;
}
}
@Sathya:
Am not convinced it works. Can you demonstrate on this array: [a1,a2,a3,a4,a5,b1,b2,b3,b4,b5]. Thanks
Given k rows and an array of size n; we want to add every (n/k)th element of the array
for every element 'i' in array
array[i%k] += array[i]
// not the first k elements of the array is the required output
-> Time: O(n), Space: O(1)
(unique?? random?? )prime numbers. never heard of such prime numbers
- GekkoGordan February 07, 2011Hash table: Time: O(n), space: O(n)
Sort and count: Time: O(nlogn), space: O(1)
are we given a "balancing scale" or just a "weighing scale"??? some reason financial companies are fond of "Coins" with incomplete questions. :D
- GekkoGordan February 04, 2011key = "line", value = 1
if value already 1 then its a duplicate
u mean the book?
- GekkoGordan February 04, 2011i.e lights that are toggled odd number of times are ON at the end.
so another perspective,
given 'n' unit blocks and you can arrange them in a rectangle (includes squares). what are the values of 'n' <= 100 that can form odd number of rectangles?
Soln: if you can form more than 2 rectangle with 'n' blocks then 'n' is not prime. And only "squares" have odd number of rectangles
okay, so its basically toggling, its not just setting. so previous states should matter
- GekkoGordan February 03, 2011hmmm... maybe I am missing something in the question. lets look at a smaller example 10 lights
1st round: all on
2nd round: divisible by 2 are set off --> [1,3,5,7,9] are on
3rd round: divisible by 3 are set on --> [1,3,5,7,9] are on
4th round: divisible by 3 are set off --> doesn't matter because none from the previous set are divisible by 4
so at the end of the day we should be left with just odd numbered lights? isn't it?
hmmm good question, it kind of has the same design as a "social chatroom" where there's a moderator and bunch of users.
Poker Table:
-> 'has-a' dealer, deck of cards, chips, cash
-> displays its properties such as current cards dealt, bets, potmoney
-> provides interface to the player: such as player requests to deal, place bets, cash-in/out etc...
more suggestions?
well, there's a space complexity of O(n) in ur case.
we can reverse LL in-place by using 2 temporary pointers
Node *tmp1,*tmp2;
tmp1 = NULL, tmp2 = rootNode;
while(rootNode!=NULL){
rootNode = rootNode->next;
tmp2->next = tmp1;
tmp1 = tmp2;
tmp2 = rootNode;
} rootNode = tmp1;
Well, equality is defined by how a node is defined. maybe we need an equality operator for node class? And recursively traverse both trees at same time?
- GekkoGordan February 03, 2011Why specifically 30GB?
Maybe we need external hashing?
sort and binary search
- GekkoGordan February 03, 2011well, the question is incorrectly stated so I've edited this post. Answers are provided by other folks
- GekkoGordan February 03, 2011at the first fork() a new process spawns off
so now we have two process executing the seconding fork(), which spawns off two more
total = 4
@Anurag, the problem with iterating through hash table would add a bit more computations to it i.e. atleast 'n'
Here's a modified solution:
-> For every element 'i' in array
if key=array[i] doesn't exist in hash table
insert with value=1 and ++count
else{ //already exists then
if value==2
continue loop;
if value==1
--count and set value = 2;
}
//This should give you result without iterating hash table in the end
- GekkoGordan February 01, 2011Not necessarily: Example:
1,3,4,4,8,10
As per ur algo: [1,4,8] , [3,4,10] : sums = 12 , 17
Actually answer: [1,4,10], [3,4,8] : sums = 15 , 15
build a binary decision tree
node[] = [1 to NumRowsInMatrix];
col = 1
splitNode(matrix[][], node[], col){
for every 'row' in node[]
if matrix(row,col)==0 then add row to rightNode[]
else add row to leftNode[]
if(!rightNode.isEmpty() && col!=MAX_COLS)
splitNode(matrix,rightNode,col+1)
if(!leftNode.isEmpty() && col!=MAX_COLS)
splitNode(matrix,leftNode,col+1)
if(!rightNode.isEmpty() && col==MAX_COLS)
//all elements in rightNode are same rows
print matrix[rightNode[0],:]
if(!leftNode.isEmpty() && col==MAX_COLS)
//all elements in leftNode are same rows
print matrix[leftNode[0],:]
}
Time: O(NxM) i.e. linear //N rows M columns
Space: O(NxM) i.e. linear //
-> For every element 'i' in array
Insert in hash table, if already exists (--count) else (++count)
O(n) time and space
yes "Divide given array into two equal sets, sort them" and keep "moving elements from one array to other"
- GekkoGordan February 01, 2011well, its a convergence algo, like a least squares. maybe there's a proof for least squares
- GekkoGordan February 01, 2011if there are 'k' +ves and 'm' -ves then we can do it in O(n) time and O (k || m whichever is lesser) space for arrays/vectors
- GekkoGordan February 01, 2011my bad... thats what I meant. difference/2 is right
- GekkoGordan February 01, 2011
hmm.... an array of pointers. I believe that is still O(n) space. And if we have an array of pointers we can use any O(nlogn) sorting algo.
- GekkoGordan February 23, 2011