### CS354: Operating Systems

CS252: Systems Programming
Ninghui Li
Program Interview Questions
String Problem
Input is a string containing a set of words
separated by white space(s). Write a function
that will transform it to a string in which the
words appear in the reverse order. For
example "this is really good" becomes "good
really is this".
• We require that only a constant amount
of extra space, and linear time is used.
•
String Problem Solution
•
Solution: two-pass processing
• First pass reverse whole string
• Second pass, find each word and reverse
it locally
Similar Problem
Consider strings over alphabet {a,b,c,d},
write a function that takes an input string, and
(1) removes each “b”, (2) replaces each “a”
by “dd”, and does so in place (assume the
string is in a buffer long enough for the result)
•
Given a singly linked list, you are given one
node and are asked to delete it from the list.
• You are asked to do it in constant time.
• What is the challenge?
• This is possible when the node is not the
last node in the list, and copying the data
field in the node takes constant time.
• How?
•
Cyclicity
Although a linked list is supposed to end
with NULL, it is possible to have it points to
another element in the list, creating a cycle
•
Write code to check whether a singly linked
list ends in NULL or contains a cycle
• C1: no modifying the list.
• C2: constant extra space.
• C3: linear time running time
• How to find the first element of the cycle?
•
Cyclicity
•
Solution 1: Satisfies C2, C3; violate C1;
list as one traverses it, and report cycle if
one reaches the head node again.
Solution 2: Satisfies C2, C3; violates C1;
assumes that there is a bit in the data structure
that is initialized to 0
•
Cyclicity
•
Solution 3: Satisfies C1, C3; violate C2;
• Record all visiting nodes in a hash table,
and do a lookup for each newly
encountered node.
•
Solution 4: Satisfies C1, C2; violates C3;
• For each newly encountered node, check
whether its next will be visited if one
starts from head again and try to traverse
to current node.
Cyclicity
•
Solution 5: Satisfies C1, C2, C3;
•
•
Uses 2 pointers. One fast and one slow. Fast
one advances two steps each time, and show
one advances one step each time, they meet if
and only if there is a cycle.
To figure out where cycle starts,
• First figure out cycle length X, and pinning
fast pointer, and count how many steps it
takes slow pointer to meet fast
• Then set fast pointer at position X, and slow
at beginning, advance both at 1 step at a
time, when they meet, slow is pointing at
beginning of cycle
How to find the middle of a linked list in
one pass of the linked list?
•
Tower of Hanoi
Move n rings stacked on Peg 1 (rings are
from small to large from top to bottom) to
Peg 2,
• Peg 3 is empty.
•
Write a program to output the necessary
steps to move n rings on Peg 1 to Peg 2.
•
Implementing a Queue with two
Stacks
•
Queue (FIFO) supports two operation
• dequeue (remove the first added element)
•
Stack (LIFO) supports two operations
• pop (remove the last added element)
How to implement a queue using two
stacks?
•
Implementing a Queue with two
Stacks
Enqueue(e) {
stack1.push(e);
}
Dequeue(){
if (stack2.isEmpty()) {
while(! stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
Implement a Reentrant (or
Recursive) Lock
• If a thread currently holding the lock tries
to lock it again, for a non-reentrant or nonrecursive lock, we have a deadlock
• A reentrant (or recursive) lock allows the
correct number of times for other process
to obtain the lock
Big Data with Limited Memory
• Given an input file with four billion nonnegative integers, provide an algorithm to
generate an integer which is not contained
in the file. Assume you have 1GB of
• Use a bit vector, each bit to represent whether
an integer is present; this requires 2^31 bit, or
Taken from Gayle Laakmann McDowell: “Cracking the Coding
Interview”, 5th Edition.
Big Data with Memory Limit
(continued)
• What if you have only 10MB of memory?
Assume that for input you have no more than one
billion non-negative integers, and they are all
distinct.
•
•
First scan determines # of integers in each thousands,
e.g., between 0 and 1023, 1024 and 2047, etc.
Find a region that is not full, second scan finds a
number in that region
• What if the integers are not guaranteed to be
distinct?
Taken from Gayle Laakmann McDowell: “Cracking the Coding
Interview”, 5th Edition.
Hash Table
How to design a hash function for words in a
dictionary, e.g., for use in a hash table of
size N?
What makes a good hash function?
• Distribution of output is close of uniform over
[0..N-1].
• Is sum of all characters a good hash function?
• Is product of all characters a good hash
function?
Anagrams
• Two words are anagrams if they contain
the same set of characters.
• Write a program to partition a dictionary
into sets of words such that all words in
each set are anagrams.
Divide and Conquer
Recursively
Divide: break down the problem into two or
more sub problems:
Conquer: solve the sub problems, and then
combine their results
Example: Merge sort
Divide and Conquer Question
Compute the number of reversed pairs in an array A of
numbers. A pair (i,j) is reversed if A[i]>A[j].
Solution idea (do merge sort while computing this):
# of inverse in whole =
# of inverse in left half
+ # of inverse in right half
+ # of inverse involving one element in left and one in
right (can be computed while merging left and right)
Code available
versions.java
Divide and Conquer Question
Diameter of a tree
Consider a tree where each edge has a number
(distance), compute the maximal distance between
two leaf nodes.
Solution Idea:
For each internal node, computes the max distance
as well as the max height
Pseudo Code
max_dist(node *p, &dt, &ht) { // dt:distance, ht:height
int cd, ch, ht2=0, nht; // ht2 stores second highest height
*dt=0;
*ht=0;
if (p is leaf) return;
for each child c of p {
max_dist(c, &cd, &ch);
if (cd>*dt) *dt=cd;
// current max distance is from subtree at c
nht = ch + e(c);
// e(c) is distance on the edge to child c
if (nht > *ht) { ht2 = *ht; *ht = nht;}
else if (nht > ht2) { ht2 = nht; }
if (ht2>0 && *ht+ht2>*dt)
{ *dt = *ht+ht2; }
// current max distance from leafs in two subtrees
}
}