Laxmi Narsimha Rao Oruganti
BAN USERPreamble:
- Definitions:
Box(ID, Weight, Scheduled?),
Machine(ID, Capacity),
Schedule(Machine, Boxes)
- Create sorted array of machines sorted by Machine.CarryingCapacity - say, machines
- Create array of boxes sorted by Box.Weight - say, boxes
- Assume there is a binary search utility method over sorted arrays with a twist as:
-- For Machines: Try exact match, otherwise return the next highest capacity machine
Algorithm:
- For every pending box,
-- Find best machine
-- Reduce the machine capacity
-- Add box to schedule
-- Remove box from pending list
- Repeat the above loop
-- Until all the boxes are scheduled or no new schedule has been created
-- Reason for repeating of loop can be
--- More boxes than machines can carry
--- Machine that can fit box has been selected for other boxes with not enough capacity
Psuedo-Code:
total_schedules = new Array()
time_units = 0
while (true) {
# Initialize the loop state
unscheduled_boxes = boxes.filter_by { |box| NOT box.Scheduled? }
unscheduled_machines = machines.dup_as_sorted()
scheduled_machines = new SortedArray()
current_schedules = new Array()
for (Box box in unscheduled_boxes) {
# Find best possible machine for this box weight
# in both scheduled and unscheduled machines
old_machine = scheduled_machines.binary_search(box.Weight)
new_machine = unscheduled_machines.binary_search(box.Weight)
# If both Old and New Machines are NULL, then continue
# Why not break? May be one of the old machines has higher capacity
# but due to it's existing scheduled capacity can't have this in the schedule
if (old_machine == NULL && new_machine == NULL) {
continue;
}
# If old machine remaining capacity is apt
if (old_machine!= NULL &&
(
(old_machine.CarryingCapacity == box.Weight) ||
(old_machine.CarryingCapacity <= new_machine.CarryingCapacity)
) {
# Update Schedule
schedule = current_schedules.find(old_machine)
schedule.Boxes.add(box)
# Update Box
box.Scheduled? = true
# Update Machine Lists
## Removing and adding would make the machine sorted on reduced capacity
old_machine.CarryingCapacity -= box.weight
scheduled_machines.remove(old_machine)
## Only add if there is some capacity left over
if (old_machine.CarryingCapacity > 0) {
scheduled_machines.add(old_machine)
}
}
# If new machine capacity is apt
else
if (new_machine!= NULL &&
(
(new_machine.CarryingCapacity == box.Weight) ||
(new_machine.CarryingCapacity < old_machine.CarryingCapacity)
) {
# Update Schedule
schedule = new Schedule(new_machine, [box])
current_schedules.add(schedule)
# Update Box
box.Scheduled? = true
# Update Machine Lists
new_machine.CarryingCapacity -= box.weight
unscheduled_machines.remove(new_machine)
## Only add if there is some capacity left over
if (new_machine.CarryingCapacity > 0) {
scheduled_machines.add(new_machine)
}
}
}
if (current_schedules.empty?) {
# Scheduling failed! Fatal Error
# May be the box(es) weight is more than machine capacity
break
}
total_schedules.add(current_schedules)
time_units += 1
}
Algorithm:
- Do a inorder tree traversal with following changes
Root Node is denoted with Row Ordinal and Column Ordinal as 0
Every time traversal take a left, Column Ordinal is decremented by 1
Every time traversal take a right, Column Ordinal is incremented by 1
Every time traversal takes to children, Row Ordinal is incremented by 1
Every time traversal moves back to parent, Row Ordinal is decremented by 1
- Sort Nodes based on Column Ordinal, if Column Ordinal matches, then use Row Ordinal
- Print Sorted Nodes
Psuedo-Code:
- Class Node definition is (Value, Left, Right)
- Class NodeEx definition is (Value, RowOrdinal, ColumnOrdinal)
class TreePrinter {
private Node treeRootNode;
private ArrayList<NodeEx> nodes;
public TreePrinter(Node rootNode) {
this.treeRootNode = rootNode;
this.nodes = new ArrayList<NodeEx>();
}
public void printTree() {
this.nodes.clear();
traverseInOrder(rootNode, 0, 0);
sortNodesByOrdinals();
printNodes();
}
private void traverseInOrder(Node node, int rowOrdinal, int columnOrdinal) {
if (null == node) return;
this.nodes.append(new NodeEx(node.value, rowOrdinal, columnOrdinal));
traverseInOrder(node.Left, rowOrdinal+1, columnOrdinal-1);
traverseInOrder(node.Right, rowOrdinal+1, columnOrdinal+1);
}
private sortNodesByOrdinals() {
nodes.sort_by(node1, node2) {
if node1.ColumnOrdinal < node2.ColumnOrdinal return -1;
else node1.ColumnOrdinal > node2.ColumnOrdinal return +1;
else if node1.RowOrdinal < node2.RowOrdinal return -1;
else if node1.RowOrdinal > node2.RowOrdinal return +1;
else return 0;
}
}
}
Recursion:
- Recursion on Shops, Mood Change Count is an extra parameter
- In each recursion of a shop,
-- you do both sell and buy so that you can compute all the possible scenarios
-- In each buy/sell case, check if mood has changed, if so update the mood change count and pass on the updated mood count change to next level recursion
-- In each buy/sell case, push the activity on to stack (also have to pop once the control comes back to this level)
- Recursion ends when all shops are visited
-- When recursion ends, check total mood change count with that of stored count, if the new one is more, store that and also take copy stack of sales/buys
Observations:
- Transit Station Memory Needs
-- For every transit station, we need to remember only top two items (because of two tickets)
-- Ex: For NYC, NYC-HAWAI, NYC-SEATTLE are top two and rest such as NYC-LA, NYC-CHI can be forgotten with NYC as transit station. However, we should not forget the same with NYC station as start/end station
- We can't forget anything other than transit related stuff. Otherwise, issues would occur. For example, in the given input example;
let's say fifth row input is CHI:WA is 8192, then longest route is 8911:NYC:CHI:WA
At this row, can we forget NYC:SEATTLE?
let's say sixth row input is SEATTLE:WA is 9100, then longest route is 11558:NYC:SEATTLE:WA which requires NYC:SEATTLE to be remembered
Algorithm:
- Route is of type (String Station1, String Station2, int Distance)
- There is a NONE(String.EMPTY, String.EMPTY, 0) route to indicate no route
- Longest Route is of type (String startStation, String transitStation, String endStation, int totalDistance)
Initialized as (String.EMPTY, String.EMPTY, String.EMPTY, 0)
- Hash Table with Key as Transit Station, Value as Pair<Route, Route>
Where, Pair contains two stations with longest distance from this station
If there is only one route, other route would be NONE route
- For every input received,
Create a record
Add record to Hash Table twice - with key as station1 and station2
If hash already has an entry for a station, update the value (pair of routes) appropriately such that top two routes are retained
- Get entries from hash using two stations of input route
We will get four routes at the max
Compute longest two-ticket distance using these four routes
If newly computed longest route is longer than stored longest route
{ update stored longest route }
Print stored longest route
Question is confusing. "bet _opposite_ color every time. _same_ color 4 in a row". Please revise the question.
- Laxmi Narsimha Rao Oruganti November 26, 2018Type: Recursion + Loop Problem
Loop on String Length. That is, 1 to MAX(CEILING(N/K), (N-K)) (inclusive)
- Minimum String Length is 1 because non-empty string
- Maximum String Length is a bit tricky
-- K cuts would result in K+1 Strings
-- Case-A: Cuts are equal in size, so max str len is (N/K) (ceiled)
-- Case-B: Cuts are not equal. Max length of (K+1)th string is (N-K) where other K strings are of min len 1
Recursion on String
Psuedo-Code:
class StringCutter {
private String str;
private Stack<Pair<int, int>> substrings;
private int numCuts;
private int maxStringSize;
private int maxCutSize;
private int numPalindromes;
public StringCutter(String input) {
this.str = input;
this.maxStringSize = input.Size();
this.substring = new Stack<Pair<int, int>>();
}
public void cut(int cutCount) {
this.substring.clear();
this.numCuts = cutCount;
this.maxCutSize = MAX(CEILING(maxStringSize/numCuts), (maxStringSize-numCuts));
this.numPalindromes = 0;
cutInternal(0);
System.output.printf("Palindrome Count = %d", this.numPalindromes);
}
private void cutInternal(int usedOffset) {
// Did we make enough cuts?
if (substring.size() == this.numCuts) {
// Do cut strings complete the string? if not discard
if (usedOffset < maxStringSize) return;
StringBuilder sb = new StringBuilder();
for (Pair<int, int> p : substrings) {
cutString = str.substring(p.key, p.value);
if (isPalindrome(cutString)) this.numPalindromes++;
sb.append(cutString + "|"));
}
System.output.println(sb.toString());
}
for (int len = 1; len <= maxCutSize; len++) {
substring.push(new Pair<int,int>(usedOffset, len));
cutInternal(usedOffset + len);
substring.pop();
}
}
private boolean isPalindrome(String s) {
// Trivial code to check if 's' is a palindrome
}
}
Hi @ProTechMulti - Not just nodes w/o relation, but I could have groups of courses that are exclusive to each other. Hence, I created a dummy root node 'ALL' to attach all of them.
I have updated my answer above with more details to clarify a bit more. I am hoping that I was able to answer your question. If not. please do let me know.
This seems like a good tree problem. Think like each node in a tree is a course, children are nothing but per-requisites. As a single course can be pre-requisites to multiple other courses, we can't really imagine this as a tree, but actually need to have a graph. To make the problem simple, after building the graph, keep the courses with multiple parents (or that have this course as pre-req) at the highest depth.
Algorithm:
- Treat this as a Graph where nodes are courses and edges are pre-requisites (i.e. directed edges)
- Create an initial node as 'ALL' to represent ALL coursees
- Create nodes for all other courses and create an edge between ALL node to each of these nodes
- For each pre-requisites relationship add edges in the graph
- Convert the graph into tree by pruning any edges to a node with shorter depth (with ALL node as root node)
- Assume each semester allows 'N' courses
- Do a level order traversal of the tree, get an output in an array
- Pick the 'N' courses at a time from the last to first and produce semester wise course schedule
For example:
Courses are: A, B, C, D, E, F, G, H
Legend: [X, {Y,Z}] Course X pre-requisites are courses Y, Z
Pre-requisites:
- [A, {B,C}], [E, {D, F, G}], [H, {None}]
- [B, {None}], [C, {D}], [F, {None}], [G, {None}]
- [D, {None}]
Initial Graph:
(without edges from ALL root node if the node already has an edge from another node)
ALL -------.
/ \ |
/ \ |
A .----E H
/ \ | / \
/ \ | / \
B C | F G
\|
D
- Course D has multiple parents C and E
- Depth of D via parent C is more than via parent E, so prune edge D-E
Initial Tree:
(after pruning of extraneous edges)
ALL -------.
/ \ |
/ \ |
A E H
/ \ / \
/ \ / \
B C F G
\
D
Level Order Output of Tree:
[A, E, H, B, C, F, G, D]
Say, no. of Courses per Semester = 4
Pick courses from right to left for each semester
Semester-1: [D, G, F, C]
Semester-2: [B, H, E, A]
1) Assumption: Input Number Order can be changed
2) Assumption: Ignore the numbers beyond the returned 'n' index
3) Do a bubble sort with a twist that you can check if the prev Bubble was same as current Bubble and just eat the duplicate
int removeDuplicates(List<int> list) {
int b = 0, i = 0;
int temp = 0;
int n = list.size();
for (b = 0; b < n; b++) {
for (i = b+1; i < n; i++) {
if (list[b] > list[i]) {
temp = list[b];
list[b] = list[i];
list[i] = temp;
} else if (list[b] == list[i]) {
list[i] = list[n-1];
n = n -1;
}
}
}
// TODO: How do we truncate the list from list.size() to n?
return n;
}
Hi @Andy2000,
In my impl. above, all stacks grow in right direction. It is intermixed stacks than contiguous stacks. Stacks is a concept and not necessary 'contiguous memory'.
Thanks,
Laxmi
0.1) Assume: ThreeWayStack<T> is a single class/interface provides 3 stacks of 'T' in one instance
0.2) Assume: ThreeWayStack.Push(int stackId, T item) - Notice extra 'stackId' param
0.3) Assume: ThreeWayStack.Pop(int stackId) - Notice extra 'stackId' param
0.4) Assume: TWS is short form of ThreeWayStack
1) Define StackItem<T> as { T userItem; int link; }
1.1) Link is used as 'previous' item for stacks
1.2) Link is used as 'next' item for free
1.3) UserItem is actual user item
2) TWS has members as:
2.1) top[3] is an array integers initialized to -1
2.2) items[MAX_SIZE] is an array of StackItem<T> - initialized to item(null, slotId+1)
2.2.1) Ex: items[0] = (null, 1), items[1] = (null, 2)
2.3) free - integer representing the free slot id - initialized to 0
3) None
4) TWS.Push(stackId, item)
4.1) Get free slot id (using member var 'free')
4.2) If free slot can't be found, return stack full error
4.3) Take copy of current 'top' as prevTop, and set top of the stack to this free slot
4.4) Move free slot to next free slot using 'link'
4.5) Update a stack item at top slot with userItem = input item and link = prevTop
5) TWS.Pop(stackId)
5.1) Check if top of the given stack id is < 0; if true, return stack empty error
5.2) Take out the stack item at the top of stack id
5.3) Update top of that stack id to the stack item's 'link' value
5.4) Get stack item's userItem in a local variable, say userItem
5.5) Update stack item, with userItem as null and 'link' as current free slot id
5.6) Update current free slot to this slot id
5.7) Return userItem
Time Complexity: O(1) for push and pop
Thanks,
Laxmi
havefun - Yes, the code awfully fails on your input. Thanks for the test case. Voted down my post.
- Laxmi Narsimha Rao Oruganti December 13, 2012But this requires a 'Queue' (memory). In my version, no extra memory required.
- Laxmi Narsimha Rao Oruganti December 12, 2012This is much like triangle.
0.1) Assume: Line Count (n) is given
0.2) Assume: n <= 32
0.3) Print Row - Prints a '*' when '0', print input number when '1'
1) Item Count per line would be 2 * n -1
2) Have two long integers, say currRow, prevRow
2.1) Set prevRow = 0, currRow = 1 << n
2.2) Print currRow with '1'
3) for integer k from 2 to n (inclusive on both sides)
3.1) prevRow = currRow and currRow = 0
3.2) For every bit '1' in prevRow (say at index 'm'), set bit 'm-1' and 'm+1' to 1 in currRow
3.3) Print currRow with 'k'
Step (3.2) - Is actually a loop (though a single statement in text)
Thanks,
Laxmi
0.1) Assume there is Queue<T> available
0.2) Assume total no. of songs is known (say n)
1) Define a struct Range { int Low; int High; }
2) Declare Queue<Range> rangeQ;
3) Add Range(1, n) to rangeQ
4) While rangeQ is not emtpy
4.1) Dequeue a range 'r'
4.2) Call random number generator with (r.Low, r.High) - say number is 'm'
4.3) If m != r.Low, Enqueue Range (r.Low, m-1)
4.4) If m != r.High, Enqueue Range (m+1, r.High)
4.5) Yield Return Song with Id 'm'
5) After the above loop, rangeQ would be empty
6) If 'Repeat Mode' is off quit; otherwise repeat again from step (3)
Thanks,
Laxmi
You are assuming that repeated characters are together in this logic which is never stated
- Laxmi Narsimha Rao Oruganti December 12, 20120) Assume: we have const brace variables such as SQURE_BRACE, ROUND_BRACE, CURLY_BRACE
1) For every type of brace, have separate weightCounter
1.1) For curly braces "{}", curlyBraceWeight
1.2) For square braces "[]", squareBraceWeight
1.3) For round braces "()" - roundBracesWeight
2) Initialize all brace weights to zero
3) For every brace in the string
3.1) If it is left brace, set modVal to '+1"; if it is right, set modVal to '-1'
3.2) Check the brace type (using the const brace vars), and add modVal to that brace type's weight
3.3) If this brace type's weight hits negative value - quit the loop and report 'unbalanced'
4) After finishing the string, if any weight is not zero - report 'unbalanced'
5) Otherwise, report 'balanced'.
Assume the following Extra Library API:
- MaxBraceTypes - Returns the max no. of brace types
- GetBraceType() - Returns an integer less than MaxBraceTypes (i.e. type ids are continuous)
We could:
- Have an array of MaxBraceTypes size (inited to zero)
- Step (3.2) would be modifying the weight at that index in array of weights
Thanks,
Laxmi
Here is my understanding of the question:
Given a binary tree - where each node has three pointers namely parent, left Child, right Child. Find the 'right' (as in right direction) sibling of any given node.
Answer:
0.1) Assumption: Assume that the actual node pointer is given
1) Integer variable: 'hop count' initialized to zero
2) Walk-up the tree using parent pointer (keep track of the actual node - say prev)
2.1) Increment hop count
2.2) If 'prev' is node's left child and node's right is not null, stop walk-up and quit the loop
2.3) continue the walk-up
3) Initialize tempHops = hopCount - 1, subTree = node's right
4) Do depth-first traversal on sub-Tree (i.e. prefer left child over right child if exists)
4.1) For every walk down, decrement tempHops
4.2) For every walk (back up), increment tempHops
4.2) When tempHops is 'zero', that node is right sibling
5) If we exhausted the subtree and did not hit tempHops zero
5.1) It means the right sub-tree is not of same height at this node level
5.2) Repeat step (2)-(4) with continuation of hopCount (without resetting it to zero)
5.3) If we reached the root node and never could find tempHops zero, it means that there is no right sibling at the level of a given node
Thanks,
Laxmi
0.1) Assumption: We have empty spare bags to use (or memory)
0.2) Assumption: No two bolts should be bigger than biggest nut
0.3) Extra Assumption (not MUST): No two nuts should be bigger than biggest bolt
1) We can not sort bags as we can't compare the two bolts and two nuts
2) But there is a math law here: Nut1 < Bolt1 and Bolt1 < Nut2 implies Nut1 < Nut2. We can divide any bag into two portions with a reference of a other bag item.
2.1) Have two spare bags, namely lowBag and highBag
3) Take a nut (randomly), for every bolt
3.1) compare the bolt with nut. If bolt < nut, put it in lowBag; otherwise put it in high bag
3.2) Now we have emptied the original bolt bag and have two new bolt bags
3.3) If highBag has at least one item, throw away the lowBag items
3.4) If highBag is empty, nut is greater than all bolts - throw away the nut
3.5) Now we have only one bag
4) Repeat step (3) and sub-steps with a new nut
5) After finishing all nuts with steps (3) and (4), we will have highBag with few items
5.1) With assumption (0.1) - highBag should contain only one item (biggest bolt)
5.2) With assumption (0.2) - the first nut to be thrown away in step (3.4) is biggest nut
If no. of bolts is b and no. of nuts is n - The time complexity is O(n * b * log(b))
Thanks,
Laxmi
No, the logic works. The failure happens at the very first character in your example as the total would be -1. Read carefully his logic: 'as soon as'. He did not say to wait till the end.
Thanks,
Laxmi
I am sorry, but can you explain how would you use binary search here? Let us take an example of letter: J. In this case, middle char would not be '1'. How do you select which half to probe further? Is it left half or right half?
- Laxmi Narsimha Rao Oruganti December 11, 2012There must be some catch in this question. Is there any time complexity expectation? The simplest would be of O(m*n) complexity.
Algorithm would be:
- Find first row from _top_ which has at least one column in that row as '1'
- Find first row from _bottom_ which has at least one column in that row as '1'
The difference of the above row numbers + 1 is height of the character.
Thanks,
Laxmi
Good thinking but requires an extra stack.
- Laxmi Narsimha Rao Oruganti February 19, 2012Here is the working code link: h t t p://codepad.org/qqd48QUT
Logic:
0) The length of the string (or count of nodes) with given restrictions will always be odd
1) For every 'N' visited, call the create function to populate left sub-tree and right sub-tree.
In more detailed manner:
1) Let us assume CreateTree is a function that takes the input string, string length, parent node reference, and an index into the string about current node
2) When the index surpasses the string length, it means we are expecting more nodes as per restrictions but the input given does not have. Which means, invalid input. Bail out
3) Create a node with current index data
4) If current node data is 'L', no more children for this node. just return success
5) If current node data is 'N', it means we have two children for this node.
5.1) Increment the current node index, call the CreateTree function to populate left sub-tree
5.2) Increment the current node index, call the CreateTree function to populate right sub-tree
6) Set the root at this level to this node and return success
Thanks for clarification. Now I read it again, I can see how my reading comprehension is low.
Thanks,
Laxmi
One can construct multiple trees if we have to satisfy just pre-order traversal.
Example: Pre-Order Traversal Result: A B D E C F G
A
/ \
B C
/ \ / \
D E F G
A
/ \
B D
/ \
E C
/ \
F G
It is also not clear what other nodes are possible than N & L in a binary tree?
To conclude, question is incomplete or the interviewer is expecting you to prove that question leads to multiple answers :).
Thanks,
Laxmi
Choice (4) - Every tuple in RelV2 has a FK value that is equal to the K value in some tuple in RelV1
Thanks,
Laxmi
We are given (as input) count of numbers 'n' and pairwise sums in sorted order.
Extra assumption: First Lowest Number is also given
Number Of Pairs(n) = (n-1) + (n-2) + ... + 1 = (n-1)*n/2
Let us name the sorted order of pairs as, p[1], p[2], ..., p[(n-1)*n/2]
Let us call the resulting numbers in sorted order as b[1], b[2], ..., b[n]
p[1] is always b[1] + b[2]
- b[1] is known (assumption is that it is given)
- b[2] = p[1] - b[1] = b[1] + b[2] - b[1] = b[2]
p[2] is always b[1] + b[3]
- b[3] = p[2] - First Lowest Number = b[1] + b[3] - b[1] = b[3]
p[3] = min (b[1] + b[4], b[2] + b[3])
- We know b[1], b[2], b[3] by now
- Case: p[3] < b[2] + b[3]
-- Then p[3] is b[1] + b[4]
-- b[4] = p[3] - b[1] = b[1] + b[4] - b[1] = b[4]
- Case: p[3] == b[2] + b[3]
-- If p[3] == p[4], then it means b[1] + b[4] == b[2] + b[3]
--- b[4] = p[3] - b[1] = b[1] + b[4] - b[1] = b[4]
-- If p[3] != p[4], then it means p[4] = b[1] + b[4]
--- b[4] = p[4] - b[1] = b[1] + b[4] - b[1] = b[4]
p[4] = min(b[1] + b[5], b[2] + b[4], max(b[1] + b[4], b[2] + b[3]) )
- We know b[1], b[2], b[3], b[4] by now and repeat the logic
Thanks,
Laxmi
This does not work for the following tree where a = 25, b = 125
100
/ \
50 150
/ \ / \
25 75 125 175
Is not it better to upload it on Scribd (or similar) site and share a link. It not only saves bandwidth but lot of your time.
Thanks,
Laxmi
Algo:
- Find lengths of lists with two given heads. Let us say they are m, n.
- Have two pointers each pointing to given head pointers
- Find abs(m - n), and skip abs(m - n) nodes in the long list
- Compare both pointers. If they match, return. Otherwise, move both pointers by one step. Repeat this step till the lists end
Logic:
- Maximum length of common list < minimum of lengths of linked lists
-- Case - 1: One is a sub-list of the other
-- Case - 2: Both lists are same
- That means big list length - small list length nodes can safely be skipped for comparison
Space Complexity : O(1)
Time Complexity: O(m + n)
Thanks,
Laxmi
What is the language/environment C, C++, C++ with GC, .NET, Java?
Thanks,
Laxmi
- Count the number of 0's, 1's, 2's - O(n).
- Write in the array 0, 1, 2 as per the above counters - O(n)
Thanks,
Laxmi
CC is eating up spaces in rendering :(. Let me try again:
P........A.......H........N
A...P...L...S...I....I...G
Y........I........R
Thanks,
Laxmi
Hey Swathi,
I have updated the algo inplace and hope this explains. The codepad link has code with an example.
Thanks,
Laxmi
I have tried to solve the problem in O(n*n) time and O(1) space complexity.
Code Pad Link (C Code): h t t p://codepad.org/uhesUQZJ
Algo:
- Reverse the linked list by their next pointer
- Allocate a node, put dummy values and name it as 'Reverse Tail'
- Find all 'Random Pointer' linked list head nodes. A head node is never pointed to by any other node. So, no other node's random pointer should point to a node to it is a 'Head Node'. Below for-loop is a way to find head node.
- For every Node (starting from New Head)
-- If node's random pointer is NULL, ignore the node. This could be just one-node list or a tail. In either case, this is not a head node. Hence, skip & jump to next node
-- If node's random pointer is not NULL,
--- Check if the node is pointed to by any other node's Random pointer.
---- If yes (pointed to by), it means it is not a head node.
---- If no, it is a head node (via random pointer)
--- If node is head node, check the tail. If the tail is pointing to 'Reverse Tail' mentioned above, it means it is already reversed (per below logic). Skip this node and jump to next node
-- Reverse this list (via random pointer) and point the tail to 'Reverse Tail' node instead of NULL
- Now all 'random pointer' sub-lists are reversed but the tails are pointing to 'Reverse Tail' node allocated above
- Reset all 'Reverse Tail' pointers to NULL and free the 'Reverse Tail' node
Thanks,
Laxmi
[Note: '-' is indent level of the algo. Unfortunately, even if I keep spaces CC is not displaying properly :( ]
>> Step i) traverse the random chain whose head is current node and check if any of the nodes in the chain has already been travered.
This step requires O(n) space as for every node you need a bool flag isReversed.
Thanks,
Laxmi
Is there any restriction on time complexity?
Thanks,
Laxmi
Yes Gaurav, you are right. Just revering right side portion and finding the right place for iSort would would do the trick.
Thanks,
Laxmi
Do the digits need to be unique? For example, can we say 1122 is a qulified number for N = 4? IOW, in your example, the relationship between ith and jth digits, where i < j, is '<', can it be '<='?
- Laxmi Narsimha Rao Oruganti November 29, 2011'Next Highest' is the smallest number greater than the flip-point left digit with in the 'right portion' than a whole. I have clarified the text. The code is clear, but explanation is not. Sorry about that.
Thanks,
Laxmi
Dear Anonymous,
I do not have any intention to get into fight. Please look at my reply (both original and next one) and realize that my language is 'C' (than C++). Unfortunately, std:string belongs to C++ world.
Again, if you search the linux kernel source code (C language code) you can see many hits 'goto', and is used very effectively. Per your assessment, many of linux kernel developers are incompetent which neither me nor the world agree.
I can only try to educate if people are open to learn than keeping their minds closed and take a chance to get into fight.
I dont have anything to hide here (clear Id 'olnrao' than anonymous). Plus, I dont have time to enter or entertain fight either :). All the best for your 'fight' nature in some other place, it does not work out here :).
Thanks,
Laxmi
2222 is '2' and not 'A' as you imagine.
2 - A,
22 - B,
222 - C,
2222 - 2
For fifth press onwards we will start from start.
Thanks,
Laxmi
Dear Prakash,
Thanks for reminding everyone about the evilness of goto.
However, I would like to let you know that goto can be used effectively than in a bad way. For example, goto with circular jumping is bad, but unidirectional is not bad. goto statements increase maintainability, enhanceability, cleanliness of the code if used properly.
You might not like it but goto is used in production code at kernel and device drivers level. Yes, its usage decreases as one goes up the stack. If you do not believe, go and search in linux kernel soure code @ h t t p://lxr.linux.no/linux+v3.1.2/ (Search box is on top right)
I hope you searched and came back here :).
If you start 'reasoning out' why gotos are bad then you can see that my usage of goto does not fall in that 'bad usage' category. I have been writing systems code for few years and it is very natural for me to use goto even on solving problems like this. You may have got irritated by reading such code (HORRIBLE in caps is an indication that you have irritation feeling). I am sorry to have caused you irritation, but I believe you have to change for better by understanding how useful is goto.
Here is a method written both using and not using gotos.
=============================================
void foo_with_goto()
{
char *p1 = NULL, *p2 = NULL;
int errorCode;
// Some code - 1
...
// Explicitly written code here
p1 = (char *) malloc(10);
if (NULL == p1)
{
errorCode = -1;
goto Exit;
}
if (some_error_condition)
{
errorCode = -2;
goto Exit;
}
// Some code - 2
...
// Explicitly written code here
p2 = (char *) malloc(10);
if (NULL == p2)
{
errorCode = -1;
goto Exit;
}
// Some code - 3
...
if (some_error_condition)
{
errorCode = -2;
goto Exit;
}
// Some code - 4
...
if (some_error_condition)
{
errorCode = -2;
goto Exit;
}
// Some code - 5
...
Exit:
if (NULL != p2) free(p2);
if (NULL != p1) free(p1);
}
=============================================
void foo_without_goto()
{
char *p1 = NULL, *p2 = NULL;
int errorCode;
// Some code - 1
...
// Explicitly written code here
p1 = (char *) malloc(10);
if (NULL == p1)
{
return;
}
if (some_error_condition)
{
free(p1);
return;
}
// Some code - 2
...
// Explicitly written code here
p2 = (char *) malloc(10);
if (NULL == p2)
{
free(p1);
return;
}
// Some code - 3
...
if (some_error_condition)
{
free(p2);
free(p1);
return;
}
// Some code - 4
...
if (some_error_condition)
{
free(p2);
free(p1);
return;
}
// Some code - 5
...
Exit:
free(p2);
free(p1);
}
=============================================
Now think about the next developer (not original developer) who need to add some extra code and also handle error condition in that code. He need to be very careful in case of non-goto version as to what to free based on where he is adding the code. It is also highly error prone in non-goto version as a single miss of free leads to memory leak.
It is even more night mare if the new developer has to allocate another memory and the code is before some other existing allocation. Now suddenly he has to change multiple places to make sure his newly allocated memory has to be freed at multiple points of return.
I would like to thank you if you have taken this positively for a healthy debate than treating this as a fight.
Thanks,
Laxmi
Oops..I did not handle *, I handled 0-9 and #. Sorry for missing that out.
Update: I have updated the above codepad link to the code that handles '*' as well. Again, thanks for pointing out '*' issue.
Codepad Link (C Code) : h t t p://codepad.org/KwgZJ6UP
- Laxmi Narsimha Rao Oruganti November 25, 2011Codepad (C Code) Link: h t t p://codepad.org/IYyYIgvO
- Laxmi Narsimha Rao Oruganti November 25, 2011Here is the understanding I have. CRT allocates a big chunk say 100 KB of heap space. This heaps metadata is surely with OS. At this time, CRT has one entry in free list which says 100 KB free memory.
Now, when user asks 100 bytes, CRT gives 100 + m bytes from this and free-list entry gets updated to 100KB-100-m and alloc-list gets a new entry with data 100+m bytes. Like this, for every allocation CRT alloc-list and free-list are updated. There are merge, compaction, etc. usually memory management techniques that are done when you free memory.
Now as you can see there are two metadatas. The metadata of large chunks that CRT allocates which are with OS and there are small allocation with in this heap whose metadata sits right inside the heap.
System calls are costly and I believe that is why languages do these things. In case of .NET, Java also virtual machine allocates the large chunks and have their own memory managements of that chunk.
Hope this clears up. I will double confirm the stuff and also provide pointers to online materials once I find them. I was trying to browse FreeBSD (fxr.watson.org) and I could not find any good link.
Thanks,
Laxmi
I did not say it is a memory leak. My conclusion is free(p) leads to unpredictable behavior (including crash). CRT could behave well by detect these kinds of situations and returning an error 'Invalid Pointer'.
OS Memory APIs are system calls but C Memory API are not. For example, malloc and free are C Memory API, where as HeapAlloc is Windows OS Memory API.
CRT optimizes the system call cost by allocating a good amount of heap and does memory management of that heap by itself as I mentioned above.
hprem991: I am afraid that you are wrong about free releases fewer bytes than allocated. CRT does not know how much allocated unless it gets the metadata which itself is read at wrong location. free method here just gets confused.
Thanks,
Laxmi
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 ...
Is not this simply two level hash table? Ex: hash[key][time] = value
- Laxmi Narsimha Rao Oruganti November 30, 2018