Laxmi Narsimha Rao Oruganti
BAN USERI am not sure where it won't compile. It works fine on codepad!
Code: h t t p://codepad.org/IzbqB7Mc
a[1] translates to *(a + 1).
a[-1] translates to *(a - 1).
In words: value at (base address of array 'a' minus a integer size).
By all means, it should compile. However, at runtime one might hit segmentation fault/acces-violation if the address does not belong to this thread. But, array is a local variable in this case inside function main. Which means, the allocation of array 'a' is on the stack. Minus four bytes just takes to the call stack frame of function main. So, in most cases you get unpredictable value (and may not really hit AV/SegFault).
Thanks,
Laxmi
IP Header: h t t p://lxr.linux.no/linux+v3.1.2/include/linux/ip.h#L85
TCP Header: h t t p://lxr.linux.no/linux+v3.1.2/include/linux/tcp.h#L24
The question in simpler terms:
In a collection of 'M' elements, some elements have repeated occurrences. Find the element which occurred at least M/2 times.
Thanks for noticing this. I have fixed the bug in the code and edited the old comment to reflect right algorithm.
Thanks,
Laxmi
Code: h t t p://codepad.org/3yb97kQR
- Split the number into digits
- Scan from right to left (digits) till we find the digit lower than what we have passed by. Let us, call this as flip-point.
- Find 'Next Highest' of the flip-point left digit with in the flip-point right portion (not in the whole set of digits).
- Swap and flip-point left digit with 'Next Highest'.
- Now sort the digits from the flip-point onwards (and including flip-point)
- Construct the number back from digits
For example:
Input = 12345, Flip = 5, Next Highest = 5, Answer = 12354
Input = 13483, Flip = 8, Next Highest = 8, Answer = 13834
Input = 37723971, Flip = 9, Next Highest = 7, Answer = 37727139
Thanks,
Laxmi
Majority of the solutions here assuming the digits are unique. Original question poster might need to clarify that part. I guess we should also consider stuff like 33434 (ans: 33443).
This sounds to me the other problem where we need to find all numbers in sorted order for a given N. That is,
N = 1: 1
N = 2: 11, 12, 21, 22
N = 3: 111, 112, 113, 121, 122, 123, 131, 132, 133, 211, 212, 213, 221, 222, 223, 231, 232, 233, 311, 312, 313, 321, 322, 323, 331, 332, 333
In this case, N = number of digits in the given number
We have to drop the sequence generation in this program after we hit the input number, and till we find the next number that uses the same digits (and the number of repetetions).
Thanks,
Laxmi
A code pad link: h t t p://codepad.org/105PvGBm
Thanks,
Laxmi
For dynamic memory leaks:
In C++:
We can override new, delete operators. We should also make sure to override new[] and delete[] operators. The override methods, internally call C++ built-in routines, plus do tracking. By tracking I mean:
- On new (and new][]), we add the memory pointer (if not null) to a hash table
- On delete (and delete[]), we remove the entry in hash table.
When the program terminates, one can check the hash table contents. If the hash table is empty, then there are no leaks. Otherwise, there are leaks. We can also check double-free/double-deletes in this override model. When someone deletes a pointer, and the entry does not exist in hash table; it means it is either a random address are double-free.
Similarly, in C:
We can write our own malloc and free functions Ex: mymalloc and myfree. These routines are same as the routines mentioned above. The only catch is that we have to expect every allocation to use these my* methods than built-in methods. If your C compiler supports function/method overrides, you could override malloc and free as well.
For static memory leaks:
I am assuming you meant to say 'unused' variables. By unused, they are either not initialized or initialized but never used (never participated as R-Value, OR, always appeared as L-Value). This is done using code parsers. Here we have to write C language parser much like compiler. And do a static analysis of code.
Thanks,
Laxmi
You can always edit your comment and correct any typos. Check 'Edit' link on your reply.
- Laxmi Narsimha Rao Oruganti November 07, 2011Do we need to move the nodes from existing linked lists to the result list? OR Do we need to create a result list with new nodes with content copied?
Anyway, here is working code. Remove spaces in http word, CareerCup does not allow URLs :(.
h t t p://codepad.org/nn3loNH0
Time Complexity: O(m + n) where m is List1 length and n is List 2 length.
Space Complexity: O(constant) - Nodes from existing lists are moved into result list
Thanks,
Laxmi
- Restriction: Timezone is assumed to be same
- Restriction: Meeting granularity is 15 min. That is, you can't start a meeting at other than 15 min. boundary like 10:42.
- We divide the 'allowed meeting hours' into 15 min slots. 8:00 to 18:00 meeting hours (10 hours) and 4 slots per hour (15 min slot) - Resulting in 40 slot
- Keep a bitmap where each bit represents a slot.
If bit is '1', then it is busy/used
If bit is '0', then it is free
- We will convert employee's calender data into a 64-bit integer with each bit representing free/busy status (we need and use only 40 bits)
- Now do a bit operation 'OR' of all 'required employees' calender bitmaps
In the result bitmap, search for 'n' bits continuously set to '0' where 'n' is number of slots for the meeting tenure requested.
Thanks,
Laxmi
From WikiPedia: h t t p://en.wikipedia.org/wiki/Call_stack
"Returning from the called function will pop the top frame off of the stack, perhaps leaving a return value."
Note that you have to search for 'return value' ('return address' is another data we store in call stack frame).
Thanks,
Laxmi
When a function call is made, a stack frame is created. As part of this frame, space for return value is also allocated. So, if nothing is explicitly returned; this space is never filled and hence whatever be in that stack at that memory location gets considered as return value.
Thanks,
Laxmi
I guess you misunderstood. Mine is also linear algorithm and pretty simple. n^2 itself is the number of elements here. In those algorithms you mentioned, O(n) is the time where 'n' is element count. In case of matrix of size nxn, the element count is 'n^2'. I hope that makes it clear.
Thanks,
Laxmi
If it helps, here is why the code works.
If we append all unique elements to the collection, then the collection would have all numbers repeated even number of times except one. In this situation, XOR of all values would yield the only element that occurred odd number of times.
Here the code is first getting XOR of all array and then the XOR values is continued (see result is not reset to zero) to the unique value set.
Hence, the code works.
Thanks,
Laxmi
We could simply sort the numbers O(n*log(n)) and do a scan+count on the fly. Stop when we hit the count is even and found a non-matching number.
I guess, the intent is to get algorithm with time complexity O(n) and space complexity O(constant).
Logic:
- Matrix of nxn numbers will have n^2 (say: nsq) numbers in sorted list.
If nsq is odd, median is a number at index nsq / 2 in the sorted list
If nsq is even, median is a a mean of numbers at indexes nsq / 2 and (nsq + 1) /2
- The trick is obtaining a sorted list out of this matrix. Strictly, speaking we
really don't need sorted list, but we need to traverse the matrix in sorted order.
- For i = 0 to n, Compare [i, i + 1 -> n-1] with [i + 1 -> n-1, i] and traverse
- Keep counting the number of sorted numbers passed by
- When sorted number counter reaches median index(es), take a value and note. In case of odd list, we just need to take one value. In case of even list, we need to take two values, and get mean of the two
- We can quit traversal once we find the values at median indexes
Here is the working code: h t t p://codepad.org/FEvad3aP (Remove spaces in http word of URL, CareerCup does not allow URLs in answers)
The complexity is: linear O(m) where 'm' is the element count (in case of a matrix of size nxn, m = n^2). The algorithm traverses at most m/2 elements and also does at most m/2 comparisons.
Thanks,
Laxmi
strcat, strcpy, memcpy - All these behave undeterministically when the src and target memory regions overlap. In case of mem* API, memmove is designed to work correctly with overlapping regions. I dont think there is something called strmove which would take care of overlapping regions. Again, you might find this working on one particular implementation, but that is not guarenteed across all platforms and processors.
Thanks,
Laxmi
This is because ostream_iterator is taking the input as int. So, the value 200.2 becomes 200 during the iterator run.
- Laxmi Narsimha Rao Oruganti November 03, 2011We can also represent this as a matrix of bits.
Example:
Students (S1, S2, S3),
Courses (C1, C2, C3, C4)
S1's Courses: C1, C2
S2's Courses: C2, C3
S3's Courses: C4, C1
Matrix can be (Students x Courses):
1 1 0 0
0 1 1 0
1 0 0 1
In this all operations asked in the question are : O(n). Strictly speaking, O(Courses) for course list (full or a student's) and O(Students) for Students list.
With tables in a database, this becomes very easy.
Three tables:
Courses(ID, Name, KEY(ID))
Students(ID, Name, KEY(ID))
StudentCourses(StudentID FOREIGN KEY Students(ID), CourseID FOREIGN KEY Courses(ID), KEY (StudentID, CourseID))
// 'letters' is an array of letters
List<string> GetWords(char[] letters, int length)
{
List<string> currentSet = new List<string>();
List<string> nextSet = new List<string>();
List<string> tempSet;
for (int l = 0; l < letterCount; l++)
{
currentSet.Add(string.Empty);
}
for (int x = 0; x < length; x++)
{
foreach(string item in currentSet)
{
for (int l = 0; l < letterCount; l++)
{
nextSet.Add(item + letters[l]);
}
}
currentSet.Clear();
tempSet = currentSet;
currentSet = nextSet;
nextSet = tempSet;
}
return currentSet;
}
This is merge sort with a change that remove the duplicates.
1) Keep comparison as a delegate/function-pointer/user-call-back (namely: comparator). The guideline for comparator function is: It should take two inputs and returns -1 if value1 < value2, 0 if value1 == value2, +1 if value1 > value2
2) Now do a parallel traversal of both sets, one at a time.
3) For every one item in sets, call the comparator with one item from each set (ex: value1 is item from set1 and value2 is an item from set2)
4) if comparator returns value is 0, add it to result-set, move forward in both sets
5) if comparator returns value -1, add value1 to result-set, move forward only in set 1
6) if comparator returns value +1, add value2 to result-set, move forward only in set 2
7) Repeat 3-7, till both or any of them sets finish. If any set is remaining, just transfer its contents to result-set as-is
This is same as what DH wrote in code, but more generic and no restriction on data set size and data type of data.
Repamieeriddler, Financial Software Developer at ABC TECH SUPPORT
I am Amiee , a Professional Insurance Agent providing valuable services to consumers in need of insurance coverage. As a part ...
Repharrytallh, Web Developer at Realty Depot
I am working as a Web developer . Here I create and maintain websites. Here I handle many responsibilities where I ...
The answer needs little understanding of C runtime (CRT) memory management. malloc() takes size of memory to allocate, but free() does not. So, when someone sends a pointer to free() method, CRT should be able to know the amount of memory to be released. This is what I would like to refer to as 'metadata'.
- Laxmi Narsimha Rao Oruganti November 22, 2011When a memory allocation for 'n' bytes requested by program, CRT internally allocates 'n' + 'm' bytes. Where 'm' bytes are for its metadata like how much is allocated, etc. CRT fills in 'm' bytes of metadata and returns the pointer by 'm' byte offset to the program. When programs calls free, CRT simply subtracts 'm' from the given address to locate metadata for that allocation.
Here in this code, we are passing a pointer shifted by sizeof(char). So, the metadata it reads is not correct. At this time, the behavior depends really on CRT.
Many legacy CRTs just do not accommodate such 'bad' programs, and result in unpredictable behavior (including program crashes).
I believe CRT can keep fixed byte value at fixed offset with in metadta (cookie?). Check the fixed value at the fixed offset and make sure the metadata read is correct. If it is not, it can simply return error 'invalid pointer'.
Hope this helps.
Thanks
Laxmi