nsdxnsk
BAN USERSimple recursion solution for appending '1' or '0' to bit where counter == 0 -> 1 and last array endswith '0' -> 1
static void Main(string[] args)
{
char[] c = new char[5];
PrintBinaryStrings(c.Length, 0, c);
}
private static void PrintBinaryStrings(int k, int counter, char[] c)
{
if (counter == k)
{
Console.WriteLine(new string(c));
return;
}
else if (counter < k)
{
// Concat 1
c[counter] = '1';
PrintBinaryStrings(k, counter + 1, c);
// Concat 0
if (counter > 0 && c[counter - 1] != '0')
{
c[counter] = '0';
PrintBinaryStrings(k, counter + 1, c);
}
}
}
Naive solution using Hash Map.
public void GroupSet(Set<int> a, Set<int> b)
{
HashMap<int, int> map = new HashMap<int, int>();
//Iterates set for a & b
foreach(int val in a)
{
map[val] += 1;
}
// Same for set b...
// Iterates map and group based on the condition
foreach (int key in map.AllKeys)
{
if (map[key] > 1) // Then group overlaps A & B
else if (map[key] == 1 && a.Contains(key)) // Then group A
else if (map[key] == 1 && b.Contains(key)) // Then group B
}
}
Time Complexity O(2N)
Space Complexity O(N)
Assume Head node of the circular list contains minimum value
1. Compare circular.Head.Data to linear.Head.Data, if liniar's Data is smaller, replace circular Head, and move linear's pointer to next.
2. Do 1 until linear.Node.Data > circular.Head.Data
3. Do normal merge sort for those 2 under condition of
while (circular.Node.Next != circular.Node.Head) // If it equals to Head, it means it gets back to Head pointer
4. After the while loop, if still linear pointer is in the middle, insert Nodes at the last of cirsular list.
If we had head pointer, then this can be solved
void DeleteNth(int n)
{
Node current = First;
for (int i = 0; i < n - 1; i++)
{
//Move pointer to n - 1th
current = current.Next;
}
Node prev = current;
current = current.Next.Next; // Move pointer to N + 1th
prev.Next = current; // N - 1th node points to N + 1th
}
In case of handling only consecutive strings, RunLength algorithm is sufficient
function encodeRunLength(data) {
var encode_data = new Array();
var c;
var len = 0;
for (var i = 0; i < data.length; i++) {
if ((0 < len) && (len<9) && (c == data.charAt(i))) {
len++;
continue;
}
if(len != 0) {
encode_data.push(c);
encode_data.push(len);
}
c = data.charAt(i);
len = 1;
}
if(len != 0) {
encode_data.push(c);
encode_data.push(len);
}
return encode_data;
}
public bool IsBalanced(Node root)
{
return Max(root) - Min(root) <= 1;
}
private int Max(Node root)
{
if (root == null) return 0;
return 1 + Math.Max(Max(root.Left), Max(root.Right));
}
private int Mini(Node root)
{
if (root == null) return 0;
return 1 + Math.Mini(Mini(root.Left), Mini(root.Right));
}
If I could tick the nodes like IsVisited=true, tick node and when either listA or listB found the ticked node, that could be the goal
public Node GetMergedPoint(Node rootA, Node rootB)
{
while (rootA.Next != null && rootB.Next != null)
{
if (rootA.IsVisited) return rootA;;
if (rootB.IsVisited) return rootB;
rootA.IsVisited = true;
rootA = rootA.Next;
rootB.IsVisited = true;
rootB = rootB.Next;
}
return null;
}
If I'm allowed to ignore time complexity, I would handle like this
Assume array contains Integers >= 1
public int FindKthSmallest(int[] array, int k)
{
int smallest = 0;
int smaller = 0;
for (int i = 1; i <= k; i++)
{
for (int j = 0; j < array.Length - 1; j++)
{
if (array[j] < array[j + 1] && array[j] > smallest)
{
smaller = array[i];
}
else if (array[j + 1] < array[j] && array[j + 1] > smallest))
{
smaller = array[j + 1];
}
}
smallest = smaller;
}
}
Time complexity is O(k * n!)
- nsdxnsk July 13, 2012
For the 2nd part, if you sort the string at first with Quick Sort or some smart sort algorithms. Simply, you need one temp value to check duplicates.
- nsdxnsk August 22, 2012That makes time complex O(NlogN) + O(N)