chisingh
BAN USERNon-recursive solution: (in PHP as per the question)-
<?php
function find_sum($n) {
$array[1] = array("1");
for ($i=2; $i <= $n; $i++) {
$array[$i] = array();
for ($j=1; $j < $i; $j++) {
foreach ($array[$j] as $el) {
array_push($array[$i], $el.",".($i-$j));
}
}
array_push($array[$i], $i);
}
return $array[$n];
}
$n = 4;
$res = find_sum($n);
foreach ($res as $str) {
if ($n == 1 || $str != $n)
print "(".$str.")\n";
}
?>
output:
(1,3)
(1,1,2)
(2,2)
(1,2,1)
(1,1,1,1)
(2,1,1)
(3,1)
Yeah, so you can recursively solve the sub-problems and memoize the results using dynamic programming. In other words:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int count_valid(char *str, int size, int *array) {
int n, count = 0;
char substr[2];
if (size == 0)
return 1;
if (size == 1) {
if (*str != '0')
return 1;
else return 0;
}
if (array[size] >= 0)
return array[size];
if (str[size-1] != '0')
count += count_valid(str, size-1, array);
strncpy(substr, str+(size-2), 2);
n = atoi (substr);
if (n >= 1 && n <= 26)
count += count_valid(str, size-2, array);
array[size] = count;
return count;
}
int main () {
char *input = "1234";
int i, size = strlen(input);
int *array = (int *) malloc (sizeof(int) * (size+1));
for (i=1; i <= size; i++)
array[i] = -1;
printf ("%d\n", count_valid(input, size, array));
}
Here's a plain vanilla C implementation using Trie based suffix tree.
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
char key;
int value;
struct node *next, *children;
} node;
node *makeNode(char key, int value) {
node *n = (node *) malloc(sizeof(node));
n->key = key;
n->value = value;
n->next = n->children = NULL;
return n;
}
int insert (node *trie, char *str, int value) {
int ret = 1;
node *curr;
if (trie == NULL)
return 0;
curr = trie;
if (curr->children) {
curr = curr->children;
while (curr->key != *str) {
if (curr->next)
curr = curr->next;
else {
curr->next = makeNode(*str, value);
curr = curr->next;
ret = 0;
}
}
}
else {
curr->children = makeNode(*str, value);
curr = curr->children;
ret = 0;
}
if (*str == '\0')
return 0;
else
return ret + insert(curr, str+1, value);
}
int main () {
int i, n, max=0, index;
char str[] = "sdkljasdasdhjfhsfhsfdsjdjshjdshjdshhdsjdhhjhfhshhjshfjh";
node *trie;
trie = makeNode('\0', 0);
for (i=0; i < sizeof(str)/sizeof(char); i++) {
n = insert(trie, str+i, 0);
if (n > max) {
max = n;
index = i;
}
}
for (i=0; i<max; i++)
printf ("%c", str[index+i]);
printf ("\n");
}
node *prepend(node * root, int k)
{
node *prev, *curr;
curr = root;
for (int i = 0; i < k; i++) {
curr = curr->next;
if (curr == NULL)
return NULL;
}
prev = root;
while (curr->next != NULL) {
curr = curr->next;
prev = prev->next;
}
curr->next = root;
root = prev->next;
prev->next = NULL;
return root;
}
int maxLevel(node *root) {
int max, curr_level, max_level;
if (root == NULL)
return 0;
queue<node *> currentLevel, nextLevel;
currentLevel.push(root);
max = curr_level = 1;
while (!currentLevel.empty()) {
node *curr = currentLevel.front();
currentLevel.pop();
if (curr->left != NULL)
nextLevel.push(curr->left);
if (curr->right != NULL)
nextLevel.push(curr->right);
if (currentLevel.empty()) {
queue<node *> temp = currentLevel;
currentLevel = nextLevel;
nextLevel = temp;
curr_level ++;
if (currentLevel.size() > max) {
max = currentLevel.size();
max_level = curr_level;
}
}
}
return max_level;
}
Alright, Let me try one more time.
As we know, each node in a max-heap can have at most children which are both smaller than the value of this node. Just like in array representation of heaps where children are located at 2*i+1 and 2*i+2, here in case of matrix, the children are located at [i-1][j] and [i][j-1]. There is absolutely no logical difference between this representation and the conventional array one. Now you just have to pop the root node of the heap k times and restore the original heap property by pushing up the node at [n][n] to it's correct place, where it is greater than its both children.
Please carefully look at the code to understand the rest of the minor details, since it's not easy to explain in words.
May be someone can provide a C/Java implementation of this method?
Why are you creating another heap when the input matrix is itself a heap? I would't recommend using high level library routines for programming interviews, since they trivialize the original problem. Do you think you should use the built-in sort() routine when the interviewer is asking you to write mergesort code?
- chisingh January 27, 2013Sure. The main function is popping the largest element k times, and replacing it with the smallest one. After swapping these two elements we need to restore the original property of the matrix. That is precisely what pushUp() function does. Just like we have heapify() for max-heaps. Only difference is for an element at [i,j] we have [i-1][j] and [i][j-1] as its 'children'.
- chisingh January 27, 2013Here is my correct working solution in python:
Assumed a square matrix, but the solution can be easily modified for a rectangular matrix.
def pushUp(m):
i = j = len(m)-1
n = m[i][j]
while i > 0 and j > 0:
if m[i-1][j] < n:
if m[i][j-1] < n: return;
else:
m[i][j-1], m[i][j] = m[i][j], m[i][j-1]
j -= 1
else:
if m[i][j-1] < n:
m[i-1][j], m[i][j] = m[i][j], m[i-1][j]
i -= 1
else:
x,y = i-1, j
if m[i][j-1] > m[i-1][j]: x,y = i, j-1
m[i][j], m[x][y] = m[x][y], m[i][j]
i,j = x,y
if __name__ == "__main__":
matrix = [[1, 2, 3, 25],
[4, 23, 30, 88],
[7, 82, 90, 100],
[8, 83, 91, 101]]
k = 7
n = len(matrix)-1
while k > 1:
matrix[0][0], matrix[n][n] = - matrix[n][n], matrix[0][0]
pushUp(matrix)
k -= 1
print matrix[n][n]
Very similar to extracting kth largest element from a max-heap.
- chisingh January 27, 2013
Replisafergusona, Consultant at Myntra
I am Lisa from Chicago,I am working as a Show host in the New World. I also work Performs ...
Rephoychrista, Blockchain Developer at ASU
Worked with Clients to guide them through the event details about copier leasing companies and served as their personal coordinator ...
How about this?
- chisingh June 09, 2013